LeetCode 面试150

最近准备面试，我以前不愿意面对的

现在保持一颗本心，就是专注于算法思想，语言基础的磨炼；

不为速成，不急功近利的想要比赛，或者为了面试。

单纯的本心，体验算法带来的快乐，是一件非常了不起的事。

加油，持续输出~

战胜恐惧最好的方法，就是面对

一、滑动窗口

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_map<char, int> hs, ht;for(auto a : t)ht[a]++;int cnt = 0;string res = "";for(int i=0, j=0; 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-j+1))){//条件根据实际情况res = s.substr(j, i-j+1);}}return res;
}
对于字符串也可以用vector， 更节省时间string minWindow(string s, string t) {//unordered_map<char, int> hs, ht;vector<int> ht(128,0);for(auto a : t)ht[a]++;int cnt = 0;//string res = "";int rlen = INT_MAX;int len = t.size();int i=0, j=0, 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-j+1)) //更新目标子串{rlen = (i-j+1);ri = i;rj = j;}}}if(rlen != INT_MAX)return s.substr(rj, ri-rj+1);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, vector<int>& nums) {int hs = 0;int nlen = nums.size();int len = nlen + 1;for(int i=0,j=0; i < nlen; i++){hs+= nums[i];            while(hs-nums[j] >= target){hs=hs-nums[j]; j++;} if(hs >= target && len > i-j+1)len = i-j+1;if(len == 1)return 1;}if(len!=nlen+1)return len;elsereturn 0;}
};