Shawn's Blog

Posted on Edited 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 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* 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 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
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 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
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 Edited 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 Edited 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 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
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 Edited 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;
    }
};

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
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (left == right) return head;
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* prev = dummyHead;
        int i = 1;
        for (; i < left; ++i)
            prev = prev->next;
        ListNode *conn = prev, *tail = prev->next ,*curr = prev->next;
        while (i++ <= right) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        if (conn) conn->next = prev;
        else dummyHead->next = prev;
        tail->next = curr;
        return dummyHead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (left == right) return head;
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* prev = dummyHead;
        int i = 1;
        for (; i < left; ++i)
            prev = prev->next;
        ListNode *curr = prev->next, *next;
        while (i++ < right) {
            next = curr->next;
            curr->next = next->next;
            next->next = prev->next;
            prev->next = next;
        }
        return dummyHead->next;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numDistinct(string s, string t) {
        const int m = s.size(), n = t.size();
        if (m < n) return 0;
        vector<vector<long>> dp(m + 1, vector<long>(n + 1));
        for (int i = 0; i <= m; ++i)
            dp[i][n] = 1;
        for (int i = m - 1; i >= 0; --i)
            for (int j = n - 1; j >= 0; --j)
                dp[i][j] = dp[i + 1][j] + (s[i] == t[j] ? dp[i + 1][j + 1] : 0);
        return dp[0][0];
    }
};
0%