20240410
1.接雨水
方法一，动态规划，时间复杂度O（n^2），空间复杂度O（n）
public int trap(int[] height) { int n=height.length; if(n==0){ return 0; } int[] leftMax=new int[n]; leftMax[0]=height[0]; for(int i=1;i<n;++i){ leftMax[i]=Math.max(leftMax[i-1],height[i]); } int[] rightMax=new int[n]; rightMax[n-1]=height[n-1]; for(int i=n-2;i>=0;--i){ rightMax[i]=Math.max(rightMax[i+1],height[i]); } int ans=0; for(int i=0;i<n;++i){ ans+=Math.min(leftMax[i],rightMax[i])-height[i]; } return ans; }
方法二、栈
时间复杂度O（n）,空间复杂度O（n）
public int trap(int[] height) { int ans=0; Deque<Integer> stack=new LinkedList<Integer>(); int n=height.length; for(int i=0;i<n;++i){ while(!stack.isEmpty()&&height[i]>height[stack.peek()]){ int top=stack.pop(); if(stack.isEmpty()){ break; } int left=stack.peek(); int currWidth=i-left-1; int currHeight=Math.min(height[left],height[i])-height[top]; ans+=currWidth*currHeight; } stack.push(i); } return ans; }
方法三.双指针法
时间复杂度O（n）,空间复杂度O（1）
public int trap(int[] height) { int ans=0; int left=0,right=height.length-1; int leftMax=0,rightMax=0; while(left<right){ leftMax=Math.max(leftMax,height[left]); rightMax=Math.max(rightMax,height[right]); if(height[left]<height[right]){ ans+=leftMax-height[left]; ++left; }else{ ans+=rightMax-height[right]; --right; } } return ans; }
20240411
滑动窗口
1.无重复字符的最长子串
public int lengthOfLongestSubstring(String s) { Set<Character> occ=new HashSet<Character>(); int n=s.length(); int rk=-1,ans=0; for(int i=0;i<n;i++){ if(i!=0){ occ.remove(s.charAt(i-1)); } while(rk+1<n&&!occ.contains(s.charAt(rk+1))){ occ.add(s.charAt(rk+1)); ++rk; } ans=Math.max(ans,rk-i+1); } return ans; }
时间复杂度O（n），感觉有点累死字符串匹配算法
2.找到字符串中所有字母异味词
public List<Integer> findAnagrams(String s, String p) { int sLen=s.length(),pLen=p.length(); if(sLen<pLen){ return new ArrayList<Integer>(); } List<Integer> ans=new ArrayList<Integer>(); int[] sCount=new int[26]; int[] pCount=new int[26]; for(int i=0;i<pLen;++i){ ++sCount[s.charAt(i)-'a']; ++pCount[p.charAt(i)-'a']; } if(int i=0;i<sLen-pLen;++i){ --sCount[s.charAt(i)-'a']; ++sCount[s.charAt(i+pLen)-'a']; if(Arrays.equals(sCount,pCount)){ ans.add(i+1); } } return ans; }
int sLen=s.length();
int pLen=p.length();
if(sLen<pLen){
return ans;
}
//建立两个数组存放字符串中字母出现的词频，并以此作为标准比较
int [] scount=new int[26];
int [] pcount=new int[26];
//当滑动窗口的首位在s[0]处时 （相当于放置滑动窗口进入数组）
for(int i=0;i<pLen;i++){
++scount[s.charAt(i)-'a'];
//记录s中前pLen个字母的词频
++pcount[p.charAt(i)-'a'];
//记录要寻找的字符串中每个字母的词频(只用进行一次来确定)
}
//判断放置处是否有异位词 (在放置时只需判断一次)
if(Arrays.equals(scount,pcount)){ ans.add(0); }
//开始让窗口进行滑动
for(int i=0;i<sLen-pLen;i++){
//i是滑动前的首位
--scount[s.charAt(i) -'a'];
//将滑动前首位的词频删去
++scount[s.charAt(i+pLen) -'a'];
//增加滑动后最后一位的词频（以此达到滑动的效果）
//判断滑动后处，是否有异位词
if(Arrays.equals(scount,pcount)){
ans.add(i+1);
}
}
return ans;
}
560.和为K的子数组
前缀和+哈希表优化
public int subarraySum(int[] nums, int k) {
int count=0,pre=0;
HashMap<Integer,Integer> mp=new HashMap<>();
mp.put(0,1);
for(int i=0;i<nums.length;i++){
pre+=nums[i];
if(mp.containsKey(pre-k)){
count+=mp.get(pre-k);
}
mp.put(pre,mp.getOrDefault(pre,0)+1);
}
return count;
}
20240412
239.滑动窗口最大值
https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
1.优先队列
public int[] maxSlidingWindow(int[] nums, int k) { int n=nums.length; PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() { public int compare(int[] pair1, int[] pair2) { return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]; } }); for(int i=0;i<k;++i){ pq.offer(new int[]{nums[i],i}); } int[] ans=new int[n-k+1]; ans[0]=pq.peek()[0]; for(int i=k;i<n;++i){ pq.offer(new int[]{nums[i],i}); while(pq.peek()[1]<=i-k){ pq.poll(); } ans[i-k+1]=pq.peek()[0]; } return ans; }
2.单调队列
class MyQueue{ Deque<Integer> deque=new LinkedList<Integer>(); void poll(int val){ if(!deque.isEmpty()&&val==deque.peek()){ deque.poll(); } } void add(int val){ while(!deque.isEmpty()&&val>deque.getLast()){ deque.removeLast(); } deque.add(val); } int peek(){ return deque.peek(); } } public class TwoNum { public int[] maxSlidingWindow(int[] nums,int k){ if(nums.length==1){ return nums; } int len= nums.length-k+1; int[] res=new int[len]; int num=0; MyQueue myQueue=new MyQueue(); for(int i=0;i<k;i++){ myQueue.add(nums[i]); } res[num++]= myQueue.peek(); for(int i=k;i<nums.length;i++){ myQueue.poll(nums[i-k]); myQueue.add(nums[i]); res[num++]=myQueue.peek(); } return res; } }
