文章目录
- 39. 组合总和
- 33. 搜索旋转排序数组
- 153. 寻找旋转排序数组中的最小值
- 49. 字母异位词分组
- 53. 最大子数组和
- 55. 跳跃游戏
- 56. 合并区间
- 62. 不同路径
39. 组合总和
39. 组合总和
DFS排列：每个元素可选0次，1次以及多次
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//Arrays.sort(candidates);//注释了也能通过
this.candidates = candidates;
ans.clear();
comb(0,target,new ArrayList<Integer>());
return ans;
}
int[] candidates;
List<List<Integer>> ans = new ArrayList<>();
void comb(int k,int target,List<Integer> nums){
if(target==0){
ans.add(nums);
return;
}
// target后判断
if(k>=candidates.length) return;
//不选
comb(k+1,target,nums);
// 选一个或者多个
int t = target;
List<Integer> numst = new ArrayList<Integer>(nums);
while (t-candidates[k]>=0){
t -= candidates[k];// 本结点可以选多次
numst.add(candidates[k]);
comb(k+1,t,numst);
}
}
33. 搜索旋转排序数组
33. 搜索旋转排序数组
难点在于logN的时间复杂度
旋转之后的数据分为两个分别升序的部分，若能找到分割点(原来的a[0]）那么在两部分分别进行两次二分查找，不就logN了
这个时候难点就在找分割点了，旋转次数是未知的，分割点也就未知，还得最高logN找分割点，这个时候题目转换成另外一个问题了。
153. 寻找旋转排序数组中的最小值
做完下面的153，再来做本题，就很简单了。
public int search(int[] nums, int target) {
int min = findMin(nums),low=0,high=nums.length-1;
if(target>nums[high]) high = min-1; //左边
else low = min;
// 接下来 low和high里二分查找即可
while (low<=high){//加等号 可能正好相遇时相等呢
int mid = (low+high)/2;
if(nums[mid]==target) return mid;
else if(nums[mid]<target) low = mid+1;
else high = mid-1;
}
return -1;
}
// 153. 寻找旋转排序数组中的最小值 改成返回最小值下标
public int findMin(int[] nums) {
int low=0,high=nums.length-1;
while (low<high){ // 区间长度为1时结束二分
int mid = (low+high)/2;
if(nums[mid]>nums[high]) low = mid+1; //改成+1 low右偏，一定在high相遇
else high = mid;
// 元素互不相同 不会出现相等的情况
}
return high;
}
接下来不找中点，直接用找中点 时nums[high]的性质，判断是在左半段还是右半段，其实用nums[0]也可以判断出来，就用nums[0]吧，target>nums[0] 一定左半段 target<nums[0] 一定在右半段，相等就直接找到了。 其实就是两个方法合二为一了
- 利用性质直接二分
还是二分，但是每次判断3点
- nums[mid]和target 谁大 taregt小，下标变化要舍弃nums里一些偏大的元素， 否则舍弃nums里比较小的元素
- target在左边还是右边 =》 根据target和nums[0]大小可以判断 这会影响舍弃元素时下标变化的策略
- mid 在左边还是右边 =》 根据mid 和nums[0]大小可以判断 这会影响舍弃元素时下标变化的策略
合起来一共23-2 = 6 种情况 。 舍弃的两种是:
- nums[mid]<target<nums[0] ： 也就是不会出现 nums[mid]<target，target右边时(target<nums[0]) ，mid在左边（mid>nums[0]）
- nums[mid]>target>nums[0] ： 也就是不会出现 nums[mid]>target，target左边时(target>nums[0]) ，mid在右边（mid<nums[0]）
153. 寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值
不会，直接看题解，真的简单啊。简单分析一下，就会发现，
nums[high]有一个非常美的性质，取一个元素t, 若t<nums[high],一定在右半段，若t>nums[high],则一定在左半段。 中点 mid = (low+high)/2 ，中点值 nums[mid]必然也满足这个性质。
（“给你一个元素值 互不相同 的数组 nums” 数组元素互不相同）
mid在右半段，去掉其右边的：
mid在左半段，去掉其左边的：
边界就自己举2个例子，一奇一偶，分别手算看看即可。初步分析，因为high在右边小的部分，
- 当然最简单的思路，最终只剩下两个元素时退出二分，取小的一个即可
public int findMin(int[] nums) {
int low=0,high=nums.length-1;
while (high-low>1){ // 区间长度为1时结束二分
int mid = (low+high)/2;
if(nums[mid]>nums[high]) low = mid;
else high = mid;
// 元素互不相同 不会出现相等的情况
}
return Math.min(nums[low],nums[high]); // 最后剩下两个 取一个最小的即可
}
真的要这么麻烦吗，为何要最后两个取最小，因为 mid = (low+high)/2 左偏了，最后一大一小时 会偏向小下标（大值）。而原本就有序时，左偏又是正确的。
那么让一大一小时，mid右偏不就行了，往右偏，最终相遇点一定偏小，（原本有序，肯定nums[0]相遇）
- mid = (low+high)/2+1 右偏即可
public int findMin(int[] nums) {
int low=0,high=nums.length-1;
while (low<high){ // 区间长度为1时结束二分
int mid = (low+high)/2;
if(nums[mid]>nums[high]) low = mid+1; //改成+1 low右偏，一定在high相遇
else high = mid;
// 元素互不相同 不会出现相等的情况
}
return nums[high];
}
2022年09月07日 17:47:32
49. 字母异位词分组
49. 字母异位词分组
太水了，直接暴力也能过：
Map<String,List<String>> mp = new HashMap<String,List<String>>();
public List<List<String>> groupAnagrams(String[] strs) {
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
if(mp.containsKey(key)){
mp.get(key).add(str);
}else {
ArrayList<String> list = new ArrayList<>();
list.add(str);
mp.put(key,list);
}
}
List<List<String>> ans = new ArrayList<>();
for (String s : mp.keySet()) {
ans.add(mp.get(s));
}
return ans;
}
看了题解，跟我写法一样，但是人家代码写得比我清爽多了：
map.getOrDefault(getOrDefault(key, default)如果存在key, 则返回其对应的value, 否则返回给定的默认值default)
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> mp = new HashMap<String,List<String>>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List<String> list = mp.getOrDefault(key, new ArrayList<String>());
list.add(str);
mp.put(key,list);//无则添加 有则覆盖 就是Hash表
}
return new ArrayList<>(mp.values());
}
53. 最大子数组和
53. 最大子数组和
简单DP,但是长时间不写，还是生疏了
核心： dp[i-1]>0 就连上，否则dp[i]=nums[i]只取自己（必须至少取一个啊） 然后到i+1时若dp[i]<0不要就是喽
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max=dp[0];
for (int i = 1; i < nums.length; i++) {
/*if(dp[i-1]+nums[i]>nums[i]) dp[i] = dp[i-1]+nums[i];
else dp[i]=nums[i];*/
dp[i] = Math.max(dp[i-1]+nums[i],nums[i]); // 前面的和>0 加上 否则不加
max=Math.max(max,dp[i]);
}
return max;
}
很明显可以滚动来压缩空间，因为每次dp[i]都只是需要用到dp[i-1]
public int maxSubArray(int[] nums) {
int dp = nums[0],max=nums[0];
for (int i = 1; i < nums.length; i++) {
dp = Math.max(dp+nums[i],nums[i]); // 前面的和>0 加上 否则不加
max=Math.max(max,dp);
}
return max;
}
55. 跳跃游戏
55. 跳跃游戏
public boolean canJump(int[] nums) {
if(nums.length<=1) return true;
// 能跨过0元素即可到达
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
int j = i;
while (j-- > 0) {
if (nums[j] > i - j) break;
else if(nums[j]==i-j&&i==nums.length-1) break;//刚好到最后一个也行
}
if (j < 0) return false;
}
}
return true;
}
- 代码优化
其实最后一个元素不必判断，能跨过前n-1所有的0，肯定能跨过倒数第2个，也就一定能到最后一个
然后再语法层面做一些优化
public boolean canJump(int[] nums) {
// 能跨过0元素即可到达 (调试发现最后一个不必判断 能跨过前n-1所有的0 一定能到达最后)
for (int i = 0; i < nums.length-1; i++) {
if (nums[i] == 0) {
int j = i;
while (--j>=0 && nums[j]<=i-j);
if (j < 0) return false;
}
}
return true;
}
看题解发现一种特别简洁的做法，直接跳就行了，但是时间上慢了
直接跳就行了
能跳到nums[i]其左边的一定能到
每个元素都往最远的跳 都能跳就行
public boolean canJump(int[] nums) {
// 其实一直跳就行了
int k = 0;
for (int i = 0; i < nums.length; i++) {
if(i>k) return false;
k = Math.max(k,nums[i]+i);//每个元素都往最远的跳 都能跳就行 能跳到nums[i]其左边的一定能到
}
return true;
}
56. 合并区间
56. 合并区间
先直接贪心取一下
过了，就行了吧
public int[][] merge(int[][] intervals) {
// lambda表达式 指定按照第一维排序一级排序 第二维二级排序
ArrayList<int[]> list = new ArrayList<>();
Arrays.sort(intervals,(a1,a2)->a1[0]-a2[0]);
for (int i = 0; i < intervals.length; i++) {
int l = intervals[i][0],r=intervals[i][1];
while (i+1<intervals.length&&r>=intervals[i+1][0]){//注意是维护的当前最大右边界>=intervals[i+1][0]
r = Math.max(r,intervals[i+1][1]);//需要维护 不一定最后一个第二维就最大
i++;
}
list.add(new int[]{l,r});
}
int[][] ans = new int[list.size()][2];
for (int i = 0; i < list.size(); i++) {
ans[i] = list.get(i);
}
return ans;
}
62. 不同路径
62. 不同路径
- 方法1，直接用杨辉三角
public int uniquePaths(int m, int n) {
int[][] path = new int[m + 1][n + 1];//外围填充一层0就不用判断边界了
for (int i = 1; i <=m ; i++) {
for (int j = 1; j <= n; j++) {
if(i==1&&j==1) path[i][j] = 1; //这个启始条件还是要有的
else path[i][j] = path[i-1][j]+path[i][j-1];
}
}
return path[m][n];
}
记得高中学排列组合时有个公式直接能算出来啊，去题解看看吧：
果然是有：
高中肯定会，读个大学，啥都忘了，唉~
总共移动(m-1)+(n-1)=m+n-2次 ， 其中向下m-1次，向右n-1次，也就是m+n-2次中挑出m-1次向下,即： C m + n − 2 m − 1 C_{m+n-2}^{m-1} Cm+n−2m−1
或者m+n-2次中挑出n-1次向右，即： C m + n − 2 n − 1 C_{m+n-2}^{n-1} Cm+n−2n−1
