Hanota

经典递归问题，从这道题学到的关于递归的思想挺多的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void move(int size, List<Integer> A, List<Integer> B, List<Integer> C){
        if (size == 1){
            C.add(A.remove(A.size() - 1));
            return;
        }
        move(size - 1, A, C, B);
        C.add(A.remove(A.size() - 1));
        move(size - 1, B, A, C);
    }

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }
}

Plaint

经典的dfs问题，好像有一个比较高大上的名字叫做漫水算法？

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 void dfs(int[][] image, int[][] sign, int sr, int sc, int newColor){
        if (sign[sr][sc]  == 1){
            return;
        }
        int[][] step = {{1, 0}, {-1, 0},
                {0, 1}, {0, -1}};
        int width = image.length;
        int length = image[0].length;

        sign[sr][sc] = 1;
        int temp = image[sr][sc];
        image[sr][sc] = newColor;
        for (int i = 0; i < 4; i++) {
            int row = sr + step[i][0];
            int col = sc + step[i][1];
            if (row >= width || row < 0 || col >= length || col < 0 || sign[row][col] == 1 || temp != image[row][col]){
                continue;
            }
            dfs(image, sign, row, col, newColor);
        }
    }
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int[][] sign = new int[image.length][image[0].length];
        dfs(image, sign ,sr, sc, newColor);
        return image;
    }
}

岛屿数量

刷LeetCode第一次一遍过😁

  1. 判断是否为水，或判断标记是否走过
  2. dfs确定连在一起的岛的范围
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
class Solution {
    int height = 0;
    int width = 0;
    // 上下左右改变
    int[][] step = {{1,0},{-1,0},{0,1},{0,-1}};
    public void numIslandsDfs(char[][] grid, int row, int col, int[][] book){
        //如果越界就返回
        if (row < 0 || row >= height || col < 0 || col >= width)return;
       	
        // 如果是水域或者该点已经走过也返回
        else if (grid[row][col] == '0' || book[row][col] == 1)return;
        book[row][col] = 1;
        for (int i = 0; i < 4; i++) {
            int post_x = row + step[i][0];
            int post_y = col + step[i][1];
            numIslandsDfs(grid, post_x, post_y, book);
        }
    }

    public int numIslands(char[][] grid) {
        /*
        * 不用直接判断孤岛
        * 从0开始检索，如果book数组中没有标记且是陆地，则标记book
        * 开始dfs检索
        * */
        int count = 0;
        height = grid.length;
        width = grid[0].length;
        int book[][]= new int[grid.length][grid[0].length];
        
        // 两层for循环来遍历所有坐标
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                
                // 如果该坐标为水域或者标记为1就忽略
                if (grid[i][j] == '0' || book[i][j] == 1) {
                    continue;
                }else {
                    numIslandsDfs(grid, i, j, book);
                    count++;
                }
            }
        }
        return count;
    }
}

矩阵中的路径

1
2
3
4
5
6
7
思路如下

将返回值设置为false
如果dfs出一个完整的单词链则将返回值设置为true，并且直接break
遍历表，只对应单词的首字符
首字母存在就直接进行dfs遍历，遍历的方向只有四个方向
回溯，如果道路不符合需要把之前走过的路全部清0

第一次写的代码最后三个检测点死活不能过，下面贴第一次写的代码

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 Solution {
     int[][] step = {{1,0},{-1,0},{0,1},{0,-1}};
    int height = 0;
    int width = 0;
    boolean objRet = false;
    public void existDfs(char[][] board, int row, int col, int[][] book, char[] wordArray, int wordIndex){
        if (wordIndex == wordArray.length){
            this.objRet = true;
            return;
        }
        if (row >= height || row < 0 || col >= width || col < 0 ) return;
        else if (book[row][col] == 1 || board[row][col] != wordArray[wordIndex]) return;
        book[row][col] = 1;
        wordIndex++;
        for (int i = 0; i < 4; i++) {
            int post_x = step[i][0] + row;
            int post_y = step[i][1] + col;
    
            existDfs(board, post_x, post_y, book, wordArray, wordIndex);
        }
        book[row][col] = 0;
    }

    public boolean exist(char[][] board, String word) {
        char[] wordArray = word.toCharArray();
        height = board.length;
        width = board[0].length;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                    if (board[i][j] == wordArray[0]){
                        int[][] book = new int[height][width];
                        // 开始进行dfs搜索，如果搜索成功就将ret赋值为true
                        existDfs(board,i,j,book,wordArray,0);
                        // 判断在进行dfs后是否找到矩阵中相应单词
                    }
            }
        }
        return this.objRet;
    }
}

第二次写的代码，虽然过了，但是效率也太低了。。。服了

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
class Solution {
   int[][] step = {{1,0},{-1,0},{0,1},{0,-1}};
    int height = 0;
    int width = 0;

    public boolean existDfs(char[][] board, int row, int col, int[][] book, char[] wordArray, int wordIndex){
        if (row >= height || row < 0 || col >= width || col < 0)return false;
        else if (board[row][col] != wordArray[wordIndex] || book[row][col] == 1)return false;
        if (wordIndex == wordArray.length-1)return true;

        boolean ret = false;
        for (int i = 0; i < 4; i++) {
            int post_x = step[i][0] + row;
            int post_y = step[i][1] + col;
            book[row][col] = 1;
            ret =  existDfs(board, post_x, post_y, book, wordArray, wordIndex+1);
            if (ret == true)break;
            book[row][col] = 0;
        }

        return ret;
    }

