计算机网站建设是什么,渭南网站建设价格,郑州短视频培训机构,wordpress 企业沟通插件#x1f339;作者:云小逸 #x1f4dd;个人主页:云小逸的主页 #x1f4dd;Github:云小逸的Github #x1f91f;motto:要敢于一个人默默的面对自己#xff0c;强大自己才是核心。不要等到什么都没有了#xff0c;才下定决心去做。种一颗树#xff0c;最好的时间是十年前… 作者:云小逸 个人主页:云小逸的主页 Github:云小逸的Github motto:要敢于一个人默默的面对自己强大自己才是核心。不要等到什么都没有了才下定决心去做。种一颗树最好的时间是十年前其次就是现在学会自己和解与过去和解努力爱自己。希望春天来之前我们一起面朝大海春暖花开 专栏C 专栏Java语言专栏Linux学习 专栏C语言初阶专栏数据结构专栏备战蓝桥杯 文章目录前言例题我在哪题目输入格式输出格式数据范围输入样例输出样例暴力解法 On4思想代码二分 STL Set O(n^2^logn)思想代码最后前言
今天这篇文章我们继续学习二分法这里讲解有一道有关二分的算法题我在哪
——————————————————————————————
首先先写上几句话献给坚持创作的我和点开这篇文章希望进步的你 1.学不进去的时候就看看这段话 “你考的不是试是前途和暮年的欢喜你桌面上的书本是将来做选择时的意气和拒绝时的底气。”
2.“要是想哭的话把能做的事情全部做完之后再尽情地哭。”
3.“我想向自己证明我从未停止努力我从未选择放弃所以我一定能再回顶峰。”
4.“我们每个人都像陨石即便终将陨落也请我们尽情燃烧。”
5.“假如你什么都不学习那就只能生活在现时现世的一个小圈子里狭窄得很。”
例题我在哪
题目
农夫约翰出门沿着马路散步但是他现在发现自己可能迷路了 沿路有一排共 N 个农场。不幸的是农场并没有编号这使得约翰难以分辨他在这条路上所处的位置。然而每个农场都沿路设有一个彩色的邮箱所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。每个邮箱的颜色用 A…Z 之间的一个字母来指定所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A…Z 组成的字符串来表示。某些邮箱可能会有相同的颜色。 约翰想要知道最小的 K 的值使得他查看任意连续 K 个邮箱序列他都可以唯一确定这一序列在道路上的位置。 例如假设沿路的邮箱序列为 ABCDABC 。 约翰不能令 K3因为如果他看到了 ABC则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K 的值为 K4因为如果他查看任意连续 4 个邮箱那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
输入格式
输入的第一行包含 N第二行包含一个由 N 个字符组成的字符串每个字符均在 A…Z 之内。
输出格式
输出一行包含一个整数为可以解决农夫约翰的问题的最小 K 值。
数据范围
1≤N≤100
输入样例 7 ABCDABC 输出样例 4 暴力解法 On4
思想
可以直接进行枚举两个子串并比较如 写四个for循环 第一个先枚举k 第二个枚举其中任意一个子串k值一定只要枚举起点就可以了 第三个再枚举第二个子串 第四个判断两个子串是否相同 N最大是100四次方是1个亿刚好可以过而且它是达不到最大一个亿的有的时候直接break了
代码
#include iostream
#include cstring
#include algorithmusing namespace std;int n;
string str;int main()
{cin n str;for (int k 1; k n; k )//先枚举k{bool flag false;for (int i 0; i k - 1 n; i )//枚举其中任意一个子串k值一定只需要枚举起点就可以了{for (int j i 1; j k - 1 n; j )//再枚举第二个子串{bool same true;for (int u 0; u k; u )//判断两个子串是否相同if (str[i u] ! str[j u]){same false;break;}if (same){flag true;break;}}if (flag) break;}if (!flag){cout k endl;break;}}return 0;
}二分 STL Set O(n2logn)
思想
判断是否可以二分要看它是否有二段性 假设ans为正确答案【最小的k】故小于ans都是不合法的大于ans都是合法的。故其具有二段性那么就可以使用二分法来二分出分界点了这样可以把上面的暴力法的第一次循环改为二分这样复杂度就变成了O(n3logn)。 继续分析 我们题意是想统计每一个串是否只出现一次然而判断一个东西只出现一次可以使用哈希表 将每一个串映射到哈希表里然后判断每一串是否只出现一次这样可以再去掉一个循环复杂度变成O(n2logn);
代码
#include iostream
#include cstring
#include algorithm
#include unordered_setusing namespace std;int n;
string str;
unordered_setstring S;bool check(int mid)
{S.clear();for (int i 0; i mid - 1 n; i ){string s str.substr(i, mid);if (S.count(s)) return false;S.insert(s);}return true;
}int main()
{cin n str;int l 1, r n;while (l r){int mid l r 1;if (check(mid)) r mid;else l mid 1;}cout r endl;return 0;
}
最后
十分感谢你可以耐着性子把它读完和我可以坚持写到这里送几句话对你也对我
1.“我们永远也不知道下一刻会发生什么我只是觉得还有希望的时候不要选择放弃。”
2.“生活坏到一定程度就会好起来因为它无法更坏努力过后才知道许多事情坚持坚持就过来了。
3.“在无人问津的地方历练在万众瞩目的地方出现。”
4.“如果你第一步不迈出永远不知道你的梦想是多么容易实现。”
5.“虽然绿灯没怎么为我亮过但我还是对生活充满了希望。”
最后如果觉得我写的还不错请不要忘记点赞✌收藏✌加关注✌哦(ω)
愿我们一起加油奔向更美好的未来愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油为自己点赞
