Shawn's Blog

Posted 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 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;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return head;
        ListNode* curr = head;
        while (curr->next)
            if (curr->val == curr->next->val)
                curr->next = curr->next->next;
            else
                curr = curr->next;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next)
            return head;
        while (head->next && head->next->val == head->val)
            head = head->next;
        head->next = deleteDuplicates(head->next);
        return head;
    }
};

Posted 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* deleteDuplicates(ListNode* head) {
        if (!head) return head;
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* curr = dummyHead;
        while (curr->next && curr->next->next) {
            if (curr->next->val == curr->next->next->val) {
                int x = curr->next->val;
                curr->next = curr->next->next->next;
                while(curr->next && curr->next->val == x)
                    curr->next = curr->next->next;
            } else {
                curr = curr->next;
            }
        }
        return dummyHead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;
        if (head->val != head->next->val) {
            head->next = deleteDuplicates(head->next);
            return head;
        }
        int x = head->val;
        head = head->next->next;
        while (head != nullptr && head->val == x)
            head = head->next;
        return deleteDuplicates(head);
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        stack<int> candidate_k;
        candidate_k.push(nums[n - 1]);
        int max_k = INT_MIN;
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < max_k) {
                return true;
            }
            while (!candidate_k.empty() && nums[i] > candidate_k.top()) {
                max_k = candidate_k.top();
                candidate_k.pop();
            }
            if (nums[i] > max_k) {
                candidate_k.push(nums[i]);
            }
        }
        return false;
    }
};

Posted 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
class NestedIterator {
private:
    stack<pair<vector<NestedInteger>::iterator, vector<NestedInteger>::iterator>> stk;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        stk.emplace(nestedList.begin(), nestedList.end());
    }
    int next() {
        return stk.top().first++->getInteger();
    }
    bool hasNext() {
        while (!stk.empty()) {
            auto &p = stk.top();
            if (p.first == p.second) {
                stk.pop();
                continue;
            }
            if (p.first->isInteger())
                return true;
            auto &lst = p.first++->getList();
            stk.emplace(lst.begin(), lst.end());
        }
        return false;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            n &= n - 1;
            ans++;
        }
        return ans;
    }
}

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> row(m), col(n);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (!matrix[i][j])
                    row[i] = col[j] = true;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (row[i] || col[j])
                    matrix[i][j] = 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
28
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false, flag_row0 = false;
        for (int i = 0; i < m; i++)
            if (!matrix[i][0])
                flag_col0 = true;
        for (int j = 0; j < n; j++)
            if (!matrix[0][j])
                flag_row0 = true;
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (!matrix[i][j])
                    matrix[i][0] = matrix[0][j] = 0;
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (!matrix[i][0] || !matrix[0][j])
                    matrix[i][j] = 0;
        if (flag_col0)
            for (int i = 0; i < m; i++)
                matrix[i][0] = 0;
        if (flag_row0)
            for (int j = 0; j < n; j++)
                matrix[0][j] = 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0])
                flag_col0 = true;
            for (int j = 1; j < n; j++)
                if (!matrix[i][j])
                    matrix[i][0] = matrix[0][j] = 0;
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++)
                if (!matrix[i][0] || !matrix[0][j])
                    matrix[i][j] = 0;
            if (flag_col0)
                matrix[i][0] = 0;
        }
    }
};

Posted 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
30
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        int ans = 0;
        for (string& token : tokens) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int num2 = stk.top(); stk.pop();
                int num1 = stk.top(); stk.pop();
                switch (token[0]) {
                    case '+':
                        stk.push(num1 + num2);
                        break;
                    case '-':
                        stk.push(num1 - num2);
                        break;
                    case '*':
                        stk.push(num1 * num2);
                        break;
                    case '/':
                        stk.push(num1 / num2);
                        break;
                }
            } else {
                stk.push(atoi(token.c_str()));
            }
        }
        return stk.top();
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class ParkingSystem {
private:
    int b, m, s;
public:
    ParkingSystem(int big, int medium, int small): b(big), m(medium), s(small) {
    }
    bool addCar(int carType) {
        switch (carType) {
            case 1:
                return b-- > 0;
            case 2:
                return m-- > 0;
            case 3:
                return s-- > 0;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class ParkingSystem {
private:
    int counts;
public:
    ParkingSystem(int big, int medium, int small) {
        counts = (small << 20) | (medium << 10) | big;
    }
    bool addCar(int carType) {
        int bits = (carType - 1) * 10;
        if ((counts >> bits) & 0b1111111111) {
            counts -= 1 << bits;
            return true;
        }
        return false;
    }
};
0%