Mind palace

some thoughts

0%

Posted on In Disqus:
Symbols count in article: 542 Reading time ≈ 1 mins.

O(n) time O(1) space

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto slow(head), fast(head);
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                break;
        }
        if (!fast || !fast->next) return nullptr; // 有可能没有cycle
        while (head != slow) {
            head = head->next;
            slow = slow->next;
        }
        return head;
    }
};

Posted on In Disqus:
Symbols count in article: 729 Reading time ≈ 1 mins.

BFS O(n)

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
/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode *> q{{root}};
        while (!q.empty()) {
            res.push_back({});
            for (int i = q.size(); i > 0; --i) {
                auto x = q.front(); q.pop();
                if (x) {
                    res.back().push_back(x->val);
                    q.push(x->left);
                    q.push(x->right);
                }
            }
            if (!(res.size() & 1)) {
                reverse(begin(res.back()), end(res.back()));
            }
        }
        res.pop_back();
        return res;
    }
};

Posted on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 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* invertTree(TreeNode* root) {
        if (!root) return root;
        auto t = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(t);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 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* invertTree(TreeNode* root) {
        if (!root) return root;
        auto l = invertTree(root->left);
        auto r = invertTree(root->right);
        root->left = r;
        root->right = l;
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 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* & invertTree(TreeNode* &root) { // 必须返回ref，否则不能swap
        if (!root) return root;
        swap(invertTree(root->left), invertTree(root->right));
        return root;
    }
};

Posted on In Disqus:
Symbols count in article: 906 Reading time ≈ 1 mins.

两个栈，s相当于queue的后半部分，q相当于queue的前半部分，amortized O(1)

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
class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        s.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        adjust();
        int res = q.top();
        q.pop();
        return res;
    }

    /** Get the front element. */
    int peek() {
        adjust();
        return q.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s.empty() && q.empty();
    }

    void adjust() {
        if (q.empty()) { // 这行很重要，不需要每次都调整
            while (!s.empty()) {
                q.push(s.top());
                s.pop();
            }
        }
    }

    stack<int> s;
    stack<int> q;
};

/**
 * 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();
 * bool param_4 = obj.empty();
 */

Posted on In Disqus:
Symbols count in article: 300 Reading time ≈ 1 mins.

O(logn) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size(), l = 0, r = n - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) return m;
            if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }
};

Posted on In Disqus:
Symbols count in article: 661 Reading time ≈ 1 mins.

O(32) time
把两个数相加的结果拆成两部分 一部分是每个bit的无进位和 一部分是进位 不考虑进位的话每一bit的和就是异或的结果 每一个进位就是两个数相与再左移一位即可
必须用unsigned因为runtime error: left shift of negative value -2147483648，对INT_MIN左移位。不能对负数进行左移，就是说最高位符号位必须要为0，才能左移
因为左移以后要补0 所以最多32个iteration

1
2
3
4
5
6
class Solution {
public:
    int getSum(int a, int b) {
        return b == 0 ? a : getSum(a ^ b, (unsigned)(a & b) << 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int getSum(int a, int b) {
        int res = 0;
        int c = 0;
        for (int i = 0; i < 32 && (a || b || c); ++i, a >>= 1, b >>= 1) {
            int a_bit = (a & 1);
            int b_bit = (b & 1);
            int sum_bit = a_bit ^ b_bit ^ c;
            c = (a_bit & b_bit) | (b_bit & c) | (a_bit & c);
            res |= (sum_bit << i);
        }
        return res;
    }
};

Posted on In Disqus:
Symbols count in article: 231 Reading time ≈ 1 mins.

O(n) time O(n) space
朴素解法即可

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for (int x : nums) {
            if (s.count(x)) return true;
            s.insert(x);
        }
        return false;
    }
};

Posted on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

binary search O(logn) on avg
O(n) worst case [1, 1, …, 1, 0, 1, 1, …, 1] search 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
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) return true;
            if (nums[l] < nums[m]) {
                if (nums[l] <= target && target < nums[m]) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            } else if (nums[l] > nums[m]) {
                if (nums[m] < target && target <= nums[r]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            } else {
                ++l; // 因为nums[m]不是target而nums[m] == nums[l]，所以++l来缩小搜索范围
            }
        }
        return false;
    }
};

worst case [0, 1, 1, 1, …, 1, 1]

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
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) return true;
            if (nums[m] > nums[r]) {
                if (nums[l] <= target && target < nums[m]) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            } else if (nums[m] < nums[r]) {
                if (nums[m] < target && target <= nums[r]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            } else {
                --r;
            }
        }
        return false;
    }
};

Posted on In Disqus:
Symbols count in article: 208 Reading time ≈ 1 mins.

扫描线 O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxDepth(string s) {
        int res = 0, cnt = 0;
        for (char c : s) {
            cnt += c == ')' ? -1 : (c == '(');
            res = max(res, cnt);
        }
        return res;
    }
};

Posted on In Disqus:
Symbols count in article: 273 Reading time ≈ 1 mins.

O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int sumOfUnique(vector<int>& nums) {
        unordered_map<int, int> m;
        for (int x : nums) {
            ++m[x];
        }
        int res = 0;
        for (auto &[x, cnt] : m) {
            if (cnt == 1) {
                res += x;
            }
        }
        return res;
    }
};