algorithm-array

简单

合并两个有序数组

• 合并两个有序数组

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

 

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
 

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
 

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

题目解答

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            while (i >= 0 && j >= 0 && nums1[i] >= nums2[j]) {
                nums1[k--] = nums1[i--];
            }
            while (i >= 0 && j >= 0 && nums2[j] >= nums1[i]) {
                nums1[k--] = nums2[j--];
            }
        }

        while (i >= 0) {
            nums1[k--] = nums1[i--];
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[] nums1 = { 1, 2, 3, 0, 0, 0 };
        int m = 3;

        int[] nums2 = { 2, 5, 6 };
        int n = 3;

        new Solution().merge(nums1, m, nums2, n);
        ArrayUtils.printArray(nums1);
    }

    public static void testCase2() {
        int[] nums1 = { 1 };
        int m = 1;

        int[] nums2 = {};
        int n = 0;

        new Solution().merge(nums1, m, nums2, n);
        ArrayUtils.printArray(nums1);
    }

    public static void testCase3() {
        int[] nums1 = { 0 };
        int m = 0;

        int[] nums2 = { 1 };
        int n = 1;

        new Solution().merge(nums1, m, nums2, n);
        ArrayUtils.printArray(nums1);
    }
}

移除元素

• 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

 

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
 

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

题目解答

public class Solution {
    public int removeElement(int[] nums, int val) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                count++;
            } else {
                if (count != 0) {
                    nums[i - count] = nums[i];
                }
            }
        }

        return nums.length - count;
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 3, 2, 2, 3 };
        int val = 3;

        int len = new Solution().removeElement(nums, val);
        ArrayUtils.printArray(nums, len);
    }

    public static void testCase2() {
        int[] nums = { 0, 1, 2, 2, 3, 0, 4, 2 };
        int val = 2;

        int len = new Solution().removeElement(nums, val);
        ArrayUtils.printArray(nums, len);
    }
}

删除有序数组中的重复项

• 删除有序数组中的重复项

题目描述

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。

 

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
 

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列

题目解答

public class Solution {
    public int removeDuplicates(int[] nums) {
        int count = 0;
        int prev = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == prev) {
                count++;
            } else {
                prev = nums[i];
                if (count != 0) {
                    nums[i - count] = nums[i];
                }
            }
        }

        return nums.length - count;
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 1, 1, 2 };

        int len = new Solution().removeDuplicates(nums);
        ArrayUtils.printArray(nums, len);
    }

    public static void testCase2() {
        int[] nums = { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 };

        int len = new Solution().removeDuplicates(nums);
        ArrayUtils.printArray(nums, len);
    }
}

删除有序数组中的重复项II

• 删除有序数组中的重复项II

题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

 

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
 

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

题目解答

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }

        int count = 0;
        int prev1 = nums[0];
        int prev2 = nums[1];

        for (int i = 2; i < nums.length; i++) {
            if (nums[i] == prev2 && prev2 == prev1) {
                count++;
            } else {
                prev1 = prev2;
                prev2 = nums[i];
                if (count != 0) {
                    nums[i - count] = nums[i];
                }
            }
        }

        return nums.length - count;
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 1, 1, 1, 2, 2, 3 };

        int len = new Solution().removeDuplicates(nums);
        ArrayUtils.printArray(nums, len);
    }

    public static void testCase2() {
        int[] nums = { 0, 0, 1, 1, 1, 1, 2, 3, 3 };

        int len = new Solution().removeDuplicates(nums);
        ArrayUtils.printArray(nums, len);
    }
}

多数元素

• 多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2
 

提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
 

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

题目解答

• 用计数统计并选择出最大值就是众数，时间复杂度O(n)，空间复杂度O(m)
• 用map统计数量并选择出最大值就是众数，时间复杂度O(n)，空间复杂度O(n)
• 排序后n/2处的数就是众数，时间复杂度O(nlogn)，空间复杂度取决于排序算法的空间复杂度
• 随机选择一个数判断是不是众数（因为众数的占比高），最坏时间复杂度O(∞)，空间复杂度O(1)
• 分治法选择出众数，时间复杂度O(nlogn)，空间复杂度O(logn)
• 投票算法，时间复杂度O(n)，空间复杂度O(1)

投票算法详解

• 先假定一个数为众数，再遍历数组进行投票
• 如果当前数和假定数相等，则投票数加1，否则投票数减1
• 投票前先判断一下当前票数，如果票数为0，则代表假定数不是众数，需淘汰出局，并假定当前数为众数后继续

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int val = 0;

        for (int num : nums) {
            if (count == 0) {
                val = num;
            }

            count = count + (num == val ? 1 : -1);
        }

        return val;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 3, 2, 3 };

        int result = new Solution().majorityElement(nums);
        System.out.println(result);
    }

    public static void testCase2() {
        int[] nums = { 2, 2, 1, 1, 1, 2, 2 };

        int result = new Solution().majorityElement(nums);
        System.out.println(result);
    }
}

轮转数组

• 轮转数组

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

 

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
 

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

