力扣hot100刷题day2（滑动窗口&字串&普通数组&矩阵）-爱代码爱编程
一：滑动窗口
1. 无重复字符的最长子串
题目
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0; //0,1情况
if (s.length()==1) return 1;
Set<Character> set = new HashSet<>();
int left = 0; int right = 0;//窗口左右端
int sum=1; //记录窗口大小
//滑动窗口
while (right<s.length()) {
if (!set.contains(s.charAt(right))) {
set.add(s.charAt(right));
sum=Math.max(sum, set.size());
right++;
}else{
set.remove(s.charAt(left));
left++;
}
}
return sum ;
}
}2.找到字符串中所有字母异位词
找异位词：子串转26位数组（或强转为字符串）
哈希表存储子串，所含字母和出现的次数相同，即为异位词
//字符转26位数组(存为字符)，数组值为字符的出现次数，再强转为字符串 String encode(String s){ char[] chars=new char[26]; for (char i : s.toCharArray()) { int idCount=i-'a'; //记录每个字符出现的次数 chars[idCount]++; } return new String(chars); }
class Solution { public List<Integer> findAnagrams(String s, String p) { int pLen=p.length(); int sLen =s.length(); //s,母串， p，子串 //结果列表 List<Integer> result =new ArrayList<>(); if (sLen < pLen) return result; //存储子串--count函数 //Set<int []> map=new HashSet<>(); //map.add(count(p)); int left=0; int right =pLen-1; while (right<sLen) { String sSub=s.substring(left, right+1); if (Arrays.equals(count(p), count(sSub)) ) { result.add(left); } left++; right++; } return result; } //字符转26位数组，数组值为字符的出现次数， int[] count(String s){ int[] counts=new int[26]; for (int i = 0; i < s.length(); i++) { int idCount=s.charAt(i)-'a'; //记录每个字符出现的次数 counts[idCount]++; } return counts; } }
class Solution { public List<Integer> findAnagrams(String s, String p) { int pLen=p.length(); int sLen =s.length(); //s,母串， p，子串 //结果列表 List<Integer> result =new ArrayList<>(); if (sLen < pLen) return result; //存储子串--count函数 Set<String> map=new HashSet<>(); map.add(encode(p)); int left=0; int right =pLen-1; while (right<sLen) { String sSub=s.substring(left, right+1); if (map.contains(encode(sSub)) ) { result.add(left); } left++; right++; } return result; } //字符转26位数组(存为字符)，数组值为字符的出现次数，再强转为字符串 String encode(String s){ char[] chars=new char[26]; for (char i : s.toCharArray()) { int idCount=i-'a'; //记录每个字符出现的次数 chars[idCount]++; } return new String(chars); } }
class Solution { public List<Integer> findAnagrams(String s, String p) { int n = s.length(); int m = p.length(); if (n < m) { return new ArrayList<>(); } char[] pArr = new char[26]; char[] tempArr = new char[26]; List<Integer> result = new ArrayList<>(); int right = 0; //初始化指针 for (int i = 0; i < m; i++) { pArr[p.charAt(i) - 'a']++; tempArr[s.charAt(i) - 'a']++; right++; } // if (Arrays.equals(pArr, tempArr)) { result.add(0); } for (int i = 1; i <= n - m; i++) { tempArr[s.charAt(i - 1) - 'a']--; tempArr[s.charAt(right) - 'a']++; right++; if (Arrays.equals(pArr, tempArr)) { result.add(i); } } return result; } }8ms
二：子串
1.和为 K 的子数组
前缀和，求前缀和的差为k的个数
class Solution {
public int subarraySum(int[] nums, int k) {
int preSum=0; // 记录前缀和
int count=0; //记录前缀和的差为k的个数
// key值为前缀和,value为出现的次数（集合set元素要唯一）
HashMap<Integer,Integer> map =new HashMap<>();
//先存储（0，1）进去，和为0的次数先有一次
map.put(0, 1);
for (int num : nums) {
preSum+=num;
//边记录前缀和，边找有没有差为k的
count+=map.getOrDefault(preSum-k,0);
//把每一次得到的前缀和加入到map中
int midValue=map.getOrDefault(preSum, 0);
map.put(preSum, midValue+1);
}
return count ;
}
}2.滑动窗口最大值
补充知识：Java队列Queue
offer是队列满了，添加不了，出现异常
pull()返回false,表示删除失败，remove()抛出异常
peek()返回null,表示查不到，element()抛出异常
补充知识：Java队列Deque
Deque是一个双端队列接口，继承自Queue接口，Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最常用的。
Deque是一个线性collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。
思路：
3.最小覆盖子串
public String minWindow(String s, String t) {
// 参数校验
if (s == null || t == null || s.length() < t.length()) {
return "";
}
// 保存t字符出现的次数，表示每个字符待需要的数量
Map<Character, Integer> tMap = new HashMap<>(t.length());
for (int i = 0; i < t.length(); i++) {
tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
}
// 判断窗口是否包含了t的所有元素，避免每次去遍历tMap，增加耗时
int needCnt = t.length();
// 定义最小结果集时的左右边界，初始化边界长度为最大值
int[] minResult = new int[]{0, Integer.MAX_VALUE};
int length = s.length();
// 定义滑动窗口左右边界，右边界开始移动
for (int i = 0, j = 0; j < length; j++) {
char c = s.charAt(j);
// 包含t，待需要的数量减一
if (tMap.getOrDefault(c, 0) > 0) {
needCnt--;
}
// 同时map需要的字符数量减一
tMap.put(c, tMap.getOrDefault(c, 0) - 1);
// 都包含了，此时右边界j不动，开始移动左边界，尝试缩小窗口
if (needCnt == 0) {
while (true) {
c = s.charAt(i);
// 左边界字符已经满足了，不再需要了，则退出循环，没办法继续缩小了
// 否则继续缩小，那么会执行下面的+1，所需要的字符又增加了
if (tMap.get(c) == 0) {
break;
}
// 左边界字符
// map还有多余数量可以缩小
// 缩小左边界，该字符所需要的数量+1
tMap.put(c, tMap.getOrDefault(c, 0) + 1);
i++;
}
// 左边界也更新完了，这时该更新结果了,覆盖res
if (j - i < minResult[1] - minResult[0]) {
minResult[1] = j;
minResult[0] = i;
}
c = s.charAt(i);
//将左边界右移,执行下一个窗口
// 由于左边界是t需要的字符，右移后，需要更新tMap和needCnt，表示还需要增加一个字符
tMap.put(c, tMap.getOrDefault(c, 0) + 1);
needCnt++;
i++;
}
}
// 超过边界，返回空串
if (minResult[1] > length) {
return "";
} else {
return s.substring(minResult[0], minResult[1] + 1);
}
}三：普通数组
1.最大子数组和
思路：
代码
[-2,1,-3,4,-1,2,1,-5,4]class Solution { public int maxSubArray(int[] nums) { int foreMax=0; //记录不包含当前第i个的 子数组 和 int resultMax=Integer.MIN_VALUE; //包含第 i个 的 子数组 和 for ( int i = 0; i < nums.length; i++) { //判断加上i项是否比第i项还小 //是，重置，丢弃前面的i-1项 //（因为求的是连续子数组和） // if (foreMax+nums[i]<nums[i]) { // foreMax=nums[i]; // }else foreMax+=nums[i]; foreMax=foreMax+nums[i]<nums[i]?nums[i]:foreMax+nums[i] //判断之前记录的子数组和与当前新找的大小 //更新最大子数组和 resultMax=Math.max(resultMax, foreMax); } return resultMax; } }
2.合并区间
补充知识：Java中Arrays.sort()自定义排序
当sort()传入参数只是一个数组时，默认将数组按升序排列。
对数组的部分排序，传入起始位置和终止位置(不包括)
实现Comparator接口有两种方式，第一种是上面所示的匿名内部类实现。
第二种是新建一个类然后实现Comparator接口，再new一个类传入sort函数中。
Comparator的参数必须是泛型
将集合转为数组的方法：
merged.toArray(new int[merged.size()][]);
思路：
先按左端点排序
然后前一个区间的右端点大于下一区间的左端点，则可以合并--合并后的右端点取这两个区间右端点的最大值
小于左端点无法合并---这个操作是在新的记录合并后的新的 区间数组里进行的
自定义排序：按照区间的左端点从小到大排序
Arrays.sort(intervals, new Comparator<int[]>() { public int compare(int[] interval1, int[] interval2) { return interval1[0] - interval2[0]; } });lamda正则表达式
// 先按照区间起始位置排序 Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
代码：
class Solution { public int[][] merge(int[][] intervals) { // 所有区间按照左端点从小到大排序 //lamda正则表达式 Arrays.sort(intervals, (v1,v2)->v1[0]-v2[0]); //记录保存合并后的区间List，int不能改数组长度 List<int[]> result=new ArrayList<>(); //用于合并区间时，先把第一个区间放进result里，然后新来的再和这个比较 //看是否能合并 int index=-1; //用以记录result的索引，get(index) //也可以用result.size()记录，每次加的在result的尾端 //合并区间 for (int i = 0; i < intervals.length; i++) { int L=intervals[i][0]; int R=intervals[i][1]; if (index==-1 || result.get(index)[1]<L) { index++; result.add(new int[]{L,R}); }else { result.get(index)[1]=Math.max(R,result.get(index)[1]); } } return result.toArray(new int[index][]); } }
3.轮转数组
思路：
3步翻转
先整体翻转，然后前k个翻转，右边再翻转
翻转函数：
左右两端交换位置，第一个元素与最后一个元素交换位置
public void reverse(int [] nums, int i,int j){ while (i<=j) { int mid=nums[i]; nums[i]=nums[j]; nums[j]=mid; i++;j--; } }代码：
class Solution { public void rotate(int[] nums, int k) { if (k>nums.length) { k=k%nums.length; } reverse(nums, 0, nums.length-1); reverse(nums, 0, k-1); reverse(nums, k, nums.length-1); } public void reverse(int [] nums, int i,int j){ while (i<=j) { int mid=nums[i]; nums[i]=nums[j]; nums[j]=mid; i++;j--; } } }
4.除自身以外数组的乘积
思路1：复杂度：O(n),O(n)
复杂度：O(n),O(n)
class Solution { public int[] productExceptSelf(int[] nums) { //定义左，右乘机与返回值 数组 int[] L =new int[nums.length]; int[] R =new int[nums.length]; int[] ans =new int[nums.length]; L[0]=1;//L数组赋值 for (int i = 1; i < L.length; i++) { L[i]=L[i-1]*nums[i-1]; } R[R.length-1]=1;//L数组赋值 for (int i =R.length-2; i >=0; i--) { R[i]=R[i+1]*nums[i+1]; } for (int i = 0; i < ans.length; i++) { ans[i]=L[i]*R[i]; } return ans; } }
思路2：复杂度：O(n),空间复杂度O(1)
只用返回值数组ans
先在ans中记录i左侧的乘机
对于右侧的乘积，从最后一个元素开始遍历，边找右侧的，边乘到ans中
即完成
class Solution { public int[] productExceptSelf(int[] nums) { //返回值 数组 int[] ans =new int[nums.length]; ans[0]=1;//ans数组先记录左侧的乘积 for (int i = 1; i < ans.length; i++) { ans[i]=ans[i-1]*nums[i-1]; } int R=1;//动态记录右侧的值，并同时给ans for (int i =ans.length-1; i >=0; i--) { ans[i]=ans[i]*R; R=R*nums[i]; } return ans; } }
(运行上差不多)
5.缺失的第一个正数
思路1：O(n),空间复杂度O(n)
class Solution { public int firstMissingPositive(int[] nums) { int len = nums.length; Set<Integer> hashSet = new HashSet<>(); for (int num : nums) hashSet.add(num); for (int i = 1; i <= len ; i++) { if (!hashSet.contains(i)) return i; } return len + 1; } }
思路2：O(n),空间复杂度O(1)
代码：
矩阵置零
四：矩阵
1.矩阵置零
思路：
class Solution { public void setZeroes(int[][] matrix) { int m=matrix.length; int n=matrix[0].length; //标记第1行，列是否有0 boolean rawFlag =false ; boolean colFlag=false; //标记第1列是否有0 for (int i = 0; i < m; i++) {if (matrix[i][0]==0) colFlag=true;} //标记第1行是否有0 for (int j = 0; j < n; j++) {if (matrix[0][j]==0) rawFlag=true;} //用第1行，列标记矩阵的i,j位有0 //从1开始 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j]==0) {matrix[0][j]=0;matrix[i][0]=0;} } } //置0 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][0]==0||matrix[0][j]==0) {matrix[i][j]=0;} } } //第1行置0,//第1列置0 if (colFlag) {for (int i = 0; i < m; i++) matrix[i][0]=0;} if (rawFlag) {for (int j = 0; j < n; j++) matrix[0][j]=0;} } }
2.螺旋矩阵
思路：
直接看代码，很好懂，
代码：
class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res=new ArrayList<>();//返回值 int up=0;int low=matrix.length-1; //low行 int left=0;int right=matrix[0].length-1;//right 列 while (true) { for (int j = left; j <= right; j++) res.add(matrix[up][j]); if (++up>low) break; for (int i = up; i <= low; i++) res.add(matrix[i][right]); if (--right<left) break; for (int j = right; j >= left; j--) res.add(matrix[low][j]); if (--low<up) break; for (int i = low; i >= up; i--) res.add(matrix[i][left]); if (++left>right) break; } return res; } }
3：旋转图像
第1行变最后1列
思路：
中间矩阵，赋值过去，空间复杂度O（n2）,
原地变换，一次4个元素一起换（用中间矩阵是两个元素一起换）
一次换4个，原地换两个，会被覆盖
换的思路：
第i行换到 倒数第i列（第n-1-i列，10个，倒数第2个，正数（10-2）个）
第j列换到 正数第j行
第一个元素A(i,j) 第二个元素B(j,n-1-i)
第三个元素C(n-1-i,n-1-j),第4个元素D(n-1-j,n-1-(n-1-i))
注意不是所有元素都换，否则会回到原矩阵，
n为偶数，前n/2行和n/2列的元素----4,(2,2)--
i n/2， j n/2与 （n+1）/2等价 （4+1）/2=2
n为奇数前n/2行和（n+1）/1列的元素
i n/2 j（n+1）/2
代码
class Solution { public void rotate(int[][] matrix) { int n=matrix.length; for (int i = 0; i < n/2; i++) { for (int j = 0; j < (n+1)/2; j++) { int temp=matrix[i][j]; // matrix[i][j]=matrix[j][n-1-i]; -逆时针，转置 // matrix[j][n-1-i]=matrix[n-1-i][n-1-j]; // matrix[n-1-i][n-1-j]=matrix[n-1-j][i]; // matrix[n-1-j][i]=temp; matrix[i][j]=matrix[n-1-j][i]; matrix[n-1-j][i]=matrix[n-1-i][n-1-j]; matrix[n-1-i][n-1-j]=matrix[j][n-1-i]; matrix[j][n-1-i]=temp; } } } }
4.搜索二维矩阵 II
返回值为true,false
