队列和广度优先搜索

岛屿的个数

给定一个由 '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;
    }
}