队列和广度优先搜索

---

岛屿的个数

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/872/

解题思路：广度优先，从某个为1的点开始，广度优先搜索他附近所有为1的点，将这些点的值改为2防止重复。计算有多少次将相邻的1改为2的次数，即为岛屿的次数。

class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) return 0 ; int row = grid.length;//行数 int column = grid[0].length;//列数 int count = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < column; j++) { if (grid[i][j] == '1'){ count ++; combine(grid,i,j); } } } return count; } public static void combine(char[][] grid, int x, int y){ grid[x][y] = '2'; if (x > grid.length-1 && y > grid[0].length-1 ) { return; } if (x < grid.length-1 && grid[x+1][y] == '1') { //向下 combine(grid,x+1,y); } if (y < grid[0].length-1 && grid[x][y+1] == '1'){ //向右 combine(grid,x,y+1); } if (x > 0 && grid[x-1][y] == '1' ){ //向上 combine(grid,x-1,y); } if (y > 0 && grid[x][y-1] == '1') { //向左 combine(grid,x,y-1); } } } 

---

打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/873/

解题思路：将这道题看作是一道迷宫题，每次找一个数字当前能一步到的其他所有邻居数字，次数加1，所有邻居数字再找邻居数字的邻居数字，直到找到一个正确路径。

package com.ice.leetcode; import java.util.*; public class Solution { public static void main(String[] args) { String[] deadends = {"8887","8889","8878","8898","8788","8988","7888","9888"}; String target = "8888"; int count = openLock(deadends, target); System.out.println(count); } public static int openLock(String[] deadends, String target) { String start = "0000"; List<String> visited = new ArrayList<String>(); visited.add(start); Queue<String> queue = new LinkedList<String>(); int count = 0; queue.offer(start); while (!queue.isEmpty()) { int len = queue.size(); for (int i = 0; i < len; i++) { String top = queue.peek(); queue.poll(); List<String> neibors = findNeibors(top); for (String neibor:neibors) { if (target.equals(neibor)) { count++; return count; } if (findString(visited, neibor)) { continue; } if (!findString(Arrays.asList(deadends), neibor)) { visited.add(neibor); queue.offer(neibor); } } } count++; } return -1; } public static List<String> findNeibors(String s) { String temp = s; List<String> result = new ArrayList<>(); for (int i = 0; i < s.length(); i++) { char[] charTemp = temp.toCharArray(); charTemp[i] = String.valueOf((Integer.parseInt(String.valueOf(charTemp[i])) + 1) % 10).toCharArray()[0]; // charTemp[i] = (char) ((Integer.parseInt(String.valueOf(charTemp[i])) + 1) % 10); result.add(String.valueOf(charTemp)); charTemp[i] = String.valueOf((Integer.parseInt(String.valueOf(charTemp[i])) + 8) % 10).toCharArray()[0]; result.add(String.valueOf(charTemp)); } return result; } public static boolean findString(List<String> tofind, String s) { for (String temp : tofind) { if (s.equals(temp)) { return true; } } return false; } } 

---

完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/874/

解题思路：这道题和上一道打开转盘锁思路基本一样，同样是使用广度优先，每遍历一层将count++。不同点在于，本题每层将一个数拆成一个完全平方数和另一个数之和，每次将另一个数加入队列，判断另一个数是否为完全平方数，否则，广度搜索他的下一层。

import static java.lang.Math.sqrt; class Solution { public int numSquares(int n) { int count = 0; Queue<Integer> queue = new LinkedList<>(); if(isSquare(n)){ return 1; } queue.offer(n); while(!queue.isEmpty()){ int len = queue.size(); for (int z=0;z<len;z++){ int top = queue.peek(); queue.poll(); for(int i=0;i<=sqrt(top);i++){ int m = top-i*i; if(isSquare(m)){ count +=2; return count; } if(m==top){ continue; } queue.offer(m); } } count++; } return count; } public static boolean isSquare(int n){ double temp = sqrt(n); int m = (int) temp; return m*m==n; } } 

栈和深度优先搜索

---

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

解题思路：本题较简单，利用堆栈，遇到右括号即一直出栈，判断括号是否匹配

class Solution { public boolean isValid(String s){ Stack<String> stack = new Stack<String>(); for(int i =0;i<s.length();i++){ String temp = s.substring(i,i+1); if(temp.equals("}")||temp.equals("]")||temp.equals(")")){ if(stack.empty()){ return false; } while (!stack.empty()){ String top = stack.peek(); stack.pop(); if((top.equals("{")||top.equals("[")||top.equals("("))){ if(!matchBrackets(top,temp)){ return false; }else { break; } } } }else { stack.push(temp); } } if(stack.isEmpty()){ return true; } return false; } public static boolean matchBrackets(String a,String b){ if( (a.equals("{")&&b.equals("}")) || (a.equals("[")&&b.equals("]")) || (a.equals("(")&&b.equals(")")) ){ return true; } return false; } } 

---

每日温度

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高，请输入 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。

https://leetcode-cn.com/explore/learn/card/queue-stack/218/stack-last-in-first-out-data-structure/879/

解题思路：本题利用栈，将气温不断入栈，判断下一个气温是否比栈顶的气温高，如果高，则不断出栈直到不比栈顶的温度高，如果，并逐个计算每个出栈元素与这个比他们高的气温的差值天数，最后将这个气温入栈，寻找下一个比他高的气温。直到栈空。

class Solution { public int[] dailyTemperatures(int[] temperatures) { Stack<Entry> stack = new Stack<Entry>(); int[] res = new int[temperatures.length]; for (int i = 0; i < temperatures.length; i ++) { if (stack.isEmpty()) { stack.push(new Entry(temperatures[i], i)); continue; } if (temperatures[i] <= stack.peek().val) stack.push(new Entry(temperatures[i], i)); else { int j = 1; while (!stack.isEmpty() && temperatures[i] > stack.peek().val) { Entry tmp = stack.pop(); res[tmp.index] = i - tmp.index; } stack.push(new Entry(temperatures[i], i)); } } return res; } private class Entry { public int val; public int index; public Entry(int val, int index) { this.val = val; this.index = index; } } } 

---

逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

https://leetcode-cn.com/explore/learn/card/queue-stack/218/stack-last-in-first-out-data-structure/880/

解题思路：本题很简单，不断入栈，遇到运算符就出栈前两位进行运算即可

class Solution { public int evalRPN(String[] tokens){ Stack<String> stack = new Stack<>(); for(int i =0;i<tokens.length;i++){ if(isSimbol(tokens[i])){ int temp1 = Integer.parseInt(stack.pop()); int temp2 = Integer.parseInt(stack.pop()); if(tokens[i].equals("+")){ stack.push(String.valueOf(temp1+temp2)); } if(tokens[i].equals("-")){ stack.push(String.valueOf(temp2-temp1)); } if(tokens[i].equals("*")){ stack.push(String.valueOf(temp1*temp2)); } if(tokens[i].equals("/")){ stack.push(String.valueOf(temp2/temp1)); } }else { stack.push(tokens[i]); } } return Integer.parseInt(stack.pop()); } public static boolean isSimbol(String s){ if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){ return true; } return false; } }