刷题记录｜目标101题--搜索

写在前面

开个贴记录一下 刷题的过程，目前参照 leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～

已刷链接：

深度搜索dfs

No. 1 Max Area of Island

题目链接：链接

解题思路：

本题的重点在

  • 创建一个direction数组，用两两相邻的位置表示方向上左右下
  • dfs递归深搜
class Solution {
    int[] direction = {-1,0,1,0,-1};
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
               if (grid[i][j] == 1) {
                	result = Math.max(result,dfs(grid,i,j,m,n));
                } 
            } 
        }
        return result;
    }
    private int dfs(int[][] grid,int x, int y, int m, int n) {
        if (x < 0 || x >= m || y < 0 || y >= n) return 0;
        if (grid[x][y] == 0) return 0;
        grid[x][y] = 0;
        int result = 1;
        for (int i = 0; i < 4; i++) {
            int x_direction = direction[i];
            int y_direction = direction[i + 1];
            result += dfs(grid,x + x_direction, y + y_direction,m,n);
        }
        return result;
    } 
}

No.2 Number of Provinces

题目链接：链接

解题思路：

//二刷本发现，本题的重点在于，要把一行理解为一个城市，这样的话就可以让n*n变成n的问题，最后降低时间复杂度

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        if (n == 0) return 1;
        int result = 0;
        int[] visited = new int[n];
        for (int i = 0; i < n; i ++) {
            if (visited[i] == 0) {
                dfs(isConnected,i,visited);
                result++;
            } 
        }
        return result;
    }
    private void dfs(int[][] isConnected, int i, int[] visited) {
        if (i > isConnected.length || i < 0) return;
        if (visited[i] == 1) return;
        visited[i] = 1;
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && i != j) {
                dfs(isConnected,j,visited);
                isConnected[i][j] = 0;
            }
        }
    }
}

No.3 Pacific Atlantic Water Flow

题目：链接

解题思路：

本体的搜索思路有两点需要注意：

  • 需要一个用来记录是否要返回不再搜索的数组，不然会死循环
  • 如果单纯的搜索每个cell是否能reach则负责度太高了，最好是有办法能够在一次遍历中记录下每个cell能否reach。

综上我们这题采用反过来的思路，去从四个边开始，看水能否逆向回溯到cell。

所以我们设置两个canreach的数组，分别代表能reach太平洋和reach大西洋，从四边开始从四周向中心搜索，每个边代表可以reach一个洋，从四周开始最后整向里走，看每个cell能否reach某个洋，最后整体遍历看是否可以reach

class Solution {
    int[] direction = {-1,0,1,0,-1};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int m = heights.length, n = heights[0].length;
        boolean[][] canReachP = new boolean[m][n];
        boolean[][] canReachA = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(heights,i,0,canReachP);
            dfs(heights,i,n - 1, canReachA);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights,0,j,canReachP);
            dfs(heights,m - 1,j,canReachA);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachP[i][j] && canReachA[i][j]) {
                    result.add(Arrays.asList(i,j));
                }
            }
        }
        return result;  
    }
    private void dfs(int[][] heights, int i, int j, boolean[][] canReach) {
        if (canReach[i][j]) return;
        canReach[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int m = direction[k] + i;
            int n = direction[k + 1] + j;
            if (m >= 0 && m < heights.length && n >= 0 && n < heights[0].length && heights[m][n] >= heights[i][j]) {
                dfs(heights,m,n,canReach);
            }
        }
    }
}

No.4 Surrounded Regions

题目：链接

解题思路：

和上面的海水题目一样，从外到内去填充。

我们可以理解为，只要边缘有一个O，这个island就无法被反转，反之可以被反转，所以我们可以先找到边缘的O，然后从外dfs，最后整体遍历一遍去反转O。

