【上分日记】第380场周赛(数位dp+ KMP + 位运算 + 二分 + 双指针 )

文章目录

  • 前言
  • 正文
    • 1.3005. 最大频率元素计数
    • 2.3007.价值和小于等于 K 的最大数字
    • 3.3008. 找出数组中的美丽下标 II
  • 总结
  • 尾序

前言

 本场周赛,博主也只写出两道题(前两道, hhh菜鸡勿喷),第三道涉及位运算 ,数位dp,第四道涉及KMP。 下面我们来总结一下这四道题。

正文

1.3005. 最大频率元素计数

 这道题不难,不过有一个比较妙的写法,因此还是来分析总结一下。

  • 题目链接: 最大频率元素计数
  • 题目思路:
  1. 用一个unordered_map更新次数。
  2. 更新出最大次数时,也更新ans的初始值。
  3. 当等于最大次数时,对ans 加上 当前最大次数。
  • 关键:最大次数的出现是呈现递增趋势的.
  • 因此我们可以一边记录unordered_map, 一边更新最大次数和answer。并且一个循环就可以更新出结果。
class Solution {
public:
    int maxFrequencyElements(vector<int>& nums) 
    {
        int max_cnt = 0;
        int ans = 0;
        unordered_map<int,int> hash;
        for(auto e : nums)
        {
            if(++hash[e] > max_cnt)
                max_cnt = ans = hash[e];
            else if(hash[e] == max_cnt)
                ans += max_cnt;
        }
        return ans;   
    }
};

2.3007.价值和小于等于 K 的最大数字

  • 题目链接:价值和小于等于 K 的最大数字

  • 题目大思路:【数位dp】 / 【分类讨论 + 数学分析】 + 二分

  1. 数位dp
  1. 从高位开始枚举,一直枚举到最低位。
  2. 下一位的枚举的数字范围收到上一位的约束。
  3. 对不受到上一位约束的,采取记忆化的策略。受到上一位约束的,只有一种情况,无需记忆化。
  • 实现代码:
class Solution {
public:
    long long findMaximumNumber(long long k, int x) 
    {
         //数位dp
        auto check = [&](long long num)
        {
            //找其中为1 - num 上 x 的整数倍上 为 1的个数。
            //1.先将num转换为二进制数,到最高位即可。
            string s;
            for(int i = 0; i < 64; i++)
            {
                if(num & (1ll << (63 - i)))
                    s += "1";
                else
                    s += "0";
            }
            long long dp[64][64];
            memset(dp,-1ll,sizeof(dp));
	       /*
		       其中dp表示为枚举第 i 位,之前之前已经有j个1时,数字出现1的总数
		       1.limit表示第i位是否收到约束,即只能枚举 0 ~ s[i] - '0',
		        如果收到,下一位也要收到约束,否则可以枚举 0 ~ 9
		       2.如果枚举第i位没收到约束,且之前j个1已经求过,则无需再求,
		       即记忆化。反之,只会出现一次,没必要记忆化,当然记忆化也可以。
	       */
            function<long long(int,int,bool)> dfs = [&](int i ,\
            long long j,bool limit)
            {
                if(i == 64) return j;
                else if(!limit && dp[i][j] != -1) return dp[i][j];

                long long res = 0;
                int end = limit ? s[i] - '0' : 1;
                for(int m = 0;  m <= end; m++)
                {
                    res += dfs(i+1,j + (m == 1 && (64 - i) % x == 0),\
                    limit && (m == end));
                 /*
	                m == 1 且是x的倍数成立,结果位 j + 1,反之为 j
	                如果当前位受到限制,且枚举之后的n也达到了end,则下一位
	                受到限制。
                */
                }
                if(!limit) dp[i][j] = res;

                return res;
            };
            return dfs(0,0,true);
        };
        //二分
        long long left = 0,right = k << x;
        //找靠近右边最大的num,因此要固定右边枚举左边。
        while(left < right)
        {
            long long mid = (left + right + 1) / 2;
            if(check(mid) > k)
                right = mid - 1;
            else
                left = mid;
        }
        //必然会有答案。
        return left;
    }
};

说明:模版题——233. 数字 1 的个数

  1. 位运算 + 分类讨论
    在这里插入图片描述
