Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int, int> frequency;
        for (char ch: s)
            ++frequency[ch];
        for (int i = 0; i < s.size(); ++i)
            if (frequency[s[i]] == 1)
                return i;
        return -1;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start = 0, total = 0, tank = 0;
        for (int i = 0; i < gas.size(); ++i)
            if ((tank += gas[i] - cost[i]) < 0) {
                start = i + 1;
                total += tank;
                tank = 0;
            }
        return (total + tank) < 0 ? -1 : start;
    }
};

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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        preorder(root, 0, ans);
        return ans;
    }
private:
    void preorder(TreeNode* root, int level, vector<vector<int>>& ans) {
        if (root == nullptr) return;
        if (level >= ans.size())
            ans.push_back(vector<int>());
        auto& row = ans[level];
        if (level % 2 == 0) row.push_back(root->val);
        else row.insert(row.begin(), root->val);
        preorder(root->left, level + 1, ans);
        preorder(root->right, level + 1, 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
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;
        while (!q.empty()) {
            deque<int> row;
            int size = q.size();
            while (size--) {
                auto node = q.front(); q.pop();
                if (leftToRight) row.push_back(node->val);
                else row.push_front(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ans.emplace_back(vector<int>{row.begin(), row.end()});
            leftToRight = !leftToRight;
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size(), first = cost[0], second = cost[1], third, i = 2;
        while (i < n) {
            third = min(first, second) + cost[i++];
            first = second;
            second = third;
        }
        return min(first, second);
    }
};

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
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {\
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                ++five;
            } else if (bill == 10) {
                if (--five < 0) return false;
                ++ten;
            } else {
                if (five > 0 && ten > 0) {
                    --five;
                    --ten;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        for (int r = 0; r < m; ++r)
            dp[r][0] = 1;
        for (int c = 0; c < n; ++c)
            dp[0][c] = 1;
        for (int r = 1; r < m; ++r)
            for (int c = 1; c < n; ++c)
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        return dp[m - 1][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int uniquePaths(int m, int n) {
        int c = min(m, n);
        vector<int> dp(c, 1);
        for (int i = 1; i < max(m, n); ++i)
            for (int j = 1; j < c; ++j)
                dp[j] += dp[j - 1];
        return dp[c - 1];
    }
};
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long ans = 1;
        for (int x = m, y = 1; y < n; ++x, ++y)
            ans = ans * x / y;
        return ans;
    }
};
1
2
3
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, n - 1)

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 String removeDuplicateLetters(String s) {
        boolean[] seen = new boolean[26];
        int[] num = new int[26];
        char[] cs = s.toCharArray();
        for (char c : cs)
            num[c - 'a']++;
        StringBuilder ans = new StringBuilder();
        for (char c : cs) {
            if (!seen[c - 'a']) {
                while (ans.length() > 0 && ans.charAt(ans.length() - 1) > c && num[ans.charAt(ans.length() - 1) - 'a'] > 0) {
                    seen[ans.charAt(ans.length() - 1) - 'a'] = false;
                    ans.deleteCharAt(ans.length() - 1);
                }
                seen[c - 'a'] = true;
                ans.append(c);
            }
            num[c - 'a']--;
        }
        return ans.toString();
    }
}
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:
    string removeDuplicateLetters(string s) {
        vector<bool> seen(26);
        vector<int> num(26);
        for (char c : s)
            ++num[c - 'a'];
        string stk;
        for (char c : s) {
            if (!seen[c - 'a']) {
                while (!stk.empty() && stk.back() > c && num[stk.back() - 'a'] > 0) {
                    seen[stk.back() - 'a'] = false;
                    stk.pop_back();
                }
                seen[c - 'a'] = true;
                stk.push_back(c);
            }
            --num[c - 'a'];
        }
        return stk;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        remain_counter = collections.Counter(s)
        seen = set()

        for c in s:
            if c not in seen:
                while stack and stack[-1] > c and remain_counter[stack[-1]] > 0:
                    seen.discard(stack.pop())
                seen.add(c)
                stack.append(c)
            remain_counter[c] -= 1
        return ''.join(stack)

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        const int n = mountainArr.length();
        int topIndex = findTopIndex(mountainArr, 0, n - 1);
        if (mountainArr.get(topIndex) == target) return topIndex;
        int idx = findFromSortedArr(mountainArr, 0, topIndex - 1, target);
        if (idx >= 0) return idx;
        return findFromReversedArr(mountainArr, topIndex + 1, n - 1, target);
    }
private:
    int findTopIndex(MountainArray& mountainArr, int left, int right) {
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1))
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }

    int findFromSortedArr(MountainArray& mountainArr, int left, int right, int target) {
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (mountainArr.get(mid) < target)
                left = mid + 1;
            else
                right = mid;
        }
        return mountainArr.get(left) == target ? left : -1;
    }

    int findFromReversedArr(MountainArray& mountainArr, int left, int right, int target) {
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if (mountainArr.get(mid) < target)
                right = mid - 1;
            else
                left = mid;
        }
        return mountainArr.get(left) == target ? left : -1;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    char findTheDifference(string s, string t) {
        int bits = 0;
        for (char c : s)
            bits ^= (c - 'a');
        for (char c : t)
            bits ^= (c - 'a');
        return bits + 'a';
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char, int> m;
        for (char c : s)
            ++m[c];
        for (char c : t)
            if (--m[c] < 0)
                return c;
        return ' ';
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    char findTheDifference(string s, string t) {
        int as = 0, at = 0;
        for (char ch: s)
            as += (ch - 'a');
        for (char ch: t)
            at += (ch - 'a');
        return at - as + 'a';
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int cash = 0, hold = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            cash = max(cash, hold + prices[i] - fee);
            hold = max(hold, cash - prices[i]);
        }
        return cash;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int buy = prices[0] + fee;
        int profit = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] + fee < buy) {
                buy = prices[i] + fee;
            } else if (prices[i] > buy) {
                profit += prices[i] - buy;
                buy = prices[i];
            }
        }
        return profit;
    }
};
0%