发表于 | 分类于

Implement the following operations of a queue using stacks.

push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.
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, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

解法1：Two Queue

stack和queue的区别是前者是FILO, 后者是FIFO， 如果用另外一个stack去反倒回来就得到了queue一样的效果。
实现起来，用一个buffer stack存储应该的顺序，peek和pop都应该从buffer中取，如果读取buffer的时候为空的话，则需要把数据从原stack移到buffer。
C++

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
class Queue {
private:
    stack<int> mstack;
    stack<int> buffer;
public:
    // Push element x to the back of queue.
    void push(int x) {
        mstack.push(x);
    }
    // Removes the element from in front of queue.
    void pop(void) {
        if (buffer.empty()) {
            while (!mstack.empty()) {
                buffer.push(mstack.top());
                mstack.pop();
            }
        }
        buffer.pop();
    }
    // Get the front element.
    int peek(void) {
        if (buffer.empty()) {
             while (!mstack.empty()) {
                buffer.push(mstack.top());
                mstack.pop();
            }
        }
        return buffer.top();
    }
    // Return whether the queue is empty.
    bool empty(void) {
        return mstack.empty() && buffer.empty();
    }
};

Java
只有在push的时候，如果当前的stack里面存在元素的话，先把元素存在另外一个stack里面。然后把要push的元素push了之后再把buffer里面的元素放回stack。

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
class MyQueue {
    /** Initialize your data structure here. */
    Stack<Integer> stack;
    public MyQueue() {
        stack = new Stack<Integer>();
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
        Stack<Integer> temp = new Stack<Integer>();
        while (!stack.isEmpty()) {
            temp.push(stack.pop());
        }
        stack.push(x);
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
    }
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return stack.pop();
    }
    /** Get the front element. */
    public int peek() {
        return stack.peek();
    }
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack.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();
 */

发表于 | 分类于

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

解法1：

按照定义，balanced是指left tree和right tree的max height的差值可以小于等于1，同时要满足left tree和right tree都是一个balanced tree。
用返回一个resultSet的办法返回多值，（balanced，maxHeight). 要注意的是返回的时候root的height需要是max(leftHeight, rightHeight) + 1
C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct resultSet {
    bool isBalanced;
    int maxHeight;
    resultSet(bool b, int h): isBalanced(b), maxHeight(h) {}
};
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        resultSet res = helper(root);
        return res.isBalanced;
    }
    resultSet helper(TreeNode* root) {
        if (root == NULL) {
            return resultSet(true, 0);
        }
        if (!root->left && !root->right) {
            return resultSet(true, 1);
        }
        resultSet left = helper(root->left);
        if (!left.isBalanced) {
            return resultSet(false, 0);
        }
        resultSet right = helper(root->right);
        if (!right.isBalanced) {
            return resultSet(false, 0);
        }
        return resultSet(abs(left.maxHeight - right.maxHeight) <= 1, max(left.maxHeight, right.maxHeight) + 1);
    }
};

Java

1

解法2: O(N), 不需要mark node

直接用一个返回值来区分是否是balanced binary tree。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isBalanced(TreeNode root) {
        return depth(root) != -1;
    }
    private int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left);
        if (left == -1) return -1;
        int right = depth(root.right);
        if (right == -1) return -1;
        if (Math.abs(left - right) > 1) return -1;
        return Math.max(left, right) + 1;
    }
}

发表于 | 分类于

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],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

解法1：One Queue

比较基础的BST算法，主要是掌握用一个queue和一个每层的计数器k来维护当前层的node个数
C++

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.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == NULL) {
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int k = q.size();
            vector<int> level;
            for (int i = 0; i < k; ++i) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.push_back(level);
        }
        return res;
    }
};

Java

1

发表于 | 分类于

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

解法1：Dummy Node, O(N) One pass

