Scott の 博客
Scott
2021-12-01
目录

数组

code 原作者：画手大鹏
链接：https://leetcode-cn.com/leetbook/read/illustrate-lcof/59otf1/
来源：力扣（LeetCode）

code 原作者2：CyC2018
链接：https://github.com/CyC2018/CS-Notes
来源：GitHub
1
2
3
4
5
6
7

# 剑指 Offer 03. 数组中重复的数字

题目描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input:
{2, 3, 1, 0, 2, 5}

Output:
2
1
2
3
4
5

解题思路

  • 标签：哈希
  • 使用 HashSet 来进行处理，因为 HashSet 本身不允许出现重复元素，所以当添加元素失败或已经包含该数字时，则表示出现了重复元素，将其返回即可
  • 时间复杂度：O(n)，空间复杂度：O(n)
class Solution {
    public int findRepeatNumber(int[] nums) {
        HashSet<Integer> numsSet = new HashSet<>();
        for(int num: nums) {
            if(!numsSet.add(num)) {
                return num;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11

或者：

  • 要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。
  • 对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。
  • 以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复：

  • 标签：哈希
  • 从题目描述中我们可以看出，因为所有数字都在 0 ～ n-1 的范围内，其实完全可以省掉额外的空间开辟，将每个位置的数交换映射到其对应的数组下标下面，当出现新的元素与其对应的下标中的数字相等时，即为重复数字
  • 这本质还是哈希的思想，思路 1 是使用库函数申请额外空间，思路 2 则是数组本身做哈希表，达到了节省空间的目的
  • 此处会用到 while 循环，原因是保证交换过来的新元素位置也要正确
  • 时间复杂度：O(n)，空间复杂度：O(1)
public int duplicate(int[] nums) {
    for (int i = 0; i < nums.length; i++)
        while (nums[i] != i)
            if (nums[i] == nums[nums[i]])
                return  nums[i];
            swap(nums, i, nums[i]);
    return -1;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 剑指 Offer 04. 二维数组中的查找

题目描述

给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.
1
2
3
4
5
6
7
8
9
10
11


解题思路

要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。

该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来快速地缩小查找区间，每次减少一行或者一列的元素。当前元素的查找区间为左下角的所有元素。


public boolean Find(int target, int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
        return false;
    
    int rows = matrix.length;
    int cols = matrix[0].length;
    int r = 0, c = cols - 1; // 从右上角开始
    
    while (r <= rows - 1 && c >= 0) {
        if (target == matrix[r][c])
            return true;
        else if (target > matrix[r][c])
            r++;
        else
            c--;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 剑指 Offer 05. 替换空格

题目描述

将一个字符串中的空格替换成 "%20"。

Input:
"A B"

Output:
"A%20B"
1
2
3
4
5

解题思路

  • 标签：字符串
  • 最简单的方案自然是直接使用库函数啦！当然题目肯定是不希望我们这样做的！
  • 增加一个新字符串，遍历原来的字符串，遍历过程中，如果非空格则将原来的字符直接拼接到新字符串中，如果遇到空格则将%20拼接到新字符串中
  • 时间复杂度：O(n)，空间复杂度：O(n)
class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == ' ') {
                sb.append("%20");
            }
            else {
                sb.append(ch);
            }
        }
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

或者：（感觉不怎么实用）

① 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），所以当遍历到一个空格时，需要在尾部填充两个任意字符。

② 令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。

③ 当 P2 遇到 P1 时（P2 <= P1），或者遍历结束（P1 < 0），退出。


public String replaceSpace(StringBuffer str) {
    int P1 = str.length() - 1;
    for (int i = 0; i <= P1; i++)
        if (str.charAt(i) == ' ')
            str.append("  ");

    int P2 = str.length() - 1;
    while (P1 >= 0 && P2 > P1) {
        char c = str.charAt(P1--);
        if (c == ' ') {
            str.setCharAt(P2--, '0');
            str.setCharAt(P2--, '2');
            str.setCharAt(P2--, '%');
        } else {
            str.setCharAt(P2--, c);
        }
    }
    return str.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 剑指 Offer 11. 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1
1
2

示例 2：

输入：[2,2,2,0,1]
输出：0
1
2

思路

  • 标签：二分查找
  • 整体思路：首先数组是一个有序数组的旋转，从这个条件可以看出，数组是有大小规律的，可以使用二分查找利用存在的规律快速找出结果
  • 时间复杂度：O(logn)，空间复杂度：O(1)

算法流程

  • 初始化下标 left 和 right
  • 每次计算中间下标 mid = (right + left) / 2，这里的除法是取整运算，不能出现小数
  • 当 numbers[mid] < numbers[right] 时，说明最小值在 [left, mid] 区间中，则令 right = mid，用于下一轮计算
  • 当 numbers[mid] > numbers[right] 时，说明最小值在 [mid, right] 区间中，则令 left = mid + 1，用于下一轮计算
  • 当 numbers[mid] == numbers[right] 时，无法判断最小值在哪个区间之中，此时让 right--，缩小区间范围，在下一轮进行判断
  • 为什么是 right-- 缩小范围，而不是 left++？
    • 因为数组是升序的，所以最小值一定靠近左侧，而不是右侧
    • 比如，当存在 [1,2,2,2,2] 这种情况时，left = 0，right = 4，mid = 2，数值满足 numbers[mid] == numbers[right] 这个条件，如果 left++，则找不到最小值
class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int mid = (right + left) / 2;
            if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            } else if (numbers[mid] < numbers[right]) {
                right = mid;
            } else {
                right --;
            }
        }
        return numbers[left];
    }
    
    // without duplication
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int mid = (right + left) / 2;
            if (numbers[mid] <= numbers[right])
                right = mid;
            else
                left = mid + 1;
        }
        return numbers[left];
    }
}
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

或

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

# 剑指 Offer 17. 打印从 1 到最大的 n 位数

题目描述

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
1
2

说明：

  • 用返回一个整数列表来代替打印
  • n 为正整数

思路

  • 标签：数组
  • 整体思路：首先求出要打印的数字范围，然后再从 1 开始打印到最大的数字
  • 时间复杂度：O()，空间复杂度：O()

算法流程

  • 初始化 sum = 1
  • 循环遍历乘 10 让 sum 变为边界值
  • 新建 res 数组，大小为 sum-1
  • 从 1 开始打印，直到 sum-1 为止
