【代码随想录】刷题笔记Day35

2023-12-13 23:56:25

前言

  • 日常学习,抵触心理5%;毫无指示的干活,抵触心理95%

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

  • 把整体利润拆分为每次利润,只要积上涨的就可以,so easy
  • class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int result = 0;
            for (int i = 1; i < prices.size(); i++) {
                result += max(prices[i] - prices[i - 1], 0);
            }
            return result;
        }
    };

55. 跳跃游戏 - 力扣(LeetCode)

  • 一步步走,更新最大可覆盖到的位置,关键在 i <= cover
  • class Solution {
    public:
        bool canJump(vector<int>& nums) {
            int cover = 0;
            if (nums.size() == 1) return true; // 只有一个元素,就是能达到
            for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
                cover = max(i + nums[i], cover);
                if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
            }
            return false;
        }
    };

45. 跳跃游戏 II - 力扣(LeetCode)

  • 当前最大范围走到底发现不够了,就用该范围内更新的最大范围替代,相当于走一步
  • class Solution {
    public:
        int jump(vector<int>& nums) {
            if (nums.size() == 1) return 0;
            int curDistance = 0;    // 当前覆盖最远距离下标
            int ans = 0;            // 记录走的最大步数
            int nextDistance = 0;   // 下一步覆盖最远距离下标
            for (int i = 0; i < nums.size(); i++) {
                nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标
                if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                    ans++;                                  // 需要走下一步
                    curDistance = nextDistance;             // 更新当前覆盖最远距离下标(相当于加油了)
                    if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点,不用做ans++操作了,直接结束
                    // 这个特殊情况也可以通过控制for里的i<nums.size()-1解决
                }
            }
            return ans;
        }
    };

1005. K 次取反后最大化的数组和 - 力扣(LeetCode)?

  • 先按照绝对值从大到小排,负数先转一遍,K有余1则把绝对值最小的转了
  • class Solution {
    static bool cmp(int a, int b) {
        return abs(a) > abs(b);
    }
    public:
        int largestSumAfterKNegations(vector<int>& A, int K) {
            sort(A.begin(), A.end(), cmp);       // 第一步
            for (int i = 0; i < A.size(); i++) { // 第二步
                if (A[i] < 0 && K > 0) {
                    A[i] *= -1;
                    K--;
                }
            }
            if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
            int result = 0;
            for (int a : A) result += a;        // 第四步
            return result;
        }
    };

后言

  • 代码盯久了脑阔疼,今天2.33搞到B站大会员月卡,刷B站去咯

文章来源:https://blog.csdn.net/qq_56077562/article/details/134980015
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。