数组篇三

数组

54. 螺旋矩阵 - 力扣（LeetCode）

递归的一种写法不会让人一下子就能想得到

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        circle(matrix, 0, 0, m - 1, n - 1, ans);
        return ans;
    }
    //遍历以x1,y1为左上角;x2,y2为右下角的一圈
    public void circle(int[][] mat, int x1, int y1, int x2, int y2,List<Integer> ans){
        if(x1 > x2 || y1 > y2) return;
        //只有一行的情况下
        if(x1 == x2){
            for(int i = y1; i <= y2; i++) ans.add(mat[x1][i]); return;
        }
        //只有一列的情况下
        if(y1 == y2){
            for(int i = x1; i <= x2; i++) ans.add(mat[i][y1]);return;
        }
        //遍历
        for(int i = y1; i < y2; i++) ans.add(mat[x1][i]);
        for(int i = x1; i < x2; i++) ans.add(mat[i][y2]);
        for(int i = y2; i > y1; i--) ans.add(mat[x2][i]);
        for(int i = x2; i > x1; i--) ans.add(mat[i][y1]);
        circle(mat,x1 + 1, y1 + 1, x2 - 1, y2 - 1, ans);
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int l = 0, r = matrix[0].length - 1;
        int t = 0, b = matrix.length - 1;
        int x = 0;
        Integer[] res = new Integer[(r + 1)*(b + 1)];
        while (true){
            for (int i = l; i <= r; i++) res[x++] = matrix[t][i];//从左向右（变列数）
            if(++t > b) break;
            for (int i = t; i <= b; i++) res[x++] = matrix[i][r];//从上往下（变行数）
            if (l > --r) break;
            for (int i = r; i >= l; i--) res[x++] = matrix[b][i];//从右向左
            if (t > --b) break;
            for (int i = b; i >= t; i--) res[x++] = matrix[i][l];//从下向上
            if(++l > r) break;
        }
        return Arrays.asList(res);
    }
}

59. 螺旋矩阵 II - 力扣（LeetCode）

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int start = 1, end = n*n;
        int t = 0, b = n - 1, l = 0, r = n - 1;
        while (start <= end){
            for (int i = l; i <= r; i++) ans[t][i] = start++;
            t++;
            for (int i = t; i <= b; i++) ans[i][r] = start++;
            r--;
            for (int i = r; i >= l; i--) ans[b][i] = start++;
            b--;
            for (int i = b; i >= t; i--) ans[i][l] = start++;
            l++;
        }
        return ans;
    }
}

118. 杨辉三角 - 力扣（LeetCode）

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = 0; i < numRows; i++){
            List<Integer> r = new ArrayList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    r.add(1);
                }else{
                    r.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
                }
            }
            ans.add(r);
        }
        return ans;

    }
}

119. 杨辉三角 II - 力扣（LeetCode）

class Solution {
    public List<Integer> getRow(int row_Index) {
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = 0; i <= row_Index; i++){
            List<Integer> tmp = new ArrayList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    tmp.add(1);
                }else{
                    tmp.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
                }
            }
            ans.add(tmp);
        }
        return ans.get(row_Index);
    }
}