    public boolean exist(char[][] board, String word) {
        /*
        * 首先将返回值设置为false
        * 如果dfs出一个完整的单词链则将返回值设置为true，并且直接break
        *
        * 首先需要遍历表，只对应单词的首字符
        * 首字母存在就直接进行dfs遍历
        * 遍历的方向只有四个方向
        * 还需要回溯，如果道路不符合需要把之前走过的路全部清0
        * */

        char[] wordArray = word.toCharArray();
        height = board.length;
        width = board[0].length;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                int[][] book = new int[height][width];
                if (existDfs(board,i,j,book,wordArray,0)){
                    return true;
                }
            }
        }
        return false;
    }
}

解码异或后的数组

简单的签到题

1
2
3
4
5
6
7
8
9
10
11
class Solution {
   public int[] decode(int[] encoded, int first) {
        int decodedLength = encoded.length + 1;
        int[] decoded = new int[decodedLength];
        decoded[0] = first;
        for (int i = 0; i < encoded.length; i++) {
            decoded[i+1] = encoded[i] ^ decoded[i];
        }
        return decoded;
    }
}

数组异或操作

两天都是简单的签到题？感觉这道题随便都可以跑到100%

1
2
3
4
5
6
7
8
9
class Solution {
    public int xorOperation(int n, int start) {
        int retNum = start;
        for (int i = 1; i < n; i++) {
            retNum ^= start+i*2;
        }
        return retNum;
    }
}

螺旋矩阵Ⅰ

开始螺旋矩阵三部曲冲冲冲🐱‍🏍

经典题目，学C语言的时候看过没写过，写关于矩阵的东西需要找到矩阵变化规律。

网上找的图，就是把四条边动态化（反正这个思路我是想不出来）。矩阵的上下两条边对应，左右两条边对应，一边在加则另一边减，直到两条边重合。

1
2
3
思路:
定义矩阵的四条边
每当遍历完一层这条边就减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
class Solution {
     public List<Integer> spiralOrder(int[][] matrix) {
            /*
            * 定义四个边界
            * 两两对应
            * 一边加就一边减*/
            int up = 0,down = matrix.length - 1;
            int left = 0,right = matrix[0].length - 1;
            List<Integer> list = new ArrayList<Integer>();
            while (true){
                for (int i = left; i <= right; i++) {
                    list.add(matrix[up][i]);
                }
                if (++up>down)break;

                for (int i = up; i <= down; i++) {
                    list.add(matrix[i][right]);
                }
                if (--right < left)break;

                for (int i = right; i >= left ; i--) {
                    list.add(matrix[down][i]);
                }
                if (--down < up)break;

                for (int i = down; i >= up ; i--) {
                    list.add(matrix[i][left]);
                }
                if (++left > right)break;
            }
            return list;
        }
}

螺旋矩阵Ⅱ

和螺旋矩阵Ⅰ的思路是一样的

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[][] generateMatrix(int n) {
        int left = 0,right = n - 1;
        int up = 0, down = n - 1;
        int[][] matrix = new int[n][n];
        int num=1;
        while (true){
            for (int i = up; i <= right; i++) {
                matrix[up][i] = num++;
            }
            if (++up>down)break;

            for (int i = up; i <= down ; i++) {
                matrix[i][right] = num++;
            }
            if (--right < left)break;

            for (int i = right; i >= left ; i--) {
                matrix[down][i] = num++;
            }
            if (--down < up)break;

            for (int i = down; i >= up ; i--) {
                matrix[i][left] = num++;
            }
            if (++left>right)break;
        }

        return matrix;
    }
}

螺旋矩阵Ⅲ

两种思路：

  • 和上面的思路一样，动态模拟四条边
  • 找规律，通过观察可知，每次右移和下移走的步数是奇数，左移和上移走的步数是偶数，所以可以以起始点为中心（上图其实都表示出来了），定义一个正方形，遍历这个正方形的所有坐标，如果坐标范围在矩形内，则符合条件
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
54
55
56
57
58
59
60
61
class Solution {
     public boolean checkPost(int R,int C,int r0,int c0){
        if (r0>=R || r0<0 || c0>=C || c0<0) return false;
        else return true;
    }
    public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
        // 输入参数，矩阵宽高，起始位置
        /*
         * 将不规则矩阵看成正方形
         * 模拟上下左右边界
         * 单独设置一个技术变量判断是否遍历完成
         * 遍历方向：右，下，左，上*/
        int[][] arr = new int[R*C][2];
        int num = 0;
        int max = R>=C?R:C;
        arr[num][0] = r0;
        arr[num][1] = c0;
        for (int i = 1; i <= max*2; i+=2) {
            for (int j = 1; j <= i; j++) {
                c0+=1;
                if (checkPost(R,C,r0,c0)){
                    ++num;
                    arr[num][0]=r0;
                    arr[num][1]=c0;
//                    System.out.println("x,y: "+r0+","+c0);
                }
            }

            for (int j = 1; j <= i; j++) {
                r0 += 1;
                if (checkPost(R,C,r0,c0)){
                    ++num ;
                    arr[num][0]=r0;
                    arr[num][1]=c0;
//                    System.out.println("x,y: "+r0+","+c0);
                }
            }

            for (int j = 1; j < i+2; j++) {
                c0 -=1;
                if (checkPost(R,C,r0,c0)){
                    ++num ;
                    arr[num][0]=r0;
                    arr[num][1]=c0;
//                    System.out.println("x,y: "+r0+","+c0);
                }
            }

            for (int j = 1; j < i+2; j++) {
                r0 -= 1;
                if (checkPost(R,C,r0,c0)){
                    ++num ;
                    arr[num][0]=r0;
                    arr[num][1]=c0;
//                    System.out.println("x,y: "+r0+","+c0);
                }
            }
        }
        return arr;
    }
}