IVN
0%

Array

Posted on Edited on In
Symbols count in article: 12k Reading time ≈ 11 mins.

数组好题选编

前缀和数组

前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。

303. Range Sum Query - Immutable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class NumArray {
    // 前缀和数组
    private int[] preSum;	//前i个数之和

    /* 输入一个数组，构造前缀和 */
    public NumArray(int[] nums) {
        // preSum[0] = 0，便于计算累加和
        preSum = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    
    /* 查询闭区间 [left, right] 的累加和 */
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];	//[0,right] - [0,left-1] = [left,right]
    }
}

304. Range Sum Query 2D - Immutable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumMatrix {
    // 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
    private int[][] preSum;
    
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        if (m == 0 || n == 0) return;
        // 构造前缀和矩阵
        preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 计算每个矩阵 [0, 0, i, j] 的元素和
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
            }
        }
    }
    
    // 计算子矩阵 [x1, y1, x2, y2] 的元素和
    public int sumRegion(int x1, int y1, int x2, int y2) {
        // 目标矩阵之和由四个相邻矩阵运算获得
        return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
    }
}

差分数组

前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减

370. Range Addition

由于初始res数组是全0，初始dif数组就是全0，无需初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode370 {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] res=new int[length];
        int[] dif=new int[length];
        for (int[] update : updates) {
            int from=update[0];
            int to=update[1];
            int inc=update[2];
            dif[from]+=inc;
            if(to+1<length){
                dif[to+1]-=inc;
            }
        }
        res[0]=dif[0];
        for (int i = 1; i < length; i++) {
            res[i]=res[i-1]+dif[i];
        }
        return res;
    }
}

1109. Corporate Flight Bookings

可以优化空间复杂度，无需另外开辟res数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode1109 {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] dif=new int[n];
        for (int[] booking : bookings) {
            int from=booking[0]-1;
            int to=booking[1]-1;
            int inc=booking[2];
            dif[from]+=inc;
            if(to+1<n){
                dif[to+1]-=inc;
            }
        }
        for (int i = 1; i < n; i++) {
            dif[i]+=dif[i-1];
        }
        return dif;
    }
}

1094. Car Pooling

每多一段trip的影响就是，区间[from, to-1]+=passenger

只要保证在每一个地点车上人数都不超过capacity即可

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
public class LeetCode1094 {
    public boolean carPooling(int[][] trips, int capacity) {
        int n=1000;
        int[] dif=new int[n+1];
        for (int[] trip : trips) {
            int inc=trip[0];
            int from=trip[1];
            int to=trip[2]-1;
            dif[from]+=inc;
            if(to+1<n){
                dif[to+1]-=inc;
            }
        }
        int i=0;
        while(i<=n){
            if(i>0){
                dif[i]+=dif[i-1];
            }
            if(dif[i]>capacity){
                return false;
            }
            i++;
        }
        return true;
    }
}

Sliding Window

209. Minimum Size Subarray Sum

看到求 minimal length, 考虑用 sliding window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n=nums.length;
        int sum=0;
        int left=0;
        int right=0;
        int len=Integer.MAX_VALUE;
        while(right<n){//[left,right)
            sum+=nums[right];
            right++;
            while(sum>=target){
                if(right-left<len){
                    len=right-left;
                }
                sum-=nums[left];
                left++;
            }
        }
        return len==Integer.MAX_VALUE ? 0 : len;
    }
}

二维数组遍历

54. Spiral Matrix

大基本功

注意处理完rowStart和colEnd后，要注意判断区间是否还合法，不合法则提前结束

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        List<Integer> res=new ArrayList<>();
        int rowStart=0;
        int rowEnd=row-1;
        int colStart=0;
        int colEnd=col-1;
        while(rowStart<=rowEnd && colStart<=colEnd){
            for(int i=colStart; i<=colEnd; i++){
                res.add(matrix[rowStart][i]);
            }
            rowStart++;
            for(int i=rowStart; i<=rowEnd; i++){
                res.add(matrix[i][colEnd]);
            }
            colEnd--;
            if(rowStart>rowEnd || colStart>colEnd){
                break;
            }
            for(int i=colEnd; i>=colStart; i--){
                res.add(matrix[rowEnd][i]);
            }
            rowEnd--;
            for(int i=rowEnd; i>=rowStart; i--){
                res.add(matrix[i][colStart]);
            }
            colStart++;
        }
        return res;
    }
}

59. Spiral Matrix II

继续大基本功

