每日算法一练：剑指offer——数组篇（7）

1.文物朝代确认

        展览馆展出来自 13 个朝代的文物，每排展柜展出 5 个文物。某排文物的摆放情况记录于数组 places，其中 places[i] 表示处于第 i 位文物的所属朝代编号。其中，编号为 0 的朝代表示未知朝代。请判断并返回这排文物的所属朝代编号是否能够视为连续的五个朝代（如遇未知朝代可算作连续情况）。

示例 1：

输入: places = [0, 6, 9, 0, 7]
输出: True

示例 2：

输入: places = [7, 8, 9, 10, 11]
输出: True

        这道题要求判断 5 个展出朝代是否能看作是连续的朝代编号，允许出现“未知朝代”的编号 0。在解题时，我们可以利用两个思路来判断是否满足连续条件：

1. 除未知朝代外的朝代编号无重复
2. 最大编号朝代与最小编号朝代的差小于 5

1.1使用辅助哈希表

解题思路：

• 使用哈希表 (Set) 来存储非 0 的朝代编号，以便检查重复。
• 记录最大编号朝代和最小编号朝代，如果满足 max - min < 5，则表示编号是连续的。

算法流程：

1. 初始化 Set<Integer> repeat 用于存放非 0 编号的朝代，max 用于记录最大朝代编号，min 用于记录最小朝代编号。
2. 遍历 places 数组：
   • 遇到 0 表示未知朝代，直接跳过。
   • 更新 max 和 min。
   • 如果 repeat 中已包含当前朝代编号，说明出现重复，直接返回 false。
   • 否则，将当前朝代编号加入 repeat。
3. 遍历结束后，检查 max - min < 5 是否成立，如果成立，返回 true，否则返回 false。

代码示例：

class Solution {
    public boolean checkDynasty(int[] places) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for (int place : places) {
            if (place == 0) continue; // 跳过未知朝代
            max = Math.max(max, place); // 更新最大编号朝代
            min = Math.min(min, place); // 更新最小编号朝代
            if (repeat.contains(place)) return false; // 若有重复，提前返回 false
            repeat.add(place); // 添加此朝代至 Set
        }
        return max - min < 5; // 判断是否连续
    }
}

复杂度分析：

• 时间复杂度：O(1)。遍历固定长度 5 的数组，复杂度为 O(5) = O(1)。
• 空间复杂度：O(1)。哈希表最多存储 5 个元素，空间复杂度为 O(1)。

1.2排序+遍历        

解题思路：

• 先对数组排序，使重复的元素变得相邻，便于检测重复朝代。
• 排序后可以很方便地找到最大值和最小值（排除未知朝代后）。
• 最后通过 max - min < 5 来判断是否连续。

算法流程：

1. 对 places 数组进行排序。
2. 遍历排序后的数组：
   • 统计未知朝代的数量。
   • 如果出现两个相同的非 0 编号，直接返回 false。
3. 遍历结束后，判断 places[4] - places[unknown] < 5 是否成立，如果成立，返回 true，否则返回 false。

代码示例：

class Solution {
    public boolean checkDynasty(int[] places) {
        int unknown = 0;
        Arrays.sort(places); // 数组排序
        for (int i = 0; i < 4; i++) {
            if (places[i] == 0) unknown++; // 统计未知朝代数量
            else if (places[i] == places[i + 1]) return false; // 若有重复，提前返回 false
        }
        return places[4] - places[unknown] < 5; // 判断是否连续
    }
}

复杂度分析：

• 时间复杂度：O(1)。排序和遍历 5 个元素，复杂度为 O(5 log 5) + O(5) = O(1)。
• 空间复杂度：O(1)。仅使用固定大小的变量 unknown。

2.设计机械累计器

        请设计一个机械累加器，计算从 1、2... 一直累加到目标数值 target 的总和。注意这是一个只能进行加法操作的程序，不具备乘除、if-else、switch-case、for 循环、while 循环，及条件判断语句等高级功能。

示例 1：

输入: target = 5
输出: 15

示例 2：

输入: target = 7
输出: 28

提示：

• 1 <= target <= 10000

2.1短路效应

解题思路

        在这个问题中，由于有许多限制条件（例如禁止使用乘法、循环和条件判断），我们只能通过递归和短路效应来实现目标。

