力扣面试经典150题——数组/字符串

1. 合并两个有序数组

题目编号：88

题目链接：88. 合并两个有序数组 - 力扣（LeetCode）

难度：简单

题目描述：

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

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

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

示例 1：

1
2
3
4
输入：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：

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

示例 3：

1
2
3
4
5
输入：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) 的算法解决此问题吗？

解题：

方法一：
0. 排除nums1和num2为空的情况

  1. 遍历nums1和nums2，并从头开始，依次对两个数组取出的元素做对比，将较小的元素放入temp数组
  2. 将没有遍历完的nums数组元素直接放入temp数组后面
  3. 将temp数组的元素赋值给num1，用于返回
    使用临时数组，空间复杂度为O(m+n)，时间复杂度为O(m+n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 使用临时数组
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return; // 排除nums2为空的情况
        if (m == 0) { //排除nums1为空的情况
            for (int i = 0; i < nums1.length; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }

        int[] temp = new int[m + n]; //临时数组

        int i = 0, j = 0, k = 0;
        // 1. 遍历nums1和nums2，并从头开始，依次对两个数组取出的元素做对比，将较小的元素放入temp数组
        while ((i < m && j < n)) {
            temp[k++] = nums1[i] < nums2[j] ? nums1[i++] :nums2[j++];
        }

        // 2. 将没有遍历完的nums数组元素直接放入temp数组后面
        if (i < m) {
            while (i < m) {
                temp[k++] = nums1[i++];
            }
        } else if (j < n) {
            while (j < n) {
                temp[k++] = nums2[j++];
            }
        }

        // 将temp数组的元素赋值给num1，用于返回
        for (i = 0; i < nums1.length; i++) {
            nums1[i] = temp[i];
        }
    }
}

方法二，利用nums1多余的n个空间，倒序构造合并后的数组

  1. 从nums1和nums2的末尾开始遍历元素，依次对两个数组取出的元素做对比，将较大的元素放入num1[k]中
  2. nums1遍历完了，将nums2的元素直接放到nums1前面空缺的位置；如果nums2遍历完了，不用动，因为nums1剩余的没遍历的元素刚好符合顺序

空间复杂度O(1),时间复杂度O(m+n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 方法二，利用nums1多余的n个空间，倒序构造合并后的数组
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return; // 排除nums2为空的情况
        if (m == 0) { //排除nums1为空的情况
            for (int i = 0; i < nums1.length; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }

        int i = m - 1, j = n - 1, k = m + n - 1; //定义尾指针
        // 1. 从nums1和nums2的末尾开始遍历元素，依次对两个数组取出的元素做对比，将较大的元素放入num1[k]中
        while (i>=0 && j >= 0) {
            nums1[k--] = nums2[j] > nums1[i] ? nums2[j--] : nums1[i--];
        }
        
        //2.nums1遍历完了，将nums2的元素直接放到nums1前面空缺的位置
        if(i < 0){
            while (j >= 0) nums1[k--] = nums2[j--];
        }
        //如果nums2遍历完了，不用动，nums1剩余的没遍历的元素刚好符合顺序
    }
}

参考题解：

思路
标签：从后向前数组遍历
因为 nums1 的空间都集中在后面，所以从后向前处理排序的数据会更好，节省空间，一边遍历一边将值填充进去
设置指针 len1 和 len2 分别指向 nums1 和 nums2 的有数字尾部，从尾部值开始比较遍历，同时设置指针 len 指向 nums1 的最末尾，每次遍历比较值大小之后，则进行填充
当 len1<0 时遍历结束，此时 nums2 中海油数据未拷贝完全，将其直接拷贝到 nums1 的前面，最后得到结果数组
时间复杂度：O(m+n)

