力扣日记1262

这篇具有很好参考价值的文章主要介绍了力扣日记1262。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 题目

LeetCode 1262. 可被三整除的最大和

1.1 题意

数组中取数,使得和可以整出3且最大,每个数最多选一次

1.2 分析

看数据量,复杂度可以到O(nlogn)往上

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

思考一下怎么选数,
先想贪心。看出来这个题的答案是需要选数的组合,贪心不出来。
想动态规划。
对于下标i的情况,模3为0,模3为1,模3为2的最大和值可以通过前一个下标i-1记录的情况 + 第i个数分析出来
具体举例来说就是,
当前数模为1:
模0最大和 = 上一个数的模2最大和 + 当前数
模1最大和 = 上一个数的模0最大和 + 当前数
模2最大和 = 上一个数的模1最大和 + 当前数
但并不是每次都会更新(因为求最大值),所以加上一个取max
模0最大和 = max(上一个数的模2最大和 + 当前数, 模0最大和)
模1最大和 = max(上一个数的模0最大和 + 当前数, 模1最大和)
模2最大和 = max(上一个数的模1最大和 + 当前数, 模2最大和)

再加上一点点空间的优化可以做到只用常量级空间,每次的状态只与上次的状态有关,所以可以只记录上一次的状态(类似滚动数组)

加上亿点点细节:
初始时,模为0,1,2的和最大值都为0
那么在规划中,初始为0的情况有些是不能往下传递的
举个例子

mod0=0, mod1=0, mod2=0
当前数为4,模3为1
此时能使用上述转移方程的只有mod1
必须满足这个边界条件才可以

1.3 我的解法

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        // nlogn
        // 记录模3为0,1,2的最大和
        int mod0=0, mod1=0, mod2=0;
        int n = nums.size();
        for(int i=0;i<n;i++){
            int num = nums[i];
            if(num%3==0){
                if(mod1 != 0){
                    // 为什么要加这个判断
                    // 因为边界初始化
                    // 如果mod1压根没有值,就不能有mod1继续往下传
                    // 这很细节 别问我怎么想到这个的 。。。
                    mod1 += num;
                }
                if(mod2 != 0){
                    mod2 += num;
                }
                mod0 += num;
            }
            else if(num%3==1){
                int tmp0 = mod0, tmp1 = mod1, tmp2 = mod2;
                if(tmp2!=0)
                    mod0 = max(tmp2 + num, mod0);
                mod1 = max(tmp0 + num, mod1);
                if(tmp1!=0)
                    mod2 = max(tmp1 + num, mod2);
            }
            else if(num%3==2){
                int tmp0 = mod0, tmp1 = mod1, tmp2 = mod2;
                if(tmp1!=0)
                    mod0 = max(tmp1 + num, mod0);
                if(tmp2!=0)
                    mod1 = max(tmp2 + num, mod1);
                mod2 = max(tmp0 + num, mod2);
            }
            // cout<<num<<" "<<mod0<<" "<<mod1<<" "<<mod2<<endl;
        }
        return mod0;
    }
};

1.4 学习题解反思

时间复杂度O(n), 空间复杂度O(1)

题解的贪心太强了,把数组分成3堆,依次是模3为0,模3为1,模3为2。
接着由上范围限制,这个模3为1、模3为2的集合中选取数的个数的范围限制真的难想。又是学到了的一天。

1.5 bug日记

1.5.1 边界状态的转移考虑不全

2. 后记

仅分享自己的想法,有意见和指点非常感谢文章来源地址https://www.toymoban.com/news/detail-502148.html

到了这里,关于力扣日记1262的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode算法心得——和可被 K 整除的子数组(前缀和+HashMap)

    大家好,我是晴天学长,同余定理的应用,需要的小伙伴可以关注支持一下哦!后续会继续更新的。 1) .和可被 K 整除的子数组 题目描述 给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。 示例: 输入:A = [4,5,0,-2,-3,1], K = 5 输出:7 解释:

    2024年02月07日
    浏览(41)
  • 【1015. 可被 K 整除的最小整数】

    来源:力扣(LeetCode) 描述: 给定正整数 k ,你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。 返回 n 的长度。如果不存在这样的 n ,就返回 -1 。 注意: n 不符合 64 位带符号整数。 示例 1: 示例 2: 示例 3: 提示: 1 = k = 10 5 方法:遍历 思路与算法 题

    2024年02月03日
    浏览(71)
  • 和可被K整除的子数组(Java详解)

    目录 一、题目描述 二、题解 思路分析 具体实现 完整代码 给定一个整数数组  nums  和一个整数  k  ,返回其中元素之和可被  k  整除的(连续、非空)  子数组  的数目。 子数组  是数组的  连续  部分。 示例: 输入:nums = [4,5,0,-2,-3,1],k = 5 输出:7 输入:nums = [ 5 ],

    2024年02月01日
    浏览(36)
  • 【每日一题Day199】LC1010总持续时间可被 60 整除的歌曲 | 哈希表

    总持续时间可被 60 整除的歌曲【LC1010】 在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。 返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望下标数字 i 和 j 满足 i j 且有 (time[i] + time[j]) % 60 == 0 。 思路 由于需要求两首歌的总时间可被60整除

    2024年02月03日
    浏览(43)
  • [Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解

    和为 K 的子数组 分析 :因为有 负数 的存在 无法使用\\\" 双指针 \\\"优化,因为 区间求和不具备单调性 可能已经找到前缀和为k的子数组了,但是后面仍然可能会有更长的和为k的子数组存在 思路 :前缀和 + 哈希表 前缀和 : 以 i 位置为结尾 的所有的子数组 将问题转化为 :在

    2024年04月28日
    浏览(33)
  • 算法——前缀和之除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和

    这几道题对于我们前面讲过的一维、二维前缀和进行了运用,包含了面对特殊情况的反操作 目录 4.除自身以外数组的乘积 4.1解析 4.2题解 5.和为K的子数组 5.1解析 5.2题解 6.和可被K整除的子数组 6.1解析 6.2题解 7.连续数组 7.1题解 7.2题解 8.矩阵区域和 8.1解析 8.2题解 4.除自身以外

    2024年04月14日
    浏览(44)
  • 【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)

    题目链接:5. 最长回文子串 题目内容: 题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。 优化的点在于,假设子

    2024年02月09日
    浏览(48)
  • 题目:2520.统计能整除数字的位数

    ​​ 题目来源:         leetcode题目,网址:2520. 统计能整除数字的位数 - 力扣(LeetCode) 解题思路:        逐位判断即可。 解题代码: 总结:         无官方题解。

    2024年02月13日
    浏览(65)
  • 【数字IC手撕代码】Verilog模三检测器(判断输入序列能否被三整除)|题目|原理|设计|仿真

    芯片设计验证社区·芯片爱好者聚集地·硬件相关讨论社区·数字verifier星球 四社区 联合力荐 !近500篇 数字IC精品文章收录 ! 【数字IC精品文章收录】学习路线·基础知识·总线·脚本语言·芯片求职·EDA工具·低功耗设计Verilog·STA·设计·验证·FPGA·架构·AMBA·书籍 本系列旨在提

    2024年02月16日
    浏览(41)
  • 力扣代码学习日记四

    Problem: 459. 重复的子字符串 给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。 示例 1: 示例 2: 示例 3: 提示: 可以考虑将原始字符串看作是由其最小循环节组成的。如果存在一个子串,将这个子串重复多次后可以得到原始字符串,则原始字符串可以

    2024年02月19日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包