LeetCode 算法之搜索
深度优先搜索和广度优先搜索广泛运用于树和图中,但是它们的应用远远不止如此。
BFS
广度优先搜索一层一层地进行遍历,每层遍历都是以上一层遍历的结果作为起点,遍历一个距离能访问到的所有节点。需要注意的是,遍历过的节点不能再次被遍历。 第一层:
- 0 -> {6,2,1,5}
第二层:
- 6 -> {4}
- 2 -> {}
- 1 -> {}
- 5 -> {3}
第三层:
- 4 -> {}
- 3 -> {}
每一层遍历的节点都与根节点距离相同。设 di 表示第 i 个节点与根节点的距离,推导出一个结论:对于先遍历的节点 i 与后遍历的节点 j,有 di <= dj。利用这个结论,可以求解最短路径等 最优解 问题:第一次遍历到目的节点,其所经过的路径为最短路径。应该注意的是,使用 BFS 只能求解无权图的最短路径,无权图是指从一个节点到另一个节点的代价都记为 1。 在程序实现 BFS 时需要考虑以下问题:
- 队列:用来存储每一轮遍历得到的节点;
- 标记:对于遍历过的节点,应该将它标记,防止重复遍历。
DFS
广度优先搜索一层一层遍历,每一层得到的所有新节点,要用队列存储起来以备下一层遍历的时候再遍历。 而深度优先搜索在得到一个新节点时立即对新节点进行遍历:从节点 0 出发开始遍历,得到到新节点 6 时,立马对新节点 6 进行遍历,得到新节点 4;如此反复以这种方式遍历新节点,直到没有新节点了,此时返回。返回到根节点 0 的情况是,继续对根节点 0 进行遍历,得到新节点 2,然后继续以上步骤。 从一个节点出发,使用 DFS 对一个图进行遍历时,能够遍历到的节点都是从初始节点可达的,DFS 常用来求解这种 可达性 问题。 在程序实现 DFS 时需要考虑以下问题:
- 栈:用栈来保存当前节点信息,当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
- 标记:和 BFS 一样同样需要对已经遍历过的节点进行标记。
1.岛屿的最大面积
695.给定一个包含了一些 0 和 1 的非空二维数组 grid 。 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1 。 思路:对遍历过的 1 清零。
class Solution {
public int maxAreaOfIsland(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length, n = grid[0].length;
int maxArea = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
maxArea = Math.max(maxArea, dfs(grid, m, n, i, j));
}
}
}
return maxArea;
}
private int dfs(int[][] grid, int m, int n, int i, int j){
if(i < 0 || j < 0 || i >= m || j >= n) return 0;
if(grid[i][j] == 0) return 0;
grid[i][j] = 0;
int area = 1;
area += dfs(grid, m, n, i + 1, j);
area += dfs(grid, m, n, i - 1, j);
area += dfs(grid, m, n, i, j + 1);
area += dfs(grid, m, n, i, j - 1);
return area;
}
}
2.岛屿数量
200.给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
思路:可以将矩阵表示看成一张有向图。
class Solution {
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0){
return 0;
}
int m = grid.length, n = grid[0].length;
int num = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1'){
num++;
dfs(grid, m, n, i, j);
}
}
}
return num;
}
private void dfs(char[][] grid, int m, int n, int i, int j){
if(i < 0 || j < 0 || i >= m || j >= n) return;
if(grid[i][j] == '0') return;
grid[i][j] = '0';
dfs(grid, m, n, i+1, j);
dfs(grid, m, n, i-1, j);
dfs(grid, m, n, i, j+1);
dfs(grid, m, n, i, j-1);
}
}
3.朋友圈
547.班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。 给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果 M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。 思路:好友关系可以看成是一个无向图,例如第 0 个人与第 1 个人是好友,那么 M[0][1] 和 M[1][0] 的值都为 1。 使用一个 visited 数组, 依次判断每个节点, 如果其未访问, 朋友圈数加 1 并对该节点进行 dfs 搜索标记所有访问到的节点。
class Solution {
public int findCircleNum(int[][] M) {
if(M == null || M.length == 0 || M[0].length == 0) return 0;
int n = M.length;
int num = 0;
boolean[] visited = new boolean[n];
for(int i = 0; i < n; i++){
if(!visited[i]){
num++;
dfs(M, n, i, visited);
}
}
return num;
}
private void dfs(int[][] M, int n, int i, boolean[] visited){
visited[i] = true;
for(int k = 0; k < n; k++){
if(M[i][k] == 1 && !visited[k]){
dfs(M, n, k, visited);
}
}
}
}
3.被围绕的区域
130.给定一个二维的矩阵,包含 'X' 和 'O'(字母 O)。 找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。 示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后,矩阵变为:
X X X X
X X X X
X X X X
X O X X
解释: 被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。 思路: 先填充最外侧以及最外侧相连的,剩下的就是里侧了。 (从边缘往里走)
class Solution {
public void solve(char[][] board) {
if(board == null || board.length == 0 || board[0].length == 0) return;
int m = board.length, n = board[0].length;
for(int i = 0; i < m; i++){
dfs(board, m, n, i, 0);
dfs(board, m, n, i, n-1);
}
for(int j = 0; j < n; j++){
dfs(board, m, n, 0, j);
dfs(board, m, n, m-1, j);
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == 'O'){
board[i][j] = 'X';
}else if(board[i][j] == 'T'){
board[i][j] = 'O';
}
}
}
}
private void dfs(char[][] board, int m, int n, int i, int j){
if(i < 0 || j < 0 || i >= m || j >= n) return;
if(board[i][j] != 'O') return;
board[i][j] = 'T';
dfs(board, m, n, i+1, j);
dfs(board, m, n, i-1, j);
dfs(board, m, n, i, j+1);
dfs(board, m, n, i, j-1);
}
}
5.太平洋大西洋水流问题
417.给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。 规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。 请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标。
给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋
返回:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
思路: 要同时满足可以到达大西洋与太平洋,所以一个点需要进行两次路径的行走,一次以太平洋为目标,一次以大西洋为目标。从内部的点以边界为目标去进行路径行走比较麻烦,但是如果换一个思路,从边缘往里面走。 从边缘向里走就修改通行规则,要往高度比当前点高或者相等的点走。
public class Solution {
private int m, n;
private int[][] matrix;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> ret = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return ret;
}
m = matrix.length;
n = matrix[0].length;
this.matrix = matrix;
boolean[][] canReachP = new boolean[m][n];
boolean[][] canReachA = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(i, 0, canReachP);
dfs(i, n - 1, canReachA);
}
for (int i = 0; i < n; i++) {
dfs(0, i, canReachP);
dfs(m - 1, i, canReachA);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (canReachP[i][j] && canReachA[i][j]) {
ret.add(Arrays.asList(i, j));
}
}
}
return ret;
}
private void dfs(int r, int c, boolean[][] canReach) {
if (canReach[r][c]) {
return;
}
canReach[r][c] = true;
for (int[] d : direction) {
int nextR = d[0] + r;
int nextC = d[1] + c;
if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
|| matrix[r][c] > matrix[nextR][nextC]) {
continue;
}
dfs(nextR, nextC, canReach);
}
}
}
回溯
Backtracking(回溯)属于 DFS。
- 普通 DFS 主要用在 可达性问题 ,这种问题只需要执行到特点的位置然后返回即可。
- 而 Backtracking 主要用于求解 排列组合 问题,例如有 { 'a','b','c' } 三个字符,求解所有由这三个字符排列得到的字符串,这种问题在执行到特定的位置返回之后还会继续执行求解过程。
因为 Backtracking 不是立即返回,而要继续求解,因此在程序实现时,需要注意对元素的标记问题:
- 在访问一个新元素进入新的递归调用时,需要将新元素标记为已经访问,这样才能在继续递归调用时不用重复访问该元素;
- 但是在递归返回时,需要将元素标记为未访问,因为只需要保证在一个递归链中不同时访问一个元素,可以访问已经访问过但是不在当前递归链中的元素。
1. 数字键盘组合
17.给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
class Solution {
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
StringBuilder sb = new StringBuilder();//用于构造字符串
List<String> result = new ArrayList<>();//保存结果
public List<String> letterCombinations(String digits) {
if(digits.length() == 0) return result;
if(digits.length() == sb.length()){
result.add(sb.toString());
return result;//虚假的返回
}
int cur = digits.charAt(sb.length()) - '0';
String letters = KEYS[cur];
for(char c : letters.toCharArray()){
sb.append(c);
letterCombinations(digits);
sb.deleteCharAt(sb.length()-1);
}
return result;
}
}
2. IP 地址划分
93.给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
class Solution {
StringBuilder sb = new StringBuilder();
List<String> result = new ArrayList<>();
int k = -1;//用于记录此时在划分第几个整数
public List<String> restoreIpAddresses(String s) {
k++;
//已经分好四个整数或者已经将字符串分完
if(k == 4 || s.length() == 0){
if(k == 4 && s.length() == 0){//恰好分完
result.add(sb.toString());
}
return result;//虚假的返回
}
for(int i = 0; i < s.length() && i <= 2; i++){
if(i != 0 && s.charAt(0) == '0'){//0 后面不能跟其他数
break;
}
String part = s.substring(0, i+1);
if(Integer.valueOf(part) <= 255) {
if(sb.length() != 0){//第一个整数前不用加
part = "." + part;
}
sb.append(part);
restoreIpAddresses(s.substring(i+1));
sb.delete(sb.length() - part.length(), sb.length());
k--;//k 也要复原
}
}
return result;
}
}
剑指 27.字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc,则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,cab 和 cba。
输入一个字符串,长度不超过 9(可能有字符重复),字符只包括大小写字母。
思路: 回溯。 固定 A 不动,然后交换 B 与 C,从而得到"ABC" 和 "ACB" 同理,对于"BAC"、"BCA" 、"CAB"和"CBA"是同样道理。 当两个字符相同时,不应该交换。
- 递归函数的功能:dfs(int pos, string s), 表示固定字符串 s 的 pos 下标的字符 s[pos]
- 递归终止条件:当 pos+1 == s.length()的时候,终止,表示对最后一个字符进行固定,也就说明,完成了一次全排列
- 下一次递归:dfs(pos+1, s), 很显然,下一次递归就是对字符串的下一个下标进行固定
回溯:每次递归完成后,须重新交换回来。
import java.util.ArrayList;
import java.util.Collections;
public class Solution
{
public ArrayList<String> Permutation(String str)
{
ArrayList<String> res=new ArrayList<String>();
if(str.length()==0||str==null)return res;
int n= str.length();
helper(res,0,str.toCharArray());
Collections.sort(res);
return res;
}
public void helper( ArrayList<String> res,int index,char []s)
{
if(index==s.length-1)res.add(new String(s));
for(int i=index;i<s.length;i++)
{
if(i==index||s[index]!=s[i])
{
swap(s,index,i);
helper(res,index+1,s);
swap(s,index,i);
}
}
}
public void swap(char[]t,int i,int j)
{
char c=t[i];
t[i]=t[j];
t[j]=c;
}
}
剑指 65.矩阵中的路径
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 思路: 回溯。
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
//标志位,初始化为 false
boolean[] flag = new boolean[matrix.length];
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
//循环遍历二维数组,找到起点等于 str 第一个元素的值,再递归判断四周是否有符合条件的----回溯法
if(judge(matrix,i,j,rows,cols,flag,str,0)){
return true;
}
}
}
return false;
}
//judge(初始矩阵,索引行坐标 i,索引纵坐标 j,矩阵行数,矩阵列数,待判断的字符串,字符串索引初始为 0 即先判断字符串的第一位)
private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
//先根据 i 和 j 计算匹配的第一个元素转为一维数组的位置
int index = i*cols+j;
//递归终止条件
if(i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[k] || flag[index] == true)
return false;
//若 k 已经到达 str 末尾了,说明之前的都已经匹配成功了,直接返回 true 即可
if(k == str.length-1)
return true;
//要走的第一个位置置为 true,表示已经走过了
flag[index] = true;
//回溯,递归寻找,每次找到了就给 k 加一,找不到,还原
if(judge(matrix,i-1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i+1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i,j-1,rows,cols,flag,str,k+1) ||
judge(matrix,i,j+1,rows,cols,flag,str,k+1) )
{
return true;
}
//走到这,说明这一条路不通,还原,再试其他的路径
flag[index] = false;
return false;
}
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
上一篇: LeetCode 位运算
下一篇: 谈谈自己对于 AOP 的了解
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论