作者：画手大鹏
链接：https://leetcode.cn/problems/merge-sorted-array/

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len1 = m - 1;
        int len2 = n - 1;
        int len = m + n - 1;
        while(len1 >= 0 && len2 >= 0) {
            // 注意--符号在后面，表示先进行计算再减1，这种缩写缩短了代码
            nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
        }
        // 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1
        System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
    }
}

2. 移除元素

题目编号：27

题目链接：27. 移除元素 - 力扣（LeetCode）

难度：简单

题目描述：

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

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

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

说明:

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

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

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

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

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

示例 1：

1
2
3
输入：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：

1
2
3
输入：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

解题：

方法1：

nums中的val直接设为比数组所有元素大的值，然后使用排序算法排序
时间复杂度 O(nlog(n))

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

方法二：

使用双指针
目标：将所有val值移动到数组末端
分别定义指针h、r，分别指向数组第一个元素和最后一个元素
针对h指针：如果nums[h] != val,指针直接后移即h++，如果nums[h] == val,将nums[h]与num[r]交换，即与val相同的数挪到数组末端
针对r指针：如果nums[r] == val,指针直接前移即r–，如果nums[h] != val,将nums[h]与num[r]交换

注意：

  1. 要考虑没有val的情况
  2. 要考虑全是val的情况
    时间复杂度 O(n/2)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {

    public int removeElement(int[] nums, int val) {
        int count = 0; //val值的数量
        int h = 0, r = nums.length - 1; //定义头指针和尾指针

        int t; //临时变量
        while (h <= r) { // 遍历数组条件：头尾指针还未相遇
            if (nums[h] != val) h++;
            else { //nums[h] == val
                if (nums[r] == val) {
                    r--;
                    count++;
                } else if (nums[r] != val) {
                    t = nums[h];
                    nums[h] = nums[r];
                    nums[r] = t;

                    count++; //交换才+1
                    h++;
                    r--;
                }
            }

        }
        return nums.length - count;
    }
}

参考题解：

方法一：双指针
思路及算法

由于题目要求删除数组中等于 val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。可以使用双指针：右指针 right 指向当前将要处理的元素，左指针 left 指向下一个将要赋值的位置。

如果右指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；

如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。

整个过程保持不变的性质是：区间 [0,left)中的元素都不等于 val。当左右指针遍历完输入数组以后，left的值就是输出数组的长度。

这样的算法在最坏情况下（输入数组中没有元素等于 val，左右指针各遍历了数组一次。

作者：力扣官方题解
链接：https://leetcode.cn/problems/remove-element/

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}

方法二：双指针优化
思路

如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5]，当 val 为 1 时，我们需要把每一个元素都左移一位。注意到题目中说：「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 5移动到序列开头，取代元素 1，得到序列 [5,2,3,4]，同样满足题目要求。这个优化在序列中 val 元素的数量较少时非常有效。

实现方面，我们依然使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。

算法

如果左指针 left指向的元素等于 val，此时将右指针 right指向的元素复制到左指针 left 的位置，然后右指针 right左移一位。如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val为止。

当左指针 left和右指针 right重合的时候，左右指针遍历完数组中所有的元素。

这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。

复杂度分析：

时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多一次。

空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

作者：力扣官方题解
链接：https://leetcode.cn/problems/remove-element/

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}

3. 删除有序数组中的重复项

题目编号：26

题目链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

难度：简单

题目描述：

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

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

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

判题标准:

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

1
2
3
4
5
6
7
8
9
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：

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

示例 2：

1
2
3
输入：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 已按 非严格递增 排列

解题：

