主要是想练习下递归,学下递归思想,还有dfs。

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;
}
}