注意：n*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
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res=new int[n][n];
        int rowStart=0;
        int rowEnd=n-1;
        int colStart=0;
        int colEnd=n-1;
        int index=1;
        while(rowStart<=rowEnd && colStart<=colEnd){
            for(int i=colStart; i<=colEnd; i++){
                res[rowStart][i]=index++;
            }
            rowStart++;
            for(int i=rowStart; i<=rowEnd; i++){
                res[i][colEnd]=index++;
            }
            colEnd--;
            /*if(rowStart>rowEnd || colStart>colEnd){
                break;
            }*/
            for(int i=colEnd; i>=colStart; i--){
                res[rowEnd][i]=index++;
            }
            rowEnd--;
            for(int i=rowEnd; i>=rowStart; i--){
                res[i][colStart]=index++;
            }
            colStart++;
        }
        return res;
    }
}

48. Rotate Image

rotate the image by 90 degrees (clockwise)

解法：

  1. 先将 n x n 矩阵 matrix 按照左上到右下的对角线进行镜像对称
  2. 然后再对矩阵的每一行进行反转

结果就是 matrix 顺时针旋转 90 度的结果

逆时针旋转？同理：

  1. 沿着另一条对角线翻转
  2. 再反转每一行

给你一个包含若干单词和空格的字符串 s，请你写一个算法，原地反转所有单词的顺序

解法：

  1. 先将整个字符串 s 反转
  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
public class LeetCode48 {
    public void rotate(int[][] matrix) {
        int n=matrix.length;
        for (int i = 0; i < n; i++) {
            for(int j=i+1; j<n; j++){
                int temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }

        for (int i = 0; i < n; i++) {
            int left=0;
            int right=n-1;
            while(left<right){
                int temp=matrix[i][left];
                matrix[i][left]=matrix[i][right];
                matrix[i][right]=temp;
                left++;
                right--;
            }
        }
    }
}

其他

1365. How Many Numbers Are Smaller Than the Current Number

注意数组元素范围为[0,100]， 可以用数组记录每个元素出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode1365 {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        //计数排序
        int[] count=new int[101];
        for (int num : nums) {
            count[num]++;
        }
        for (int i = 1; i < 101; i++) {
            count[i]+=count[i-1];
        }
        //此时count[i]表示[0,i]元素出现的次数
        //小于num的元素个数即为count[num-1]
        int[] res=new int[nums.length];
        for (int i = 0; i < res.length; i++) {
            res[i]=nums[i]>0 ? count[nums[i]-1] : 0;
        }
        return res;
    }
}

283. Move Zeroes

转换思路：不需要交换0和非0，只要把非0的数按顺序填入数组头即可

同侧双指针，left代表要填的位置，right代表要填的数

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
class Solution {
    public void moveZeroes(int[] nums) {
        int left=0;
        int right=0;
        int n=nums.length;
        while(right<n){
            while(right<n && nums[right]==0){
                right++;
            }
            if(right>=n){
                break;
            }
            swap(nums,left,right);
            left++;
            right++;
        }
    }

    void swap(int[] nums, int i, int j){
        if(i==j){
            return;
        }
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

152. Maximum Product Subarray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxProduct(int[] nums) {
    int n=nums.length;
    int[][] dp=new int[n][2];
    dp[0][0]=nums[0];
    dp[0][1]=nums[0];
    int res=nums[0];
    for (int i = 1; i < n; i++) {
        if(nums[i]>=0){
            dp[i][0]=Math.max(nums[i]*dp[i-1][0],nums[i]);
            dp[i][1]=Math.min(nums[i]*dp[i-1][1],nums[i]);
        }else{
            dp[i][0]=Math.max(nums[i]*dp[i-1][1],nums[i]);
            dp[i][1]=Math.min(nums[i]*dp[i-1][0],nums[i]);
        }
        res=Math.max(dp[i][0],res);
    }
    return res;
}

150. Evaluate Reverse Polish Notation

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
public int evalRPN(String[] tokens) {
    Deque<Integer> stack=new LinkedList<>();
    for (int i = 0; i < tokens.length; i++) {
        String s=tokens[i];
        if(s.equals("+") || s.equals("-")
                || s.equals("*") || s.equals("/")){
            int a=stack.pop();
            int b=stack.pop();
            stack.push(cal(s,a,b));
        }else{
            stack.push(Integer.valueOf(s));
        }
    }
    return stack.pop();
}

int cal(String s, int a, int b){
    switch (s){
        case "+":
            return b+a;
        case "-":
            return b-a;
        case "*":
            return b*a;
        case "/":
            return b/a;
    }
    return 0;
}

169. Majority Element

Follow-up: Could you solve the problem in linear time and in O(1) space?

Approach 4: Bit Manipulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int majorityElement(int[] nums) {
    int n=nums.length;
    int res=0;
    for (int i = 0; i < 32; i++) {
        int bit=1<<i;
        int count=0;
        for (int num : nums) {
            if((num&bit)!=0){
                count++;
            }
        }
        if(count>n/2){
            res|=bit;
        }
    }
    return res;
}

189. Rotate Array

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
public void rotate(int[] nums, int k) {
    //1 2 3 4 5
    //k=2
    //3 2 1 5 4
    //4 5 1 2 3
    int n=nums.length;
    //[0,n-k-1] , [n-k,n-1]
    int p=((n-k-1)%n + n)%n;
    int left=0;
    int right=p;
    while(left<right){
        swap(nums,left++,right--);
    }
    left=p+1;
    right=n-1;
    while(left<right){
        swap(nums,left++,right--);
    }
    left=0;
    right=n-1;
    while(left<right){
        swap(nums,left++,right--);
    }
}

void swap(int[] nums, int i, int j){
    nums[i]=nums[i]^nums[j];    //a=a^b
    nums[j]=nums[i]^nums[j];    //b=a^b^b=a
    nums[i]=nums[i]^nums[j];    //a=a^b^a=b
}

221. Maximal Square

逐一判断，超时!

注意：

  • 类比maximum rectangle, 用dp!
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
public int maximalSquare(char[][] matrix) {
    int row=matrix.length;
    int col=matrix[0].length;
    int max=0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(matrix[i][j]=='1'){
                max=Math.max(max,cal(matrix,i,j,row,col));
            }
        }
    }
    return max;
}

