341. Flatten Nested List Iterator
Posted Updated LeetCode / Medium3 minutes read (About 391 words)

341. Flatten Nested List Iterator

Question

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

  • NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
  • int next() Returns the next integer in the nested list.
  • boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Solution

将所有的NestedInteger展开后加入全局变量队列。

辅助方法buildQueue():
递归，如果当前元素是列表，则向下递归列表内的所有元素。
如果当前元素是单个整数，则将其加入队列。

next():
返回并挤出队列中的下一个元素，返回其整数。

hasNext():
返回队列是否为空。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    Queue<NestedInteger> q;
    public NestedIterator(List<NestedInteger> nestedList) {
        q = new LinkedList<>();
        for(NestedInteger item : nestedList){
            buildQueue(item);
        }
    }
    
    private void buildQueue(NestedInteger ni){
        if(!ni.isInteger()){
            for(NestedInteger item : ni.getList()){
                buildQueue(item);
            }
        }
        else{
            q.offer(ni);
        }
    }

    @Override
    public Integer next() {
        return q.poll().getInteger();
    }

    @Override
    public boolean hasNext() {
        return !q.isEmpty();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */
225. Implement Stack using Queues
Posted Updated LeetCode / Easy2 minutes read (About 366 words)

225. Implement Stack using Queues

Question

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

  • void push(int x) Pushes element x to the top of the stack.

  • int pop() Removes the element on the top of the stack and returns it.

  • int top() Returns the element on the top of the stack.

  • boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

  • You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
  • Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Solution

用两个队列实现栈。一个队列存放压入的元素。

push()

将当前元素加入到第一个队列。

top() & pop()

当需要挤出或者查看栈顶时，第一个队列只保留一个元素，其余元素加入第二个队列。最后一个元素就是栈顶。当第一个队列为空时，交换第一个队列与第二个队列。

empty()

返回两个队列是否均为空。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();
        
    }
    
    public void push(int x) {
        q1.add(x);
    }
    
    public int pop() {
        move();
        return q1.poll();
    }
    
    public int top() {
        move();
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
    
    private void move(){
        if(q1.isEmpty()){
            Queue<Integer> temp = q1;
            q1 = q2;
            q2 = temp;
        }
        while(q1.size() != 1){
            q2.add(q1.poll());
        }
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */
Posted Updated LeetCode / Mediuma minute read (About 217 words)

284. Peeking Iterator

Design an iterator that supports the peek operation on an existing iterator in addition to the hasNext and the next operations.

Implement the PeekingIterator class:

  • PeekingIterator(Iterator nums) Initializes the object with the given integer iterator iterator.
  • int next() Returns the next element in the array and moves the pointer to the next element.
  • boolean hasNext() Returns true if there are still elements in the array.
  • int peek() Returns the next element in the array without moving the pointer.

Note: Each language may have a different implementation of the constructor and Iterator, but they all support the int next() and boolean hasNext() functions.

使用队列储存迭代器里的数据，根据需要返回队列里的数据。

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
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    Queue<Integer> q;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    q = new LinkedList<>();
        while(iterator.hasNext()){
            q.add(iterator.next());
        }
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return q.peek();
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
	    return q.poll();
	}
	
	@Override
	public boolean hasNext() {
	    return !q.isEmpty();
	}
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 228 words)

82. Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

使用队列暂存遍历的节点。
初始化prev为一个dummy节点。
如果当前节点不等于队列里节点的值，则倾倒出队列里的值。如果队列此时只有一个值，则将其添加到prev.next。
遍历完毕后如果队列内只有一个值则将其设置到prev.next。
最后返回dummy.next。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Queue<ListNode> q = new LinkedList();
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        ListNode curr = head; 
        while(curr != null){
            if(q.isEmpty() || curr.val == q.peek().val){
                q.offer(curr);
                curr = curr.next;
            }
            else{
                if(q.size()==1){
                    prev.next = q.poll();
                    prev = prev.next;
                    prev.next = null;
                }
                else{
                    q.clear();   
                }
            }
        }
        
        if(q.size()==1){
            prev.next = q.poll();
        }
        
        return dummy.next;
    }

}
Posted Updated LeetCode / Easya minute read (About 210 words)

897. Increasing Order Search Tree

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

DFS搜索，在递归时将in-order遍历节点，并将其加入队列。
从队列中挤出节点，将上一个节点的右子节点设置为下一个节点。
同时需要将下一个节点的左子节点设置为null。
`

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
/**
 * 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 {
    Queue<TreeNode> q;
    public TreeNode increasingBST(TreeNode root) {
        q = new LinkedList();
        dfs(root);
        TreeNode head = q.poll();
        TreeNode curr = head;
        while(!q.isEmpty()){
            curr.left = null;
            curr.right = q.poll();
            curr = curr.right;
        }
        curr.left = null;
        return head;
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        q.offer(root);
        dfs(root.right);
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 320 words)

232. Implement Queue using Stacks

问题
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.

  • int pop() Removes the element from the front of the queue and returns it.

  • int peek() Returns the element at the front of the queue.

  • boolean empty() Returns true if the queue is empty, false otherwise.
    Notes:

  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

  • Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

创建两个栈。
当入队列时，将元素压入第一个栈。
当出队列或进行其他操作时，如第二个栈为空，则将第一个栈的元素倒出到第二个栈。
此时第二个栈内的内容为顺序。

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
49
50
51
class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
        
    public MyQueue() {
        s1 = new Stack();
        s2 = new Stack();
    }
    
    public void push(int x) {
        s1.add(x);
    }
    
    public int pop() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.pop();
        }
        else{
            return s2.pop();
        }
        
    }
    
    public int peek() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.peek();
        }
        else{
            return s2.peek();
        }
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
Follow

Recents

Archives

Links

×