class Solution {
    int[] direction = {-1,0,1,0,-1};
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] keep = new boolean[m][n];
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                keep[i][0] = true;dfs(board,i,0,keep,m,n,visited);
            }
            if (board[i][n - 1] == 'O') {
                keep[i][n - 1] = true;dfs(board,i,n - 1, keep,m,n,visited);
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                keep[0][i] = true;dfs(board,0,i,keep,m,n,visited);
            }
            if (board[m - 1][i] == 'O') {
                 keep[m - 1][i] = true;
                dfs(board,m - 1,i, keep,m,n,visited);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j ++) {
                if (keep[i][j]) {
                    continue;
                }
                board[i][j] = 'X';
            }
        }
    }
    private void dfs(char[][] board, int i, int j, boolean[][] keep, int m, int n, boolean[][] visited) {
        if (!keep[i][j] || visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int p = i + direction[k];
            int q = j + direction[k + 1];
            if (p >= 0 && p < m && q >= 0 && q < n) {
                if (board[p][q] == 'O') {
                    keep[p][q] = true;
                    dfs(board,p,q,keep,m,n,visited);
                }
            }
        }
    }
}

回溯法

No.1  Permutations

题目：链接

解题思路：

回溯算法。此题需要注意的是：

  • 所谓不重复数组的排列组合，只要当前位置与后面的每个位置交换，直到最后一位即可实现排列组合
  • 为了防止每次都创建新的数组，要利用回溯法，直接修改，本次修改完再改回

这里需要注意的java知识：

int[] 转 List<Integer> 需要 List<Integer> tem = Arrays.stream(nums).boxed().collect(Collectors.toList());

  • Arrays.stream(nums) 将基本类型数组转换为基本类型流。 int[ ] => IntStream
  • .boxed() 将基本类型流转换为对象流。 => Stream< Integer >
  • .collect(Collectors.toList()) 将对象流收集为集合。 => List< Integer >
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        dfs(nums,result,0);
        return result;
    }
    private void dfs(int[] nums, List<List<Integer>> result,int level) {
        if (level == nums.length - 1) {
            List<Integer> tem = Arrays.stream(nums).boxed().collect(Collectors.toList());
            result.add(tem);
            return;
        }
        for (int i = level; i < nums.length; i ++) {
            swap(nums,i,level);
            dfs(nums,result,level+1);
            swap(nums,i,level);
        }
    }
    private void swap(int[] nums,int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

No.2 Combinations

题目：链接

解题思路：

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        dfs(n,k,1,result, new ArrayList<>());
        return result;
    }
    private void dfs(int n, int k, int level, List<List<Integer>> result, List<Integer> temp) {
        if (temp.size() == k) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = level; i <= n; i++) {
            temp.add(i);
            dfs(n,k,i + 1,result,temp);
            temp.remove(temp.size() - 1);
        }
    }
}

用到的java知识：

  • java中如何初始化list：链接
  • java如何深拷贝：java中的深拷贝方法要自己实现，刷题时简单起见可以用下面方法：
  • 有一个list temp，可以用 new ArrayList<>(temp) 对其进行深拷贝

No.3 Word Search

题目：链接

解题思路：

class Solution {
    int[] direction = {-1,0,1,0,-1};
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        if (m * n < word.length()) return false;
        char[] wordArray = word.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == wordArray[0]) {
                    if (dfs(board,wordArray,0,i,j,new boolean[m][n])) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, char[] word, int k, int i, int j, boolean[][] reached) {
        if (k == word.length - 1) return true;
        reached[i][j] = true;
        for (int a = 0; a < 4; a++) {
            int q = direction[a] + i;
            int p = direction[a + 1] + j;
            if (q >= 0 && q < board.length && p >= 0 && p < board[0].length && board[q][p] == word[k + 1] && !reached[q][p]) {
                if (dfs(board,word,k + 1,q,p,reached)) return true;
            }
        }
        reached[i][j] = false;
        return false;
    }
}

No.4  N-Queens

题目：链接

解题思路：

这题重点是

  • 明白满足结果的每一行或者每一列仅有一个皇后，所以我们可以对行进行遍历，对列进行数组存储即可
  • 45度和135度的数组要怎么创建？