class Solution {
public:
    long long findMaximumNumber(long long k, int x) 
    {
         //位运算 + 分类讨论
        auto check = [&](long long num)
        {
            long long ans = 0;
            int cnt = x - 1;
            for(long long i = num >> cnt; i; cnt += x,i >>= x)
            {
                ans += (i / 2) << cnt;
                if(i % 2)
                {
                    long long mask = (1ll << cnt) - 1;
                    ans += (num & mask) + 1;
                }
            }
            return ans;
        };
        //二分
        long long left = 0,right = k << x;
        //找靠近右边最大的num,因此要固定右边枚举左边。
        while(left < right)
        {
            long long mid = (left + right + 1) / 2;
            if(check(mid) > k)
                right = mid - 1;
            else
                left = mid;
        }
        //必然会有答案。
        return left;
    }
};
  • 补充一点:这里的right 是 最多 num 能取到的数,设为上界,具体分析跟位运算的分析雷同,看奇数位且只看最低位,即 (num / 2x-1 - 1) / 2 == k,解出上界,取一个大于 num 的即可。当然如果不想这样写,也可以直接枚举最大值作为上界。

3.3008. 找出数组中的美丽下标 II

  • 题目链接:找出数组中的美丽下标 II

  • 题目大思路:KMP + 【二分】/ 【双指针】

  • 前置知识 ——【数据结构与算法】KMP算法
  • KMP模版
vector<int> kmp(string& text,string& pattern)
{
    //求next数组
    int tsz = text.size(),psz = pattern.size();
    vector<int> next(psz);
    int index = 0;
    for(int i = 1; i < psz; i++)
    {
        char ch = pattern[i];
        while(index && ch != pattern[index])
        {
            //进行回退找最长匹配串与之匹配
            index = next[index-1];
        }
        if(ch == pattern[index])
            index++;
        next[i] = index;
    }
    vector<int> ans;
    //求子串的起始位置。
    index = 0;
    for(int i = 0; i < tsz; i++)
    {
        char ch = text[i];
        while(index && ch != pattern[index])
        {
            index = next[index-1];
        }
        if(ch == pattern[index])
            index++;
        
        if(index == psz)
        {
            //说明找到子串了,记录下标并进行回退
            ans.push_back(i + 1 - psz);
            index = next[index - 1];
        }
    }
    return ans;
};
  1. 双指针,因为要找 |j - i| <= k 的,所以我们固定 i找符合满足的 j 即可, 可以让j追i,当 j < i - k, 就让k++, 追上 i 或者 超过i 就停下。
  • 实现代码:
class Solution {
public:
    vector<int> beautifulIndices(string s, string a, string b, int k) 
    {
       
        vector<int> res;
        vector<int> pos_a = kmp(s,a);
        vector<int> pos_b = kmp(s,b);
        int asz = pos_a.size(),bsz = pos_b.size();
        int j = 0;
        for(int i = 0; i < asz; i++)
        {
            //让 j 追 i 且满足pos_b[j] < pos_a[i] - k, 就去追
            while(j < bsz && pos_b[j] + k < pos_a[i])
                j++;

            // 追上了,且满足情况
            if(j < bsz && abs(pos_a[i] - pos_b[j]) <= k)
                res.push_back(pos_a[i]);
        }
        return res;
    }
};
  1. 二分,也是固定 i , 二分找 j,因为pos_b存的是下标是递增的,因此可以二分找,我们可以找 大于等于 pos_a[ i ] 的第一个pos_b[ j ]pos_b[j - 1]可能是靠近pos_a[i]的其左边最近的那一个,对这两种情况进行讨论即可。
  • 实现代码:
   vector<int> beautifulIndices(string s, string a, string b, int k) 
   {
      
       vector<int> res;
       vector<int> pos_a = kmp(s,a);
       vector<int> pos_b = kmp(s,b);
       int asz = pos_a.size(),bsz = pos_b.size();
       for(int i = 0; i < asz; i++)
       {
           //二分找左边那个j  >= i 的最靠近的元素
           int left = 0,right = bsz - 1;
           while(left <  right)
           {
               int mid = (left + right - 1) / 2;
               if(pos_b[mid] < pos_a[i])
                   left = mid + 1;
               else
                   right = mid;
           }
           if(right >= 0 && pos_b[right] >= pos_a[i])
           {
               left = right - 1;
           }
           else
           {
               left = bsz == 0 ? -1 : right;
               right = bsz;
           }
           if( right < bsz && pos_b[right] - pos_a[i] <= k 
           || left >= 0 && pos_a[i] - pos_b[left] <= k)
           {
               res.push_back(pos_a[i]);
           } 
       }
       return res;
   }
};
  • 这里的二分,要对结果判断一下是否有效,且这里 left是 pos_b 左边最靠近 pos_a[i ] 的,right 是 pos_b右边最靠近 pos_a[i]的。
  • 推荐双指针的写法。

