Queue

队列的特性是先进先出FIFO

Design Circular Queue

设计环形队列的数据操作类，环形队列的优势在于节省空间，但指针的控制复杂，设计思路重点看isFull & isEmpty这两个方法

class MyCircularQueue {

    private int[] queue;
    private int headP;
    private int tailP;

    public MyCircularQueue(int k) {
        queue = new int[k + 1];
        headP = 0;
        tailP = 0;
        for (int i = 0; i < k + 1; i++) {
            queue[i] = -1;
        }
    }
    //3、既然tailP指向空位，入队列就简单了
    public boolean enQueue(int value) {

        if (!isFull()) {
            queue[tailP] = value;
            tailP = (tailP + 1) % queue.length;
            return true;
        }

        return false;
    }

    //4、出队列时要清空数据（非必须、但有造成内存泄漏的风险）
    public boolean deQueue() {
        if (!isEmpty()) {
            queue[headP] = -1;
            headP = (headP + 1) % queue.length;
            return true;
        }

        return false;
    }

    public int Front() {
        return queue[headP];
    }
    //5、注意指针越界
    public int Rear() {
        return queue[(tailP + queue.length - 1) % queue.length];
    }

    //1、tailP指向的永远是空位，headP指向头元素
    public boolean isEmpty() {
        return headP == tailP;
    }
    //2、这就会浪费一个空间，用来区分Empty、Full的状态
    public boolean isFull() {
        return (tailP + 1) % queue.length == headP;
    }

}

Queue and BFS

由于队列FIFO的性质，BFS广度优先查找一般由Queue来实现

先处理顶层，记录同层的数量，依次处理此层的数据，与其相关的下层加入队尾，从而实现广度优先查找

Number of Islands

用二维数组表示平面，其中1代表岛屿，0代表海，相连岛屿算一个岛，计算平面内共有多少座岛屿

class Solution {

    public int numIslands(char[][] grid) {

        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] != '0') {//找到第一个岛
                    export(grid, i, j);//探索该岛
                    count++;
                }
            }

        }

        return count;
    }

    private void export(char[][] grid, int x, int y) {
        if (x < 0 || y < 0) {//超出地图范围
            return;
        }

        if (x < grid.length && y < grid[x].length && grid[x][y] == '1') {
            grid[x][y] = '0';//将岛屿打小
        } else {
            return;
        }

        //上下左右各方探索
        export(grid, x, y + 1);
        export(grid, x, y - 1);
        export(grid, x + 1, y);
        export(grid, x - 1, y);
    }
    
}

Open the Lock

四位数字密码锁，每次转动一下，已知密码和死亡触发，求解最少的解锁步骤

这种最少的求解算法，多数要用到BFS

class Solution {
    public int openLock(String[] deadends, String target) {

        Set<String> visited = new HashSet<String>();
        Set<String> deadEnds = new HashSet<String>(deadends.length);

        deadEnds.addAll(Arrays.asList(deadends));

        Queue<String> queue = new LinkedList();
        queue.offer("0000");//起始位置
        visited.add("0000");
        int level = 0;

        while (!queue.isEmpty()) {

            int length = queue.size();//每一层要查找的次数

            for (int j = 0; j < length; j++) {

                String poll = queue.poll();
                if (poll.equals(target)) {//命中
                    return level;
                }
                if (deadEnds.contains(poll)) continue;//陷阱！避开

                String cur = new String(poll);

                for (int i = 0; i < 4; i++) {//一共四位，走向每一位的前后
                    char c = cur.charAt(i);
                    String next = cur.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + cur.substring(i + 1);
                    String pre = cur.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + cur.substring(i + 1);
                    //避开陷阱和重复
                    if (!visited.contains(pre) && !deadEnds.contains(pre)) {
                        queue.offer(pre);
                        visited.add(pre);
                    }
                    if (!visited.contains(next) && !deadEnds.contains(next)) {
                        queue.offer(next);
                        visited.add(next);
                    }
                }
            }
            level++;

        }

        return -1;
    }
}

Perfect Squares

给定数字n，求它由最少多少个完全平方数的和组成

两种解法：
一种是纯数学定理【四平方和定理】；
第二种则是动态规划（所采取的），将0-n全部数字找出完全平方数的最少个数

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;

        for (int i = 1; i < dp.length; i++) {//遍历0-n

            int j = 1;
            int min = 5;
            while (i - j * j >= 0) {//计算第i位数字i，完全平方数的最少个数
                min = Math.min(min, dp[i - j * j] + 1);
                j++;
            }
            dp[i] = min;

        }

        return dp[n];
    }
}

Stack

栈的特性是后进先出LIFO

Min Stack

设计简单的栈结构类，能够检索最小值。

难点：正常情况下，入栈时比较最小值，能够保留最小值。问题发生在最小值出栈后，剩余数据中的最小值怎么获取？？