题目解答

• 暴力法：循环K次，每次向右轮转1个位置
• 归并法：用新数组先归并后K个，再归并剩余的部分，最后将结果拷贝回原数组
• 置换法：将元素存到新数组中轮转后的位置，最后将结果拷贝回原数组

ps：移动nums.length次就会回到原位，所以K要先降到模数一下，即 K = K % nums.length `

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;

        int c = 0;
        int i = 0;
        while (c < nums.length) {

            int j = i;
            int x = nums[i]; // 保存当前元素
            int y = -1; // 保存下一个元素

            while (true) {
                // 计算下一个元素的位置
                j = (j + k) % nums.length;

                // 保存下一个元素
                y = nums[j];

                // 用当前元素占领下一个元素的位置
                nums[j] = x;

                // 处理完的个数加1
                c++;

                // 个数达标了，全部处理完毕，结束
                if (c == nums.length) {
                    break;
                }

                // 回到起点了，不能重复处理，结束
                if (j == i) {
                    break;
                }

                // 更新当前元素
                x = y;
            }

            i = i + 1;
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 1, 2, 3, 4, 5, 6, 7 };
        int k = 3;

        new Solution().rotate(nums, k);
        ArrayUtils.printArray(nums);
    }

    public static void testCase2() {
        int[] nums = { -1, -100, 3, 99 };
        int k = 2;

        new Solution().rotate(nums, k);
        ArrayUtils.printArray(nums);
    }
}

买卖股票的最佳时机

• 买卖股票的最佳时机

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

 

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
 

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104

题目解答

• 二层循环（j > i）求的最大差值就是最大利润
• 一次循环时判断最小值时购买后卖出的利润是不是最大利润

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        // 本质上是求最高点和最低点的高低差（股票的本质是低买高卖）
        // 因为得先买入后卖出，所以要求最高点不能出现在最低点左边
        // 这样就会出现多对最低点和最高点的组合
        // 所以需要求出所有组合里面的高低差
        // 高低差的最大值就是答案

        int maxProfit = 0;
        int minPrice = prices[0]; // 记录最低点的价格
        int maxPrice = minPrice; // 记录最高点的价格

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] >= maxPrice) {
                // 有更高的价格，更新最高点的价格
                maxPrice = prices[i];
            }

            if (prices[i] < minPrice) {
                // 检查和更新当前的最高点和最低点的高低差是不是最大值
                // maxPrice != minPrice 可以代表不能同一天买入后卖出
                // maxPrice != minPrice 也可以代表后续的最大利润不能为0
                // maxPrice != minPrice 条件其实省略掉也不影响结果
                // 因为 maxPrice - minPrice > maxProfit > 0 可以覆盖 maxPrice != minPrice
                if (maxPrice != minPrice && maxPrice - minPrice > maxProfit) {
                    maxProfit = maxPrice - minPrice;
                }

                // 有更低的价格，更新价格的最低点
                // 因为得先买入后卖出，所以要求最高点不能出现在最低点左边
                // 所以最高点也得更新
                minPrice = prices[i];
                maxPrice = minPrice;
            }
        }

        // 检查和更新当前的最高点和最低点的高低差是不是最大值
        // maxPrice != minPrice 可以代表不能同一天买入后卖出
        // maxPrice != minPrice 也可以代表后续的最大利润不能为0
        // maxPrice != minPrice 条件其实省略掉也不影响结果
        // 因为 maxPrice - minPrice > maxProfit > 0 可以覆盖 maxPrice != minPrice
        if (maxPrice != minPrice && maxPrice - minPrice > maxProfit) {
            maxProfit = maxPrice - minPrice;
        }

        // 上面的代码可以简化成下面的代码
        // int minPrice = Integer.MAX_VALUE;
        // int maxProfit = 0;
        // for (int i = 0; i < prices.length; i++) {
        // if (prices[i] < minPrice) {
        // minPrice = prices[i];
        // } else if (prices[i] - minPrice > maxProfit) {
        // maxProfit = prices[i] - minPrice;
        // }
        // }

        return maxProfit;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 7, 1, 5, 3, 6, 4 };

        int result = new Solution().maxProfit(nums);
        System.out.println(result);
    }

    public static void testCase2() {
        int[] nums = { 7, 6, 4, 3, 1 };

        int result = new Solution().maxProfit(nums);
        System.out.println(result);
    }
}

买卖股票的最佳时机II

• 买卖股票的最佳时机II

题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

 

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。
示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。
示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
 

提示：

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

题目解答

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        // 本质上是求多个上升区间的区间差之和（股票的本质是低买高卖）

        int maxProfit = 0;
        int minPrice = prices[0]; // 记录上升区间的最小值
        int maxPrice = minPrice; // 记录上升区间的最大值

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] >= maxPrice) {
                // 还是上升趋势，继续扩大区间
                maxPrice = prices[i];
            } else {
                // 出现拐点了
                maxProfit = maxProfit + (maxPrice - minPrice);

                // 重设窗口位置
                minPrice = prices[i];
                maxPrice = minPrice;
            }
        }

        maxProfit = maxProfit + (maxPrice - minPrice);

        return maxProfit;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[] nums = { 7, 1, 5, 3, 6, 4 };

        int result = new Solution().maxProfit(nums);
        System.out.println(result);
    }

    public static void testCase2() {
        int[] nums = { 1, 2, 3, 4, 5 };

        int result = new Solution().maxProfit(nums);
        System.out.println(result);
    }

    public static void testCase3() {
        int[] nums = { 7, 6, 4, 3, 1 };

        int result = new Solution().maxProfit(nums);
        System.out.println(result);
    }
}

跳跃游戏

• 跳跃游戏

题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
 

提示：

1 <= nums.length <= 104
0 <= nums[i] <= 105

题目解答

public class Solution {
    public boolean canJump(int[] nums) {
        int p = 0; // 记录向右可跳的最远位置
        for (int i = 0; i < nums.length; i++) {
            // i <= p 说明i可到达
            if (i <= p) {
                if (i + nums[i] >= p) {
                    // 更新可达的最远位置
                    p = i + nums[i];
                    if (p >= nums.length - 1) {
                        return true;
                    }
                }
            } else {
                return false;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 2, 3, 1, 1, 4 };

        boolean result = new Solution().canJump(nums);
        System.out.println(result);
    }

    public static void testCase2() {
        int[] nums = { 3, 2, 1, 0, 4 };

        boolean result = new Solution().canJump(nums);
        System.out.println(result);
    }
}

跳跃游戏II

• 跳跃游戏II

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i] 
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

 

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4]
输出: 2
 

提示:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

题目解答

public class Solution {
    public int jump(int[] nums) {
        int c = 0;
        int p = nums.length - 1; // 记录向左反跳的最远位置
        while (p > 0) {
            // 查找最远的上一跳位置
            for (int i = 0; i < p; i++) {
                if (i + nums[i] >= p) {
                    p = i;

                    // 反向跳一次到上一跳位置
                    c++;

                    break;
                }
            }
        }

        return c;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 2, 3, 1, 1, 4 };

        int result = new Solution().jump(nums);
        System.out.println(result);
    }

    public static void testCase2() {
        int[] nums = { 2, 3, 0, 1, 4 };

        int result = new Solution().jump(nums);
        System.out.println(result);
    }
}

H指数

• H指数

题目描述

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。

 

示例 1：

输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
示例 2：

输入：citations = [1,3,1]
输出：1
 

提示：

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

题目解答

import java.util.Arrays;

public class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);

        int h = 0;
        int i = citations.length - 1;
        while (i >= 0 && citations[i] > h) {
            h++;
            i--;
        }

        return h;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 3, 0, 6, 1, 5 };

        int result = new Solution().hIndex(nums);
        System.out.println(result);
    }

    public static void testCase2() {
        int[] nums = { 1, 3, 1 };

        int result = new Solution().hIndex(nums);
        System.out.println(result);
    }
}

O(1)时间插入、删除和获取随机元素

• O(1)时间插入、删除和获取随机元素

题目描述

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1)

题目解答

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

class RandomizedSet {
    List<Integer> list;
    Map<Integer, Integer> map;
    Random random;

    public RandomizedSet() {
        list = new ArrayList<Integer>();
        map = new HashMap<Integer, Integer>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }

        int index = list.size();

        list.add(val);

        map.put(val, index);

        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }

        int index = map.get(val);
        int lastIndex = list.size() - 1;
        int lastVal = list.get(lastIndex);

        list.set(index, lastVal);
        list.remove(lastIndex);

        map.put(lastVal, index);
        map.remove(val);

        return true;
    }

    public int getRandom() {
        int randomIndex = random.nextInt(list.size());
        return list.get(randomIndex);
    }
}

除自身以外数组的乘积

• 除自身以外数组的乘积

题目描述

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

 

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
 

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内
 

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

题目解答

public 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;
    }
}

加油站

• 加油站

题目描述

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

 

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
 

提示:

gas.length == n
cost.length == n
1 <= n <= 105
0 <= gas[i], cost[i] <= 104

题目解答

设从x出发，不能行驶一圈时能够最远到达的加油站为y，并设z为x和y之间的加油站
则从z出发，也不能到达y的下一站（则说明从z出发也不能行驶一圈）

证明如下：

• 因为从x能到达y，z在x和y之间，所以从x能到z
• 因为从x能到达z，所以在到达z后汽油可能还有剩余
• 因为从x到达z后汽油可能还有剩余继续行进也不能到达y的下一站，所以从z直接出发肯定也不能到达y的下一站

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
}

困难

分发糖果

• 分发糖果

题目描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

 

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
 

提示：

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

题目解答

TODO：分发糖果

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        int right = 0, ret = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                right++;
            } else {
                right = 1;
            }
            ret += Math.max(left[i], right);
        }
        return ret;
    }
}

接雨水

• 接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 

示例 1：



输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9
 

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

题目解答

TODO：接雨水

public class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}