LeetCode872(2021.5.10)

LC872. 叶子相似的树

class Solution {
public:
    void dfs(TreeNode* node, vector<int>& seq) {
        if (!node->left && !node->right) seq.push_back(node->val);
        else {
            if (node->left) dfs(node->left, seq);
            if (node->right) dfs(node->right, seq);
        }
    }

    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> seq1, seq2;
        if (root1) dfs(root1, seq1);
        if (root2) dfs(root2, seq2);
        return seq1 == seq2;
    }
};

LeetCode1482(2021.5.9)

LC1482. 制作 m 束花所需的最少天数

class Solution {
public:
    int n, m, k;
    int inf = 0x3f3f3f3f;

    bool ck(vector<int> nums, int mid){
        int cnt = 0;
        for(int i = 0; i < n && cnt < m;){
            int cur = nums[i] <= mid ? 1 : 0;
            int j = i;
            if(cur){
                while(cur < k && j + 1 < n && nums[j + 1] <= mid) j++, cur++;
                if(cur == k) cnt++;
                i = j + 1;
            }
            else i++;
        }
        return cnt >= m;
    }

    int minDays(vector<int>& bloomDay, int t_m, int t_k) {
        m = t_m, k = t_k;
        n = bloomDay.size();
        if(n < m * k) return -1;
        int l = 0, r = inf;
        while(l < r){
            int mid = l + r >> 1;
            if(ck(bloomDay, mid)) r = mid;
            else l = mid + 1;
        }
        return ck(bloomDay, l) ? l : -1;
    }
};

LeetCode1723(2021.5.8)

LC1723. 完成所有工作的最短时间

class Solution {
public:
    int res = 0x3f3f3f3f;

    void dfs(vector<int> jobs, int i, vector<int>worker, int maxi){
        if (i == jobs.size()) {
            res = min(res, maxi);
            return;
        }
        set<int> st;
        for (int j = 0; j < worker.size(); ++j) {
            if (st.find(worker[j]) != st.end()) continue;
            st.insert(worker[j]);
            if (worker[j] + jobs[i] >= res) continue;
            worker[j] += jobs[i];
            dfs(jobs, i + 1, worker, max(worker[j], maxi));
            worker[j] -= jobs[i];
        }
    }

    int minimumTimeRequired(vector<int>& jobs, int k) {
        vector<int> x(k);
        dfs(jobs, 0, x, 0);
        return res;
    }
};

LeetCode740(2021.5.5)

LC740. 删除并获得点数

class Solution {
public:
    int rob(vector<int> &nums) {
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

    int deleteAndEarn(vector<int> &nums) {
        vector<int> sum(10010);
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }
};

LeetCode1473(2021.5.4)

LC1473. 粉刷房子 III

class Solution {
private:
    static constexpr int INFTY = 0x3f3f3f3f;

    using TIII = tuple<int, int, int>;

public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        for (int& c: houses) {
            --c;
        }

        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(target, INFTY)));
        vector<vector<TIII>> best(m, vector<TIII>(target, {INFTY, -1, INFTY}));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (houses[i] != -1 && houses[i] != j) {
                    continue;
                }
                
                for (int k = 0; k < target; ++k) {
                    if (i == 0) {
                        if (k == 0) {
                            dp[i][j][k] = 0;
                        }
                    }
                    else {
                        dp[i][j][k] = dp[i - 1][j][k];
                        if (k > 0) {
                            auto&& [first, first_idx, second] = best[i - 1][k - 1];
                            dp[i][j][k] = min(dp[i][j][k], (j == first_idx ? second : first));
                        }
                    }

                    if (dp[i][j][k] != INFTY && houses[i] == -1) {
                        dp[i][j][k] += cost[i][j];
                    }

                    auto&& [first, first_idx, second] = best[i][k];
                    if (dp[i][j][k] < first) {
                        second = first;
                        first = dp[i][j][k];
                        first_idx = j;
                    }
                    else if (dp[i][j][k] < second) {
                        second = dp[i][j][k];
                    }
                }
            }
        }

        int ans = INFTY;
        for (int j = 0; j < n; ++j) {
            ans = min(ans, dp[m - 1][j][target - 1]);
        }
        return ans == INFTY ? -1 : ans;
    }
};

LeetCode554(2021.5.2)

LC554. 砖墙

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> cnt;
        for (auto widths : wall) {
            int n = widths.size(), sum = 0;
            for (int i = 0; i < n - 1; ++i) {
                sum += widths[i];
                cnt[sum]++;
            }
        }
        int maxCnt = 0;
        for (auto c : cnt) maxCnt = max(maxCnt, c.second);
        return wall.size() - maxCnt;
    }
};