1. 平均计算：使用公式 (1+target)×target/2是不可行的，因为涉及乘除法。

2. 迭代方法：使用循环结构（如 for 或 while）也被排除。

3. 递归方法：使用递归进行累加是可行的，但我们需要处理递归的终止条件，而不直接使用 if 语句。

        通过逻辑运算符的短路效应，我们可以实现当 target = 1 时停止递归：

• 当 target > 1 时，我们继续递归调用 mechanicalAccumulator(target - 1)。
• 当 target = 1 时，target > 1 不成立，短路效果使得后续的递归调用不再执行，从而达到了停止条件。

复杂度分析

• 时间复杂度：O(target)
  • 每次递归调用都会处理一个目标值，直到 target 减至 1，总共进行 target 次递归。
• 空间复杂度：O(target)
  • 递归的深度为 target，因此需要 O(target) 的栈空间。

代码实现：

class Solution {
    int res = 0;

    public int mechanicalAccumulator(int target) {
        // 使用短路效应进行递归
        boolean x = target > 1 && mechanicalAccumulator(target - 1) > 0;
        res += target; // 每次累加目标值
        return res; // 返回当前累加和
    }
}

代码说明

• res 变量用于记录累加的结果。
• 在 mechanicalAccumulator 方法中，通过逻辑与运算符的短路特性判断 target > 1。
• 递归调用会在 target 递减到 1 时停止继续调用，最终将所有值累加到 res 中。

3.按规则计算统计结果

        为了深入了解这些生物群体的生态特征，你们进行了大量的实地观察和数据采集。数组 arrayA 记录了各个生物群体数量数据，其中 arrayA[i] 表示第 i 个生物群体的数量。请返回一个数组 arrayB，该数组为基于数组 arrayA 中的数据计算得出的结果，其中 arrayB[i] 表示将第 i 个生物群体的数量从总体中排除后的其他数量的乘积。

示例 1：

输入：arrayA = [2, 4, 6, 8, 10]
输出：[1920, 960, 640, 480, 384]

提示：

• 所有元素乘积之和不会溢出 32 位整数
  • arrayA.length <= 100000

解题思路

我们需要计算一个数组 arrayA 中每个元素排除后的其他元素的乘积，生成新数组 arrayB。为了不使用除法，我们可以利用数组的上下三角结构来计算。

根据题目中 B[i] 的定义，我们可以将其视作一个矩阵，其中主对角线的值为1。这个矩阵可以分为上三角和下三角两部分。我们可以分别计算这两个部分的乘积并相乘，从而得到结果。

算法流程

1. 初始化：

   • 创建结果数组 B，并设置 B[0] = 1。
   • 初始化一个辅助变量 tmp 为 1，用于存储上三角的乘积。

2. 计算下三角乘积：

   • 从左到右遍历数组 A，更新 B[i]：
     • 对于每个 i，将 B[i] 设为 B[i-1] 乘以 arrayA[i-1]，计算下三角的乘积。

3. 计算上三角乘积：

   • 从右到左遍历数组 A：
     • 对于每个 i，将 tmp 乘以 arrayA[i+1]，然后将 tmp 乘入 B[i]，计算上三角的乘积。

4. 返回结果：

   • 返回数组 B。

复杂度分析

• 时间复杂度：O(N)，其中 N 是数组的长度。我们对数组 A 进行了两轮遍历。
• 空间复杂度：O(1)，我们只使用了常数大小的额外空间（辅助变量 tmp），而 B 数组不计入复杂度分析。

代码示例

下面是对应的 Java 代码实现：

class Solution {
    public int[] statisticalResult(int[] arrayA) {
        int len = arrayA.length;
        if (len == 0) return new int[0];
        
        int[] arrayB = new int[len];
        arrayB[0] = 1; // 初始化 B[0] 为 1
        int tmp = 1; // 辅助变量
        
        // 计算下三角乘积
        for (int i = 1; i < len; i++) {
            arrayB[i] = arrayB[i - 1] * arrayA[i - 1];
        }
        
        // 计算上三角乘积
        for (int i = len - 2; i >= 0; i--) {
            tmp *= arrayA[i + 1];
            arrayB[i] *= tmp;
        }
        
        return arrayB; // 返回结果数组
    }
}

这个代码实现了我们的思路，首先初始化 arrayB，然后通过两轮遍历计算上下三角的乘积，最后返回结果。