int cal(char[][] matrix, int x, int y, int row, int col){
    int cur=1;
    while(valid(matrix,x,y,row,col,cur)){
        cur++;
    }
    return cur*cur;
}

boolean valid(char[][] matrix, int x, int y, int row, int col, int cur){
    for(int i=y; i<=y+cur; i++){
        if(x+cur>=row || i>=col  || matrix[x+cur][i]=='0'){
            return false;
        }
    }
    for(int i=x; i<=x+cur; i++){
        if(y+cur>=col || i>=row || matrix[i][y+cur]=='0'){
            return false;
        }
    }
    return true;
}

Approach 2: Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maximalSquare(char[][] matrix) {
    int row=matrix.length;
    int col=matrix[0].length;
    int[][] dp=new int[row+1][col+1];
    int max=0;
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            if(matrix[i-1][j-1]=='1'){
                dp[i][j]=Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
                max=Math.max(max,dp[i][j]);
            }
        }
    }
    return max*max;
}

Approach #3 (Better Dynamic Programming) [Accepted]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int[] dp = new int[cols + 1];
        int maxsqlen = 0, prev = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
                    maxsqlen = Math.max(maxsqlen, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxsqlen * maxsqlen;
    }
}

228. Summary Ranges

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<String> summaryRanges(int[] nums) {
    List<String> res=new ArrayList<>();
    int n=nums.length;
    int i=0;
    while(i<n){
        int start=i;
        int end=i;
        while(end+1<n && nums[end+1]==nums[end]+1){
            end++;
        }
        if(start==end){
            res.add(String.valueOf(nums[start]));
        }else{
            res.add(nums[start]+"->"+nums[end]);
        }
        i=end+1;
    }
    return res;
}

289. Game of Life

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
41
42
43
44
45
46
47
48
49
50
51
52
53
public void gameOfLife(int[][] board) {
    int row=board.length;
    int col=board[0].length;
    boolean[][] change=new boolean[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(board[i][j]==0 && lives(board,i,j,row,col)){
                change[i][j]=true;
            }else if(board[i][j]==1 && dies(board,i,j,row,col)){
                change[i][j]=true;
            }
        }
    }
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(change[i][j]){
                board[i][j]=board[i][j]==1 ? 0 :1;
            }
        }
    }
}

boolean lives(int[][] board, int i, int j, int row, int col){
    int count=0;
    for(int x=i-1; x<=i+1; x++){
        for(int y=j-1; y<=j+1; y++){
            if(x==i && y==j){
                continue;
            }
            if(x<0 || x>=row || y<0 || y>=col || board[x][y]==0){
                continue;
            }
            count++;
        }
    }
    return count==3;
}

boolean dies(int[][] board, int i, int j, int row, int col){
    int count=0;
    for(int x=i-1; x<=i+1; x++){
        for(int y=j-1; y<=j+1; y++){
            if(x==i && y==j){
                continue;
            }
            if(x<0 || x>=row || y<0 || y>=col || board[x][y]==0){
                continue;
            }
            count++;
        }
    }
    return count!=2 && count!=3;
}