思路：既然次小值、次次小值无法确定，那就想方法将其保留。当出栈为最小值时，栈顶是次小值的话问题就解决了

class MinStack {

    int min = Integer.MAX_VALUE;
    Stack<Integer> stack;

    public MinStack() {
        stack = new Stack();
    }

    public void push(int x) {
        if (x <= min) {//1、入栈发现最小值
            stack.push(min);//2、将次小值先入栈
            min = x;//3、记录最小值
        }
        stack.push(x);//4、再将最小值入栈；5、如果是一般值，则正常入栈，不经过1、2、3
    }//由此就保证了栈内最小值的下方为次小值

    public void pop() {
        if (stack.pop() == min)//出栈值为最小值
            min = stack.pop();//取出次小值，为最小值
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

Valid Parentheses

判断输入的括号是否配对

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        if (s.length() % 2 != 0) return false;//奇数项的话一定不能配对

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {//反向入栈，看后续内容是否匹配栈内内容
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != c) {//不匹配则不能配对
                return false;
            }

        }

        return stack.isEmpty();

    }
}

Daily Temperatures

给出连续几天的温度，计算出，还要等几天，温度才比现在的温度高。

class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<Integer>();//没有找到结果的集合，栈内栈顶永远小于栈底，从上到下是升序
        int[] waits = new int[T.length];//结果集合

        for (int i = 0; i < T.length; i++) {//从第一天开始遍历
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {//今天大于栈内最小元素，则栈顶元素可计算出结果
                int index = stack.pop();
                waits[index] = i - index;//保存结果
            }
            stack.push(i);
        }
        return waits;

    }
}

Evaluate Reverse Polish Notation

这是计算机编译原理中的概念，书中是由计算公式引申到栈内的表示，而这里题目则是反向，给出了栈内表示反推计算公式的结果

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();

        for (String str : tokens) {
            if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
                int num2 = stack.pop();//先出栈的是num2
                int num1 = stack.pop();
                int result = 0;
                if (str.equals("+")) {
                    result = num1 + num2;
                }
                if (str.equals("-")) {
                    result = num1 - num2;
                }
                if (str.equals("*")) {
                    result = num1 * num2;
                }
                if (str.equals("/")) {
                    result = num1 / num2;
                }
                stack.push(result);
            } else {
                stack.push(Integer.valueOf(str));
            }
        }
        return stack.pop();
    }
}

Stack and DFS

由于栈LIFO的性质，DFS深度优先查找一般由Stack来实现

逮到一根线深入（即入栈），碰到南墙就回头（出栈），遇到分叉口再次深入（即入栈），知道得出结果，因此Stack与DFS密不可分

Clone Graph

将无向图深度复制

因为是无向图，所以同一节点可以被多个节点关联，可以使用Map避免同一节点被多次复制的问题

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
    public Node cloneGraph(Node node) {

        Stack<Node> stack = new Stack<Node>();
        HashMap<Node, Node> map = new HashMap<Node, Node>();

        Node root = new Node();//先复制根节点
        root.val = node.val;
        root.neighbors = new ArrayList<Node>();

        map.put(node, root);//记录已复制的节点
        stack.push(node);//记录将要复制其子节点的节点

        while (!stack.isEmpty()) {
            Node node1 = stack.pop();
            for (Node node2 : node1.neighbors) {//子节点
                if (!map.containsKey(node2)) {//已有子节点，避免重复复制
                    Node newNode = new Node();
                    newNode.val = node2.val;
                    newNode.neighbors = new ArrayList<Node>();
                    map.put(node2, newNode);
                    stack.push(node2);
                }
                map.get(node1).neighbors.add(map.get(node2));

            }
        }

        return map.get(node);
    }
}

Target Sum

给定一正整型数组和一目标值，只能通过加减法遍历操作数组内所有项使其结果为目标值，求共有多少种操作方式。

class Solution {
    int result = 0;

    public int findTargetSumWays(int[] nums, int S) {
        helper(nums, 0, S);
        return result;
    }

    private void helper(int[] nums, int position, int S) {//数组、第几位开始、当前结果
        if (position >= nums.length) {//最后一位
            if (S == 0) {//且结果为0
                result++;
            }
            return;
        }

        helper(nums, position + 1, S - nums[position]);//DFS
        helper(nums, position + 1, S + nums[position]);
    }
}

Implement Queue using Stacks

通过使用栈来实现队列，即利用LIFO的数据结构实现FIFO的操作方式

重点：在peek方法，通过左右手倒换来实现

    class MyQueue {

        Stack<Integer> inStack;
        Stack<Integer> outStack;

        public MyQueue() {
            inStack=new Stack<Integer>();
            outStack=new Stack<Integer>();
        }

        public void push(int x) {
            inStack.push(x);
        }

        public int pop() {
            peek();
            return outStack.pop();
        }

        public int peek() {
            if (outStack.isEmpty()) {//将入栈的栈底元素，转到了栈顶
                while (!inStack.isEmpty()) {
                    outStack.push(inStack.pop());
                }
            }
            return outStack.peek();
        }

        public boolean empty() {
            return inStack.isEmpty()&&outStack.isEmpty();
        }
    }