这题比array的partition容易一些，主要用两个dummy node记录两个list，一个小于x，一个大于等于x。用一个head指针维护现在遍历到的node。最后将两个dummy连在一起就可以了。
C++

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 singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* left = new ListNode(0);
        ListNode* lefttail = left;
        ListNode* right = new ListNode(0);
        ListNode* righttail = right;
        while (head != NULL) {
            ListNode* next = head->next;
            head->next = NULL;
            if (head->val < x) {
                lefttail->next = head;
                lefttail = lefttail->next;
            } else {
                righttail->next = head;
                righttail = righttail->next;
            }
            head = next;
        }
        lefttail->next = right->next;
        ListNode* res = left->next;
        delete left;
        delete right;
        return res;
    }
};

Java

1

发表于 | 分类于

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],
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

解法1：BST + Two container

用按层遍历（one queue）的办法遍历得出每一层的vector，然后放入一个stack，最后按顺序读出vector中的值即可。
C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        stack<vector<int>> temp;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int k = q.size();
            vector<int> level;
            for (int i = 0; i < k; ++i) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            temp.push(level);
        }
        while (!temp.empty()) {
            res.push_back(temp.top());
            temp.pop();
        }
        return res;
    }
};

Java

1

发表于 | 分类于

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1

/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3

Note:
Bonus points if you could solve it both recursively and iteratively.

解法1：Recursive

主要还是分治的思想，对称的意思就是left = right，实际上我们要比较的是left tree 和right tree。
需要满足的条件是left.left = right.right && left.right = right.left
然后不停的递归下去就可以了。
C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        if (root->left == NULL && root->right == NULL) {
            return true;
        }
        return mirror(root->left, root->right);
    }
    bool mirror(TreeNode* left, TreeNode* right) {
        if (left == NULL && right == NULL) {
            return true;
        }
        if (left != NULL && right == NULL) {
            return false;
        }
        if (left == NULL && right != NULL) {
            return false;
        }
        if (left->val != right->val) {
            return false;
        }
        bool leftChild = mirror(left->left, right->right);
        if (!leftChild) return false;
        bool rightChild = mirror(left->right, right->left);
        return rightChild;
    }
};

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 boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }
    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right != null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

解法2：Iteratively

非递归一般需要用额外的数据结构，这里可以想到的是用queue，然后做一个BFS（按层遍历）。和比较是否是same tree很像，唯一不一样的是这里left需要从左往右，而right需要从右往左。
参考了喜唰唰的解法。
C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
       if (!root) return true;
       queue<TreeNode*> left, right;
       left.push(root->left);
       right.push(root->right);
       while(!left.empty() && !right.empty()) {
           TreeNode* lchild = left.front();
           TreeNode* rchild = right.front();
           left.pop();
           right.pop();
           if (!lchild && !rchild) continue;
           if (!lchild && rchild) return false;
           if (lchild && !rchild) return false;
           if (lchild->val != rchild->val) return false;
           left.push(lchild->left);
           left.push(lchild->right);
           right.push(rchild->right);
           right.push(rchild->left);
       }
       if (!left.empty() || !right.empty()) {
           return false;
       }
     return true;
    }
};

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        if ((root.left != null && root.right == null) || (root.right != null && root.left == null)) {
            return false;
        }
        if (root.left == null && root.right == null) return true;
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            if (queue.size() % 2 != 0) return false;
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if ((left.left != null && right.right == null) || (left.left == null && right.right != null)) return false;
            if ((left.right != null && right.left == null) || (left.right == null && right.left != null)) return false;
            if (left.val != right.val) return false;
            if (left.left != null) {
                queue.offer(left.left);
                queue.offer(right.right);
            }
            if (left.right != null) {
                queue.offer(left.right);
                queue.offer(right.left);
            }
        }
        return true;
    }
}

发表于 | 分类于

Sort a linked list using insertion sort.

解法1：Dummy Node, Insertion Sort O(N^2)

