LeetCode220(2021.4.17)

LC220. 存在重复元素 III

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int> &nums, int k, int t) {
        set<long long> st;
        for (int i = 0; i < nums.size(); i++) {
            auto lb = st.lower_bound((long long) nums[i] - t);
            if (lb != st.end() && *lb <= (long long) nums[i] + t) return true;
            st.insert(nums[i]);
            if (i >= k) st.erase(nums[i - k]);
        }
        return false;
    }
};

LeetCode87(2021.4.16)

LC87. 扰乱字符串

class Solution:
    @functools.lru_cache(None)
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)
        if n == 0: return True
        if n == 1: return s1 == s2
        if sorted(s1) != sorted(s2):
            return False
        for i in range(1, n):
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
                return True
            elif self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):
                return True
        return False

LeetCode213(2021.4.15)

LC213. 打家劫舍 II

class Solution {
public:
    int rob(vector<int> &nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        //取第一间
        int fst = nums[0], sec1 = max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; ++i) {
            int tmp = sec1;
            sec1 = max(fst + nums[i], sec1), fst = tmp;
        }
        //取最后一间
        int sec2 = max(nums[1], nums[2]);
        fst = nums[1];
        for (int i = 3; i < n; ++i) {
            int tmp = sec2;
            sec2 = max(fst + nums[i], sec2), fst = tmp;
        }
        return max(sec1, sec2);
    }
};

LeetCode208(2021.4.14)

LC208. 实现 Trie (前缀树)

class Trie {
private:
    vector<Trie *> children;
    bool isEnd;

    Trie *searchPrefix(string prefix) {
        Trie *node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie *node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie *node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};

LeetCode783(2021.4.13)

LC783. 二叉搜索树节点最小距离

class Solution {
public:
    void dfs(TreeNode *root, int &pre, int &ans) {
        if (root == nullptr) {
            return;
        }
        dfs(root->left, pre, ans);
        if (pre == -1) {
            pre = root->val;
        }
        else {
            ans = min(ans, root->val - pre);
            pre = root->val;
        }
        dfs(root->right, pre, ans);
    }

    int minDiffInBST(TreeNode *root) {
        int ans = INT_MAX, pre = -1;
        dfs(root, pre, ans); //中序遍历,维护最小差值
        return ans;
    }
};

LeetCode179(2021.4.12)

LC179. 最大数

class Solution {
public:
    static bool cmp(string a, string b) {
        return a + b > b + a;
    }

    string largestNumber(vector<int> &nums) {
        vector<string> numstr;
        for (int i:nums) numstr.push_back(to_string(i));
        sort(numstr.begin(), numstr.end(), cmp);
        if (numstr[0] == "0") return numstr[0];
        string res = "";
        for (string i:numstr) res += i;
        return res;
    }
};

LeetCode264(2021.4.11)

LC264. 丑数 II

class Solution {
public:
    int nthUglyNumber(int n) {
        int nums[3] = {2, 3, 5};
        set<long long> s;
        priority_queue<long long, vector<long long>, greater<long long>> q;
        s.insert(1), q.push(1);

        for (int i = 1; i <= n; ++i) {
            long long tmp = q.top();
            q.pop();
            if (i == n) return tmp;
            for (int j = 0; j < 3; ++j) {
                long long tp = nums[j] * tmp;
                if (!s.count(tp)) s.insert(tp), q.push(tp);
            }
        }
        return 0;
    }
};