// *使用双指针解题：
/*
如果nums.length == 1,直接return 1;
定义两个指针，分别为left和right，初始状态left指向数组的第一个元素，right指向第二个元素
定义一个flag用来标志是否有重复元素，初始状态为false
进入循环体，循环条件为，right<nums.length,即遍历完整个数组
如果nums[right] == nums[left],right指针继续后移一位，即right++，left指针不动；flag=true，即标志为该元素有重复
**
如果nums[right] != nums[left],并且flag==true,则nums[++left] = nums[right++]
//重点：right–* *回溯一下，避免[1,1,2,3]这种情况
若flag == false（即该元素没有重复），则移动left指针，即**++left
**
* **/*

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 2) return len; //排除数组长度为1的情况

        int left = 0;
        boolean flag = false; //用来标志是否有重复元素

        for (int right = 1; right < len; right++) {
            if (nums[left] == nums[right])
                flag = true;
            else {
                if (flag) {
                    nums[++left] = nums[right--]; //重点：right-- 回溯一下，避免[1,1,2,3]这种情况
                    flag = false;//重新置为false
                } else {
                    ++left;
                }
            }
        }
        return left + 1;
    }
}

时间复杂度O(n),空间复杂度O(1)

参考题解：

使用快慢双指针，思路同我自己的解题方法，不过此方法更简洁

作者：力扣官方题解
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}

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

题目编号：80

题目链接：80. 删除有序数组中的重复项 II - 力扣（LeetCode）

难度：中等

题目描述：

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

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

说明：

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

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

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

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

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

示例 1：

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

示例 2：

1
2
3
输入：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 已按升序排列

参考题解：

方法一：

因为本题要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素 nums[slow−2] 是否和当前待检查元素 nums[fast]相同。当且仅当 nums[slow−2]=nums[fast] 时，当前待检查元素 nums[fast]不应该被保留（因为此时必然有nums[slow−2]=nums[slow−1]=nums[fast]）。最后，slow 即为处理好的数组的长度。

特别地，数组的前两个数必然可以被保留，因此对于长度不超过 2的数组，我们无需进行任何处理，对于长度超过 2的数组，我们直接将双指针的初始值设为 2 即可。

作者：力扣官方题解
链接：80. 删除有序数组中的重复项 II - 力扣（LeetCode）题解

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n<=2) return n; //若数组为小于等于两个元素，必然满足题意
        int fast = 2, slow = 2;
        while(fast<n){
            //如果快指针指向的元素与慢指针指向的上上个元素不等
            if(nums[fast] != nums[slow-2]){
                nums[slow++] = nums[fast];
            }
            fast++;
        }

        return slow;
    }
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 *方法二：计数法
 * 定义计数器count表示当前元素重复次数，
 * 慢指针++cur表示小于等于两次重复项的元素索引位置，
 * 快指针i用来扫描数组的元素
 *
 * 初始状态count=1，cur=0，i=1
 * 用快指针扫描数组，
 * 当nums[i] == nums[cur]时，
 * 若count<2,则使得nums[++cur] = nums[i]，并且++count，即保正重复次数的元素最多只出现两次
 * 若count>=2即重复元素次数大于2，则快指针直接继续往后扫描，寻找不重复的元素
 *
 * 当nums[i] != nums[cur]时，即快指针遇到不重复元素时
 * 则使得nums[++cur] = nums[i],且count归为初始状态1
 */
class Solution {
    public int removeDuplicates(int[] nums) {
        int count = 1,cur = 0;
        int n = nums.length;

        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[cur]){
                if (count<2){
                    nums[++cur] = nums[i];
                    ++count;
                }
            }else {
                nums[++cur] = nums[i];
                count = 1;
            }
        }
        return cur + 1;
    }
}

5.多数元素：

题目编号：169

题目链接：169. 多数元素 - 力扣（LeetCode）

难度：简单

题目描述：

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

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

示例 1：

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

示例 2：

1
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) 的算法解决此问题

解题：

方法1：
使用哈希表，不用遍历哈希表
由题意多数元素必为出现在数组中最多的元素
定义一个哈希表，key为数组元素的值，value存储该数组元素重复的次数
如果元素重复次数大于n/2，则返回该元素