Implement Stack using Queues

通过使用队列来实现栈

class MyStack {

        Queue<Integer> q = new LinkedList<Integer>();

        public void push(int x) {
            q.add(x);

            int n = q.size();
            while (n-- > 1)//每入队一元素，将其前面的元素出队并再次入队，达到新进元素在队首的效果
                q.add(q.poll());
        }

        public int pop() {
            return q.poll();
        }

        public int top() {
            return q.peek();
        }

        public boolean empty() {
            return q.isEmpty();
        }
}

Decode String

看效果比题目描述更直观

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

class Solution {
    public static String decodeString(String s) {
        String res = "";
        Stack<Integer> countStack = new Stack();//记录数字
        Stack<String> resStack = new Stack();//记录字符
        int index = 0;

        while (index < s.length()) {

            if (Character.isDigit(s.charAt(index))) {
                int count = 0;
                while (Character.isDigit(s.charAt(index))) {//多位整数
                    count = count * 10 + (s.charAt(index) - '0');
                    index++;
                }
                countStack.push(count);
            } else if (s.charAt(index) == '[') {//字符的开始
                resStack.push(res);
                res = "";
                index++;
            } else if (s.charAt(index) == ']') {//字符的结束，表示要开始重复拼接字符
                StringBuffer temp = new StringBuffer(resStack.pop());
                int repeat = countStack.pop();
                for (int i = 0; i < repeat; i++) {
                    temp.append(res);
                }
                res = temp.toString();
                index++;
            } else {
                res += s.charAt(index++);
            }

        }

        return res;
    }
}

Flood Fill

泛洪算法，即指定一点，将该点周围与其相同的点统一变换

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {

        int oldColor = image[sr][sc];

        fun(image, sr, sc, newColor, oldColor);

        return image;
    }

    private void fun(int[][] image, int sr, int sc, int newColor, int oldColor) {
        if (sr < 0 || sc < 0) {//越界处理
            return;
        }

        if (sr >= image.length || sc >= image[0].length) {
            return;
        }
        if (oldColor == newColor) {//已处理过，或不需处理的相邻点
            return;
        }
        if (image[sr][sc] == oldColor) {//必须是相同的点
            image[sr][sc] = newColor;
            //四个方向拓展
            fun(image, sr + 1, sc, newColor, oldColor);
            fun(image, sr - 1, sc, newColor, oldColor);
            fun(image, sr, sc + 1, newColor, oldColor);
            fun(image, sr, sc - 1, newColor, oldColor);

        }
    }
}

01 Matrix

二位数组中，求出所有点距离最近0点的距离

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {//当前点本身是0点
                    continue;
                } else {
                    int count = find(matrix, i, j);//找到此点距最近0点的距离
                    matrix[i][j] = count;
                }
            }
        }
        return matrix;
    }

    private int find(int[][] matrix, int r, int c) {//BFS

        Queue<String> queue = new LinkedList<String>();

        queue.offer(r + "-" + c);

        int count = 0;

        while (!queue.isEmpty()) {

            int loop = queue.size();
            for (int i = 0; i < loop; i++) {

                String[] temp = queue.poll().split("-");
                int row = Integer.parseInt(temp[0]);
                int col = Integer.parseInt(temp[1]);

                if (matrix[row][col] == 0) {
                    return count;
                }

                if (row + 1 < matrix.length) {
                    queue.offer((row + 1) + "-" + col);
                }
                if (col + 1 < matrix[0].length) {
                    queue.offer(row + "-" + (col + 1));
                }
                if (row > 0) {
                    queue.offer((row - 1) + "-" + col);
                }
                if (col > 0) {
                    queue.offer(row + "-" + (col - 1));
                }
            }
            count += 1;
        }

        return count;
    }
}

Keys and Rooms

有多间房，每间房内存在开启其他房间的钥匙，问是否能进入所有房间

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {

        Queue<Integer> queue = new LinkedList<Integer>();//手上有的钥匙
        Set<Integer> visited = new HashSet<Integer>();//已进过的房间

        for (int i = 0; i < rooms.get(0).size(); i++) {
            queue.offer(rooms.get(0).get(i));//拿到房间0的所有钥匙
        }
        visited.add(0);//去过房间0

        while (!queue.isEmpty()) {

            int room = queue.poll();
            visited.add(room);//拿钥匙去其他房间
            List<Integer> keys = rooms.get(room);
            for (int i = 0; i < keys.size(); i++) {//并将其他房间的钥匙拿入手中
                if (!visited.contains(keys.get(i))) {
                    queue.offer(keys.get(i));
                }
            }

        }

        return visited.size() == rooms.size();//去过的房间数等于房间总数则表示能够遍历所有房间，反之不能
    }
}