黑龙江省关于城市建设政策网站,做任务赚佣金的网站,网站服务器租用价格表,如何安装wordpress的插件安装教程最近准备面试#xff0c;我以前不愿意面对的 现在保持一颗本心#xff0c;就是专注于算法思想#xff0c;语言基础的磨炼#xff1b; 不为速成#xff0c;不急功近利的想要比赛#xff0c;或者为了面试。 单纯的本心#xff0c;体验算法带来的快乐#xff0c;是一件非常… 最近准备面试我以前不愿意面对的 现在保持一颗本心就是专注于算法思想语言基础的磨炼 不为速成不急功近利的想要比赛或者为了面试。 单纯的本心体验算法带来的快乐是一件非常了不起的事。 加油持续输出~ 战胜恐惧最好的方法就是面对 一、滑动窗口
1.1 最小覆盖子串
集成度越高的结构体unordered_map再使用上虽然方便但遇到多次循环处理处理速度不如用vector维护的可变数组
把两组映射转换为一个数组非常巧妙
运行速度真的是见仁见电脑吗我参考的1ms 的写法甚至把他的源码放我的LeetCode提交我的最快也还是3ms。
想到了飞驰人生2虽然比不上专业赛车只要你苦练技术一定可以超越自己
/*滑动窗口 O(1)
对于一个数组、字符串、链表 原串 s 目标串 t 最终结果 res
定义两个hash map: hs 负责记录滑动窗口ht 负责目标串
定义i,j两个指针i负责扩展满足条件 cnt 计数器
j负责缩圈 当满足条件j--
*/
//模板
string minWindow(string s, string t) {unordered_mapchar, int hs, ht;for(auto a : t)ht[a];int cnt 0;string res ;for(int i0, j0; i s.size(); i){hs[s[i]];if(hs[s[i]] ht[s[i]])//条件可根据实际发生变化cnt;while(hs[s[j]] ht[s[j]]) //缩圈hs[s[j]]--;if(cnt t.size() (res ||res.size() (i-j1))){//条件根据实际情况res s.substr(j, i-j1);}}return res;
}
对于字符串也可以用vector 更节省时间string minWindow(string s, string t) {//unordered_mapchar, int hs, ht;vectorint ht(128,0);for(auto a : t)ht[a];int cnt 0;//string res ;int rlen INT_MAX;int len t.size();int i0, j0, rj 0, ri 0;for(; i s.size(); i){//hs[s[i]];//if(hs[s[i]] ht[s[i]])char c s[i];if(ht[c] 0){cnt;} ht[c]--; //每个字符都减掉如果是目标字符都是0说明找到了如果是-1 说明遇到重复的了需要缩圈//while(hs[s[j]] ht[s[j]]) // hs[s[j]]--;if(cnt len) {while(ht[s[j]]0){ht[s[j]];//把多减掉的不回来j; //指针往后移动继续缩圈就是删掉不用重复的字符} if(rlen (i-j1)) //更新目标子串{rlen (i-j1);ri i;rj j;}}}if(rlen ! INT_MAX)return s.substr(rj, ri-rj1);elsereturn ; }
1.2 长度最小子数组
输入输出流的取消能快很多一些特殊判断
auto optimize_cpp_stdio[](){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
}();
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int hs 0;int nlen nums.size();int len nlen 1;for(int i0,j0; i nlen; i){hs nums[i]; while(hs-nums[j] target){hshs-nums[j]; j;} if(hs target len i-j1)len i-j1;if(len 1)return 1;}if(len!nlen1)return len;elsereturn 0;}
};
