DFS（深度优先搜索）
DFS/ 回溯模板 子序列的模板
List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();public void dfs(int cur, int[] nums) {if (cur == nums.length) {// 判断是否合法，如果合法判断是否重复，将满足条件的加入答案if (isValid() && notVisited()) {ans.add(new ArrayList<Integer>(temp));}return;}// 如果选择当前元素temp.add(nums[cur]);dfs(cur + 1, nums);temp.remove(temp.size() - 1);// 如果不选择当前元素dfs(cur + 1, nums);}
486. 预测赢家
模拟一下这个操作，
841. 钥匙和房间
这道题需要一set 来记录一下什么已经放进去了。 对于每一个房间的钥匙，打开相应的门，如果里面的钥匙是没有过的，那就进入下一轮的搜索中去。
class Solution {
HashSet<Integer> set = new HashSet<>();
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int n = rooms.size();
set.add(0);
dfs(rooms.get(0),rooms);
// System.out.println(set.size());
return set.size() == rooms.size();
}
private void dfs(List<Integer> room, List<List<Integer>> rooms) {
if(room.size() == 0){
return;
}else {
for (int i = 0; i < room.size(); i++) {
int num = room.get(i);
if(set.contains(num)){
continue;
}
else {
set.add(num);
dfs(rooms.get(num),rooms);
}
}
}
}
}
130. 被围绕的区域
这道题的里面，只有和边界连接的O才不会变成X。 所以从边界上的O开始DFS，把遇到的O 设置为Q，最后遍历一次，把Q变成O，其余的都是X。
class Solution {
public void solve(char[][] board) {
if(board==null||board.length<1){
return;
}
if(board.length==1||board[0].length==1){
return;
}
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
if(board[i][0] == 'O'){
dfs(board,i,0);
}
if(board[i][n-1] =='O'){
dfs(board,i,n-1);
}
}
for (int i = 0; i < n; i++) {
if(board[0][i] =='O'){
dfs(board,0,i);
}
if(board[m-1][i] == 'O'){
dfs(board,m-1,i);
}
}
for (int i = 0; i <m; i++) {
for (int j = 0; j < n; j++) {
if(board[i][j] =='Q'){
board[i][j] = 'O';
}else {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int i, int j) {
if(i<0||j<0||j>=board[0].length||i>=board.length||board[i][j]!='O'){
return;
}
int[] dx = new int[]{1,0,0,-1};
int[] dy = new int[]{0,-1,1,0};
board[i][j] = 'Q';
for (int k = 0; k < 4; k++) {
dfs(board,i+dx[k],j+dy[k]);
}
}
}
78. 子集
对于每一个的选项，我们都有选择，或者不选择的情况。
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
LinkedList<Integer> tmp = new LinkedList<>();
if(nums == null) return res;
dfs(nums,tmp,0);
return res;
}
private void dfs(int[] nums, LinkedList<Integer> tmp, int index) {
if(index ==nums.length){
res.add(new LinkedList<>(tmp));
return;
}
dfs(nums,tmp,index+1);
tmp.add(nums[index]);
dfs(nums,tmp,index+1);
tmp.removeLast();
}
}
17. 电话号码的字母组合
有一点像是括号生成的题目。先把数值和字符串的对应起来。
对于每一个输入的数字。 我们都对他进行一个搜索。只要到了最后面，那就加入到结果里面。
class Solution {
public List<String> letterCombinations(String digits) {
List<String> res = new LinkedList<>();
HashMap<Character,String> map = new HashMap<>();
if(digits==null||digits.length()<1)return res;
map.put('2',"abc");
map.put('3',"def");
map.put('4',"ghi");
map.put('5',"jkl");
map.put('6',"mno");
map.put('7',"pqrs");
map.put('8',"tuv");
map.put('9',"wxyz");
letterCombinations(res,digits,0,map,"");
return res;
}
private void letterCombinations(List<String> res, String digits, int index, HashMap<Character, String> map,String s) {
if(index == digits.length()){
res.add(s);
return;
}
String tmp = map.get(digits.charAt(index));
for (int i=0;i<tmp.length();i++){
letterCombinations(res,digits,index+1,map,s+tmp.charAt(i));
}
}
}
199. 二叉树的右视图
根结点 -> 右子树 -> 左子树」 的顺序访问， 就可以保证每层都是最先访问最右边的节点的。
（与先序遍历 「根结点 -> 左子树 -> 右子树」 正好相反，先序遍历每层最先访问的是最左边的节点）
List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
int step = 0;
dfs(root,step);
return res;
}
private void dfs(TreeNode root ,int step){
if(root ==null) return;
if(step>=res.size()){
res.add(root.val);
}
dfs(root.right,step+1);
dfs(root.left,step+1);
}
BFS解法：
其实在获得就是每一层的最后一个元素。这就和一层一层的遍历是一样的。在最后的一个元素的时候放到res里面。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root ==null){
return res;
}
queue.add(root);
while (!queue.isEmpty()){
int size = queue.size();
for(int i=0;i<size;i++){
TreeNode tmp = queue.poll();
if(tmp.left!=null){
queue.add(tmp.left);
}
if(tmp.right!=null){
queue.add(tmp.right);
}
if(i == size-1){
res.add(tmp.val);
}
}
}
return res;
}
}
22. 括号生成
思路：tql我想不出来这么简洁的代码。TAT 其实就是一个递归。中间对于递归的条件有所限制。 left要大于0，right要大于left的时候才行
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs(n,n,"");
return res;
}
private void dfs(int left,int right,String curStr){
if(left == 0&&right ==0){
res.add(curStr);
}
if(left>0){
dfs(left-1,right,curStr+"(");
}
if(right>left){
dfs(left,right-1,curStr+")");
}
}
}
面试题13. 机器人的运动范围
这道题的思路还是比较清晰的。 需要一个数组来记录一下是否访问过数组。DFS的话使用递归来实现。 判断一下当前的位置的下面有多少个可以找到的格子。
class Solution {
int m,n,k;
boolean[][] visited;
public int movingCount(int m, int n, int k) {
this.m = m;
this.k = k;
this.n = n;
visited = new boolean[m][n];
return dfs(0,0,0,0);
}
private int dfs(int i,int j,int sx,int sj){
if(i>=m||j>=n||k<sx+sj||visited[i][j]){
return 0;
}
visited[i][j] = true;
return 1+dfs(i+1,j,(i+1)%10==0?sx-8:sx+1,sj)+dfs(i,j+1,sx,(j+1)%10==0?sj-8:sj+1);
}
}
543-二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1<br /> / \<br /> 2 3<br /> / \ <br /> 4 5 <br />返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
思路：
这道题其实在寻找根节点的左右子树的最大深度。直径的意思其实就是找到节点和其子树的的最大直径（因为最大的路径可能不经过根节点），设置某个节点的为 Node 深度分别为L 和R，maxd 是最大路径。如果节点为空，返回0. 不然就计算一下他的左右节点的深度。 maxd = max（L+R，maxd） 递归的返回值呢就是max（L+R）+1，左右子树的深度最大值+1，因为到了上一层，这里还有一个路径的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int maxd = 0;
public int diameterOfBinaryTree(TreeNode root) {
deepth(root);
return maxd;
}
private int deepth(TreeNode node){
if(node == null) return 0;
int left = deepth(node.left);
int right = deepth(node.right);
maxd = Math.max(left+right,maxd); //节点的最大直径（左边的深度+右边的深度）取最大值
return Math.max(left,right)+1;// 返回节点的深度。
}
}
695-岛屿的最大面积
思路：
这道题的意思其实是说，给你一个这么大的数组，遍历一下看一看1连起来的地方有多大。返回最大值。
其实在考我们深度优先遍历的思想。
我们遍历一下整个数组，如果里面的有1，就遍历一下。遍历的流程是这样的，把现在的这个1变成0，递归计算一下他的上下左右的num值。加到一起作为这个点的结果。 结果取最大值。
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int res = 0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j] ==1){
res = Math.max(res,dfs(i,j,grid));
}
}
}
return res;
}
private int dfs(int i,int j,int[][] grid){
if(i<0||j<0||i>grid.length-1||j>grid[0].length-1||grid[i][j] ==0){
return 0;
}
grid[i][j] = 0;
int num = 1;
num+=dfs(i,j-1,grid);
num+=dfs(i,j+1,grid);
num+=dfs(i-1,j,grid);
num+=dfs(i+1,j,grid);
return num;
}
}
BFS（广度优先搜索）
1030. 距离顺序排列矩阵单元格
思路：
从给定的那个节点开始往外面逐层的遍历，不需要计算曼哈顿距离，依次加入到结果中进而好了，使用一个数组来确保每一个元素放在同一个位置里面。
class Solution {
public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
int[][] marix = new int[R*C][2];
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[R][C];
queue.add(new int[]{r0,c0});
int cnt = 0;
while(!queue.isEmpty()){
int[] tmp = queue.poll();
int x = tmp[0];
int y = tmp[1];
if(x<0||y<0||x>=R||y>=C||visited[x][y]){
continue;
}
marix[cnt][0] = x;
marix[cnt][1] = y;
cnt++;
visited[x][y] = true;
queue.add(new int[]{x+1,y});
queue.add(new int[]{x-1,y});
queue.add(new int[]{x,y-1});
queue.add(new int[]{x,y+1});
}
return marix;
}
}
210. 课程表 II
可以想象成一个超级节点下面连着别的节点。 一个图的样子。 我们需要记录一下，每门课需要的前置课程的数量。 把前置课程是0的加入到队列里面。 每一次循环的时候，取出相应的课程。 把需要门课的课程的前置数量减1. 如果已经是0 的话，加入到队列里面。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Queue<Integer> queue = new LinkedList<>();
int[] input = new int[numCourses];
int[] res = new int[numCourses];
int index = 0;
for(int[] edge: prerequisites){
input[edge[0]]++;
}
for(int i=0;i<input.length;i++){
if(input[i] ==0){
queue.add(i);
}
}
while(!queue.isEmpty()){
int tmp = queue.poll();
res[index++] = tmp;
for(int[] edge:prerequisites){
if(edge[1] == tmp){
input[edge[0]]--;
if(input[edge[0]] == 0){
queue.add(edge[0]);
}
}
}
}
if(index!= numCourses){
return new int[]{};
}
return res;
}
}
542. 01 矩阵
这道题和1162非常的接近，这道题是从0扩散到1的过程。
class Solution {
public int[][] updateMatrix(int[][] matrix) {
Queue<int[]> queue = new LinkedList<>();
for(int i=0;i<matrix.length;i++){
for (int j=0;j<matrix[0].length;j++){
if(matrix[i][j] ==0){
queue.add(new int[]{i,j});
}else{
matrix[i][j] = -1;
}
}
}
int[] dx = new int[]{0,0,1,-1};
int[] dy = new int[]{1,-1,0,0};
while (!queue.isEmpty()){
int[] tmp = queue.poll();
int x = tmp[0];
int y = tmp[1];
for(int i=0;i<4;i++){
int newX = x+dx[i];
int newY = y+dy[i];
if(newX<0||newY<0||newX>=matrix.length||newY>=matrix[0].length||matrix[newX][newY]!=-1){
continue;
}
matrix[newX][newY] = matrix[x][y]+1;
queue.add(new int[]{newX,newY});
}
}
return matrix;
}
}
1162. 地图分析
BFS的题目一般来说都是使用一个队列来标记待检测的区域。对于这道题来说，各你一个矩阵，找到里面0到1的最大距离、可以把0先全部入队，一层一层的进行扩散遍历。
class Solution {
public int maxDistance(int[][] grid) {
int[] dx = {0,0,1,-1};
int[] dy = {1,-1,0,0};
Deque<int[]> queue = new ArrayDeque<>();
int m = grid.length;
int n = grid[0].length;
for(int i=0;i<m;i++){
for (int j=0;j<n;j++){
if(grid[i][j]==1){
queue.add(new int[]{i,j});
}
}
}
boolean isSea = false;//标记一下是不是都是海洋的情况
int[] point = null; // 记录一下最后的一个元素。因为是一层一层的，所以最后的肯定是最大的
while (!queue.isEmpty()){
point = queue.poll();
int x = point[0],y = point[1];
for(int i=0;i<4;i++){
int newX = x+dx[i];
int newY = y+dy[i];
if(newX<0||newY<0||newX>=m||newY>=n||grid[newX][newY]!=0){
continue;
}
isSea = true;
grid[newX][newY] = grid[x][y]+1;
queue.add(new int[]{newX,newY});
}
}
if(point==null||!isSea){
return -1;
}
return grid[point[0]][point[1]]-1;
}
}
面试题13. 机器人的运动范围
使用BFS的话，一般我使用一个队列来标记，接下来需要访问的节点。计算数位和的方法。假如有进位的话，那就-8，不然加1.
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0,0,0,0});
int res = 0;
while (!queue.isEmpty()){
int[] tmp = queue.poll();
int x = tmp[0],y=tmp[1],sx = tmp[2],sj = tmp[3];
if(x<0||y<0||x>=m||y>=n||visited[x][y]||sj+sx>k)continue;
res++;
visited[x][y] = true;
queue.add(new int[]{x+1,y,(x+1)%10==0?sx-8:sx+1,sj});
queue.add(new int[]{x,y+1,sx,(y+1)%10==0?sj-8:sj+1});
}
return res;
}
}
994-腐烂的橘子
思路：
有一点像回溯的思路。每个隔一次时间，橘子会把相邻的橘子都腐烂掉。先遍历一下述，找到不好的橘子的坐标。记录一下橘子的总数。使用队列来存储不好的橘子。每次取出不好的橘子，搜索一下他的上下左右又没有新鲜的橘子。有的话，将橘子标为坏的，存入队列里面。时间加一。假如队列中没有橘子了，判断一下count。是否有到达不了的橘子。
代码：
class Solution {
public int orangesRotting(int[][] grid) {
int R = grid.length;
int C = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
// 遍历一下里面好的橘子和坏的橘子
int count =0;
for(int r = 0;r<R;++r){
for(int c=0;c<C;++c){
if(grid[r][c] == 1){
++count;
}else if(grid[r][c] == 2){
queue.add(new int[]{r,c});
}
}
}
int round = 0;
while(count>0&&!queue.isEmpty()){//只要队列不为空
++round;
int n = queue.size();
for(int i=0;i<n;i++){ // 每次都取空，执行size次。
int[] orange = queue.poll();
int r = orange[0];
int c = orange[1];
// 判断他的上下左右又没有橘子，有的话加入到队列里面。
if(r-1>=0&&grid[r-1][c]==1){
grid[r-1][c]=2;
queue.add(new int[]{r-1,c});
--count;
}
if(c-1>=0&&grid[r][c-1]==1){
grid[r][c-1]=2;
queue.add(new int[]{r,c-1});
--count;
}
if(r+1<R&&grid[r+1][c]==1){
grid[r+1][c]=2;
queue.add(new int[]{r+1,c});
--count;
}
if(c+1<C&&grid[r][c+1]==1){
grid[r][c+1]=2;
queue.add(new int[]{r,c+1});
--count;
}
}
}
if(count>0){ // 说明有到达不了的位置
return -1;
}else
return round;
}
}
滑动窗口
使用滑动窗口的模板，需要回答几个问题。
- 当移动 right 扩大窗口，即加入字符时，应该更新那些数据？
- 什么条件下，窗口应该停止扩大，开始移动 left 缩小窗口？
- 当移动 left 缩小窗口的时候，就是说移除字符时，应该更新那些数据？
-
滑动窗口的模板
```java public void slidingWindow(String s,String t){
HashMap<Character,Integer> need = new HashMap<>(); HashMap<Character,Integer> window = new HashMap<>(); int left = 0,right = 0; int vaild = 0; while (right<s.length()){// c是将要加入滑动窗口的哪个字符。
char c = s.charAt(right);// 右移窗口
right++;// 对窗口内的数据进行一系列的操作。
// Debug 输出位置 System.out.println(“window:[“+left+”,%d]”+right);
while (window need shrink){
// d 是需要移除的哪个字符 char d = s.charAt(left); left++;
// 进行窗口内的数据的变化
}
}
}
<a name="zInJZ"></a>
### [76. 最小覆盖子串](https://leetcode-cn.com/problems/minimum-window-substring/)
[参考资料](https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/)
```java
public String minWindow(String s, String t) {
int left = 0 ,right = 0;
int start = 0; // 开始的位置
int len = Integer.MAX_VALUE;// 偏移的位数
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
// 把 t 中的字符需要的数量做记录。
for(char c:t.toCharArray()){
need.put(c,need.getOrDefault(c,0)+1);
}
int valid = 0; // window 里面符合 need 字符的个数。
while (right<s.length()){
char c = s.charAt(right);
right++;
// 假如这个字符在 need 中，把他出现的频率+1 假如达到了need中需要的数量。则+1；
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if(window.get(c).equals(need.get(c))){
valid++;
}
}
while (valid == need.size()){// need.size() 方法返回的是key的数量。 而不是value的总数。
// 更新一下这个最小的子串的范围。
if(right-left<len){
start = left;
len = right-left;
}
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
// 原来是达标的，现在将left 移除了所以数量还没有达标，vaild--；
if(window.get(d).equals(need.get(d))){
valid--;
}
// 将频率-1
window.put(d,window.get(d)-1);
}
}
}
return
}
567. 字符串的排列
对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：
1、本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，应为排列嘛，显然长度应该是一样的。
2、当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。
至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。
class Solution {
public boolean checkInclusion(String s1, String s2) {
int left = 0,right = 0;
int vaild = 0;
HashMap<Character,Integer> need =new HashMap<>();
HashMap<Character,Integer> window =new HashMap<>();
for(char c:s1.toCharArray()){
need.put(c,need.getOrDefault(c,0)+1);
}
while (right<s2.length()){
char c = s2.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if(window.get(c).equals(need.get(c))){
vaild++;
}
}
while (right-left>=s1.length()){
if(vaild == need.size()){
return true;
}
char d = s2.charAt(left);
left++;
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
vaild--;
}
window.put(d,window.get(d)-1);
}
}
}
return false;
}
}
438. 找到字符串中所有字母异位词
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new LinkedList<>();
int left=0,right = 0;
int vaild = 0;
HashMap<Character,Integer> need = new HashMap<>();
HashMap<Character,Integer> window = new HashMap<>();
for(char c:p.toCharArray()){
need.put(c,need.getOrDefault(c,0)+1);
}
while (right<s.length()){
char c = s.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if(window.get(c).equals(need.get(c))){
vaild++;
}
}
while (right-left>=p.length()){
if(vaild == need.size()){
res.add(left);
}
char d = s.charAt(left);
left++;
if(window.containsKey(d)){
if(need.get(d).equals(window.get(d))){
vaild--;
}
window.put(d,window.get(d)-1);
}
}
}
return res;
}
}
3. 无重复字符的最长子串
和前面的差不多，但是这道题只需要一个map来记录一下。收缩的条件是里面的个数大于1。
把遍历到的每一个字符加入到map里面，记录相应的频次。 只要频次大于1 就说明有重复的字符，需要进行收缩。因为在滑动的时候已经记录了当前的最大值。所以我们需要直接滑动到重复的数那儿，重新开始计算。
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character,Integer> window = new HashMap<>();
int left = 0,right=0;
int valid = 0;
int max = 0;
while (right<s.length()){
char c = s.charAt(right++);
window.put(c,window.getOrDefault(c,0)+1);
while (window.get(c)>1){
char d = s.charAt(left++);
window.put(d,window.get(d)-1);
}
max = Math.max(max,right-left);
}
return max;
}
}
和为s的连续正数序列
思路： 诗使用滑动窗口的方法去做。滑动窗口可以看成数组中框起来的一个部分。在一些数组类题目中，我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边，我们就可以从所有的候选结果中找到最优的结果。
滑动窗口的重要性质是：窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n)O(n)。如果左右边界向左移动的话，这叫做“回溯”，算法的时间复杂度就可能不止 O(n)O(n)。
要用滑动窗口解这道题，我们要回答两个问题：
第一个问题，窗口何时扩大，何时缩小？
第二个问题，滑动窗口能找到全部的解吗？
对于第一个问题，回答非常简单：
当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)[i,j)，那么我们已经找到了一个 ii 开头的序列，也是唯一一个 ii 开头的序列，接下来需要找 i+1i+1 开头的序列，所以窗口的左边界要向右移动
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> res = new LinkedList<>();
int head = 1;
int end = 2;
int sum = 1;
while(head<=target/2){
if(sum>target){
sum-=head;
++head;
}else if(sum<target){
sum+=end;
++end;
}else{
int[] tmp = new int[end-head];
for(int i=0;i<tmp.length;i++){
tmp[i] = head+i;
}
res.add(tmp);
sum-=head;
++head;
}
}
return res.toArray(new int[res.size()][]);
}
}
面试题 17.16. 按摩师
若有收获，就点个赞吧
0 人点赞
