每日一题

单调栈 / dp + 树

1130. 叶值的最小代价生成树

1130. 叶值的最小代价生成树 - 力扣（LeetCode）

class Solution {
public:
    // 做法二：单调栈
    // 分析：树形结构为 当前节点 与 右两侧的最小节点 运算（考虑左右子树） 左子树为当前节点，右子树为建好的树 ；； 因此我们只需要 逆向思维，先将后面的最小值找到，再算左边
    // 单调栈 -- 考虑找到右侧第一个大于栈顶（当前的左侧最后一个）的元素
    //        -- 将所有在他之前的比他小的叶节点计算出来，然后他在作为当前叶节点中 最后的最大值
    int mctFromLeafValues(vector<int>& a) {
        // 手写单调栈 -- 保证不为空
        int ans = 0;
        stack<int> st; st.push(1e9);
        for (int i = 0; i < a.size(); i++) {
            while (!st.empty() && st.top() > a[i]) st.push(a[i]);
            // 
            while (a[i] >= st.top()) {
                int t = st.top(); st.pop();
                ans += t * min(st.top(), a[i]);
            }
            st.push(a[i]);
        }
        while (st.size() > 2) {
            int t = st.top(); st.pop();
            ans += st.top() * t;
        }
        return ans;
    }


    // 做法一：动态规划
    // 因为 题可以转化为左右区间中，最小叶子节点的值和 + 左区间 + 右区间 当前值的最小值
    int mctFromLeafValues(vector<int>& a) {
        int n = a.size();
        // 最小 - 转移方向问题：[] + [] = [ ]
        // f[i][j] = min(f[i][k] + f[k+1][j] + a[i-k] * a[k+1][j], f[i][j]);
        vector<vector<int>> f(n + 1, vector<int>(n+1, 1e9)), mx(n+1, vector<int>(n+1, 0));

        // 只能从 j -> i转移 ，不能从 i -> j转移

        // 分析；f[i][k] 需要用到 后面的 区间[k][j],但是当前尚未计算出 [k][j]区间的值
        // 如果从 j开始，则每次从 i ->j时，后面的 [k][j]已经计算出来，可以用
        
        // 错误
        // for (int i = 0; i < n; i++) {
        //     f[i][i] = 0;
        //     mx[i][i] = a[i];
        //     for (int j = i+1; j < n; j++) {
        //         mx[i][j] = max(a[j], mx[i][j-1]);
        //         for (int k = i; k < j; k++) {
        //             f[i][j] = min(f[i][k] + f[k+1][j] + mx[i][k] * mx[k+1][j], f[i][j]);
        //             cout << f[i][j] << " " << endl;
        //         }
        //     }
        // }

        for (int j = 0; j < n; j++) {
            f[j][j] = 0; mx[j][j] = a[j];
            for (int i = j - 1; i >= 0; i--) {
                mx[i][j] = max(a[i], mx[i+1][j]);
                for (int k = i; k < j; k++) {
                    f[i][j] = min(f[i][k] + f[k+1][j] + mx[i][k] * mx[k+1][j], f[i][j]);
                }
            }
        }

        return f[0][n-1];
    }
};

倍增

Loading Question… - 力扣（LeetCode）

class TreeAncestor {
public:
    const static int N = 16;
    unordered_map<int, int> mp;
    // cur, 1, 2, 3
    // 最小公共祖先

    vector<vector<int> > f;
    TreeAncestor(int n, vector<int>& parent) {
        f = vector<vector<int> >(n, vector<int>(N, -1));
        for (int i = 0; i < n; i++) {
            f[i][0] = parent[i];    // 2 ^ 0 == 1;
        }
        for (int j = 1; j < N; j++) {
            for (int i = 0; i < n; i++) {
                if (f[i][j-1] != -1) {
                    f[i][j] = f[f[i][j-1]][j-1];
                }
            }
        }
    }
    
    int getKthAncestor(int node, int k) {
    
        for (int i = 0; i < N; i++) {
            if ((k >> i) & 1) {
                node = f[node][i];
            }
            if (node == -1)
                return -1;
        }
        return node;
    }
};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */

滑动窗口

3. 无重复字符的最长子串 题解 - 力扣（LeetCode）

class Solution {
public:
    // 滑动窗口：需要记住 从左往右，不要跳跃
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp;
        for (auto& ss : s) mp[ss] = -1;
        int ans = 0, l = 0;
        for (int i = 0; i < s.size(); i++) {
            // 不断更新 left指针位置，（l， 0， mp[s[i]] + 1）
            // 不断用 新加入的 right 更新ans
            // 不断更新 mp[s[i]]
            l = max(l, mp[s[i]] + 1);
            ans = max(ans, i - l + 1);
            mp[s[i]] = i;
        }
        return ans;
    }
};

3. 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l = 0;
        map<char, int> a;
        for (int i = 0; i < s.size(); i++) a[s[i]] = -1;
        int ans = 0;
        // 这题等核心：顺序，更新l的顺序，l每次选可能的最大值
        for (int i = 0; i < s.size(); i++) {
            if (a[s[i]] != - 1)
                l = max(a[s[i]] + 1, l);
            ans = max(i - l + 1, ans);
            a[s[i]] = i;
        }
        ans = max(ans, int(s.size()- l));
        return ans;
    }
};