这里设置45度和135的数组长度为2*n-1，45度数组从左上到右下，他的坐标为row+col，135度数组从左下到右上，他的数组坐标为n-row+col-1

涉及到的java知识点：

链接 string.valueof(char[])可以讲char数组的内容转为字符串

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<List<String>>();
        char[][] board = new char[n][n];
        boolean[] column = new boolean[n], dialog45 = new boolean[2 * n - 1], dialog135 = new boolean[2 * n - 1];
        for (int i = 0; i < n; i ++) {
            Arrays.fill(board[i],'.');
        }
        dfs(result,board,column,dialog45,dialog135,0,n);
        return result;
    }
    private void dfs(List<List<String>> result, char[][] board ,boolean[] column, boolean[] dialog45, boolean[] dialog135, int row, int n) {
        if (row == n) {
            List<String> temp = new ArrayList<>();
            for (int i = 0; i < board.length; i++) {
                temp.add(String.valueOf(board[i]));
            }
            result.add(temp);
            return;
        }
        for (int i = 0; i < n; i ++) {
            if (column[i] || dialog45[row + i] || dialog135[n - 1 - row + i]) {
                continue;
            }
            column[i] = dialog45[row + i] = dialog135[n - 1 - row + i] = true;
            board[row][i] = 'Q';
            dfs(result,board,column,dialog45,dialog135,row + 1,n);
            column[i] = dialog45[row + i] = dialog135[n - 1 - row + i] = false;
            board[row][i] = '.';
        }
    }
}

No.5 Binary Tree Paths

题目：链接

解题思路：

这题有个很重要的点就是java的string是可以使用+去链接string和int的，不知道这点的话要傻傻的转半天

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<String>();
        dfs(root, result, "");
        return result;
    }
    public void dfs(TreeNode cur,List<String> result, String s) {
        if (cur.left == null && cur.right == null) {
            result.add(s + cur.val);
        }
        if (cur.left != null)
            dfs(cur.left,result,s + cur.val + "->");
        if (cur.right != null)
            dfs(cur.right,result,s + cur.val + "->");
    }
}

No.6 Sudoku Solver

题目：链接

解题思路：

这道题首先要进行回溯，也就是如果这个方法不行还要可以改回来继续走。

其次要知道这个数独要如何计算，不要害怕，其实可以理解为遍历每个cell，从1到9看能不能把数字放下，能放下就继续下面一个放，不能放下的话要回溯计算。

所以问题来到了如何可以在位置i，j放下一个数x

我们根据题目要求有三个条件：

  • 同行不能有相同的数字
  • 同列不能有相同的数字
  • 同一个3*3的section不能有相同的数字

对应到代码中，1和2可以轻易的使用一个从1到9的遍历，判断board[i][col]和board[row][i]是否有数字x，但是第三个条件比较难以理解，特别出如下：

想要一个位置（i，j）的3*3方块遍历，我们先求得位置(i,j）所在的方块

  • 对于行来说，第i行的元素位于i/3的方块行内
  • 为了将方块行转为board的行数，我们先将(i/3)乘三，此时得到这个方块的起始行数
  • 然后我们再取k为遍历1到9，将k/3即可得到每个方块内的行数，
  • 3 * （i/3) + k / 3即为这个方块内的所有行
  • 对于列来说，第j行的元素位置j/3的方块行内
  • 为了将方块列转为board的列数，我们先将(j/3)乘三，此时得到这个方块的起始行数，
  • 然后我们再取k为遍历1到9，配合上述的行数计算，我们将对k进行余3的操作，这样可以这个行数对应的列数，构成一个方块
  • 3 * (j / ) + k %3即为这个方块内所有的列数
