Shawn's Blog

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int rob(vector<int>& nums) {
        const int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        return max(rob(nums, 0, n - 1), rob(nums, 1, n));
    }
    int rob(vector<int>& nums, int start, int end) {
        int pre2 = nums[start], pre1 = max(nums[start], nums[start + 1]), tmp;
        for (int i = start + 2; i < end; ++i) {
            tmp = max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = tmp;
        }
        return max(pre1, pre2);
    }
};

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
31
32
33
34
35
36
37
38
39
class Trie {
private:
    struct TrieNode {
        TrieNode(): is_word(false), children(26, nullptr) {}
        ~TrieNode() {
            for (TrieNode* child : children)
                if (child) delete child;
        }
        bool is_word;
        vector<TrieNode*> children;
    };
    const TrieNode* find(const string& prefix) const {
        const TrieNode* p = root_.get();
        for (const char c : prefix) {
            p = p->children[c - 'a'];
            if (p == nullptr) break;
        }
        return p;
    }
public:
    std::unique_ptr<TrieNode> root_;
    Trie():root_(new TrieNode()) {}
    void insert(string word) {
        TrieNode* p = root_.get();
        for (const char c : word) {
            if (!p->children[c - 'a'])
                p->children[c - 'a'] = new TrieNode();
            p = p->children[c - 'a'];
        }
        p->is_word = true;
    }
    bool search(string word) {
        const TrieNode* p = find(word);
        return p && p->is_word;
    }
    bool startsWith(string prefix) {
        return find(prefix) != nullptr;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
const minDiffInBST = (root) => {
    let ans = Number.MAX_SAFE_INTEGER, prev = -1;
    const dfs = (root) => {
        if (root) {
            dfs(root.left);
            if (prev != -1)
                ans = Math.min(ans, root.val - prev);
            prev = root.val;
            dfs(root.right);
        }
    };
    dfs(root);
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const minDiffInBST = (root) => {
    let ans = Number.MAX_SAFE_INTEGER, prev = -1;
    const stk = [];
    while (stk.length > 0 || root) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        if (prev != -1)
            ans = Math.min(ans, root.val - prev);
        prev = root.val;
        root = root.right;
    }
    return ans;
};

Posted on In 
1
2
3
4
5
6
7
8
const largestNumber = (nums) => {
    const ans = nums.map(a => a.toString())
        // .sort((a, b) => (a + b) - (b + a))
        // .reduce((prev, curr) => curr + prev);
        .sort((a, b) => (b + a) - (a + b))
        .join('')
    return ans[0] == '0' ? '0' : ans;
};

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
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> factors = {2, 3, 5};
        unordered_set<long> seen;
        priority_queue<long, vector<long>, greater<long>> heap;
        seen.insert(1L);
        heap.push(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.top();
            heap.pop();
            ugly = (int) curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (!seen.count(next)) {
                    seen.insert(next);
                    heap.push(next);
                }
            }
        }
        return ugly;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 1) return true;
        vector<int> dp(n + 1);
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = min(min(num2, num3), num5);
            if (dp[i] == num2) p2++;
            if (dp[i] == num3) p3++;
            if (dp[i] == num5) p5++;
        }
        return dp[n];
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) return false;
        int factors[] = {2, 3, 5};
        for (int factor : factors)
            while (n % factor == 0)
                n /= factor;
        return n == 1;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right])
                left = mid + 1;
            else if (nums[mid] > nums[right])
                right = mid;
            else
                --right;
        }
        return nums[left];
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (right + left) / 2;
            if (nums[mid] < nums[right])
                right = mid;
            else
                left = mid + 1;
        }
        return nums[left];
    }
};

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