总结

  1. 第一道题的一种遍历写法值得品味一番。
  2. 第二道题的数位dp + 位运算 需要认真思考。
  3. 第三道题的KMP算法 的线性复杂度值得探索。
  • 彩蛋:如果存在两个题目相同,可以先把简单的AC掉,然后用难的去简单的上测试,出错是不会罚时的哦!

尾序

我是舜华,期待与你的下一次相遇!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/328836.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Mac系统下,保姆级Jenkins自动化部署Android

一、Jenkins自动化部署 1、安装jenkins 官网&#xff1a;macOS Installers for Jenkins LTS 选择macOS brew install jenkins-lts 安装最新: brew install jenkins-lts 启动jenkins服务: brew services start jenkins-lts 重启jenkins服务: brew services restart jenkin…

Angular系列教程之变更检测与性能优化

文章目录 前言变更检测的原理脏检查OnPush策略 示例代码总结 前言 Angular 除了默认的变化检测机制&#xff0c;也提供了ChangeDetectionStrategy.OnPush&#xff0c;用 OnPush 可以跳过某个组件或者某个父组件以及它下面所有子组件的变化检测。 在本文中&#xff0c;我们将探…

grep 在运维中的常用可选项

一、对比两个文件 vim -d <filename1> <filename2> 演示&#xff1a; 需求&#xff1a;&#xff5e;目录下有两个文件一个test.txt 以及 text2.txt,需求对比两个文件的内容。 执行后会显示如图&#xff0c;不同会高亮。 二、两次过滤 场景&#xff1a;当需要多…

如何用AI提高论文阅读效率?

已经2024年了&#xff0c;该出现一个写论文解读AI Agent了。 大家肯定也在经常刷论文吧。 但真正尝试过用GPT去刷论文、写论文解读的小伙伴&#xff0c;一定深有体验——费劲。其他agents也没有能搞定的&#xff0c;今天我发现了一个超级厉害的写论文解读的agent &#xff0c…

rust跟我学六:虚拟机检测

图为RUST吉祥物 大家好,我是get_local_info作者带剑书生,这里用一篇文章讲解get_local_info是怎么检测是否在虚拟机里运行的。 首先,先要了解get_local_info是什么? get_local_info是一个获取linux系统信息的rust三方库,并提供一些常用功能,目前版本0.2.4。详细介绍地址:…

标准ERP产品的许可期限为,2023-12-22,当前已超过使用期限,请联系系统管理员更新许可或者删除超期的许可

项目场景&#xff1a; 金蝶云星空客户端 问题描述 标准ERP产品的许可期限为&#xff0c;2023-12-22&#xff0c;当前已超过使用期限&#xff0c;请联系系统管理员更新许可或者删除超期的许可! 原因分析&#xff1a; 这个报错提示是金蝶对第三方行业许可强制绑定,行业许可到…

Android PendingIntent 闪退

先来给大家推荐一个我日常会使用到的图片高清处理在线工具&#xff0c;主要是免费&#xff0c;直接白嫖 。 有时候我看到一张图片感觉很不错&#xff0c;但是图片清晰度不合我意&#xff0c;就想有没有什么工具可以处理让其更清晰&#xff0c; 网上随便搜下就能找到&#xff…

MySQL创建表及插入数据

一、创建英雄表&#xff08;hero&#xff09; mysql> use db_han Database changed mysql> create table hero(-> name varchar(20) primary key,-> nickname varchar(20),-> address varchar(20),-> groups varchar(20),-> emile int,-> telephone i…

6.3.1认识Camtasia4(2)

6.3.2录制声音 Camtasia4也可以用来录制声音&#xff0c;不过它在音频的录制与处理上要比GoldWave5差了很多。 1&#xff0e;在Camtasia Studio主程序中&#xff0c;单击【工具】|【Camtasia音频编辑器】&#xff0c;启动Camtasia音频编辑器。在弹出的欢迎界面中&#xff0c;…

