搜索的核心概念
问题求解树
是一种思维逻辑层面的结构,而非程序中的实际存储结构;思维结构可以表示无限的概念
设计搜索算法的核心关键点
设计问题求解树的状态
搜索剪枝和优化
在问题求解树搜索过程中,对于某些分支或子树通过某些条件的筛选不进行搜索。
搜索方法
对问题求解树不同的遍历方式
深度遍历 - Depth First Search
程序实现 =》 递归
广度遍历 - Breadth First Search
层序遍历 =》 队列
适合场景:求解最优化问题
练习
来自Leetcode
下面这个题目即可使用深搜又可使用广搜,理解下两种方法解题
993. 二叉树的堂兄弟节点
在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同,但 父节点不同 ,则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root ,以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时,才返回 true 。否则,返回 false。
示例 1:
输入:root = [1,2,3,4], x = 4, y = 3
输出:false
示例 2:
输入:root = [1,2,3,null,4,null,5], x = 5, y = 4
输出:true
方法一: 深搜 dfs
思路:
- 问题状态:被查找元素 & 当前节点 & 父节点 & 当前节点层深
- 递归函数设计:
/**
* 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 {
private int dfs(TreeNode root, int val, TreeNode father) {
if (root == null) return -1;
if (root.val == val) return 0;
father.val = root.val;
int level;
level = dfs(root.left, val, father);
if (level != -1) return level + 1;
father.val = root.val;
level = dfs(root.right, val, father);
if (level != -1) return level + 1;
return -1;
}
public boolean isCousins(TreeNode root, int x, int y) {
int l_x, l_y;
TreeNode father_x = new TreeNode(-1), father_y = new TreeNode(-1);
l_x = dfs(root, x, father_x);
l_y = dfs(root, y, father_y);
return l_x == l_y && father_x.val != father_y.val;
}
}
方法二: 广搜 bfs
问题状态: 当前节点 & 父节点 & 当前节点层深
class Solution {
class Node {
TreeNode curr;
TreeNode father;
int level;
public Node(TreeNode curr, TreeNode father, int level) {
this.curr = curr;
this.father = father;
this.level = level;
}
}
public boolean isCousins(TreeNode root, int x, int y) {
int level_x = -1, level_y = -1;
TreeNode father_x = new TreeNode(-1), father_y = new TreeNode(-1);
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(root, null, 0));
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.curr.val == x) {//终止条件:判断是否为带查找元素
level_x = node.level;
father_x = node.father;
}
if (node.curr.val == y) {//终止条件:判断是否为带查找元素
level_y = node.level;
father_y = node.father;
}
if (node.curr.left != null) {//扩展状态【搜索树左右子树】
queue.offer(new Node(node.curr.left, node.curr, node.level + 1));
}
if (node.curr.right != null) {//扩展状态【搜索树左右子树】
queue.offer(new Node(node.curr.right, node.curr, node.level + 1));
}
}
return level_x == level_y && father_x.val != father_y.val;
}
}
1091. 二进制矩阵中的最短路径
给你一个 n x n 的二进制矩阵 grid 中,返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径,返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格(即,(0, 0))到 右下角 单元格(即,(n - 1, n - 1))的路径,该路径同时满足下述要求:
路径途经的所有单元格都的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一 上连通(即,相邻两单元之间彼此不同且共享一条边或者一个角)。
畅通路径的长度 是该路径途经的单元格总数。
示例 1:
输入:grid = [[0,1],[1,0]]
输出:2
示例 2:
输入:grid = [[0,0,0],[1,1,0],[1,1,0]]
输出:4
感觉这个题目就是广搜的比较又代表性的题目,其他的题目都是大同小异,可以深入理解下
问题状态:当前元素【一维坐标 & 二维坐标 & 距离起点距离】
class Solution {
int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}};
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid[0][0] != 0) return -1;//当矩阵左上角的第一个元素不为0, 则说明无法开始站在起始位置
int n = grid.length;
int m = grid[0].length;
int[][] visit = new int[n][m];//存储原矩阵相应位置是否被访问过,用于剪枝
visit[0][0] = 1;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0, 1});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
if (curr[0] == n - 1 && curr[1] == n - 1) {//是否满足搜索终止条件 (走到终点)
return curr[2];
}
for (int i = 0; i < dir.length; i++) {//扩展状态【二维矩阵方向数组dir】
int x = curr[0] + dir[i][0];
int y = curr[1] + dir[i][1];
if (x < 0 || x >= n) continue;//剪枝 (下标越界)
if (y < 0 || y >= m) continue;//剪枝 (下标越界)
if (grid[x][y] != 0) continue;//剪枝 (题目要求)
if (visit[x][y] != 0) continue;//剪枝 (重复访问)
visit[x][y] = curr[2] + 1;
queue.offer(new int[]{x, y, visit[x][y]});
}
}
return -1;
}
}
给你一个 m x n
的矩阵 board
,由若干字符 'X'
和 'O'
,找到所有被 'X'
围绕的区域,并将这些区域里所有的 'O'
用 'X'
填充。
示例 1:
分析:
四个边上的O没有被X围绕 =》由这些O向内扩展的所有可达的O均没有被X围绕; 由这些O向内扩展的所有不可达的O均被X围绕
问题状态:当前元素【一维坐标 & 二维坐标 & 是否为O且从四个边的O出发可达】
递归函数设计:
- 入参:矩阵横坐标 & 矩阵纵坐标 & 原数组
- 返回值: void
class Solution {
private int n;
private int m;
int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private void dfs(int i, int j, char[][] board) {
board[i][j] = 'o';
for (int k = 0; k < dir.length; k++) {
int x = i + dir[k][0];
int y = j + dir[k][1];
if (x < 0 || x >= n) continue;
if (y < 0 || y >= m) continue;
if (board[x][y] != 'O') continue;
dfs(x, y, board);
}
}
public void solve(char[][] board) {
n = board.length;
m = board[0].length;
for (int i = 0; i < n; i++) {
if (board[i][0] == 'O') dfs(i, 0, board);
if (board[i][m - 1] == 'O') dfs(i, m - 1, board);
}
for (int j = 0; j < m; j++) {
if (board[0][j] == 'O') dfs(0, j, board);
if (board[n - 1][j] == 'O') dfs(n - 1, j, board);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == 'o') {
board[i][j] = 'O';
}
}
}
}
}
[473. 火柴拼正方形] (dfs)
还记得童话《卖火柴的小女孩》吗?现在,你知道小女孩有多少根火柴,请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以把火柴连接起来,并且每根火柴都要用到。
输入为小女孩拥有火柴的数目,每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
分析:题目可以转化为:所拥有的火柴是否可以平均分为四组?
初始化一个大小为4的一维数组(4个桶),每个元素初始化为火柴总长度/4(桶的容量);
桶的容量为火柴总长度/4, 当将所有火柴都放入桶中时,代表4个桶均放满
问题状态: 第ind根火柴 & 桶的剩余容量 int[] arr
递归函数:
- 入参:ind & int[]arr & 原数组int[] matchsticks
- 返回值:题目所求“是否能用所有的火柴拼成正方形” boolean
- 逻辑:
class Solution {
private boolean dfs(int ind, int[] arr, int[] matchsticks) {
if (ind == -1) return true;//当ind 超限时,说明所有的火柴都放到桶中,且均放满
for (int i = 0; i < arr.length; i++) {//遍历4个桶
if (arr[i] < matchsticks[ind]) continue;//桶的容量不够火柴长度
if (arr[i] == matchsticks[ind] || arr[i] >= matchsticks[ind] + matchsticks[0]) {
arr[i] -= matchsticks[ind];//更新桶的剩余容量
if (dfs(ind - 1, arr, matchsticks)) return true;
arr[i] += matchsticks[ind];//若当前火柴放入当前桶后没有找到解,则需要将火柴从当前桶中拿出
}
}
return false;
}
public boolean makesquare(int[] matchsticks) {
Arrays.sort(matchsticks);
int sum = 0;
for (int matchstick : matchsticks) {
sum += matchstick;
}
if (sum % 4 != 0) return false;
int[] arr = new int[4];
for (int i = 0; i < arr.length; i++) {
arr[i] = sum / 4;
}
return dfs(matchsticks.length - 1, arr, matchsticks);
}
}