力扣top100(day01-04)

189. 轮转数组

class Solution {
    public void rotate(int[] nums, int k) {
        int length=nums.length;
        int[] newArr = new int[length];
        for (int i = 0; i < length; ++i) {
            newArr[(i + k) % length] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, length);
    }
}

代码解读：旋转数组（Rotate Array）

这段代码实现了将数组 nums 向右旋转 k 步的操作。以下是详细解析：

---

1. 核心思路

• 问题描述：将数组末尾的 k 个元素移动到数组开头，保持元素顺序不变。

  • 示例：nums = [1,2,3,4,5,6,7], k = 3 → 结果：[5,6,7,1,2,3,4]。

• 关键观察：旋转后的位置满足 (i + k) % length。

---

2. 代码解析

(1) 初始化新数组

java

int[] newArr = new int[length];

• 创建一个与原数组等长的新数组 newArr，用于存储旋转后的结果。

(2) 计算新位置并填充

java

for (int i = 0; i < length; ++i) {
    newArr[(i + k) % length] = nums[i];
}

• (i + k) % length：计算原数组元素 nums[i] 在旋转后的位置。

  • 示例：

    • i = 0, k = 3, length = 7 → (0 + 3) % 7 = 3（nums[0] 移动到 newArr[3]）。

    • i = 4, k = 3, length = 7 → (4 + 3) % 7 = 0（nums[4] 移动到 newArr[0]）。

(3) 复制回原数组

java

System.arraycopy(newArr, 0, nums, 0, length);

• 将 newArr 的内容复制到原数组 nums 中，完成原地修改。

---

3. 复杂度分析

• 时间复杂度：O(n)，遍历数组一次。

• 空间复杂度：O(n)，需要额外数组 newArr。

---

4. 边界处理

• k > length 的情况：通过取模运算 k % length 处理（代码中已隐含）。

  • 示例：length = 7, k = 10 → 实际有效旋转步数为 10 % 7 = 3。

238. 除自身以外数组的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;

        // L 和 R 分别表示左右两侧的乘积列表
        int[] L = new int[length];
        int[] R = new int[length];

        int[] answer = new int[length];

        // L[i] 为索引 i 左侧所有元素的乘积
        // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        // R[i] 为索引 i 右侧所有元素的乘积
        // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }

        return answer;
    }
}

代码解读：除自身以外数组的乘积（Product of Array Except Self）

这段代码实现了不使用除法的情况下，计算数组中每个元素除自身外其他所有元素的乘积。以下是详细解析：

---

1. 核心思路

• 问题要求：给定数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 外所有元素的乘积。

• 限制条件：时间复杂度 O(n)，空间复杂度 O(1)（不考虑输出数组）。

• 解决方法：利用前缀积（Prefix Product）和后缀积（Suffix Product）。

---

2. 代码解析

(1) 初始化数组

java

int[] L = new int[length];  // 存储左侧乘积
int[] R = new int[length];  // 存储右侧乘积
int[] answer = new int[length];

• L[i]：表示 nums[i] 左侧所有元素的乘积。

• R[i]：表示 nums[i] 右侧所有元素的乘积。

(2) 计算左侧乘积（L）

java

L[0] = 1;  // 第一个元素左侧无元素，初始化为1
for (int i = 1; i < length; i++) {
    L[i] = nums[i - 1] * L[i - 1];
}

• 逻辑：

  • L[0] = 1（因为 nums[0] 左侧没有元素）。

  • L[i] = nums[i-1] * L[i-1]：递推计算左侧乘积。

(3) 计算右侧乘积（R）

java

R[length - 1] = 1;  // 最后一个元素右侧无元素，初始化为1
for (int i = length - 2; i >= 0; i--) {
    R[i] = nums[i + 1] * R[i + 1];
}

• 逻辑：

  • R[length-1] = 1（因为 nums[length-1] 右侧没有元素）。

  • R[i] = nums[i+1] * R[i+1]：递推计算右侧乘积。

(4) 计算最终结果

java

for (int i = 0; i < length; i++) {
    answer[i] = L[i] * R[i];
}

• 结果公式：answer[i] = L[i] * R[i]（左侧乘积 × 右侧乘积）。

---

3. 示例演示

输入：nums = [1, 2, 3, 4]
执行过程：

1. 计算 L：

   • L = [1, 1×1=1, 1×2=2, 2×3=6] → [1, 1, 2, 6]

2. 计算 R：

   • R = [2×3×4=24, 3×4=12, 4×1=4, 1] → [24, 12, 4, 1]

3. 计算 answer：

   • answer = [1×24=24, 1×12=12, 2×4=8, 6×1=6] → [24, 12, 8, 6]

---

4. 复杂度分析

• 时间复杂度：O(n)，遍历数组 3 次（计算 L、R、answer）。

• 空间复杂度：O(n)，使用了 L 和 R 数组（若优化为 O(1)，见下文）。