如何在网络爬虫中解决CAPTCHA?使用Python进行网络爬虫

网络爬虫是从网站提取数据的重要方法。然而&#xff0c;在进行网络爬虫时&#xff0c;常常会遇到一个障碍&#xff0c;那就是CAPTCHA&#xff08;全自动公共图灵测试以区分计算机和人类&#xff09;。本文将介绍在网络爬虫中解决CAPTCHA的最佳方法&#xff0c;并重点介绍CapSol…

redis数据安全(三)数据持久化 AOF

接上一篇RDB&#xff0c;本篇看下Redis数据持久化的第二种方式AOF。 目录 一、AOF原理 1、写入机制&#xff1a; 2、缓冲机制&#xff1a; 3、重写机制 &#xff1a; 4、运行流程 二、AOF文件配置 1、开启AOF&#xff1a; 2、自动触发AOF重写 3、重写规则&#xff1…

山海鲸:金融机构数据管理的得力助手

在当今数字化的时代&#xff0c;数据已经成为金融机构的核心资产和决策依据。然而&#xff0c;如何有效地管理和分析这些数据&#xff0c;成为了金融机构面临的挑战。这时&#xff0c;一款强大的数据可视化工具显得尤为重要&#xff0c;山海鲸可视化正是这样一款助力金融机构轻…

ElasticSearch概述+SpringBoot 集成ES

ES概述 开源的、高扩展的、分布式全文检索引擎【站内搜索】 解决问题 1.搜索词是一个整体时&#xff0c;不能拆分&#xff08;mysql整体连续&#xff09; 2.效率会低&#xff0c;不会用到索引&#xff08;mysql索引失效&#xff09; 解决方式 进行数据的存储&#xff08;只存储…

【中大主办会议】第五届电子通讯与人工智能国际学术会议(ICECAI 2024)

第五届电子通讯与人工智能国际学术会议&#xff08;ICECAI 2024&#xff09; 2024 5th International Conference on Electronic communication and Artificial Intelligence 第五届电子通讯与人工智能国际学术会议&#xff08;ICECAI 2024&#xff09;将于2024年5月31日-6月…

导入失败,报错:“too many filtered rows xxx, “ErrorURL“:“

一、问题&#xff1a; 注&#xff1a;前面能正常写入&#xff0c;突然就报错&#xff0c;导入失败&#xff0c;报错&#xff1a;“too many filtered rows xxx, "ErrorURL":" {"TxnId":769494,"Label":"datax_doris_writer_bf176078-…

【算法Hot100系列】接雨水

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 jav…

分销商城多端uniapp 可编译5端 - 等级提现额度

等级提现额度 等级提现额度是一种常见的财务管理策略&#xff0c;通常用于在线平台、金融服务或游戏中&#xff0c;用于控制不同等级用户的提现限额。这样的机制有助于平台管理资金流动性&#xff0c;防范欺诈&#xff0c;并鼓励用户提升他们的活跃度或忠诚度。以下是一个简单的…

el-date-picker组件设置时间范围限制

需求&#xff1a; 如图所示&#xff0c;下图为新增的一个弹层页面&#xff0c;同时有个需求&#xff0c;日期选择需要限制一个月的时间范围&#xff08;一月默认为30天&#xff09;&#xff1a; 查看官方文档我们需要主要使用到如下表格的一些东西&#xff1a; 参数说明类型可…

java应用CPU过高查找原因

用top查到占用cpu最高的进程pid 根据进程ID找到占用CPU高的线程 ps -mp 60355 -o THREAD,tid | sort -r 用 printf "%x \n" 将tid换为十六进制&#xff1a;xid printf "%x \n" 6036 根据16进制格式的线程ID查找线程堆栈信息 jstack 60355 |grep ebcb -A…

[NISACTF 2022]babyserialize

[NISACTF 2022]babyserialize 题目做法及思路解析&#xff08;个人分享&#xff09; 题目平台地址&#xff1a;NSSCTF | 在线CTF平台 一、题目代码 查看分析代码&#xff0c;寻找漏洞点&#xff08;题目中注释为个人思路标注&#xff0c;实际代码中没有&#xff09; …