队列和广度优先搜索
岛屿的个数
给定一个由 '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] 范围内的整数。
解题思路：本题利用栈，将气温不断入栈，判断下一个气温是否比栈顶的气温高，如果高，则不断出栈直到不比栈顶的温度高，如果，并逐个计算每个出栈元素与这个比他们高的气温的差值天数，最后将这个气温入栈，寻找下一个比他高的气温。直到栈空。
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 的情况。
解题思路：本题很简单，不断入栈，遇到运算符就出栈前两位进行运算即可
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;
}
}