class Solution {
    public int[] printNumbers(int n) {
        int sum = 1;
        for (int i = 0; i < n; i++) {
            sum *= 10;
        }
        int[] res = new int[sum - 1];
        for(int i = 0; i < sum - 1; i++){
            res[i] = i + 1;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

或：

思路 2

  • 标签：字符串

  • 整体思路：原题的题意其实是希望考察大数计算，因为 int 数组有可能会溢出，所以用字符串处理可以保证一定不会溢出，但是呢，由于返回值规定是 int 数组，所以其实从返回值上来看，是一定不会溢出的，比较矛盾。所以给出个思路 2，学习下如何用字符串处理大数即可，不用特别纠结溢出这件事情

  • 时间复杂度：O()，空间复杂度：O()

算法流程 2

  • 初始化字符串 str，另其初始值为 n-1 个 "0"
  • 递增 str，使用字符去递增，递增过程中判断是否存在进位，存在进位则进位处 +1，直到达到最大值为止，结束循环
  • 每获取到一个值之后，遍历前方多余的 "0"，将多余的 "0" 去掉，转换为 int 存到结果数组中
class Solution {
    public int[] printNumbers(int n) {
        int[] res = new int[(int)Math.pow(10, n) - 1];
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < n; i++) {
            str.append('0');
        }
        int count = 0;
        while(!increment(str)){
            int index = 0;
            
            // 去除多余的 0
            while (index < str.length() && str.charAt(index) == '0'){
                index++;
            }
            res[count] = Integer.parseInt(str.toString().substring(index));
            count++;
        }
        return res;
    }

    public boolean increment(StringBuilder str) {
        boolean isCarry = false;
        for (int i = str.length() - 1; i >= 0; i--) {
            char s = (char)(str.charAt(i) + 1);
            if (s > '9') {
                str.replace(i, i + 1, "0"); // 把 i 位置上的 char 替换掉
                if (i == 0) { // 达到最大值
                    isCarry = true;
                }
            }
            else {
                str.replace(i, i + 1, String.valueOf(s));
                break;
            }
        }
        return isCarry;
    }
}
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

# 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。
1
2
3

提示：

  1. 0 <= nums.length <= 50000
  2. 0 <= nums[i] <= 10000

思路

  • 标签：双指针
  • 整体思路：首先指定前指针 start 和后指针 end，然后前指针定位偶数，后指针定位奇数，定位到之后将两个值互换，直到数组遍历完成
  • 时间复杂度：O(n)，空间复杂度：O(1)

算法流程

  • 初始化前指针 start = 0，后指针 end = nums.length - 1
  • 当 start < end 时表示该数组还未遍历完成，则继续进行奇数和偶数的交换
  • 当 nums[start] 为奇数时，则 start++，直到找到不为奇数的下标为止
  • 当 nums[end] 为偶数时，则 end--，直到找到不为偶数的下标为止
  • 交换 nums[start] 和 nums[end]，继续下一轮交换
  • 返回 nums，即为交换后的结果
class Solution {
    public int[] exchange(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        
        while(start < end) {
            while(start < end && !isEven(start))
                start++;
            
            while(start < end && isEven(end)) 
                end--;
            
            swap(nums, start, end);
        }
        return nums;
    }
    
    private boolean isEven(int x) {
    	return x % 2 == 0;
	}
    
    private void swap(int[] nums, int start, int end) {
        int tmp = nums[start];
        nums[start] = nums[end];
        nums[end] = tmp;
    }
}
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

# 剑指 Offer 29. 顺时针打印矩阵

题目描述

按顺时针的方向，从外到里打印矩阵的值。下图的矩阵打印结果为：1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10



解题思路

  • 标签：二维数组
  • 整体思路：循环遍历整个数组，循环中再嵌套四个循环，分别是从左至右，从上至下，从右至左，从下至上这几个方向，按照题意将整个数组遍历完成，控制好边界
  • mm 为行数，nn 为列数，时间复杂度：O(mn)，空间复杂度：O(1)

  • 题目中 matrix 有可能为空，直接返回空数组即可
  • 初始化边界 left、right、top、bottom 四个值，初始化结果数组 res 和数组下标 x
  • 按照遍历方向循环取出数字放入结果数组中
  • 从左至右：遍历完成后 ++top，如果 top > bottom，到达边界循环结束
  • 从上至下：遍历完成后 --right，如果 left > right，到达边界循环结束
  • 从右至左：遍历完成后 --bottom，如果 top > bottom，到达边界循环结束
  • 从下至上：遍历完成后 ++left，如果 left > right，到达边界循环结束
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int left = 0, right = matrix[0].length - 1, top = 0, bottom = matrix.length - 1, x = 0;
        int[] res = new int[(right + 1) * (bottom + 1)];
        while(true) {
            for(int i = left; i <= right; i++) res[x++] = matrix[top][i];
            if(++top > bottom) break;
            for(int i = top; i <= bottom; i++) res[x++] = matrix[i][right];
            if(left > --right) break;
            for(int i = right; i >= left; i--) res[x++] = matrix[bottom][i];
            if(top > --bottom) break;
            for(int i = bottom; i >= top; i--) res[x++] = matrix[i][left];
            if(++left > right) break;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

或者：

一层一层从外到里打印，观察可知每一层打印都有相同的处理步骤，唯一不同的是上下左右的边界不同了。因此使用四个变量 r1, r2, c1, c2 分别存储上下左右边界值，从而定义当前最外层。打印当前最外层的顺序：从左到右打印最上一行->从上到下打印最右一行->从右到左打印最下一行->从下到上打印最左一行。应当注意只有在 r1 != r2 时才打印最下一行，也就是在当前最外层的行数大于 1 时才打印最下一行，这是因为当前最外层只有一行时，继续打印最下一行，会导致重复打印。打印最左一行也要做同样处理。


public ArrayList<Integer> printMatrix(int[][] matrix) {
    ArrayList<Integer> ret = new ArrayList<>();
    int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;
    while (r1 <= r2 && c1 <= c2) {
        // 上
        for (int i = c1; i <= c2; i++)
            ret.add(matrix[r1][i]);
        // 右
        for (int i = r1 + 1; i <= r2; i++)
            ret.add(matrix[i][c2]);
        if (r1 != r2)
            // 下
            for (int i = c2 - 1; i >= c1; i--)
                ret.add(matrix[r2][i]);
        if (c1 != c2)
            // 左
            for (int i = r2 - 1; i > r1; i--)
                ret.add(matrix[i][c1]);
        r1++; r2--; c1++; c2--;
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 剑指 Offer 39. 数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
1
2

限制：

1 <= 数组长度 <= 50000


思路

  • 标签：摩尔投票
  • 本题常见解法共有 3 种
    • 数组排序：首先将 nums 排序，由于该数字超过数组长度的一半，所以数组的中间元素就是答案，时间复杂度为 O(nlogn)
    • 哈希计数：遍历 nums 数组，将数字存在 HashMap 中，统计数字出现次数，统计完成后再遍历一次 HashMap，找到超过一半计数的数字，时间复杂度为 O(n)
    • 摩尔投票：遍历 nums 数组，使用 count 进行计数，记录当前出现的数字为 cur，如果遍历到的 num 与 cur 相等，则 count 自增，否则自减，当其减为 0 时则将 cur 修改为当前遍历的 num，通过增减抵消的方式，最终达到剩下的数字是结果的效果，时间复杂度为 O(n)O(n)
  • 摩尔投票是最优解法，时间复杂度：O(n)，空间复杂度：O(1)

算法流程

  • 初始化：预期结果 cur = 0 和计数器 count = 0
  • 遍历数组 nums，遍历过程中取到的数字为 num
  • 当 count 为 0 时，表示不同的数字已经将当前的结果抵消掉了，可以换新的数字进行尝试，则 cur = num
  • 当 num == cur 时，表示遍历数字和预期结果相同，则计数器 count++
  • 当 num != cur 时，表示遍历数字和预期结果不同，则计数器 count--
  • 最终留下的数字 cur 就是最终的结果，出现次数超过一半的数字一定不会被抵消掉，最终得到了留存
class Solution {
    public int majorityElement(int[] nums) {
        int cur = 0;
        int count = 0;
        for(int num : nums){
            if(count == 0) {
                cur = num;
            }
            if(num == cur) {
                count++;
            } else {
                count--;
            }
        }
        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 剑指 Offer 45. 把数组排成最小的数

题目描述

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"
1
2

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"
1
2

提示:

0 < nums.length <= 100

说明:

  • 输出结果可能非常大，所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

思路

  • 标签：排序

  • 整体思路：

    • 拼接数组内所有元素使结果最小，本质上是排序
    • 若字符串拼接 a + b > b + a，那么排序上 b < a;
    • 根据这个规则对数组内的元素排序

  • 复杂度：

    • 时间复杂度：O(n log n)。 n 为 strList 列表长度，使用 java 内置函数的平均时间复杂度为 O(n log n) ， 最差为O(n log n)
    • 空间复杂度：O(n)： 字符串列表 strList 占用线性大小的额外空间。

算法流程

  • 将数组内的元素存入字符串列表 strList
  • 根据上述排序规则，对列表进行排序
  • 最后返回拼接的字符串
class Solution {
    public String minNumber(int[] nums) {
        List<String> strList = new ArrayList<>();
        for (int num : nums) {
            strList.add(String.valueOf(num));
        }
        strList.sort((a, b) -> (a + b).compareTo(b + a));
        StringBuilder sb = new StringBuilder();
        for (String str : strList) {
            sb.append(str);
        }
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

或：

  • 快速排序
class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        quickSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
    void quickSort(String[] strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        quickSort(strs, l, i - 1);
        quickSort(strs, i + 1, r);
    }
}
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

# 剑指 Offer 50. 第一个只出现一次的字符

题目描述

在一个字符串中找到第一个只出现一次的字符，并返回它的位置。字符串只包含 ASCII 码字符。

Input: abacc
Output: b
1
2

解题思路

最直观的解法是使用 HashMap 对出现次数进行统计：字符做为 key，出现次数作为 value，遍历字符串每次都将 key 对应的 value 加 1。最后再遍历这个 HashMap 就可以找出出现次数为 1 的字符。

考虑到要统计的字符范围有限，也可以使用整型数组代替 HashMap。ASCII 码只有 128 个字符，因此可以使用长度为 128 的整型数组来存储每个字符出现的次数。

public int FirstNotRepeatingChar(String str) {
    int[] cnts = new int[128];
    for (int i = 0; i < str.length(); i++)
        cnts[str.charAt(i)]++;
    for (int i = 0; i < str.length(); i++)
        if (cnts[str.charAt(i)] == 1)
            return i;
    return -1;
}
1
2
3
4
5
6
7
8
9

# 剑指 Offer 53 - I. 在排序数组中查找数字 I

题目描述

  • 统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
1
2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
1
2

限制：

0 <= 数组长度 <= 50000


思路

  • 标签：数组、二分查找
  • 整体思路：
    • 因为数组本身是有序的，所以利用二分查找可以降低时间复杂度，但是因为数组中的数字存在重复，所以找到 target 在数组中对应的左右边界非常重要
    • 容易想到的方式就是分别用二分查找的方式去查找 target 在数组的左边界和右边界，然后将右边界减左边界即可得到结果
    • 分别查找 target 左边界和右边界的逻辑会有差异，这里可以取巧，变成分别查找 target-1 的右边界和 target 的右边界，结果是一样的，但是代码可以进行复用了
  • 复杂度：
    • 时间复杂度：O(logn)。二分查找的时间复杂度是O(logn)
    • 空间复杂度：O(1)。只需要保存左右边界和中间值即可

算法流程

  • 首先初始化二分查找的左边界left = 0，右边界right = nums.length - 1
  • 当左边界不大于右边界时进行查找
  • 计算 mid = (left + right) / 2
  • 如果 nums[mid] <= target，则右边界在 [mid + 1, right] 中间，令 left = mid + 1
  • 如果 nums[mid] > target，则右边界在 [left, mid - 1] 中间，令 right = mid - 1
  • 如果mid与target相等，left还是会右移的，会一直移动到刚好大于target的位置，也就是最后一个target之后，而当查找target-1，找到了新的left会在target-1之后位置也就是第一个target，两个位置相减就行，而如果没有找到，left跳出循环时，依然指向target第一个位置，所以循环体中那个等号的理解是关键
class Solution {
    public int search(int[] nums, int target) {
        return getRightMargin(nums, target) - getRightMargin(nums, target - 1);
    }
    int getRightMargin(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 剑指 Offer 53 - II. 0～n-1 中缺失的数字

题目描述

  • 一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0～n-1 之内。在范围 0～n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2
1
2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8
1
2

限制：

1 <= 数组长度 <= 10000


思路

  • 标签：数组、二分查找
  • 整体思路：
    • 缺失的数字等于 “右子数组的首位元素” 对应的索引，因此考虑使用二分法查找 “右子数组的首位元素”。
    • 左子数组： nums[i] == i
    • 右子数组： nums[i] != i
  • 复杂度：
    • 时间复杂度：O(logn)
    • 空间复杂度：O(1)

算法流程

  • 首先初始化二分查找的左边界 left = 0，右边界 right = nums.length - 1
  • 当左边界不大于右边界时进行查找
  • 计算 mid = (left + right) / 2
  • 如果 nums[mid] == mid 则缺失的元素，即右子数组的首位元素在 [mid + 1, right] 中间，令 left = mid + 1
  • 如果 nums[mid] != mid 则缺失的元素，即右子数组的首位元素在 [left, mid] 中间，令 right = mid - 1
class Solution {
    public int missingNumber(int[] nums) {
        int left = 0; 
        int right = nums.length - 1; 
        while (left <= right) {
            int middle = (left + right) / 2 ; 
            if (nums[middle] == middle) 
                left = middle + 1; 
            else 
                right = middle - 1; 
        }

        return left; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 剑指 Offer 57 - I. 和为 s 的两个数字

题目描述

  • 输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
1
2

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
1
2

限制：

1 <= nums.length <= 10^5

1 <= nums[i] <= 10^6


思路

  • 标签：双指针
  • 整体思路：因为数组本身是有序的，那么完全可以在数组的开头 start 和结尾 end 位置各设置一个指针，通过二者的加和 sum 来找到目标值 target，如果 sum < target，则 start++，这样可以让下一次的 sum 变大，如果 sum > target，则 end--，这样可以让下一次的 sum 变小，找到结果
  • 时间复杂度：O(n)，空间复杂度：O(1)

算法流程

  • 首先初始化 start = 0，end = nums.length - 1，作为双指针
  • 当 start < end 时，始终进行循环遍历
  • 计算 sum = nums[start] + nums[end]，并将 sum 与 target 进行比较
  • 如果 sum < target，则需要将下一次的 sum 值变大，因为数组有序，故而 start++
  • 如果 sum > target，则需要将下一次的 sum 值变小，因为数组有序，故而 end--
  • 如果 sum == target，则找到了最终的结果，将结果返回即可
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while(start < end) {
            int sum = nums[start] + nums[end];
            if(sum < target) {
                start++;
            } else if(sum > target) {
                end--;
            } else {
                return new int[] { nums[start], nums[end] };
            }
        }
        return new int[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

或：

用 Hash Map

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums.length == 0) 
            return new int[0];

        HashMap <Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(target - num)) {
                return new int[] {num, target - num};
            } else {
                map.put(num, num);
            }
        }

        return new int[0]; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 剑指 Offer 57 - II. 和为 s 的连续正数序列

题目描述

  • 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

  • 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

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

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
1
2

限制：

1 <= target <= 10^5


思路

  • 标签：滑动窗口、指针
  • 整体思路：
    • 最容易想到的思路就是暴力枚举，因为题目条件要求至少含有两个数，所以枚举到 target/2 即可停止，时间复杂度较高
    • 更好的方式是使用滑动窗口，设立左右指针，从开始位置维护一个子数组作为窗口，判断该窗口是否求和为 target，如果是则将结果加入，如果小于 target 则窗口右移，大于 target 则窗口左移
  • 复杂度：
    • 时间复杂度：O(target)。滑动窗口最多移动 target/2 次
    • 空间复杂度：O(1)。排除必要的存储结果数组之外，只需要保存左右指针

算法流程

  • 首先初始化窗口，left=1 和 right=2
  • 当 left < right 时始终维护该窗口，只有当到达边界位置时，窗口和 sum > target，left 始终右移，才会结束窗口维护
  • 根据求和公式 sum = (left + right) * (right - left + 1) / 2sum=(left+right)∗(right−left+1)/2 可以直接算出滑动窗口和
  • 当 sum == target 时，将窗口放入结果数组中
  • 当 sum < target 时，说明窗口结果需要变大，right++
  • 当 sum > target 时，说明窗口结果需要变小，left++
class Solution {
    public int[][] findContinuousSequence(int target) {
        int left = 1;
        int right = 2;
        ArrayList<int[]> res = new ArrayList<>();

        while (left < right) {
            int sum = (left + right) * (right - left + 1) / 2;
            if (sum == target){
                int[] arr = new int[right - left + 1];
                for (int k = left; k <= right; k++) {
                    arr[k - left] = k;
                }
                res.add(arr);
                left++;
            }
            else if (sum < target) {
                right++;
            }
            else {
                left++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}
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

# 剑指 Offer 61. 扑克牌中的顺子

题目描述

  • 从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True
1
2

示例 2:

输入: [0,0,1,2,5]
输出: True
1
2

限制：

  • 数组长度为 5

  • 数组的数取值为 [0, 13] .


思路

  • 标签：数组
  • 整体思路：
    • 需要对数组升序排序
    • 如果数组中有重复数据，则返回 false
    • 令 minVal 为不包含大小王的最小值，如果 maxVal-minVal > 5，则返回 false
  • 复杂度：
    • 时间复杂度 O(Nlog N)
    • 空间复杂度 O(1)

算法流程

  • 顺子牌的定义
    • 牌数量为 5
    • 牌间的顺序为递增，且差值为 1
    • 牌间不可以有重复数据，（大小王除外）。（扑克牌术语：如果一副牌里含有对子，则不可能是顺子）
    • 大小王可以作为任意牌，即可以作为牌间空隙插入。且数量不限
    • 牌之间的空隙个数为，maxVal-minVal
    • 由于牌数量为 5，所以 maxVal-minVal <= 5
class Solution {
    public boolean isStraight(int[] nums) {
        int len = nums.length;
        if (len != 5)
            return false;

        int jkcnt = 0;
        Arrays.sort(nums);
        
        for (int i = 0; i < len; i++) {
            // 先判断，同时防止数组溢出
            if (nums[i] != 0 && i != len - 1) 
                if (nums[i] == nums[i+1]) 
                    return false;
            // 统计0的个数
            if (nums[i] == 0) {
                jkcnt++;
            }
            
        }

        return nums[len - 1] - nums[jkcnt] < 5;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

或：

  • 其实没有必要搞排序，而且轻松击败100%，只要满足两个条件即可，

    1. 数组除0外的数最大值最小值差值必须在4以及4以内。

    2. 除0以外的数保证不重复

  • 反向思维，0既然可以代替任何数，那就别考虑它，考虑其他数，如果其他数最大最小差值大于4，那么有再多0也没用，如 1，0，0，3，6；

  • 0既然可以代替任何值，那么无所谓，但是还要保证其他数不能重复，如0，0，1，1，3，这就不行了，

  • 保证最大最小小于等于4，依次遍历即可（记住要除了0）

  • 保证除0以外不重复，因为才5个数，而且5个数还有范围限制，直接来个标记数组即可，这样就轻松击败100%

  • 代码中min初始化最低14，也可以15，。。。随便，只要不是小于扑克牌中最大值13即可

public boolean isStraight(int[] nums) {
    int min = 14,max = 0;
    for(int i = 0; i < 5;i++){
        if(nums[i] > max)max = nums[i];
        if(nums[i] != 0 && nums[i] < min) min = nums[i];
    }
    if(max - min > 4) return false;
    
    // 标记数组，因为一个非零数字应该只出现一次，所以用 boolean value 标记这个数组是否出现过
    boolean[] flag = new boolean[5];
    
    for(int i = 0; i < 5; i++){
        if (nums[i] != 0) {
            if (flag[nums[i] - min] == false)
                flag[nums[i] - min] = true;
            else
                return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 剑指 Offer 66. 构建乘积数组

题目描述

  • 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
1
2

提示：

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

思路

  • 标签：数组遍历
  • 整体思路：
    • 这道题如果可以使用除法，那么就很简单了，先求出来所有数的乘积，然后再依次除掉每个对应的值即可
    • 不让使用除法，那么最简单的思路就是将B[i]每个位置都把所有需要的数乘一遍，但是这样的时间复杂度非常高
    • 降低时间复杂度的方式就是以A[i]为界线，分割出左右三角形，其中每个三角形从尖部到底部都是可以累积的，这样就可以减少时间复杂度（具体见画）
  • 复杂度：
    • 时间复杂度：O(n)。因为左右三角遍历求乘积的时间复杂度都是O(n)O(n)
    • 空间复杂度：O(1)。不将结果数组算入的话，只需要常量的空间复杂度

算法流程

  • 首先申请结果数组 res
  • 求出左侧三角从上到下的值，依次存入 res[i] 中
  • 求出右侧三角从下到上的值，并且和之前的 res[i] 做乘积存入，即可得到结果
image-20211207100608721 
class Solution {
    public int[] constructArr(int[] a) {
        int[] res = new int[a.length];
        int left = 1;
        // left 最多是 1 * 2 * 3 * 4
        for (int i = 0; i < a.length; i++) {
            res[i] = left;
            left *= a[i];
        } 
        
        // right 反向操作， 5 * 4 * 3 * 2
        int right = 1;
        for (int i = a.length - 1; i >= 0; i--) {
            res[i] *= right;
            right *= a[i];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 1. 把数组中的 0 移到末尾

283. Move Zeroes (Easy)

Leetcode (opens new window) / 力扣 (opens new window)

For example, given nums = [0, 1, 0, 3, 12], 
after calling your function, nums should be [1, 3, 12, 0, 0].
1
2
public void moveZeroes(int[] nums) {
    int idx = 0; // 记录非零数字的个数
    for (int num : nums)
        if (num != 0)
            nums[idx++] = num;

    while (idx < nums.length)
        nums[idx++] = 0;
}
1
2
3
4
5
6
7
8
9

双指针：

  • 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
  • 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
  • 注意到以下性质：
    • 左指针左边均为非零数；
    • 右指针左边直到左指针处均为零。
    • 因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right); // 将左指针的零与右指针的非零数交换
                left++; // 左指针左边均为非零数, 左指针自己也指向零
            }
            right++; 	// 右指针左边直到左指针处均为零
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 2. 改变矩阵维度

566. Reshape the Matrix (Easy)

Leetcode (opens new window) / 力扣 (opens new window)

Input:
nums =[[1,2],[3,4]]
r = 1, c = 4

Output:
[[1,2,3,4]]

Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
1
2
3
4
5
6
7
8
9
public int[][] matrixReshape(int[][] nums, int r, int c) {
    int m = nums.length, n = nums[0].length;
    if (m * n != r * c) {
        return nums;
    }
    int[][] reshapedNums = new int[r][c];
    int index = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            reshapedNums[i][j] = nums[index / n][index % n];
            index++;
        }
    }
    return reshapedNums;
}

// or 
public int[][] matrixReshape(int[][] nums, int r, int c) {
    int m = nums.length;
    int n = nums[0].length;
    if (m * n != r * c) {
        return nums;
    }

    int[][] ans = new int[r][c];
    for (int x = 0; x < m * n; x++) {
        ans[x / c][x % c] = nums[x / n][x % n];
    }
    return ans;
}
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

# 3. 找出数组中最长的连续 1

485. Max Consecutive Ones (Easy)

Leetcode (opens new window) / 力扣 (opens new window)

public int findMaxConsecutiveOnes(int[] nums) {
    int count = 0;
    int max = 0; 
    for (int i = 0; i < nums.length; i++) {
        count = nums[i] == 1 ? count + 1 : 0;
        max = Math.max(max, count);
    }

    return max; 
}
1
2
3
4
5
6
7
8
9
10

# 4. 有序矩阵查找

240. Search a 2D Matrix II (Medium)

Leetcode (opens new window) / 力扣 (opens new window)

[
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
]
1
2
3
4
5
public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    
    int m = matrix.length, n = matrix[0].length;
    int row = 0, col = n - 1;
    
    while (row < m && col >= 0) {
        if (target == matrix[row][col]) return true;
        else if (target < matrix[row][col]) col--;
        else row++;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 5. 有序矩阵的 Kth Element

378. Kth Smallest Element in a Sorted Matrix ((Medium))

Leetcode (opens new window) / 力扣 (opens new window)

matrix = [
  [ 1,  5,  9],
  [10, 11, 13],
  [12, 13, 15]
],
k = 8,

return 13.
1
2
3
4
5
6
7
8

解题参考：Share my thoughts and Clean Java Code (opens new window)

二分查找解法 （有待优化）：

public int kthSmallest(int[][] matrix, int k) {
    int m = matrix.length;
    int n = matrix[0].length;
    int lo = matrix[0][0];
    int hi = matrix[m - 1][n - 1];
    
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int cnt = 0;
        
        // count 比 mid 小的 int 的数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
                cnt++;
            }
        }
        if (cnt < k) 
            lo = mid + 1;
        else 
            hi = mid - 1;
    }
    return lo;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

归并合集：

  • 由题目给出的性质可知，这个矩阵的每一行均为一个有序数组
  • 问题即转化为从这 n 个有序数组中找第 k 大的数，可以想到利用归并排序的做法，归并到第 k 个数即可停止。
  • 一般归并排序是两个数组归并，而本题是 n 个数组归并，所以需要用小根堆维护，以优化时间复杂度。
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        int n = matrix.length;
        
        for (int i = 0; i < n; i++)
            pq.offer(new int[]{matrix[i][0], i, 0});
        
        // 小根堆，去掉 k - 1 个堆顶元素，此时堆顶元素就是第 k 的数
        for (int i = 0; i < k - 1; i++) {
            int[] now = pq.poll();
            int row = now[1];
            int col = now[2] + 1;
            if (now[2] != n - 1)
                pq.offer(new int[]{matrix[row][col], row, col});
        }
        return pq.poll()[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 6. 一个数组元素在 [1, n] 之间，其中一个数被替换为另一个数，找出重复的数和丢失的数

645. Set Mismatch (Easy)

Leetcode (opens new window) / 力扣 (opens new window)

Input: nums = [1,2,2,4]
Output: [2,3]
1
2

最直接的方法是先对数组进行排序，这种方法时间复杂度为 O(NlogN)。本题可以以 O(N) 的时间复杂度、O(1) 空间复杂度来求解。

主要思想是通过交换数组元素，使得数组上的元素在正确的位置上。

因为值的范围在 [1,n]，我们可以运用「桶排序」的思路，根据 nums[i] = i + 1 的对应关系使用 O(n) 的复杂度将每个数放在其应该落在的位置里。

然后线性扫描一遍排好序的数组，找到不符合 nums[i] = i + 1 对应关系的位置，从而确定重复元素和缺失元素是哪个值。

public int[] findErrorNums(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 因为数组里有重复的数字，所以第二个得判断他 nums[nums[i] - 1] 和  nums[i] 是不是同一个数字，如果是，就没必要换
        while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
            swap(nums, i, nums[i] - 1);
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            return new int[]{nums[i], i + 1};
        }
    }
    return null;
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

哈希表

  • 重复的数字在数组中出现 2 次，丢失的数字在数组中出现 0 次，其余的每个数字在数组中出现 1 次。因此可以使用哈希表记录每个元素在数组中出现的次数，然后遍历从 1 到 nn 的每个数字，分别找到出现 2 次和出现 0 次的数字，即为重复的数字和丢失的数字。
class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] errorNums = new int[2];
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int i = 1; i <= n; i++) {
            int count = map.getOrDefault(i, 0);
            if (count == 2) {
                errorNums[0] = i;
            } else if (count == 0) {
                errorNums[1] = i;
            }
        }
        return errorNums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  • 一个朴素的做法是，使用「哈希表」统计每个元素出现次数，然后在 [1,n] 查询每个元素的出现次数。
  • 在「哈希表」中出现 22 次的为重复元素，未在「哈希表」中出现的元素为缺失元素。
  • 由于这里数的范围确定为 [1,n]，我们可以使用数组来充当「哈希表」，以减少「哈希表」的哈希函数执行和冲突扩容的时间开销。
class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] cnts = new int[n + 1];
        for (int x : nums) cnts[x]++;
        int[] ans = new int[2];
        for (int i = 1; i <= n; i++) {
            if (cnts[i] == 0) ans[1] = i;
            if (cnts[i] == 2) ans[0] = i;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 7. 找出数组中重复的数，数组值在 [1, n] 之间

287. Find the Duplicate Number (Medium)

Leetcode (opens new window) / 力扣 (opens new window)

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

  • 如何证明 nums 中至少存在一个重复的数字?

  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

  • 二分查找解法：

public int findDuplicate(int[] nums) {
     int l = 1, h = nums.length - 1;
     while (l <= h) {
         int mid = l + (h - l) / 2;
         int cnt = 0;
         for (int i = 0; i < nums.length; i++) {
             if (nums[i] <= mid) cnt++;
         }
         if (cnt > mid) h = mid - 1;
         else l = mid + 1;
     }
     return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

双指针解法，类似于有环链表中找出环的入口：

public int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[nums[0]];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    fast = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 8. 数组相邻差值的个数

667. Beautiful Arrangement II (Medium)

Leetcode (opens new window) / 力扣 (opens new window)

Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
1
2
3

题目描述：数组元素为 1~n 的整数，要求构建数组，使得相邻元素的差值不相同的个数为 k。

让前 k+1 个元素构建出 k 个不相同的差值，序列为：1 k+1 2 k 3 k-1 ... k/2 k/2+1.

public int[] constructArray(int n, int k) {
    int[] ret = new int[n];
    ret[0] = 1;
    for (int i = 1, interval = k; i <= k; i++, interval--) {
        ret[i] = i % 2 == 1 ? ret[i - 1] + interval : ret[i - 1] - interval;
    }
    for (int i = k + 1; i < n; i++) {
        ret[i] = i + 1;
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11

# 9. 数组的度

697. Degree of an Array (Easy)

Leetcode (opens new window) / 力扣 (opens new window)

Input: [1,2,2,3,1,4,2]
Output: 6
1
2

题目描述：数组的度定义为元素出现的最高频率，例如上面的数组度为 3。要求找到一个最小的子数组，这个子数组的度和原数组一样。

public int findShortestSubArray(int[] nums) {
    Map<Integer, Integer> numsCnt = new HashMap<>();
    Map<Integer, Integer> numsLastIndex = new HashMap<>();
    Map<Integer, Integer> numsFirstIndex = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        numsCnt.put(num, numsCnt.getOrDefault(num, 0) + 1);
        numsLastIndex.put(num, i);
        if (!numsFirstIndex.containsKey(num)) {
            numsFirstIndex.put(num, i);
        }
    }
    int maxCnt = 0;
    for (int num : nums) {
        maxCnt = Math.max(maxCnt, numsCnt.get(num));
    }
    int ret = nums.length;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        int cnt = numsCnt.get(num);
        if (cnt != maxCnt) continue;
        ret = Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);
    }
    return ret;
}
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

# 10. 对角元素相等的矩阵

766. Toeplitz Matrix (Easy)

Leetcode (opens new window) / 力扣 (opens new window)

1234
5123
9512

In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.
1
2
3
4
5
public boolean isToeplitzMatrix(int[][] matrix) {
    for (int i = 0; i < matrix[0].length; i++) {
        if (!check(matrix, matrix[0][i], 0, i)) {
            return false;
        }
    }
    for (int i = 0; i < matrix.length; i++) {
        if (!check(matrix, matrix[i][0], i, 0)) {
            return false;
        }
    }
    return true;
}

private boolean check(int[][] matrix, int expectValue, int row, int col) {
    if (row >= matrix.length || col >= matrix[0].length) {
        return true;
    }
    if (matrix[row][col] != expectValue) {
        return false;
    }
    return check(matrix, expectValue, row + 1, col + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 11. 嵌套数组

565. Array Nesting (Medium)

Leetcode (opens new window) / 力扣 (opens new window)

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
1
2
3
4
5
6
7

题目描述：S[i] 表示一个集合，集合的第一个元素是 A[i]，第二个元素是 A[A[i]]，如此嵌套下去。求最大的 S[i]。

public int arrayNesting(int[] nums) {
    int max = 0;
    for (int i = 0; i < nums.length; i++) {
        int cnt = 0;
        for (int j = i; nums[j] != -1; ) {
            cnt++;
            int t = nums[j];
            nums[j] = -1; // 标记该位置已经被访问
            j = t;

        }
        max = Math.max(max, cnt);
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 12. 分隔数组

769. Max Chunks To Make Sorted (Medium)

Leetcode (opens new window) / 力扣 (opens new window)

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
1
2
3
4
5

题目描述：分隔数组，使得对每部分排序后数组就为有序。

public int maxChunksToSorted(int[] arr) {
    if (arr == null) return 0;
    int ret = 0;
    int right = arr[0];
    for (int i = 0; i < arr.length; i++) {
        right = Math.max(right, arr[i]);
        if (right == i) ret++;
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10

# 01. 删除排序数组中的重复项

给你一个有序数组 nums ，请你 原地 (opens new window) 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

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

说明:

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

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

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

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

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

示例 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 。不需要考虑数组中超出新长度后面的元素。

提示：

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

解题思路

因为数组是排序的，只要是相同的肯定是挨着的，我们只需要遍历所有数组，然后前后两两比较，如果有相同的就把后面的给删除。

双指针解决

使用两个指针，右指针始终往右移动，

  • 如果右指针指向的值等于左指针指向的值，左指针不动。
  • 如果右指针指向的值不等于左指针指向的值，那么左指针往右移一步，然后再把右指针指向的值赋给左指针。
class Solution {
    //双指针解决
    public int removeDuplicates(int[] A) {
        //边界条件判断
        if (A == null || A.length == 0)
            return 0;

        int left = 0;
        
        for (int right = 1; right < A.length; right++)
            //如果左指针和右指针指向的值一样，说明有重复的，
            //这个时候，左指针不动，右指针继续往右移。如果他俩
            //指向的值不一样就把右指针指向的值往前挪
            if (A[left] != A[right])
                A[++left] = A[right];
        return ++left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 02. 买卖股票的最佳时机 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 。

示例 2:

输入: prices = [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

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

提示：

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

解题思路

动态规划解决

定义dp[i][0]表示第i+1天交易完之后手里没有股票的最大利润，dp[i][1]表示第i+1天交易完之后手里持有股票的最大利润。

当天交易完之后手里没有股票可能有两种情况，一种是当天没有进行任何交易，又因为当天手里没有股票，所以当天没有股票的利润只能取前一天手里没有股票的利润。一种是把当天手里的股票给卖了，既然能卖，说明手里是有股票的，所以这个时候当天没有股票的利润要取前一天手里有股票的利润加上当天股票能卖的价格。这两种情况我们取利润最大的即可，所以可以得到

dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);

当天交易完之后手里持有股票也有两种情况，一种是当天没有任何交易，又因为当天手里持有股票，所以当天手里持有的股票其实前一天就已经持有了。还一种是当天买入了股票，当天能买股票，说明前一天手里肯定是没有股票的，我们取这两者的最大值，所以可以得到

dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);

动态规划的递推公式有了，那么边界条件是什么，就是第一天

如果买入：dp[0][1]=-prices[0];

如果没买：dp[0][0]=0;

有了递推公式和边界条件，代码很容易就写出来了。

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2)
        return 0;
    int length = prices.length;
    int[][] dp = new int[length][2];
    //初始条件
    dp[0][1] = -prices[0];
    dp[0][0] = 0;
    for (int i = 1; i < length; i++) {
        //递推公式
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    //最后一天肯定是手里没有股票的时候，利润才会最大，
    //只需要返回dp[length - 1][0]即可
    return dp[length - 1][0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

代码优化

上面计算的时候我们看到当天的利润只和前一天有关，没必要使用一个二维数组，只需要使用两个变量，一个记录当天交易完之后手里持有股票的最大利润，一个记录当天交易完之后手里没有股票的最大利润，来看下代码

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2)
        return 0;
    int length = prices.length;
    //初始条件
    int hold = -prices[0];//持有股票
    int noHold = 0;//没持有股票
    for (int i = 1; i < length; i++) {
        //递推公式转化的
        noHold = Math.max(noHold, hold + prices[i]);
        hold = Math.max(hold, noHold - prices[i]);
    }
    //最后一天肯定是手里没有股票的时候利润才会最大，
    //所以这里返回的是noHold
    return noHold;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

贪心算法解决

下面我随便画了一个股票的曲线图，可以看到如果股票一直上涨，只需要找到股票上涨的最大值和股票开始上涨的最小值，计算他们的差就是这段时间内股票的最大利润。如果股票下跌就不用计算，最终只需要把所有股票上涨的时间段内的利润累加就是我们所要求的结果

image.png

来看下代码

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2)
        return 0;
    int total = 0, index = 0, length = prices.length;
    while (index < length) {
        //如果股票下跌就一直找，直到找到股票开始上涨为止
        while (index < length - 1 && prices[index] >= prices[index + 1])
            index++;
        //股票上涨开始的值，也就是这段时间上涨的最小值
        int min = prices[index];
        //一直找到股票上涨的最大值为止
        while (index < length - 1 && prices[index] <= prices[index + 1])
            index++;
        //计算这段上涨时间的差值，然后累加
        total += prices[index++] - min;
    }
    return total;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

来看下运行结果
image.png

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

那么这道题使用贪心算法也是最容易解决的，只要是上涨的我们就要计算他们的差值进行累加，不需要再找开始上涨的最小值和最大值。为什么能这样计算，我举个例子。

比如a<b<c<d，因为从a到d一直是上涨的，那么最大值和最小值的差值就是d-a，也可以写成(b-a)+(c-b)+(d-c)，搞懂了这个公式所有的一切都明白了。如果还不明白，可以想象成数组中前一个值减去后一个值，构成一个新的数组，我们只需要计算这个新数组中正数的和即可，这里以示例1为例画个图看下

image.png

这里只需要计算新数组中正数的和，也就是4+3=7。这个时候代码就已经非常简化了，我们来看下

public int maxProfit(int[] prices) {
    int total = 0;
    for (int i = 0; i < prices.length - 1; i++) {
        //原数组中如果后一个减去前一个是正数，说明是上涨的，
        //我们就要累加，否则就不累加
        total += Math.max(prices[i + 1] - prices[i], 0);
    }
    return total;
}
1
2
3
4
5
6
7
8
9

# 03. 旋转数组

给你一个数组，将数组中的元素向右轮转 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

进阶：

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

解题思路

使用临时数组

可以使用一个临时数组，先把原数组的值存放到一个临时数组中，然后再把临时数组的值重新赋给原数组，重新赋值的时候要保证每个元素都要往后移k位，如果超过数组的长度就从头开始，所以这里可以使用(i + k) % length来计算重新赋值的元素下标

public void rotate(int nums[], int k) {
    int length = nums.length;
    int temp[] = new int[length];
    //把原数组值放到一个临时数组中，
    for (int i = 0; i < length; i++) {
        temp[i] = nums[i];
    }
    //然后在把临时数组的值重新放到原数组，并且往右移动k位
    for (int i = 0; i < length; i++) {
        nums[(i + k) % length] = temp[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

多次反转

先反转全部数组，在反转前k个，最后在反转剩余的，如下所示

public void rotate(int[] nums, int k) {
    int length = nums.length;
    k %= length;
    reverse(nums, 0, length - 1);//先反转全部的元素
    reverse(nums, 0, k - 1);//在反转前k个元素
    reverse(nums, k, length - 1);//接着反转剩余的
}

//把数组中从[start，end]之间的元素两两交换,也就是反转
public void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start++] = nums[end];
        nums[end--] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 04. 存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: [1,2,3,1] 输出: true

示例 2:

输入: [1,2,3,4] 输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2] 输出: true


解题思路

首先这题最容易想到的是暴力求解，但暴力求解效率很低，直接超时

public boolean containsDuplicate(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10

我们可以先对数组进行排序，然后再比较。因为排序之后如果有相同的，那么相同的值肯定是挨着的，我们只需要在排序之后两两比较即可。代码如下

public boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int ind = 1; ind < nums.length; ind++) {
        if (nums[ind] == nums[ind - 1]) {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9

使用set集合

我们知道set集合中的元素是不能有重复的，在添加的时候如果有重复的，会把之前的值给覆盖，并且返回false。我们遍历数组中的所有值，一个个添加到集合set中，在添加的时候如果返回false，就表示有重复的，直接返回true。

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        //因为集合set中不能有重复的元素，如果有重复的
        //元素添加，就会添加失败
        if (!set.add(num))
            return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10

# 05. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1] 输出: 1

示例 2:

输入: [4,1,2,1,2] 输出: 4


解题思路

位运算解决

这题说的是只有一个数出现了一次，其他数字都出现了2次，让我们求这个只出现一次的数字。这题使用位运算是最容易解决的，关于位运算有下面几个规律

1^1=0;

1^0=1;

0^1=1;

0^0=0;

也就说0和1异或的时候相同的异或结果为0，不同的异或结果为1，根据上面的规律我们得到

a^a=0；自己和自己异或等于0

a^0=a；任何数字和0异或还等于他自己

a^b^c=a^c^b；异或运算具有交换律

有了这3个规律，这题就很容易解了，我们只需要把所有的数字都异或一遍，最终的结果就是我们要求的那个数字。来看下代码

public int singleNumber(int nums[]) {
    int result = 0;
    for (int i = 0; i < nums.length; i++)
        result ^= nums[i];
    return result;
}
1
2
3
4
5
6

使用集合Set解决 这个应该是最容易想到的，我们遍历数组中的元素，然后在一个个添加到集合Set中，如果添加失败，说明以前添加过，就把他给移除掉。当我们把数组中的所有元素都遍历完的时候，集合Set中只会有一个元素，这个就是我们要求的值。

public int singleNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (!set.add(num)) {
            //如果添加失败，说明这个值
            //在集合Set中存在，我们要
            //把他给移除掉
            set.remove(num);
        }
    }
    //最终集合Set中只有一个元素，我们直接返回
    return (int) set.toArray()[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 06. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

**输入：**nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]

示例 2:

**输入：**nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

进阶**：**

  • 如果给定的数组已经排好序呢？你将如何优化你的算法？
  • 如果 nums1 的大小比 nums2 小，哪种方法更优？
  • 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

解题思路

使用map解决 还可以使用map来解决，具体操作如下

遍历nums1中的所有元素，把它存放到map中，其中key就是nums1中的元素，value就是这个元素在数组nums1中出现的次数。

遍历nums2中的所有元素，查看map中是否包含nums2的元素，如果包含，就把当前值加入到集合list中，然后对应的value要减1。

最后再把集合list转化为数组即可，代码如下

public int[] intersect(int[] nums1, int[] nums2) {
    HashMap<Integer, Integer> map = new HashMap<>();
    ArrayList<Integer> list = new ArrayList<>();

    //先把数组nums1的所有元素都存放到map中，其中key是数组中
    //的元素，value是这个元素出现在数组中的次数
    for (int i = 0; i < nums1.length; i++) {
        map.put(nums1[i], map.getOrDefault(nums1[i], 0) + 1);
    }

    //然后再遍历nums2数组，查看map中是否包含nums2的元素，如果包含，
    //就把当前值加入到集合list中，然后再把对应的value值减1。
    for (int i = 0; i < nums2.length; i++) {
        if (map.getOrDefault(nums2[i], 0) > 0) {
            list.add(nums2[i]);
            map.put(nums2[i], map.get(nums2[i]) - 1);
        }
    }

    //把集合list转化为数组
    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        res[i] = list.get(i);
    }
    return res;
}
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

# 07. 加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

**输入：**digits = [1,2,3] 输出：[1,2,4] **解释：**输入数组表示数字 123。

示例 2：

**输入：**digits = [4,3,2,1] 输出：[4,3,2,2] **解释：**输入数组表示数字 4321。

示例 3：

**输入：**digits = [0] 输出：[1]

提示：

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

解题思路

如果数组中的所有元素都是9，类似9999，加1之后肯定会变为10000，也就是数组长度会增加1位。 如果数组的元素只要有一个不是9，加1之后直接返回即可。 来看下代码。

public int[] plusOne(int[] digits) {
    int length = digits.length;
    for (int i = length - 1; i >= 0; i--) {
        if (digits[i] != 9) {
            //如果数组当前元素不等于9，直接加1
            //然后直接返回
            digits[i]++;
            return digits;
        } else {
            //如果数组当前元素等于9，那么加1之后
            //肯定会变为0，我们先让他变为0
            digits[i] = 0;
        }
    }
    //除非数组中的元素都是9，否则不会走到这一步，
    //如果数组的元素都是9，我们只需要把数组的长度
    //增加1，并且把数组的第一个元素置为1即可
    int temp[] = new int[length + 1];
    temp[0] = 1;
    return temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 08. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。
  2. 尽量减少操作次数。

解题思路

把非0的往前挪

把非0的往前挪，挪完之后，后面的就都是0了，然后在用0覆盖后面的。这种是最容易理解也是最容易想到的，代码比较简单，这里就以示例为例画个图来看下

public void moveZeroes(int[] nums) {
    if (nums == null || nums.length == 0)
        return;
    int index = 0;
    //一次遍历，把非零的都往前挪
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0)
            nums[index++] = nums[i];
    }
    //后面的都是0,
    while (index < nums.length) {
        nums[index++] = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

参照双指针解决

这里可以参照双指针的思路解决，指针j是一直往后移动的，如果指向的值不等于0才对他进行操作。而i统计的是前面0的个数，我们可以把j-i看做另一个指针，它是指向前面第一个0的位置，然后我们让j指向的值和j-i指向的值交换

public void moveZeroes(int[] nums) {
    int i = 0;//统计前面0的个数
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] == 0) {//如果当前数字是0就不操作
            i++;
        } else if (i != 0) {
            //否则，把当前数字放到最前面那个0的位置，然后再把
            //当前位置设为0
            nums[j - i] = nums[j];
            nums[j] = 0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 09. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

**输入：**nums = [2,7,11,15], target = 9 输出：[0,1] **解释：**因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

**输入：**nums = [3,2,4], target = 6 输出：[1,2]

示例 3：

**输入：**nums = [3,3], target = 6 输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？


解题思路

HashMap

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> m = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (m.get(target - nums[i]) != null) {
            return new int[]{m.get(target - nums[i]), i};
        }
        m.put(nums[i], i);
    }
    return new int[]{0, 0};
}
1
2
3
4
5
6
7
8
9
10

# 10. 有效数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 空白格用 '.' 表示。

示例 1：

**输入：**board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] **输出：**true

示例 2：

**输入：**board = [["8","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] **输出：**false **解释：**除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字（1-9）或者 '.'

解题思路

直接判断 9宫格数独大家都玩过吧，就是每行，每列以及对应3*3的单元格内只能有1-9这9个数字，并且不能有重复的。

我们首先遍历9宫格的所有元素，然后使用3个二维数组遍历，记录对应的行，列以及3*3单元格是否有某个数字，如果出现冲突，直接返回false。

public boolean isValidSudoku(char board[][]) {
    int length = board.length;
    //二维数组line表示的是对应的行中是否有对应的数字，比如line[0][3]
    //表示的是第0行（实际上是第1行，因为数组的下标是从0开始的）是否有数字3
    int line[][] = new int[length][length];
    int column[][] = new int[length][length];
    int cell[][] = new int[length][length];
    for (int i = 0; i < length; ++i)
        for (int j = 0; j < length; ++j) {
            //如果还没有填数字，直接跳过
            if (board[i][j] == '.')
                continue;
            //num是当前格子的数字
            int num = board[i][j] - '0' - 1;
            //k是第几个单元格，9宫格数独横着和竖着都是3个单元格
            int k = i / 3 * 3 + j / 3;
            //如果当前数字对应的行和列以及单元格，只要一个由数字，说明冲突了，直接返回false。
            //举个例子，如果line[i][num]不等于0，说明第i（i从0开始）行有num这个数字。
            if (line[i][num] != 0 || column[j][num] != 0 || cell[k][num] != 0)
                return false;
            //表示第i行有num这个数字，第j列有num这个数字，对应的单元格内也有num这个数字
            line[i][num] = column[j][num] = cell[k][num] = 1;
        }
    return true;
}
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

# 11. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 (opens new window) 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

**输入：**matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

**输入：**matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

示例 3：

**输入：**matrix = [[1]] 输出：[[1]]

示例 4：

**输入：**matrix = [[1,2],[3,4]] 输出：[[3,1],[4,2]]

提示：

  • matrix.length == n
  • matrix[i].length == n
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

解题思路

先上下交换，在对角线交换

leet0048.png

public void rotate(int[][] matrix) {
    int length = matrix.length;
    //先上下交换
    for (int i = 0; i < length / 2; i++) {
        int temp[] = matrix[i];
        matrix[i] = matrix[length - i - 1];
        matrix[length - i - 1] = temp;
    }
    //在按照对角线交换
    for (int i = 0; i < length; ++i) {
        for (int j = i + 1; j < length; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
上次更新: 2022/07/21, 12:07:30
Data Structure
字符串

← 字符串→

最近更新
01
day01-Java基础语法
08-31
02
1
08-29
03
路线
08-01
更多文章>
Theme by Vdoing | Copyright © 2019-2022 Evan Xu | MIT License
×