Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, k = nums1.size() - 1;
        while (j >= 0) {
            if (i < 0 || nums1[i] < nums2[j])
                nums1[k--] = nums2[j--];
            else
                nums1[k--] = nums1[i--];
        }
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int numRabbits(vector<int>& answers) {
        unordered_map<int, int> m;
        for (int y : answers)
            ++m[y];
        int ans = 0;
        for (auto &[y, x] : m)
            ans += (x + y) / (y + 1) * (y + 1);
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof(dp));
        for (size_t i = 1; i <= m; ++i)
            for (size_t j = 1; j <= n; ++j)
                dp[i][j] = (text1[i - 1] == text2[j - 1]) ? 
                    dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
        return dp[m][n];
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) / 2);
            int v = matrix[mid / n][mid % n];
            if (v == target) {
                return true;
            } else if (v < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return false;
    }
};

Posted on Edited on In 
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
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans;
        if (nums.size() != 0) {
            vector<int> cur;
            sort(nums.begin(), nums.end());
            vector<bool> visited(nums.size());
            backtrack(ans, cur, nums, 0, visited);
        }
        return ans;
    }
private:
    void backtrack(vector<vector<int>>& ans, vector<int>& cur, vector<int>& nums, int start, vector<bool>& visited) {
        if (start == nums.size()) {
            ans.emplace_back(cur);
            return;
        }
        if (start == 0 || nums[start] != nums[start - 1] || visited[start - 1]) {
            cur.emplace_back(nums[start]);
            visited[start] = true;
            backtrack(ans, cur, nums, start + 1, visited);
            visited[start] = false;
            cur.pop_back();
        }
        backtrack(ans, cur, nums, start + 1, visited);
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i)
            leftMax[i] = max(leftMax[i - 1], height[i]);
        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i)
            rightMax[i] = max(rightMax[i + 1], height[i]);
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans += min(leftMax[i], rightMax[i]) - height[i];
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<int> stk;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top(); stk.pop();
                if (stk.empty()) break;
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[i], height[left]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }
};
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:
    int trap(vector<int>& height) {
        int n =  height.size();
        if (n < 3) return 0;
        int left = 0, right = n - 1, leftMax = 0, rightMax = 0;
        int ans = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] < leftMax)
                    ans += leftMax - height[left];
                else
                    leftMax = height[left];
                ++left;
            } else {
                if (height[right] < rightMax)
                    ans += rightMax - height[right];
                else
                    rightMax = height[right];
                --right;
            }
        }
        return ans;
    }
};

Posted on Edited on In 
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
class Solution {
public:
    int clumsy(int N) {
        stack<int> stk;
        stk.push(N--);
        int idx = -1;
        while (N) {
            switch (idx = ++idx % 4) {
            case 0:
                stk.top() *= N--;
                break;
            case 1:
                stk.top() /= N--;
                break;
            case 2:
                stk.push(N--);
                break;
            case 3:
                stk.push(-(N--));
            }
        }
        int sum = 0;
        while (!stk.empty()) {
            sum += stk.top();
            stk.pop();
        }
        return sum;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        int ans = 0;
        for (int i = 0; i < 32 && n > 0; ++i) {
            ans |= (n & 1) << (31 - i);
            n >>= 1;
        }
        return ans;
    }
};

Posted on Edited on In 
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 BSTIterator {
private:
    int idx;
    vector<int> v;
    vector<int> inorder(TreeNode *root) {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }
    void inorder(TreeNode* root, vector<int>& v) {
        if (!root) return;
        inorder(root->left, v);
        v.emplace_back(root->val);
        inorder(root->right, v);
    }
public:
    BSTIterator(TreeNode* root): idx(0), v(inorder(root)) {
    }
    
    int next() {
        return v[idx++];
    }
    
    bool hasNext() {
        return idx < v.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
class BSTIterator {
private:
    TreeNode* curr;
    stack<TreeNode*> stk;
public:
    BSTIterator(TreeNode* root): curr(root) {
    }
    
    int next() {
        while (curr) {
            stk.push(curr);
            curr = curr->left;
        }
        curr = stk.top();
        stk.pop();
        int ans = curr->val;
        curr = curr->right;
        return ans;
    }
    
    bool hasNext() {
        return curr || !stk.empty();
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || !head || !head->next) return head;
        int n = 1;
        ListNode* old_tail = head;
        while (old_tail->next) {
            old_tail = old_tail->next;
            ++n;
        }
        if ((k %= n) == 0) return head;
        old_tail->next = head;
        ListNode* new_tail = head;
        for (int i = 0; i < n - k - 1; i++) new_tail = new_tail->next;
        ListNode* new_head = new_tail->next;
        new_tail->next = nullptr;
        return new_head;
    }
};
0%