class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board);
    }
    private boolean dfs(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if (canPut(board,i,j,k)) {
                            board[i][j] = k;
                            if (dfs(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    private boolean canPut(char[][] board, int row, int col, char c) {
        int section_r = 3 * (row / 3);
        int section_c = 3 * (col / 3);
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c) return false;
            if (board[row][i] == c) return false;
            if (board[section_r + i / 3][section_c + i % 3] == c) return false;
        }
        return true;
    }
}

广度优先搜索BFS

No.1 Shortest Bridge

题目：链接

新的java知识：Queue：链接 可以当作一个LinkedList，但是增加为.offer(),删除第一个元素为poll(),顶峰元素为peek()

解题思路：

dfs 找到第一个island，将其赋值为2，然后用bfs找到链接到的最短距离。

bfs：

每次记录下来level，将所有的元素都pop出来依次处理，将每个pop出来元素的赋值为2，然后判断其上下左右的元素，是的0再入栈，是2的直接跳过，是1的则找到island可以返回了，因为我们是广搜，所以可以确保level最小

class Solution {
    int[] direction = {-1,0,1,0,-1};
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        boolean flag = false;
        Queue<int[]> que = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            if (flag) break;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dfs(que,grid,i,j,n,visited);
                    flag = true;
                    break;
                }
            }
        }
        
        int result = 0;
        while (que.size() != 0) {
            result++;
            int size = que.size();
            while(size-- > 0) {
                int[] temp = que.poll();
                grid[temp[0]][temp[1]] = 2;
                for (int i = 0; i < 4; i ++) {
                    int q = temp[0] + direction[i];
                    int p = temp[1] + direction[i + 1];
                    if (q >=0 && q < n && p >= 0 && p < n) { 
                        if(grid[q][p] == 1) {
                            return result;
                        } else if (grid[q][p] == 2) {
                            continue;
                        }
                        grid[q][p] = 2;
                        que.offer(new int[]{q,p});
                    }

No.2 Word Ladder II

题目：链接

解题思路：

将字符串看为节点，先bfs寻得最短路径，再dfs一遍绘出

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<List<String>>();
        HashSet<String> dict = new HashSet<String>();
        HashMap<String,List<String>> neighbors = new HashMap<String,List<String>>();
        HashMap<String,Integer> distance = new HashMap<String,Integer>();
        List<String> path = new ArrayList<String>();
        for (String s : wordList) {
            dict.add(s);
        }
        if (!dict.contains(endWord)) return result;
        bfs(beginWord,endWord,dict,neighbors,distance);
        dfs(beginWord,endWord,dict,neighbors,result,path,distance);
        return result;
    }
    
    private void bfs(String beginWord, String endWord, HashSet<String> dict, HashMap<String,List<String>> neighbors, HashMap<String,Integer> distance) {
        for (String s : dict) {
            neighbors.put(s,new ArrayList<>());
        }
        Queue<String> que = new LinkedList<String>();
        que.offer(beginWord);
        distance.put(beginWord,0);
        neighbors.put(beginWord,new ArrayList<>());
        while (que.size() != 0) {
            int count = que.size();
            boolean found = false;
            for (int i = 0; i < count; i++) {
                String s = que.poll();

No.3 Minimum Height Trees

题目：链接

解题思路：

如果我们用bfs取遍历每个节点，求他是root的时候代表的depth，这样一个n*n的复杂度会超时

所以我们要变换思路使用拓扑排序的思路，先构建一个图，然后将从外围的子节点开始找起，将每个叶子节点从图中去除，这样会一步步逼近跟节点，最后跟节点可能存在1到2个，因为3个就会成环。

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return new ArrayList<Integer>(Arrays.asList(0));
        if (n == 2) return new ArrayList<Integer>(Arrays.asList(0,1));
        
        List<Integer> result = new ArrayList<Integer>();
        List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
        for (int i = 0; i < n; i++) {
            graph.add(new HashSet<Integer>());
        }
        
        for (int i = 0;i < edges.length; i++) {
            graph.get(edges[i][0]).add(edges[i][1]);
            graph.get(edges[i][1]).add(edges[i][0]);
        }
        
        Queue<Integer> que = new LinkedList<Integer>();
        for (int i = 0; i < n; i++) {
            if (graph.get(i).size() ==1) {
                que.offer(i);
            }
        }
        
        int remain = n;
        while (remain > 2) {
            int count = que.size();
            while (count-- > 0) {
                Integer i = que.poll();
                remain--;
                Integer j = graph.get(i).iterator().next();
                graph.get(j).remove(i);
                graph.get(i).remove(j);
                if (graph.get(j).size() == 1) {
                    que.offer(j);
                }
            }
        }
        
        int size = que.size();
        for (int i = 0; i < size; i++) {
            result.add(que.poll());
        }
        
        return result;
    }
}

#刷题#
全部评论
楼主一天刷几道
点赞 回复 分享
发布于 2022-10-13 23:18 山西

相关推荐

03-10 11:40
已编辑
河南中医药大学 Java
点赞 评论 收藏
分享
03-13 00:58
分享帖：一个计算机学渣的十年坎坷之路
说在前头，这是学渣分享帖，大佬可以绕道。我在最后也放上我的社招一年半的简历，供大家参考。&nbsp;2015~2025，从本科到硕士，从硕士到校招，从校招再到社招，十年一眨眼就过了。最近要帮公司拉实习生简历，所以又开始刷牛客刷力扣，看了许多帖子，和以前一样，到处都是大佬们offer拿到手软的帖子，让人羡慕不已，不经想起当初，自己也是那0offer默默窥屏羡慕大佬offer的人中的一员。大厂hc虽然有很多，但和计算机专业学生数量比起来，终究是少数。大厂offer拿到手软的大佬有很多很多，然后大多数都只是普通人，大多数都是像当初的我一样大厂全挂的0offer佬。往事回想起来，总是忍不住让人感慨，我一向喜欢分...
精致的烤冷面说我这儿没问题啊：一口气读完了文章，真挚感人。深夜焦虑刷牛客的我突然感觉内心平静了一些，感谢牛油前辈！向前辈学习！希望自己能像前辈一样坚韧不拔！
双非应该如何逆袭？
点赞 评论 收藏
分享
03-13 21:20
北京邮电大学 Web前端
点赞 评论 收藏
分享
评论
点赞
收藏
分享

招聘动态

查看更多

携程集团

25届校招+26届实习

26届【实习】投递合集

26届实习生双选会报名开启

交银金科

2025届春季招聘

满帮集团

2025春季校园招聘

滴滴

2025届春季校园招聘

腾讯音乐娱乐集团

2025实习生招聘

石化盈科

2025届校园招聘

26届简历拷打辅导交流

快手

25校招&26实习进行中

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 笔试 #
1990736次浏览 22675人参与
# 金融银行面经 #
59761次浏览 473人参与
# 腾讯音乐26届实习 #
113208次浏览 813人参与
# 牛友故事会 #
156661次浏览 2540人参与
# 技术岗笔试题求解 #
15976次浏览 237人参与
# 双非应该如何逆袭？ #
17456次浏览 699人参与
# 元戎现在香不香 #
63273次浏览 515人参与
# 两会劳动法放大招 #
16622次浏览 386人参与
# 我的省钱小妙招 #
4000次浏览 137人参与
# 你投递的公司有几家约面了？ #
53552次浏览 381人参与
# 蔚来开了，制造业的牛友投递了吗？ #
21617次浏览 188人参与
# 网易求职进展汇总 #
70822次浏览 548人参与
# 你怎么评价今年的春招？ #
84981次浏览 1111人参与
# 实习/项目/竞赛奖项，哪个对找工作更重要？ #
47101次浏览 624人参与
# 如果中了500万，你会离职吗？ #
56056次浏览 402人参与
# 打工人的精神状态 #
24716次浏览 426人参与
# 我和xx公司的爱恨情仇 #
35664次浏览 300人参与
# 互联网回暖，腾讯要招5000人！ #
5384次浏览 78人参与
# 携程求职进展汇总 #
175916次浏览 1179人参与
# 在国企工作的人，躺平了吗？ #
310314次浏览 3795人参与
# 秋招想进国企该如何准备 #
43794次浏览 341人参与
# 高学历就一定能找到好工作吗？ #
42724次浏览 557人参与
牛客网
牛客企业服务