这题一开始想不太清楚，但知道应该用dummy node。实际上，dummy node可以作为一个空的list，用一个指针（head）来记录当前想要插入的node，每一个node在dummy指向的list中找到位置后插入。
这样想就比较清晰了。用到的指针有

  1. cur 记录当前插入的node的指针
  2. p 用来遍历已经排序好的dummy指向的那个list
  3. head 用来遍历原list直到end

C++

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.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* dummy = new ListNode(0);
        // For each node, attach to dummy linked list
        while (head != NULL) {
            ListNode* cur = head;
            head = head->next;
            ListNode* p = dummy;
            while (p->next && p->next->val <= cur->val) {
                p = p->next;
            }
            cur->next = p->next;
            p->next = cur;
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};

Java

1

发表于 | 分类于

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

解法1：O(1) Space + O(N) Time, Two pointers

此题初看可以用hashtable来解决，用一个指针一边跑一边放入hashtable，如果跑到见过的node⑩则知道有cycle。
由于follow up中提到了不能用extra space，所以考虑经典的two pointers算法。快慢指针，一个走一步一个走两步，如果在走完之前相遇的话就有cycle。
要注意的是输入的判定，如果为空list的话直接返回false
C++

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};

Java

1

发表于 | 分类于

Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:

“abc” -> “bcd” -> … -> “xyz”
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: [“abc”, “bcd”, “acef”, “xyz”, “az”, “ba”, “a”, “z”],
A solution is:

[
[“abc”,”bcd”,”xyz”],
[“az”,”ba”],
[“acef”],
[“a”,”z”]
]

解法1：Hash Function, Hash Table

此题一看就是用hashtable的一道题，但难点在于什么是hashtable的key，换句话说，要构造出一个function，使得grouped string有相同的key。
思考一下可以得出，如果将每个字符转化为和第一个字符的距离，变可以得出一样的key。这里要注意的是，difference可以是正也可以是负，那么就需要加上25或者是26之后再对26取余来做。
C++
涉及到了几个C++的syntax：

  • access map value：iterator->second, iterator->first
  • insert to the end of a vector: vector.push_back()
    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
    class Solution {
    public:
        vector<vector<string>> groupStrings(vector<string>& strings) {
            unordered_map<string, vector<string>> map;
            for (auto str: strings) {
                string s = "";
                for (auto i : str) {
                    s += std::to_string((i - str[0] + 26) % 26) + " ";
                }
                if (map.find(s) != map.end()) {
                    map[s].push_back(str);
                } else {
                    vector<string> v;
                    v.push_back(str);
                    map[s] = v;
                }
            }
            vector<vector<string>> res;
            for (auto i = map.begin(); i != map.end(); ++i) {
                res.push_back(i->second);
            }
            return res;
        }
    };

Java

1

发表于 | 分类于

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

解法1：Divide and Conquer

按照题意是要构造一个balanced的BST,那么root一定是sorted list的中间的一个点。所以想到了linkedlist求中间点的算法。
如果中间点求到了，那么可以将原list分成左右两个子list，对于每一个子list做相应的操作，左面的list就是左子树，右面的list就是右子树。这是一种分治的思想
C++

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
54
55
56
57
58
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (head == NULL) {
            return NULL;
        }
        if (head->next == NULL) {
            return new TreeNode(head->val);
        }
        ListNode* preMiddle = findPreMiddle(head);
        ListNode* right = preMiddle->next->next;
        TreeNode* root = new TreeNode(preMiddle->next->val);
        // break left and right
        preMiddle->next->next = NULL;
        preMiddle->next = NULL;
        TreeNode* leftTree = sortedListToBST(head);
        TreeNode* rightTree = sortedListToBST(right);
        root->left = leftTree;
        root->right = rightTree;
        return root;
    }
    ListNode* findPreMiddle(ListNode* head) {
        if (head == NULL) {
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != NULL && fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

Java

1