2024-10-04

  1. 1665. 完成所有任务的最少初始能量 - 力扣（LeetCode）
class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(),
            [](const vector<int>& a, const vector<int>& b) {
                return a[0] - a[1] < b[0] - b[1];
            });
        int ans = 0;
        for (int i = tasks.size() - 1; i >= 0; i--)
            ans = max(tasks[i][1], ans + tasks[i][0]);
        return ans;
    }
/*
考虑任意一种做任务的顺序，设做完第i+2到n个任务所需的初始能量最少为S
对于两个相邻任务：设第i个和第i+1个完成的任务分别是p和q
·先做p，所需初始能量为：max(max(min[q], S+actual[q])+actual[p], min[p]);
·先做q，所需初始能量为：max(max(min[p], S+actual[p])+actual[q], min[q]);
假设先做p比较优，则应该满足
max(max(min[q], S+actual[q])+actual[p], min[p])
< max(max(min[p], S+actual[p])+actual[q], min[q])
两边消去相同式子
max(min[q]+actual[p], min[p]) < max(min[p]+actual[q], min[q])
又因为min[q]+actual[p] > min[q]
所以不等式等价于min[q]+actual[p] < min[p]+actual[q]
即actual[p] - min[p] < actual[q] - min[q]，其中p<q
则原题目中，要求最小，则按照actual-min升序排列，即可。
*/
};
  1. 63. 不同路径 II - 力扣（LeetCode）
    法一：记忆化搜索-递归
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        m = obstacleGrid.size();
        n = obstacleGrid[0].size();
        grid = obstacleGrid;
        return countPaths(0, 0);
    }

private:
    int m, n;
    vector<vector<int>> grid;
    map<pair<int, int>, int> dic;

    int countPaths(int row, int col) {
        if (dic.find({row, col}) != dic.end()) return dic[{row, col}];
        if (row >= m || col >= n || grid[row][col] == 1) return 0;
        if (row == m - 1 && col == n - 1) return dic[{row, col}] = 1;
        return dic[{row, col}] = countPaths(row + 1, col) + countPaths(row, col + 1);
    }
};

法二：DP

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (obstacleGrid[i][j] == 1) f[i][j] = 0;
                else if (i == 0 && j == 0) f[i][j] = 1;
                else if (i == 0) f[i][j] = f[i][j - 1];
                else if (j == 0) f[i][j] = f[i - 1][j];
                else f[i][j] = f[i - 1][j] + f[i][j - 1];
        return f[m - 1][n - 1];
    }
};
  1. 1143. 最长公共子序列 - 力扣（LeetCode）
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        text1 = " " + text1;
        text2 = " " + text2;
        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (text1[i] == text2[j]) 
                    f[i][j] = f[i - 1][j - 1] + 1;
                else 
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        return f[m][n];
    }
};
  1. 300. 最长递增子序列 - 力扣（LeetCode）
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1); // !!! 初始以每个成员为结尾的最长递增子序列为1
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i])
                    f[i] = max(f[i], f[j] + 1);
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, f[i]);
        return ans;
    }
};
  1. 53. 最大子数组和 - 力扣（LeetCode）
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        f[0] = nums[0];
        for (int i = 1; i < n; i++)
            f[i] = max(f[i - 1] + nums[i], nums[i]);
        int ans = f[0];
        for (int i = 1; i < n; i++)
            ans = max(ans, f[i]);
        return ans;
    }
};
  1. 152. 乘积最大子数组 - 力扣（LeetCode）
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> fmax(n);
        vector<int> fmin(n);
        fmax[0] = fmin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            fmax[i] = max(max(fmax[i - 1] * nums[i], fmin[i - 1] * nums[i]), nums[i]);
            fmin[i] = min(min(fmax[i - 1] * nums[i], fmin[i - 1] * nums[i]), nums[i]);
        }
        int ans = nums[0];
        for (int i = 1; i < n; i++)
            ans = max(ans, fmax[i]);
        return ans;
    }
};
  1. 70. 爬楼梯 - 力扣（LeetCode）
