数组篇二

数组

238. 除自身以外数组的乘积 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        //L[i]代表了nums[i]左侧的乘积
        int[] L = new int[n];
        //R[i]代表了nums[i]右侧的乘积
        int[] R = new int[n];
        int[] ans = new int[n];
        R[n - 1] = 1;
        for(int i = n - 2; i >= 0; i--) R[i] = nums[i + 1]*R[i + 1];
        L[0] = 1;
        for(int i = 1; i < n; i++) L[i] = nums[i - 1]*L[i - 1];
        for(int i = 0; i < n; i++) ans[i] = L[i]*R[i];
        return ans;
    }
}

274. H 指数 - 力扣（LeetCode）

此次题目有一些模糊，其题意大概是，在数组中寻找一个数字h（尽可能大），h表示数组中至少有h个数字都大于等于h

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int ans = 0, compare = 0;
        Arrays.sort(citations);
        for(int i = 0; i < n; i++){
            compare = Math.min(n - i, citations[i]);
            ans = Math.max(ans, compare);
        }
        return ans;
    }
}

453. 最小操作次数使数组元素相等 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int t = nums[0], ans = 0;
        for(int i = 1; i < n; i++){
            ans += nums[i] - t;
        }
        return ans;
    }
}

665. 非递减数列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean checkPossibility(int[] nums) {
        int n = nums.length;
        int ans = 1;
        int[] f = new int[n];
        f[0] = 1;
        for(int i = 1; i < n; i++){
            f[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] >= nums[j]) f[i] = Math.max(f[i], f[j] + 1);
            }
            ans = Math.max(ans, f[i]);
        }
        return  ans >= n - 1;

    }
}

283. 移动零 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int l = 0, r = 0;
        while(r < n){
            if (nums[r] != 0) {
                int tmp = nums[r];
                nums[r] = nums[l];
                nums[l] = tmp;
                l++;
            }
            r++;
        }
    }
}

566. 重塑矩阵 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length;
        int n = mat[0].length;
        if(r*c != m*n) return mat;
        int[][] ans = new int[r][c];
        int row = 0, col = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(col == c){
                    col = 0;
                    row++;
                }
                ans[row][col] = mat[i][j];
                col++;
            }
        }
        return ans;
    }
}

498. 对角线遍历 - 力扣（LeetCode）

因为沿着对角线遍历只会面临两种情况，向着右上角遍历或者向着左下角进行遍历，所以创建一个direct ，当它=1的时候，它沿着右上角方向进行遍历，，当它等于-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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length, cnt = m*n;
        int[] ans = new int[cnt];
        int x = 0, y = 0, direct = 1, flag = 0;
        while(flag < cnt){
            ans[flag] = mat[x][y];
            flag++;
            int nx = 0, ny = 0;
            //direct = 1沿着右上角的方向进行遍历
            if(direct == 1){
                //行数减一
                nx = x - 1;
                //列数加一
                ny = y + 1;
            }
            if(direct == -1){
                //行数加一
                nx = x + 1;
                //列数减一
                ny = y - 1;
            }
            //处理越界的情况
            if(nx < 0 || nx >= m || ny < 0 || ny >= n){
                //右上方的越界情况处理
                if(direct == 1){
                    nx = y + 1 < n ? x : x + 1;
                    ny = y + 1 < n ? y + 1 : y;
                }
                //左下方的越界情况处理
                else{
                    nx = x + 1 < m ? x + 1 : x;
                    ny = x + 1 < m ? y : y + 1;
                }
                //越界变方向
                direct *=  -1;
            }
            x = nx;
            y = ny;
        }
        return ans;
    }
}

注意：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//处理越界的问题
if (dx < 0 || dx >= m || dy < 0 || dy >= n){
    //处理右上方**已经**越界的问题
    if (dir == 1) {
        dx = y + 1 >= n ? x + 1 : x;
        dy = y + 1 >= n ? y : y + 1;
    }
    //左下方已经越界的问题处理
    else {
        dx = x + 1 >= m ? x : x + 1;
        dy = x + 1 >= m ? y + 1 : y;
    }
    x = dx;
    y = dy;
}
//这种情况会导致dy 取到边界值n
反着来就是不行
算法
#leetcode
数组篇二
http://example.com/2024/01/30/arr2/
作者
nianjx
发布于
2024年1月30日
许可协议