栈和队列

发表于 | 分类于

20. Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

解题思路：

括号匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public boolean isValid(String s) {
        
        Stack<Character> stack = new Stack<Character>();
        
        for(int i = 0; i < s.length(); ++i){
            
            char c = s.charAt(i);
            // 前括号入栈
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);        
            }
            else{
                //需要栈中有元素，否则没有前括号匹配了，错误
                if(stack.isEmpty()){
                    return false;
                }
                //当c为后括号，需要从stack中取出特定的后括号进行匹配
                char match;
                switch(c){
                    case ')' : match = '('; break;
                    case ']' : match = '['; break;
                    case '}' : match = '{'; break;
                    default  : return false;
                }
                
                if(match != stack.pop()){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Examples：

1
2
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

解题思路：

后缀表达式，遇到数字入栈，遇到标点符号出栈两个数并计算。
注意，计算结果之后，需要重新入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int evalRPN(String[] tokens) {
        
        Stack<Integer> stack = new Stack<Integer>();
        
        for(String s : tokens){
            if(s.equals("+")){
                stack.push(stack.pop() + stack.pop());
            }
            else if(s.equals("*")){
                stack.push(stack.pop() * stack.pop());
            }
            else if(s.equals("-")){
                int v1 = stack.pop();
                int v2 = stack.pop();
                stack.push(v2 - v1);
            }
            else if(s.equals("/")){
                int v1 = stack.pop();
                int v2 = stack.pop();
                stack.push(v2 / v1);
            }
            else{
                stack.push(Integer.parseInt(s));
            }
        }
        
        return stack.pop();
    }
}

71. Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

Example：

1
2
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

解题思路：

当遇到 “..”，需要栈的特性，弹出最后加入的元素
返回的字符串需要FIFO，需要队列的特性
使用LinkedList为最佳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public String simplifyPath(String path) {
        LinkedList<String> list = new LinkedList<String>();
        String []strings = path.split("/");
        
        for(String s : strings){
            //需要判断list为非空
            if(s.equals("..") && list.size() != 0){
                list.removeLast();
            }
            else if(s.equals("..") || s.equals(".") || s.equals("")){
                continue;
            }
            else{
                list.add(s);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(String s : list){
            sb.append("/" + s);
        }
        
        return sb.length() == 0 ? "/" : sb.toString();
    }
}

144. Binary Tree Preorder Traversal

二叉树先序遍历

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> list = new LinkedList<Integer>();
    
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root != null){
            list.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return list;
    }
    
}

迭代版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>();
        if(root == null){
            return list;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            
            //右子树节点，等左子树节点全部被弹出，才会被访问
            if(node.right != null){
                stack.push(node.right);
            }
            
            //左子树节点一放入，马上被弹出
            if(node.left != null){
                stack.push(node.left);
            }
        }
        
        return list;
    }
}

94. Binary Tree Inorder Traversal

二叉树中序遍历

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> list = new LinkedList<Integer>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root != null){
            inorderTraversal(root.left);
            list.add(root.val);
            inorderTraversal(root.right);
        }
        
        return list;
    }
}

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>();
        if(root == null){
            return list;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(root != null || !stack.isEmpty()){
            //对于每个子树，都要先遍历其最左子节点
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            //访问子树的最左节点
            //现在该节点可是看成是子树的根节点，所以访问其右节点
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;
        }
        
        return list;
    }
}

145. Binary Tree Postorder Traversal

二叉树后续遍历

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> list = new LinkedList<Integer>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root != null){
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            list.add(root.val);
        }    
        
        return list;
    }
}

迭代版：

二叉树先序遍历，中左右
二叉树后续遍历，左右中 == Reverse(中右左)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        if(root == null){
            return list;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.addFirst(node.val);
            
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
        
        return list;
    }
}

341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Example 1:

1
2
3
Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

1
2
3
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
```
#### 102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
```java
    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]

解题思路：

二叉树层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list2 = new LinkedList<List<Integer>>();
        if(root == null){
            return list2;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            int cnt = queue.size();
            List<Integer> list = new LinkedList<Integer>();
            while(cnt-- != 0){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null){ queue.offer(node.left); }
                if(node.right != null) { queue.offer(node.right); }
            }
            list2.add(list);
        }
        
        return list2;
    }
}

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its bottom-up level order traversal as:

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]

解题思路：

与上一道题目是一样的，只是List加入list2的时候要前插

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list2 = new LinkedList<List<Integer>>();
        if(root == null){
            return list2;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            int cnt = queue.size();
            LinkedList<Integer> list = new LinkedList<Integer>();
            while(cnt-- != 0){
                TreeNode node = queue.remove();
                list.add(node.val);
                if(node.left != null) { queue.add(node.left); }
                if(node.right != null) { queue.add(node.right); }
            }
            list2.add(0, list);
        }
        
        return list2;
    }
}

103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

解题思路：

之字形打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list2 = new LinkedList<List<Integer>>();
        if(root == null){
            return list2;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        boolean order = false;
        while(!queue.isEmpty()){
            order = !order;
            int cnt = queue.size();
            List<Integer> list = new LinkedList<Integer>();
            //第一次在list添加val, order为true
            while(cnt-- != 0){
                TreeNode node = queue.remove();
                if(order) { list.add(node.val); }
                else { list.add(0, node.val); }
                
                if(node.left != null) { queue.add(node.left); }
                if(node.right != null) { queue.add(node.right); }
            }
            list2.add(list);
        }
        
        return list2;
    }
}