时间复杂度O(n),空间复杂度O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int majorityElement(int[] nums) {

        HashMap<Integer, Integer> MyMap = new HashMap<Integer, Integer>();
        int n = nums.length;
        int mid = n/2;

        for (int num : nums) {
            if (MyMap.get(num) == null) {
                MyMap.put(num, 1);
            } else {
                MyMap.put(num, MyMap.get(num) + 1);
            }
            if (MyMap.get(num)>mid)
                return num;
        }
        return -1;
    }
}

参考题解：

方法二：

排序，然后直接取数组的中间元素

sort的空间复杂度O(nlogn)

时间复杂度O(nlogn)

代码：

1
2
3
4
5
6
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

6.轮转数组

题目编号：189

题目链接：189. 轮转数组 - 力扣（LeetCode）

难度：中等

题目描述：

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

示例 1:

1
2
3
4
5
6
输入: 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:

1
2
3
4
5
输入：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

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

解题：

方法一：使用双指针加额外数组
空间复杂度：O(n)
时间复杂度O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if(k>n) k = k%n;
        int cur = n - k;
        int[] tmp = new int[n];
        int i = 0;
        while (cur < n) {
            tmp[i++] = nums[cur++];
        }

        cur = 0;
        while (cur < (n - k)) {
            tmp[i++] = nums[cur++];
        }

        for (int j = 0; j < n; j++) {
            nums[j] = tmp[j];
        }
    }
}

方法二：

若k>n,则k = k%n

  1. 先反转数组的0到n-k-1的元素，再反转n-k到n-1的元素
  2. 最后再对整个数组进行反转即为最终结果
    空间复杂度O(1)
    时间复杂度O(n）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if(k>n) k = k%n;
        inverse(nums,0,n-k-1);
        inverse(nums,n-k,n-1);
        inverse(nums,0,n-1);

    }
    public void inverse(int[] nums,int start,int end){
        int tmp = 0;
        while(start<end){
            tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }

}

参考题解：

方法一：使用额外的数组
我们可以使用额外的数组来将每个元素放至正确的位置。用 n表示数组的长度，我们遍历原数组，将原数组下标为 i的元素放至新数组下标为 (i+k) mod  n的位置，最后将新数组拷贝至原数组即可。

代码：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }
}

方法二

1
2
3
4
5
6
7
8
9
10
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int[] temp = new int[k];
        System.arraycopy(nums, n - k, temp, 0, k);
        System.arraycopy(nums, 0, nums, k, n - k);
        System.arraycopy(temp, 0, nums, 0, k);
    }
}

7.买卖股票的最佳时机1

题目编号：121

题目链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）

难度：简单

题目描述：

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

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

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

示例 1：

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

示例 2：

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

提示：

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

解题：

方法一：使用双指针
1.首先定义指针right用来指向卖出股票的价格，
left指针则用来扫描right指针前面买入的股票价格，并用minPrice保存最小买入价格

2.判断当前天的卖出价格是否大于最小买入价格，
若是，则用maxValue保存最大利润，否则right++
maxValue即为返回值

时间复杂度O(n)，空间复杂度O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int maxValue = 0;
        int minPrice = prices[0];
        int left = 0, right = 1; //以left指针指向最小买入价格，right指向卖出点
        int tmpProfit;
        while (right < n) {

            while (left < right) {//找出在当前售出时间right之前的最小买入价格
                if (prices[left] < minPrice) {
                    minPrice = prices[left];//获取最小买入价格
                }
                left++;
            }

            if (prices[right] > minPrice) {
                tmpProfit = prices[right] - minPrice;
                maxValue = tmpProfit > maxValue ? tmpProfit : maxValue; //获取最大利润
            }
            right++;
        }
        return maxValue;
    }
}

参考题解：

官方题解

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int maxProfit(int prices[]) {
        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;
    }
}



8.买卖股票最佳时机2

题目编号：122

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

难度：中等

题目描述：

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

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

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

示例 1：

1
2
3
4
5
输入：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：

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

示例 3：

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

提示：

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

