leetCode 题目

初级算法

删除排序数组中的重复项

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0; // 处理边界情况
        int slow = 0; // 慢指针
        int fast = 1; // 快指针
        for (; fast < nums.length; fast++){
            if (nums[fast] != nums[slow]){
                slow++;
                nums[slow] = nums[fast];
            }
        }
    return slow+1;
    }
}

解题思路：
1. 快慢指针，初始慢指针在0，快指针从1开始遍历，处理点时启动慢指针。
2. 两两对比，将不同的数覆盖到前面相同的数。
3. 快指针遍历完，返回慢指针+1的值为新数组的长度。

买卖股票的最佳时机 II

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

解题思路：
贪心策略
遍历数组，如果当前价格比前一天高，则计算利润。

旋转数组
朴素右移（超出时间限制）

class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        for (int j = 0; j < k; j++) {
            // 右移一位
            int last = nums[nums.length - 1];
            for (int i = nums.length - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = last;
        }
    }
}

使用临时数组

class Solution {
    public void rotate(int[] nums, int k) {
        // 创建临时数组                      
        int temp[] = new int [nums.length];
        for(int i=0;i<nums.length;i++){
            temp[i] = nums[i];
        }
        // 将临时数组的值复制给nums
        for(int i=0;i<nums.length;i++){
            nums[(i + k) % nums.length] = temp[i];
        }
    }

    // 优化：使用数组复制 System.arraycopy
    public void rotate(int[] nums, int k) {
        k = k % nums.length; 
        int[] temp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            temp[(i + k) % nums.length] = nums[i];
        }
        System.arraycopy(temp, 0, nums, 0, n);
    }
}

三次反转（原地，高效）

public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1); // 反转整个数组
    reverse(nums, 0, k - 1);           // 反转前k个元素
    reverse(nums, k, nums.length - 1); // 反转后半部分元素
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        // 三杯倒
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}