class Solution {
public:
    int climbStairs(int n) {
        vector<int> f(n + 1);
        f[0] = 1, f[1] = 1;
        for (int i = 2; i <= n; i++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
};
  1. 120. 三角形最小路径和 - 力扣（LeetCode）
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        int tot = (1 + n) * n / 2;
        vector<int> f(tot);
        f[0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            f[pos(i, 0)] = f[pos(i - 1, 0)] + triangle[i][0];
            f[pos(i, i)] = f[pos(i - 1, i - 1)] + triangle[i][i];
            for (int j = 1; j < i; j++)
                f[pos(i, j)] = min(f[pos(i - 1, j - 1)], f[pos(i - 1, j)]) + triangle[i][j];
        }
        int ans = f[tot - n];
        for (int i = tot - n; i < tot; i++)
            ans = min(ans, f[i]);
        return ans;
    }

private:
    int pos(int i, int j) {
        return (1 + i) * i / 2 + j;
    }
};
  1. 121. 买卖股票的最佳时机 - 力扣（LeetCode）
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> preMin(n + 1, 1e5);
        for (int i = 1; i <= n; i++)
            preMin[i] = min(preMin[i - 1], prices[i - 1]);
        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans = max(ans, prices[i - 1] - preMin[i]);
        return ans;
    }
};

/* [7,1,5,3,6,4]
 n = 6
 prices=[  7,1,5,3,6,4]
 preMin=[0,7,1,1,1,1,1]
*/

10.9. 回文数 - 力扣（LeetCode）
O(∩_∩)O小插曲

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) return false;
        int reverse = 0;
        while (x > reverse) {
            reverse = reverse * 10 + x % 10;
            x /= 10;
        }
        return reverse == x || reverse / 10 == x;
    }
};
  1. 122. 买卖股票的最佳时机 II - 力扣（LeetCode）
    法一：贪心
    2024-10-03 - 简书 (jianshu.com)
    法二：动规
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // 0. Move index to 1-based
        prices.insert(prices.begin(), 0);
        // 1. Define f, initialize -oo
        vector<vector<int>> f(n + 1, vector<int>(2, -1e9));
        f[0][0] = 0;
        // 2. Loop over all states
        for (int i = 1; i <= n; i++) {
            // 3. Copy decisions
            f[i][1] = max(f[i][1], f[i - 1][0] - prices[i]);
            f[i][0] = max(f[i][0], f[i - 1][1] + prices[i]);
            for (int j = 0; j < 2; j++)
                f[i][j] = max(f[i][j], f[i - 1][j]);
        }
        // 4. Return target
        return f[n][0];
    }
};
  1. 188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
class Solution {
public:
    int maxProfit(int c, vector<int>& prices) {
        int n = prices.size();
        // 0. Move index to 1-based
        prices.insert(prices.begin(), 0);
        // 1. Define f, initialize -oo
        vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(2
                    , vector<int>(c + 1, -1e9)));
        f[0][0][0] = 0;
        // 2. Loop over all states
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k <= c; k++) {
                    // 3. Copy decision funcs
                    if (k > 0) f[i][0][k] = max(f[i][0][k], f[i - 1][1][k - 1] + prices[i]);
                    f[i][1][k] = max(f[i][1][k], f[i - 1][0][k] - prices[i]);
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j][k]);
                }
        // 4. Return target
        int ans = -1e9;
        for (int k = 0; k <= c; k++)
            ans = max(ans, f[n][0][k]);
        return ans;
    }
};
  1. 123. 买卖股票的最佳时机 III - 力扣（LeetCode）
    将12题中的c赋值为2即可
  2. 714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        // 0. Move index to 1-based
        prices.insert(prices.begin(), 0);
        // 1. Define f, initialize -oo
        vector<vector<int>> f(n + 1, vector<int>(2, -1e9));
        f[0][0] = 0;
        // 2. Loop over all states
        for (int i = 1; i <= n; i++) {
            f[i][1] = max(f[i][1], f[i - 1][0] - prices[i] - fee);
            f[i][0] = max(f[i][0], f[i - 1][1] + prices[i]);
            for (int j = 0; j < 2; j++)
                f[i][j] = max(f[i][j], f[i - 1][j]);
        }
        return f[n][0];
    }
};
  1. 309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // 0. Move index to 1-based
        prices.insert(prices.begin(), 0);
        // 1. Define f, initialize -oo
        vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(2, 
                vector<int>(2, -1e9)));
        f[0][0][0] = 0;
        // 2. Loop over all states
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++) {
                    // 3. Copy decision funcs
                    f[i][1][0] = max(f[i][1][0], f[i - 1][0][0] - prices[i]);
                    f[i][0][1] = max(f[i][0][1], f[i - 1][1][0] + prices[i]);
                    f[i][j][0] = max(f[i][j][0], f[i - 1][j][k]);
                }
        // 4. Return target
        return max(f[n][0][0], f[n][0][1]);
    }
};
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容