参考题解：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int maxValue = 0;
        int n = prices.length;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i-1])
                maxValue += (prices[i] - prices[i-1]);
        }
        return maxValue;
    }
}

9. 跳跃游戏1

题目编号：55

题目链接：55. 跳跃游戏 - 力扣（LeetCode）

难度：中等

题目描述：

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

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

示例 1：

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

示例 2：

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

提示：

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

参考题解：

解题思路1：
如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
如果可以一直跳到最后，就成功了

代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int k = 0;
        for(int i = 0;i<n;i++){
            if(i>k) return false;
            k = Math.max(k,i+nums[i]);
        }
        return true;
    }
}

10.跳跃游戏2

题目编号：45

题目链接：45. 跳跃游戏 II - 力扣（LeetCode）

难度：中等

题目描述：

给定一个长度为 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:

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

示例 2:

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

提示:

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

参考题解：

方法一：反向查找出发位置
我们的目标是到达数组的最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，该位置通过跳跃能够到达最后一个位置。

如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？直观上来看，我们可以「贪心」地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。

找到最后一步跳跃前所在的位置之后，我们继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。

使用这种方法编写的 C++ 和 Python 代码会超出时间限制，因此我们只给出 Java 和 Go 代码。

作者：力扣官方题解

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

11. H指数

题目编号：274

题目链接：274. H 指数 - 力扣（LeetCode）

难度：中等

题目描述：

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

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

示例 1：

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

示例 2：

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

提示：

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

参考题解：

方法一：排序
抄答案：排序
首先我们可以将初始的H指数h设为0，然后将引用次数排序，
并且对排序后的数组从大到小遍历。
根据H指数的定义，如果当前H指数为h并且在遍历过程中，
找到当前值citations[i] > h,
则说明我们找到了一篇被引用了至少h+1次的论文，所以将现有的
h值加1.继续遍历直到h无法继续增大。最后返回h作为最终答案。

时间复杂度O(nlogn)

空间复杂度O(logn)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, i = citations.length - 1; 
        while (i >= 0 && citations[i] > h) {
            h++; 
            i--;
        }
        return h;
    }
}


方法二：计数排序
根据上述题解我们发现，最终的时间复杂度与排序算法的时间复杂度有关，
所以我们可以使用计数排序算法，新建并维护一个数组counter用来记录当前引用次数的论文有几篇。

根据定义，我们可以发现H指数不可能大于总的论文发表数，
所以对于引用次数超过论文发表数的情况，
我们可以将其按照总的论文发表数来计算即可。
这样我们可以限制参与排序的数的大小为[0，n]（其中n为总的论文发表数），
使得计数排序的时间复杂度降低到O(n).

最后我们可以从后向前遍历数组counter，对于每个0<=i<=n,在数组counter中得到大于或
等于当前引用次数i的总论文数。当我们找到一个H指数时跳出循环，并返回结果。

时间复杂度 O(n)
空间复杂度 O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length, tot = 0;
        int[] counter = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n) {
                counter[n]++;
            } else {
                counter[citations[i]]++;
            }
        }
        for (int i = n; i >= 0; i--) {
            tot += counter[i];
            if (tot >= i) {
                return i;
            }
        }
        return 0;
    }
}

方法三：二分搜索
我们需要找到一个值h，它是满足【有h篇论文的引用次数至少为h】的最大值。
小于等于h的所有值x都满足这个性质，而大于h的值都不满足这个性质。
同时，因为我们可以用较短时间（扫一遍数组的时间复杂度为O(n),其中n为数组citation的长度），
来判断x是否满足这个性质，所以这个问题可以用二分搜索来解决。

设查找范围的初始左边界left为0，初始右边界right为n。
每次在查找范围内取中间点mid，同时扫描整个数组，
判断是否至少有mid个数大于mid。如果有，说明要寻找的h在搜索区间的右边，
反之则在左边。

