1209. Remove All Adjacent Duplicates in String II
Posted Updated LeetCode / Medium2 minutes read (About 365 words)

1209. Remove All Adjacent Duplicates in String II

Question

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Solution

用一个栈保存当前的字符，同时建立一个cnt[]数组记录当前字符连续出现的次数。

遍历字符串。

如果当前的字符与栈顶的字符相同时，获取数组中记录的当前连续次数lastCount并加一。
如果lastCount等于k，则匹配到了足够的字符，去掉栈顶的k - 1个元素。
否则将字符串加入栈顶，记录当前位置的出现次数lastCount。

如果当前字符与栈顶字符不同，则将字符直接加入栈顶，记录当前位置的cnt[dq.size()]为1。

最后将栈内元素倒序组成字符串。由于需要这一步操作，因此之前的栈采用双端队列实现。

Code

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 String removeDuplicates(String s, int k) {
        Deque<Character> dq = new LinkedList<Character>();
        int[] cnt = new int[s.length()+1];

        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(i > 0 && !dq.isEmpty() && dq.peek() == c){
                int lastCount = cnt[dq.size()];
                lastCount++;
                if(lastCount == k){
                    while(lastCount != 1){
                        dq.removeFirst();
                        lastCount--;
                    }
                }
                else{
                    dq.offerFirst(c);
                    cnt[dq.size()] = lastCount;
                }
            }
            else{
                dq.offerFirst(c);
                cnt[dq.size()] = 1;
            }
        }
        
        StringBuffer sb = new StringBuffer();
        while(!dq.isEmpty()){
            sb.append(dq.removeLast());
        }
        return sb.toString();
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 463 words)

103. Binary Tree Zigzag Level Order Traversal

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

BFS搜索，每次遍历挤出整层的节点。
根据真值reverse来判断列表顺序。
当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
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Deque<TreeNode> q = new LinkedList<>();
        q.add(root);
        int size = 1;
        boolean reverse = false;
        
        while(!q.isEmpty()){
            List<Integer> level = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(reverse){
                    level.add(0, curr.val);
                } 
                else{
                    level.add(curr.val);
                } 
                if(curr.left != null) q.add(curr.left);
                if(curr.right != null) q.add(curr.right);
                    
            }

            reverse = !reverse;
            ret.add(level);
            size = q.size();
        }
        return ret;
    }
}

双端队列，根据真值reverse来判断是取队头还是取队尾。
每层级需要遍历所有的节点。
注意添加节点时也需要根据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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Deque<TreeNode> dq = new LinkedList<>();
        dq.add(root);
        int size = 1;
        boolean reverse = false;
        
        while(!dq.isEmpty()){
            List<Integer> temp = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                if(reverse){
                    TreeNode curr = dq.removeLast();
                    if(curr.right != null) dq.offerFirst(curr.right);
                    if(curr.left != null) dq.offerFirst(curr.left);
                    temp.add(curr.val);
                } 
                else{
                    TreeNode curr = dq.removeFirst();
                    if(curr.left != null) dq.offerLast(curr.left);
                    if(curr.right != null) dq.offerLast(curr.right);
                    temp.add(curr.val);
                } 
            }

            reverse = !reverse;
            ret.add(temp);
            size = dq.size();
        }
        return ret;
    }
}
Follow

Recents

Archives

Links

×