199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

1
2
3
4
5
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

解题思路：

层序遍历
找二叉树每层的最后一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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> list = new ArrayList<Integer>();
        if(root == null){
            return list;
        }   
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            int cnt = queue.size();
            TreeNode node = null;
            while(cnt-- != 0){
                node = queue.remove();
                if(cnt == 0){
                    //每层的最后一个节点
                    list.add(node.val);
                }
                if(node.left != null) { queue.add(node.left); }
                if(node.right != null) { queue.add(node.right); }
            }
        }
        
        return list;
    }
}

279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

解题思路：

图论问题，广度优先搜索问题
寻找满足Ｘ = v1 + v2 + v3 + ….最少的v的个数

示例12

1
2
3
4
5
6
12	中心点
11 | 8 | 3	第一层没有出现０的情况
10 | 7 | 2 || 7 | 4 || 2	第二层没有
9 | 6 | 1 || 6 | 3 || 1 ||| 6 | 3 | || 3 | 0 ||| 1		第三层搜索到0
12 -> 8 -> 4 -> 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int numSquares(int n) {
        Queue<int []> queue = new LinkedList<int []>();   
        queue.add(new int[]{ n, 0});
        boolean []visited = new boolean[n+1];
        visited[n] = true;  //带记忆的搜索，再一层被记录，step值肯定大于前一层的，所以没必要入队
        
        while(!queue.isEmpty()){
            int []A = queue.remove();
            int num = A[0];
            int step = A[1];
            
            int factor = 1;
            while(true){
                int remain = num - factor * factor;
                if(remain < 0){
                    break;
                }
                if(remain == 0){
                    return step + 1;
                }
                if(!visited[remain]){
                    queue.add(new int[]{remain, step+1});
                    visited[remain] = true;                    
                }
                ++factor;
            }
        }
        
        return -1;
    }
}

127. Word Ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  • Only one letter can be changed at a time.
  • Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Example:

1
2
3
4
5
6
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

解题思路:

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //因为word在transform会产生大量的字符串
        //使用dictionary过滤掉无意义的字符串
        HashSet<String> dictionary = new HashSet<String>();
        for(String s: wordList){
            dictionary.add(s);
        }
        Queue<String> queue = new LinkedList<String>(); //保存广度优先搜索的每一层字符串
        Set<String> visited = new HashSet<String>();    //避免搜索重复字符串，可以减少搜索次数
        queue.add(beginWord);
        visited.add(beginWord);
        int length = 1;
        while(!queue.isEmpty()){
            ++length;
            int cnt = queue.size();
            //每一层有cnt个字符串，一一验证
            while(cnt-- != 0){
                char [] chars = queue.remove().toCharArray();
                for(int i = 0; i < chars.length; ++i){
                    char c = chars[i];
                    for(int j = 0; j < 26; ++j){
                        chars[i] = (char)('a' + j);
                        String word = String.valueOf(chars);
                        //只有在dictionary的字符串，才需要验证
                        if(dictionary.contains(word)){
                            if(word.equals(endWord)){
                                return length;
                            }
                            if(!visited.contains(word)){
                                queue.add(word);
                                visited.add(word);
                            }
                        }
                    }
                    chars[i] = c;   //复位
                }
            }
        }
        return 0;
    }
}

126. Word Ladder II

All conditions are as same as the last question，
unless the return

1
2
3
4
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

解题思路:

深度优先搜索

1
2

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example:

Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

解题思路:

HashMap统计数字的频率
最小堆，堆顶最小元素被过滤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        
        //自定义最小堆
        PriorityQueue<int []> pq = new PriorityQueue<int []>(
            new Comparator<int[]>() {
                    @Override
                    public int compare(int[] A1, int[] A2) {
                        return A1[1] == A2[1] ? 0 : (A1[1] < A2[1] ? -1 : 1);
                    }
                }
        );
        //统计每个数的频率
        for(int i : nums){
            freq.put(i, freq.getOrDefault(i, 0) + 1);
        }
        //A[0] ---- 数字 ---- key
        //A[1] ---- 频率 ---- value
        for(Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (pq.size() == k) {
                int[] A = pq.peek();
                if (A[1] < entry.getValue()) {
                    pq.poll();
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            } else {
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            }
        }
        while(!pq.isEmpty()){
            int []A = pq.poll();
            list.add(A[0]);
        }
        return list;
    }
}

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解题思路：

本来是想着把 所有的节点，依次装入优先队列，然后重新组装成链表
结果是会超时的

下面解法的思路是，最小堆每次只有lists.size()个，每次比较的是每个链表的头节点；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> pq = new PriorityQueue(new Comparator<ListNode>(){
            @Override public int compare(ListNode l1, ListNode l2) { 
                return l1.val - l2.val; 
            }
        });
        
        ListNode dummyHead = new ListNode(-1);
        ListNode pre = dummyHead;
        
        for(ListNode cur : lists){
            if(cur != null){
                pq.add(cur);
            }
        }
        
        while(!pq.isEmpty()){
            pre.next = pq.poll();
            pre = pre.next;
            if(pre.next != null){
                pq.add(pre.next);
            }
        }
        
        return dummyHead.next;
    }
}