时间复杂度O(nlogn)
空间复杂度O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int hIndex(int[] citations) {
        int left=0,right=citations.length;
        int mid=0,cnt=0;
        while(left<right){
            // +1 防止死循环
            mid=(left+right+1)>>1;
            cnt=0;
            for(int i=0;i<citations.length;i++){
                if(citations[i]>=mid){
                    cnt++;
                }
            }
            if(cnt>=mid){
                // 要找的答案在 [mid,right] 区间内
                left=mid;
            }else{
                // 要找的答案在 [0,mid) 区间内
                right=mid-1;
            }
        }
        return left;
    }
}

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

题目编号：380

题目链接：380. O(1) 时间插入、删除和获取随机元素 - 力扣（LeetCode）

难度：中等

题目描述：

实现RandomizedSet 类：

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

  • -231 <= val <= 231 - 1
  • 最多调用 insert、remove 和 getRandom 函数 2 * ``105 次
  • 在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

参考题解：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
变长数组中存储元素，哈希表中存储每个元素在变长数组中的下标
 */
class RandomizedSet {
    List<Integer> nums;
    Map<Integer,Integer> indices;
    Random random;

    public RandomizedSet(){
        nums = new ArrayList<Integer>(); //变长数组存储元素
        indices = new HashMap<Integer,Integer>(); //哈希表存储元素的下标
        random = new Random();//随机获取元素
    }
    public boolean insert(int val){
        if (indices.containsKey(val))
            return false;//该元素已经在集合中，不再插入
        int index = nums.size();//新插入元素索引为最后一个元素的位置
        nums.add(val);//将元素添加到变长数组中
        indices.put(val,index); //将该元素的下标存入哈希表
        return true;//插入成功
    }

    public boolean remove(int val){
        if (!indices.containsKey(val))
            return false;//如果该元素不存在，返回false
        int index = indices.get(val); //从哈希表中获取该需要移除元素的下标
        int last = nums.get(nums.size()-1);//从变长数组中获取最后一个元素
        nums.set(index,last);//将last移动到该删除元素的位置
        indices.put(last,index);//更新last的下标
        nums.remove(nums.size()-1);//删除变长数组的最后一个位置
        indices.remove(val);//从哈希表中删除该值的下标
        return true;
    }
    
    public int getRandom(){
        int randomIndex = random.nextInt(nums.size());//获取随机下标
        return nums.get(randomIndex);
    }

}

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

题目编号：238

题目链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）

难度：中等

题目描述：

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

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

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

示例 1:

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

示例 2:

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

提示：

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

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

解题：

方法一：暴力，时间复杂度O(n²)，超时

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = 1;
            for (int j = 0; j < n; j++) {
                if (i!=j)
                    answer[i] *= nums[j];
            }
        }
        return answer;
    }
}

参考题解：

题解：方法二：
1.先求answer的前缀之积和后缀之积
2. 用前缀之积乘后缀之积得到最终答案
空间复杂度2xO(n)
时间复杂度2xO(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] Lans = new int[n];//存储前缀之积
        int[] answer = new int[n];//存储后缀之积和存储最终答案

        int h = 1,r=n-2;
        Lans[0] = 1;
        answer[n-1] = 1;

        while (h<n){
            Lans[h] = Lans[h-1]*nums[h-1];
            answer[r] = answer[r+1]*nums[r+1];//后缀之积
            h++;
            r--;
        }

        for (int i = 0; i < n; i++) {
            answer[i] = answer[i]*Lans[i];
        }

        return answer;
    }
}

方法三：
进阶
空间复杂度O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];//存储后缀之积和存储最终答案

        int r = n - 2;

        answer[n - 1] = 1;
        while (r >= 0) {
            answer[r] = answer[r + 1] * nums[r + 1];//后缀之积
            r--;
        }
        int T = 1;//前缀之积
        for (int i = 0; i < n; i++) {
            answer[i] = answer[i] * T;
            T *= nums[i];
        }
        return answer;
    }
}

