面试经典150题链接
面试经典 150 题 – 学习计划 – 力扣(LeetCode)全球极客挚爱的技术成长平台
209 . 长度最小的子数组
思路 :
滑动窗口的思想,取i=j=0,向后遍历j,记录前缀和[l,r]为s,如果s>=target,那么左端点向右移动,直到s<target,维护一个[l,r]的滑动窗口,如此循环;
代码
python
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)ans = n+1l=0s=0for r,x in enumerate(nums):s+=xwhile s>=target:ans = min(ans,r-l+1)s-=nums[l]l+=1return ans if ans <= n else 0
c++
class Solution {public:int minSubArrayLen(int target, vector& nums) {int n = nums.size();if(n==0) return 0 ;int sum = 0;int l = 0 , r = 0 ; int ans = INT_MAX ;while(r = target){ans = min(ans , r - l + 1) ;sum -= nums[l++];}r++ ;}return ans == INT_MAX ? 0 : ans;}};
3 . 无重复字符的最长子串
思路 :
假设在一个无重复元素的字符串后面加上一个字符,如果出现重复元素,那么一定重复的是新加上的那个字符,那么设置一个hash表来统计次数,然后反复将窗口最前面的元素移出窗口,直到将前面与新加元素相同的元素移出时停止;然后循环更新答案即可;
lc题解地址 :
力扣(LeetCode)官网 – 全球极客挚爱的技术成长平台
代码 :
Python
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:l = 0cnt = Counter()ans = 0for r , c in enumerate(s):cnt[c]+=1while cnt[c]>=2:cnt[s[l]]-=1l+=1ans = max(ans,r-l+1)return ans
C++
class Solution {public:int lengthOfLongestSubstring(string s) {unordered_map hash;int ans=0;int n = s.size();int l=0;for(int r=0;r 1) --hash[s[l++]];ans = max(ans,r-l+1);}return ans;}};
java
class Solution {public int lengthOfLongestSubstring(String s) {int ans = 0 ;char[] st = s.toCharArray();boolean[] has = new boolean[128] ;int n = s.length();int i = 0 ;for(int j=0;j<n;j++){char c = st[j];while(has[c])has[st[i++]] = false;has[c] = true;ans = Math.max(ans, j-i+1);}return ans;}}
30 . 串联所有单词的子串
思路 :
滑动窗口,细节看代码
代码 :
class Solution {public:vector findSubstring(string &s, vector &words) {// 一个窗口包含s中的前a个单词;// 先删去前 i (i=0∼b−1)个字母后,// 将剩下的字母进行划分,如果末尾有不到 b 个字母也删去。vector ans ;int a = words.size() , b = words[0].size() , n = s.size() ;for(int i=0;i<b&&i+a*b<=n;i++){ // 对应b种划分方法unordered_map mp;for(int j=0;j
76 . 最小覆盖子串
滑动窗口 :
定义两个长度为 606060(足够存下所有字母种类)的数组 c1 和 c2,用于存储字符频率。其中 c1 用于记录字符串 t 中字符的频率,c2 用于记录当前滑动窗口内字符的频率。
设定好字母与频率数组下标的映射关系:小写字母 a-z 对应下标 0-25,大写字母 A-Z 对应下标 26-51。
使用变量 tot 来记录还需要匹配的字符种类数,当 tot = 0 代表当前滑动窗口对应的子串能够实现对 t 的覆盖,即任意字符满足 c2[i]≥c1[i]c2[i] \geq c1[i]c2[i]≥c1[i]。
使用双指针 j 和 i 表示滑动窗口的左右边界。从前往后遍历字符串 s,在每个位置上更新字符频率数组 c2。若 c2 中字符的频率达到了 c1 中的字符频率,则将 tot 减 1,表示一个字符已经匹配完成。
每当右边界往后移动一步之后,滑动窗口会增加一个字符。此时我们检查左边界能否右移,同时不会使得 tot 变大。即每次右边界右移后,我们检查左边界 c2[j]>c1[j]c2[j] > c1[j]c2[j]>c1[j] 是否满足:
若满足:说明当前左边界指向字符并非必须,当前子串 s[j...i]s[j...i]s[j...i] 必然不是最短子串。我们让左边界 j 进行右移,并重复进行左边界 c2[j]>c1[j]c2[j] > c1[j]c2[j]>c1[j] 的检查,直到窗口不能再收缩
若不满足:说明当前窗口没有任何一个后缀字符串能够实现对 t 的覆盖,我们并不能对窗口实现收缩
每次对窗口移动完成后,我们检查当前 tot 是否为 000(对字符串 t 的覆盖是否完成),若为 000 则尝试用当前窗口对应的字符串 s[j...i]s[j...i]s[j...i] 更新 ans。
class Solution {public:int get(char x) {return x >= 'A' && x <= 'Z' ? x - 'A' + 26 : x - 'a';}string minWindow(string s, string t) {int n = s.size() , cnt = 0 ;// cnt : 还需要匹配的字符种类数// 规定 a-z : 0-25,A-Z : 26-51// c1 用于记录字符串 t 中字符的频率,c2 用于记录当前滑动窗口内字符的频率vector c1(60),c2(60);for(char c : t) if(++c1[get(c)]==1) cnt ++ ;string ans = "" ;for(int i=0,j=0;i<n;i++){int idx1 = get(s[i]);//将s[i]加入窗口if(++c2[idx1]==c1[idx1]) cnt --;while(jc1[idx2] && --c2[idx2]>=0){// 能够滑出窗口//;j++;}else{break;//不能够滑出窗口}}if(cnt==0 && (ans.empty() || ans.size()>i-j+1)) ans = s.substr(j,i-j+1);}return ans ;}};
相似题目 :
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台