14.加油站

题目编号：134

题目链接：134. 加油站 - 力扣（LeetCode）

难度：中等

题目描述：

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

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: 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:

1
2
3
4
5
6
7
8
9
输入: 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

解题：

暴力解法

超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
暴力解法，每个起始点都试一遍
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {//尝试n个起始出发站
            int j = i, tmpGas = 0;
            while ((tmpGas+gas[j]) >= cost[j]){
                tmpGas = tmpGas+gas[j];
                tmpGas -= cost[j];
                j = (j+1)%n;
                if (i==j)
                    return i;
            }
        }

        return -1;
    }
}

参考题解：

最容易想到的解法是：从头到尾遍历每个加油站，并检查以该加油站为起点，最终能否行驶一周。我们可以通过减小被检查的加油站数目，来降低总的时间复杂度。

假设我们此前发现，从加油站 x 出发，每经过一个加油站就加一次油（包括起始加油站），最后一个可以到达的加油站是 y（不妨设 x<y）。这就说明：

$$
\sum_{i=x}^{y} gas[i]<\sum_{i=x}^{y} cost[i]
$$

$$
\sum_{i=x}^{j} gas[i]>=\sum_{i=x}^{j} cost[i] (j∈[x,y))
$$

image-20231109150919214

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}

时间复杂度O(N)

空间复杂度O(1)

15.分发糖果

题目编号：135

题目链接：135. 分发糖果 - 力扣（LeetCode）

难度：困难

题目描述：

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

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

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

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

示例 2：

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

提示：

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

解题：

方法一：

//初始状态，每个孩子至少一个糖果

//从左到右遍历,保证比左边孩子分数高的孩子糖果得到满足

//从右到左遍历，保证比右边孩子分数高的孩子糖果得到满足

给candy数组求和，得到最终答案

时间复杂度O(n)

空间复杂度O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution{
	public int candy(int[] ratings){
        int n = ratings.length;
        int[] cd =  new int[n];
        Arrays.fill(cd,1);//初始状态，每个孩子至少一个糖果
        for(int i=1;i<n;i++){//从左到右遍历,保证比左边孩子分数高的孩子糖果得到满足
            if(ratings[i]>ratings[i-1])
                cd[i] = cd[i-1] + 1;//当前孩子比前一个孩子分数高，糖果比前一个孩子多一个
        }
        for(int j =n-2;j>=0;j--){//从右到左遍历，保证比右边孩子分数高的孩子糖果得到满足
            if(ratings[j]>ratings[j+1])
                cd[j] = Math.max(cd[j],cd[j+1]+1);//右边孩子的糖果数，有可能大于等于或小于左边的
        }
        return Arrays.stream(cd).sum();
        
    }
}

参考题解：

依据前面总结的规律，我们可以提出本题的解法。我们从左到右枚举每一个同学，记前一个同学分得的糖果数量为 pre：

如果当前同学比上一个同学评分高，说明我们就在最近的递增序列中，直接分配给该同学 pre+1 个糖果即可。

否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中所有的同学都再多分配一个糖果，以保证糖果数量还是满足条件。

我们无需显式地额外分配糖果，只需要记录当前的递减序列长度，即可知道需要额外分配的糖果数量。

同时注意当当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。

这样，我们只要记录当前递减序列的长度 dec，最近的递增序列的长度 inc和前一个同学分得的糖果数量 pre 即可。

时间复杂度O(n)

空间复杂度O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {//递增序列
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ret += pre;
                inc = pre;
            } else {//递减序列
                dec++;
                if (dec == inc) {
                    dec++;
                }
                ret += dec;
                pre = 1;
            }
        }
        return ret;
    }
}


16.接雨水

题目编号：42

题目链接：42. 接雨水 - 力扣（LeetCode）

难度：困难

题目描述：

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

示例 1：

img

1
2
3
输入：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：

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

提示：

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