赞
踩
看错输入样例,以为是排序的
map底层实现是红黑树,而unordered_map为哈希表
暴力解法,两层循环遍历找到两数
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> result; int len = nums.size(); for(int i = 0; i < len - 1; i++){ for(int j = i + 1; j < len; j++){ if(nums[i] + nums[j] == target){ result.push_back(i); result.push_back(j); return result; } } } return result; } };
map映射 把vector->map中,再遍历map,以找到符合target的两个数(对于两个相同的数,如[3,0,3]是在映射到map之前,判断map中有没有存在这个key,并且2 * key是不是为target,?那为什么不每次都查找map中有无目标值呢?)
代码已改,两个for循环
hash映射 遍历vector,并插入到unorder_map中(即hash表),但在此之前判断unorder_map中有无目标值,若有则已找到结果;(这个对于两个相同的数比较好判断)
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> result; unordered_map<int, int> mymap; unordered_map<int, int>::iterator it; int len = nums.size(); for(int i = 0; i < len; i++){ it = mymap.find(target - nums[i]); if(it != mymap.end()){ result.push_back(it->second); result.push_back(i); break; } else mymap.insert(pair<int, int>(nums[i], i)); } return result; } };
最开始的想法是两层for循环遍历,找到每一种情况,但是这样时间复杂度过高。
tag中有个关键词是two-pointer就想到了首尾指针,并向中间靠拢。那到底移左边的还是右边的呢?
可以看到,每次只移动一步,那么宽度是都是减小1,指针移动后的容器面积增大=移动后的容器的高尽量大。如果left的height高于right的,短板在于right选择高度较小的指针移动,而保留left可能得到更优的结果。
class Solution { public: int maxArea(vector<int>& height) { int l = 0, r = height.size() - 1; int area = 0, temp = 0; while(l < r){ if(height[l] > height[r]){ temp = height[r] * (r - l); r--; } else{ temp = height[l] * (r - l); l++; } area = area > temp ? area : temp; } return area; } };
三个数之和和两个数之和有相似之处,先确定第一个数字,然后求得所有的两数之和(第一个数字的相反数)的组合。
开始的思路很混乱,因为有重复的数字,并且有多个组合,所有利用到了排序,变成有序数组。
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; vector<vector<int>>::iterator it; sort(nums.begin(), nums.end()); int l, r, len = nums.size() - 1; for(int i = 0; i < len - 1; i++){ if(i == 0 || nums[i] != nums[i - 1]){ l = i + 1; r = len; while(l < r){ if(nums[l] + nums[r] > - nums[i]){ r--; }else if(nums[l] + nums[r] < -nums[i]){ l++; }else{ if(l != i + 1 && nums[l] == nums[l - 1]) l++; else if(r != len && nums[r] == nums[r + 1]) r--; else{ vector<int>t {nums[i], nums[l], nums[r]}; result.push_back(t); r--; l++; } } } } } return result; } };
上一个题目就是三数之和,这个是最接近的三数之和,所有可以从target,target+1,····,target+n开始测试。
借用了上一题的代码,将排序提取出来,并且无需判断是否重复组合,当有符合条件的组合返回true。
复杂度为O(N3)
class Solution { public: bool threeSum(vector<int>& nums, int t) { int l, r, len = nums.size() - 1; for(int i = 0; i < len - 1; i++){ if(i == 0 || nums[i] != nums[i - 1]){ l = i + 1; r = len; while(l < r){ if(nums[l] + nums[r] > t - nums[i]){ r--; }else if(nums[l] + nums[r] < t -nums[i]){ l++; }else{ return true; } } } } return false; } int threeSumClosest(vector<int>& nums, int target) { int i = 0; sort(nums.begin(), nums.end()); while(1) { if(threeSum(nums, target + i) == true) return target + i; if(threeSum(nums, target - i) == true) return target - i; i++; } return 0; } };
也可以直接双层遍历
当遇到更小的sum值就更新,复杂度为O(N2)
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int l, r, len = nums.size() - 1, sum, best = target + 10000; for(int i = 0; i < len - 1; i++){ if(i == 0 || nums[i] != nums[i - 1]){ l = i + 1; r = len; while(l < r){ sum = nums[i] + nums[l] + nums[r]; if(abs(best - target) > abs(sum - target)) best = sum; if(sum > target){ r--; }else if(sum < target){ l++; }else{ return target; } } } } return best; }
第一次for循环确定a的值
第二次for循环确定b的值
最内层用双指针,找到c和d的值
并且判断是否有重复的情况
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; sort(nums.begin(), nums.end()); int l, r, len = nums.size() - 1, sum; for(int i = 0; i < len - 2; i++){ if(i == 0 || nums[i] != nums[i - 1]){ for(int j = i + 1; j < len - 1; j ++){ if(j == i + 1 || nums[j] != nums[j - 1]){ l = j + 1; r = len; while(l < r){ sum = nums[l] + nums[r] + nums[i] + nums[j]; if(sum > target){ r--; }else if(sum < target){ l++; }else{ if(l != j + 1 && nums[l] == nums[l - 1]) l++; else if(r != len && nums[r] == nums[r + 1]) r--; else{ vector<int>t {nums[i], nums[j], nums[l], nums[r]}; result.push_back(t); r--; l++; } } } } } } } return result; } };
即利用双指针,若pos与pos1指向的值不相等,则可以赋值到pos+1;
但是忽略了数组长度为0的情况
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0)
return 0;
int len = 1;
for(int i = 0; i < nums.size(); i++){
if(nums[len - 1] != nums[i])
nums[len++] = nums[i];
}
return len;
}
};
将l从左至右指向等于val的值,将r从右至左指向非val的值,并且交换;
忽略了数组的值全为val的情况,即初始代码的终止情况可能l和r会指向同一个值,但若这个值为val也应该移除,那么应该while中判断条件为l<=r
class Solution { public: int removeElement(vector<int>& nums, int val) { int l = 0, r = nums.size() - 1, temp; while(l <= r){ if(nums[l] == val && nums[r] != val){ temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; l++; r--; } if(nums[l] != val) l++; if(nums[r] == val) r--; } return r + 1; } };
数组倒着查找nums[j] > nums[j-1]的情况
class Solution { public: void nextPermutation(vector<int>& nums) { int len = nums.size(); if(len == 1) return; int t, j; for(j = len - 1; j > 0; j--){ if(nums[j] > nums[j - 1]) break; } if(j == len - 1){ t = nums[len - 1]; nums[len - 1] = nums[len - 2]; nums[len - 2] = t; } else if(j == 0){ for(int i = 0; i < len / 2; i ++){ t = nums[i]; nums[i] = nums[len - i - 1]; nums[len - i - 1] = t; } } else{ for(int i = j; i < len; i ++){ if((i == len -1 && nums[i] > nums[j - 1]) || (nums[i] > nums[j - 1] && nums[i + 1] <= nums[j - 1])){ t = nums[i]; nums[i] = nums[j - 1]; nums[j - 1] = t; break; } } for(int i = j; i < j + (len - j) / 2; i++){ t = nums[i]; nums[i] = nums[len - i - 1 + j]; nums[len - i - 1 + j] = t; } } return; } };
先找到是围绕哪个点旋转,即坐标i-1;
之后当成普通的二分搜索,但mid的坐标要加上i;
可是效率不高 是log(N)
class Solution { public: int search(vector<int>& nums, int target) { int len = nums.size(), i; int l = 0, r = len - 1, mid, m; for(i = 0; i < len - 1; i++){ if(nums[i] > nums[i + 1]) break; } i++; while(l <= r){ mid = l + (r - l) / 2; m = (mid + i) % len; if(nums[m] == target) return m; else if(nums[m] > target) r = mid - 1; else l = mid + 1; } return -1; } };
官方文档是用到了二分法,即分为排序和未排序的两段
class Solution { public: int search(vector<int>& nums, int target) { int len = nums.size(); int l = 0, r = len - 1, mid; while(l <= r){ mid = l + (r - l) / 2; if(nums[mid] == target) return mid; else if(nums[mid] > target){ if(nums[r] >= nums[mid]|| nums[r] < target) r = mid - 1; else l = mid + 1; } else{ if(nums[l] <= nums[mid] || nums[l] > target) l = mid + 1; else r = mid - 1; } return -1; } } };
题目要求时间复杂度为O(log n),所以肯定要用到二分法;
首先用普通的二分搜索找到nums[mid]=target,且记住l、r;
如果r<l那么不存在target;
否则,分为l ~ mid 以及mid ~ right;并且当mid处的值为target,mid-1处不为target,此时mid为其左边界;右边界同理;
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int len = nums.size() - 1, l = 0, r = len, mid; while(l <= r){ mid = l + (r - l) / 2; if(target == nums[mid]) break; else if(target > nums[mid]) l = mid + 1; else r = mid - 1; } if(l > r) return vector<int> {-1, -1}; int ml = mid, mr = mid; while(l <= ml){ mid = l + (ml - l) / 2; if(nums[mid] == target){ if(mid != 0 && nums[mid - 1] == target) ml = mid - 1; else{ ml = mid; break; } } else l = mid + 1; } while(mr <= r){ mid = mr + (r - mr) / 2; if(nums[mid] == target){ if(mid != len && nums[mid + 1] == target) mr = mid + 1; else{ mr = mid; break; } } else r = mid - 1; } return vector<int> {ml, mr}; } };
官方解法
即直接寻找左右边界
如找左边界时,mid处为大于等于target,应继续向左找,r=mid-1;否则l=mid+1;当l大于r时,l为所求;右边同理;
当存在这个值时,普通的二分搜索返回位置即可;
不存在的时候,nums[pos-1]<target<nums[pos]仍然返回pos;while循环结束的条件为l大于r,考虑最后一次循环移动的是r,那么mid处的值必然大于target,r=mid-1(l-1),此时mid=l;同理,即l为pos;
class Solution { public: int searchInsert(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1, mid; while(l <= r) { mid = l + (r - l) / 2; if(nums[mid] == target) return mid; else if(nums[mid] > target) r = mid - 1; else l = mid + 1; } return l; } };
回溯法,不合适就返回上一步,并且通过约束条件,剪枝;
遍历candidates数组,用temp记录当前选取的数值;当等于target时,记录该方案;大于target时,由于数组时有序的,之后的数字会更大,那么直接返回上一层,剪枝;否则,加入该candidates[i],递归到下一层,并且结束之后,可以回退到该层,继续选择candidates[i+1];这样实现全部遍历;
class Solution { public: void combinationSumHelp(vector<vector<int>> & result, vector<int> & candidates, vector<int> temp, int target, int pos){ for(int i = pos; i < candidates.size(); i++){ if(candidates[i] == target){ temp.push_back(candidates[i]); result.push_back(temp); return; } else if( candidates[i] < target){ temp.push_back(candidates[i]); combinationSumHelp(result, candidates, temp, target - candidates[i], i); temp.pop_back(); } else return; } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> result; vector<int> temp; sort(candidates.begin(), candidates.end()); combinationSumHelp(result, candidates, temp, target, 0); return result; } };
与39题类似,每个数字只能使用一次,故选择第i个数字,之后递归只能用i+1及之后的数字;candidates里面有重复的数字,需要在递归之前先判断是否candidates[i]=candidates[i-1],若等于,result中肯定出现过该组合;
class Solution { public: void combinationSum2Help(vector<vector<int>> & result, vector<int> & candidates, vector<int> temp, int target, int pos){ for(int i = pos; i < candidates.size(); i++){ if(i != pos && candidates[i] == candidates[i - 1]) continue; if(candidates[i] == target){ temp.push_back(candidates[i]); result.push_back(temp); return; } else if( candidates[i] < target){ temp.push_back(candidates[i]); combinationSum2Help(result, candidates, temp, target - candidates[i], i + 1); temp.pop_back(); } else return; } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<vector<int>> result; vector<int> temp; sort(candidates.begin(), candidates.end()); combinationSum2Help(result, candidates, temp, target, 0); return result; } };
[i][j]->[j][n-1-i]->[n-1-i][n-1-j]->[n-1-j][i]->[i][j]
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int t, n = matrix[0].size();
for(int i = 0; i < n / 2; i++){
for(int j = i; j < n - 1 - i; j++){
t = matrix[i][j];
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] = t;
}
}
}
};
动态规划 f(n) = max(f(n-1) + A[n], A[n])
将大问题分解为小问题,即当f(n-1)为0时,则不加入该子序列
class Solution {
public:
int maxSubArray(vector& nums) {
int best = nums[0], temp = nums[0];
for(int i = 1; i < nums.size(); i++){
temp = temp > 0 ? nums[i] + temp : nums[i];
best = best > temp ? best : temp;
}
return best;
}
};
用turn控制移动方向,每个方向读取的数字长度num序列为n,m-1,n-1,m-2,n-2,···当num为0时则读取结束;num与turn相关,num = m(n)-turn/2-1;;
并且先对行row列col值自加自减,然后读取元素,因此初始值row=0,col=-1;
class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> result; int m = matrix.size(); if(m == 0) return result; int n = matrix[0].size(); if(n == 0) return result; int num = n, turn = 0, row = 0, col = -1, i; while(num > 0){ i = 0; if(turn % 4 == 0){ while(i < num){ result.push_back(matrix[row][++col]); i++; } } else if(turn % 4 == 1){ while(i < num){ result.push_back(matrix[++row][col]); i++; } } else if(turn % 4 == 2){ while(i < num){ result.push_back(matrix[row][--col]); i++; } } else{ while(i < num){ result.push_back(matrix[--row][col]); i++; } } if(turn % 2 != 0) num = n - turn / 2 - 1; else num = m - turn / 2 - 1; turn++; } return result; } };
错误思路:从后往前遍历数组(倒数第二个位置开始),只要能越过每个0即可到达终点;
错误版本1:在遇到下一个0之前,判断中间位置的位置能否越过之前的0;没有考虑连续0在一起的情况
错误版本2:若与之前的0相连,则不更新pos0的值;越过pos0才可以。
int canJump(vector<int>& nums) { int end2 = nums.size() - 2; int pos = end2, pos0 = pos; bool flag = true; while(pos >= 0){ if(nums[pos] == 0){ if(pos == end2 || nums[pos + 1] != 0){ pos0 = pos; if(flag == false){ return false; } flag = false; } } else if(nums[pos] > pos0 - pos) flag = true; pos--; } return flag; }
贪心算法,对于可达位置pos它能到达最远的位置为pos+nums[pos],若大于pos0,则在pos位置,pos0可达;
官方解法:我们依次遍历数组中的每一个位置,并实时维护最远可以到达的位置。对于当前遍历到的位置 x,如果它在最远可以到达的位置的范围内,那么我们就可以从起点通过若干次跳跃到达该位置,因此我们可以用 x+nums[x] 更 最远可以到达的位置。
在遍历的过程中,如果最远可以到达的位置 大于等于数组中的最后一个位置,那就说明最后一个位置可达,我们就可以直接返回 True 作为答案
class Solution {
public:
bool canJump(vector<int>& nums) {
int end1 = nums.size() - 1, num = 0;
for(int i = 0; i <= end1; i++){
if(i <= num){
num = i + nums[i] > num ? i + nums[i] : num;
if(num >= end1)
return true;
}
}
return false;
}
};
没有找到正确的思路,太难了
对每个区间以最左区间排序,如果相邻两个区间的l2小于r,说明有重叠部分,r的值更新为r和r2中的较大值;如果l2大于r,那就是一个新的区间,把当前的l和r存入result中的一个区间;
最后区间l和r需要for循环之后再加入
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>> result; int s = intervals.size(); if(s == 0) return result; sort(intervals.begin(), intervals.end()); int l = intervals[0][0], r= intervals[0][1]; for(int i = 1; i < s; i++){ if(intervals[i][0] <= r) r = intervals[i][1] > r ? intervals[i][1] : r; else{ vector<int> t {l, r}; result.push_back(t); l = intervals[i][0]; r = intervals[i][1]; } } vector<int> t {l, r}; result.push_back(t); return result; } };
引用某题友的思路
对于这种螺旋遍历的方法,重要的是要确定上下左右四条边的位置,那么初始化的时候,上边up就是0,下边down就是m-1,左边left是0,右边right是n-1。然后我们进行while循环,先遍历上边,将所有元素加入结果res,然后上边下移一位,如果此时上边大于下边,说明此时已经遍历完成了,直接break。
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> result (n, vector<int>(n, 0)); int i = 1, left = 0, right = n - 1, up = 0, down = n - 1; while(1){ for(int j = left; j <= right; j++) result[up][j] = i++; if(++up > down) break; for(int j = up; j <= down; j++) result[j][right] = i++; if(--right < left) break; for(int j = right; j >= left; j--) result[down][j] = i++; if(--down < up) break; for(int j = down; j>= up; j--) result[j][left] = i++; if(++left > right) break; } return result; } };
动态规划:dp[i][j] = dp[i-1][j] + dp[i][j-1],时间复杂度O(n*m),空间复杂度O(n)
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> t1 (n, 1);
vector<int> t2 (n, 1);
for(int i = m - 2; i >= 0; i--){
for(int j = n - 2; j >= 0; j--){
t1[j] = t2[j] + t1[j + 1];
t2[j] = t1[j];
}
}
return t1[0];
}
};
可以利用数学排列来解
Cm−1m+n+2
依旧是动态规划算法,如果此处有障碍,则方法数为0;dp[i][j] = dp[i-1][j] + dp[i][j-1]
注意两点:
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid[0].size(); if(m == 0) return 1; vector<long long> pre(n, 1); vector<long long> cur(n, 1); for(int i = n - 1; i >= 0; i--){ if((obstacleGrid[m - 1][i] == 1) || (i != n - 1 && cur[i + 1] == 0)){ cur[i] = 0; pre[i] = 0; } } for(int i = m - 2; i >= 0; i--){ if(obstacleGrid[i][n - 1] == 1){ cur[n - 1] = 0; pre[n - 1] = 0; } for(int j = n - 2; j >= 0; j--){ if(obstacleGrid[i][j] == 1) cur[j] = 0; else cur[j] = cur[j + 1] + pre[j]; pre[j] = cur[j]; } } return (int)cur[0]; } };
还是用动态规划法做,与62、63类似
没做
应该是从右到左看有无进制,到了最前面,再插入1
只想到了额外空间O(m+n)的方法,利用位图,判断行列中是否有0,时间和空间复杂度都为O(m*n)
class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(), t = m + n; int flag[t]; for(int i = 0; i < t; i++) flag[i] = 0; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(matrix[i][j] == 0){ flag[i] = 1; flag[m + j] = 1; } } } for(int i = 0; i < m; i++){ if(flag[i] == 1){ for(int j = 0; j < n; j++){ matrix[i][j] = 0; } } } for(int i = 0; i < n; i++){ if(flag[i + m] == 1){ for(int j = 0; j < m; j++){ matrix[j][i] = 0; } } } } };
参考O(1)解法
空间复杂度 O(2) ,用两个布尔变量就可以解决。方法就是利用数组的首行和首列来记录 0 值。从数组下标的 A[1][1] 开始遍历,若A[i][j]值为0,那么将[i][0]和[0][j]置为0,表明i行和j列该置为0,而两个布尔值记录首行首列是否需要置0。
二分搜索,当成有序一维数组,mid求得行列值做判断;
有个案例是[] 0,没有考虑到
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); if(m == 0) return false; int n = matrix[0].size(); int l = 0, r = (m - 1) * n + n - 1, mid, mr, mc; while(l <= r){ mid = l + (r - l) / 2; mr = mid / n; mc = mid % n; if(matrix[mr][mc] > target) r = mid - 1; else if(matrix[mr][mc] < target) l = mid + 1; else return true; } return false; } };
没有想到一次遍历的方法
三指针法,p0和p2表示0和2的边界,curr遍历搜索;
若 nums[curr] = 0 :交换第 curr个 和 第p0个 元素,并将指针都向右移。换过来的数一定是0或者1,且为0时一定是最开始的时候;
若 nums[curr] = 2 :交换第 curr个和第 p2个元素,并将 p2指针左移 。由于不确定换过来的数是否为2;
若 nums[curr] = 1 :将指针curr右移。
class Solution { public: void sortColors(vector<int>& nums) { int l = 0, c = 0, r = nums.size() - 1, t; while(c <= r){ if(nums[c] == 0){ t = nums[l]; nums[l] = nums[c]; nums[c] = t; l++; c++; } else if(nums[c] == 1) c++; else{ t = nums[r]; nums[r] = nums[c]; nums[c] = t; r--; } } } };
vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; vector<int> r; result.push_back(r); for(int i = 0; i < nums.size(); i++){ int size = result.size(); for(int j = 0; j < size; j++){ vector<int> t (result[j]); t.push_back(nums[i]); result.push_back(t); //result.push_back(result[j]); //result[result.size() - 1].push_back(nums[i]); } } return result; } };
class Solution { public: void subsetshelp(vector<vector<int>> &result, vector<int>& nums, int pos, vector<int> t){ if(pos == nums.size()){ result.push_back(t); return; } subsetshelp(result, nums, pos + 1, t); t.push_back(nums[pos]); subsetshelp(result, nums, pos + 1, t); } vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; vector<int> t; subsetshelp(result, nums, 0, t); return result; } };
回溯搜索,flag标记数组
class Solution { public: bool existhelp(vector<vector<char>>& board, vector<vector<bool>>& flag, string word, int row, int col, int pos){ if(pos == word.length()) return true; int m = board.size(), n = board[0].size(); if(row == m || col == n || row == -1 || col == -1) return false; if(flag[row][col] == 1 || board[row][col] != word[pos]) return false; flag[row][col] = 1; if(existhelp(board, flag, word, row, col + 1, pos + 1) == true || existhelp(board, flag, word, row + 1, col, pos + 1) == true || existhelp(board, flag, word, row - 1, col, pos + 1) == true || existhelp(board, flag, word, row, col - 1, pos + 1) == true) return true; flag[row][col] = 0; return false; } bool exist(vector<vector<char>>& board, string word) { int m = board.size(), n = board[0].size(); vector<vector<bool>> flag (m, vector<bool> (n, 0)); for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(existhelp(board, flag, word, i, j, 0) == true) return true; } } return false; } };
从两个数组的尾部开始遍历,依次插入较大值;当某个数组遍历完之后,只用插入另一个数组;
开始用JAVA写代码了,可阅读性会差很多吧
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int pos = m + n - 1, i = m - 1, j = n - 1; while(i >= 0 || j >= 0){ if(i >= 0 && j >= 0){ if(nums1[i] > nums2[j]) nums1[pos--] = nums1[i--]; else nums1[pos--] = nums2[j--]; } else if(i >= 0) nums1[pos--] = nums1[i--]; else nums1[pos--] = nums2[j--]; } } }
首先判断数组的长度,0或1就是其本身;大于等于2,前两个是不用判断,肯定能保留,之前遍历数组,若不是同时等于pos-1和pos-2处数字,则保留;
class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null)
return 0;
int n = nums.length;
if(n == 1)
return n;
int pos = 2;
for(int i = 2; i < n; i++){
if(nums[i] != nums[pos - 1] || nums[i] != nums[pos - 2])
nums[pos++] = nums[i];
}
return pos;
}
}
之前有过类似的题目,但是没有想出来,这次还是有点问题,这里直接引用别人的思路
数组旋转之后,必定存在前半段或者后半段是有序;
若前半段有序left<mid处的值,left<=target<mid,说明在前半段,否则就在后半段;
后半段有序mid<target处的值,mid<target<=right,说明在后半段,否则就在前半段;
由于会出现left=mid处值的情况,则需要跳过该left直到找到和mid不一样的值为止!
class Solution { public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) { return false; } int start = 0; int end = nums.length - 1; int mid; while (start <= end) { mid = start + (end - start) / 2; if (nums[mid] == target) { return true; } if (nums[start] == nums[mid]) { start++; continue; } //前半部分有序 if (nums[start] < nums[mid]) { //target在前半部分 if (nums[mid] > target && nums[start] <= target) { end = mid - 1; } else { //否则,去后半部分找 start = mid + 1; } } else { //后半部分有序 //target在后半部分 if (nums[mid] < target && nums[end] >= target) { start = mid + 1; } else { //否则,去后半部分找 end = mid - 1; } } } //一直没找到,返回false return false; } }
跟之前的子集一样的思路,但这里存在重复的元素,因此需要用map来存储元素及其出现的次数,元素出现次数不同则子集不同
由于用JAVA编写,API实在不熟悉,出现了很多问题。
class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> result = new ArrayList<>(); result.add(new ArrayList<>()); HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i = 0; i < nums.length; i++){ if(map.containsKey(nums[i])) map.put(nums[i], map.get(nums[i]) + 1); else map.put(nums[i], 1); } for(HashMap.Entry<Integer, Integer> it : map.entrySet()){ int size = result.size(); for(int i = 0; i < size; i++){ List<Integer> temp = new ArrayList<>(result.get(i)); for(int j = 0; j < it.getValue(); j++){ temp.add(it.getKey()); List<Integer> temp2 = new ArrayList<>(temp); result.add(temp2); } } } return result; } }
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
preorder数组第一个数字为root,然后在inorder遍历找到root的index,左边为左子树,右边为右子树;分别得到左右子树的长度,将preorder分段;递归;
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTreeHelp(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } private TreeNode buildTreeHelp(int[] preorder, int pl, int pr, int[] inorder, int il, int ir){ if(pr < pl) return null; if(pr == pl) return new TreeNode(preorder[pl]); int temp = preorder[pl], index = -1; for(int i = il; i <= ir; i++){ if(inorder[i] == temp){ index = i; break; } } if(index == -1) throw new RuntimeException("!!!"); TreeNode root = new TreeNode(temp); root.left = buildTreeHelp(preorder, pl + 1, pl + (index - il), inorder, il, index - 1); root.right = buildTreeHelp(preorder, pl + (index - il) + 1, pr, inorder, index + 1, ir); return root; } }
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
[ [左子树的后序遍历结果], [右子树的后序遍历结果], 根节点 ]
class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return buildTreeHelp(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); } private TreeNode buildTreeHelp(int[] inorder, int il, int ir, int[] postorder, int pl, int pr) { if(pr < pl) return null; if(pr == pl) return new TreeNode(postorder[pr]); int temp = postorder[pr], index = -1; for(int i = il; i <= ir; i++) { if(inorder[i] == temp){ index = i; break; } } TreeNode root = new TreeNode(postorder[pr]); root.left = buildTreeHelp(inorder, il, index - 1, postorder, pl, pl + (index - il) - 1); root.right = buildTreeHelp(inorder, index + 1, ir, postorder, pl + (index - il) , pr - 1); return root; } }
JAVA的语法不一样;
List只能迭代,使用set和get,多层List只能取每一层List直到操作最内层List;
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(numRows < 1) return result; result.add(new ArrayList<Integer>()); result.get(0).add(1); for(int i = 2; i <= numRows; i++){ List<Integer> temp = new ArrayList<Integer> (); temp.add(1); List<Integer> temp1 = result.get(i - 2); for(int j = 2; j <= i - 1; j++){ temp.add(temp1.get(j - 2) + temp1.get(j - 1)); } temp.add(1); result.add(new ArrayList<Integer>(temp)); } return result; } }
用两个list
class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> l1 = new ArrayList<Integer>(); l1.add(1); int t; for(int i = 1; i <= rowIndex; i++){ List<Integer> l2 = new ArrayList<Integer>(l1); for(int j = 1; j < i; j++){ t = l2.get(j - 1) + l2.get(j); l1.set(j, t); } l1.add(1); } return l1; } }
更新当前j的时候,就把之前j的信息覆盖掉了。而更新 j + 1 的时候又需要之前j的信息,所以在更新前,我们需要一个变量把之前j的信息保存起来
动态规划算法
从最底端往上走,第i层第j个元素会经过第i+1层第j或j+1个元素中的较小值;
那么数组的第一个元素为所求;
class Solution { public int minimumTotal(List<List<Integer>> triangle) { int len = triangle.size(), t; if(len == 0) return 0; List<Integer>temp = new ArrayList<Integer>(triangle.get(len - 1)); for(int i = len - 2; i >= 0; i--){ List<Integer> temp1 = new ArrayList<Integer>(triangle.get(i)); for(int j = 0; j <= i; j++){ t = temp.get(j) < temp.get(j + 1) ? temp.get(j) : temp.get(j + 1); temp.set(j, t + temp1.get(j)); } } return temp.get(0); } }
也可以从顶端往底端走,用数组保存每一层从顶端到该层的最短路径;第i层第0/size()-1个元素只能经过第i-1层第0/size()-1个元素,但其他元素经过第i-1层第j-1/j个元素;
最后遍历数组,最小值为所求;
用动态规划来做,数组t[i][j]保存第i个元素到第j个元素的乘积,遍历得到最大值,但是内存错误;
class Solution { public int maxProduct(int[] nums) { int n = nums.length; int [][] t = new int [n][n]; for(int i = 0; i < n; i++){ for(int j = 0; j < i; j++){ t[i][j] = t[i - 1][j] * nums[i]; } t[i][i] = nums[i]; } int temp = nums[0]; for(int i = 1; i < n; i++){ for(int j = 0; j <= i; j++){ if(t[i][j] > temp) temp = t[i][j]; } } return temp; } }
开始的想法有过判断负数的个数,如果是偶数那么全乘,奇数则对左边或者右边做取舍;但是又涉及到0;没有想到像官方解法一样的思路,当有正负时,需要同时开了最大最小;
我们可以根据正负性进行分类讨论。
考虑当前位置如果是一个负数的话,那么我们希望以它前一个位置结尾的某个段的积也是个负数,这样就可以负负得正,并且我们希望这个积尽可能「负得更多」,即尽可能小。如果当前位置是一个正数的话,我们更希望以它前一个位置结尾的某个段的积也是个正数,并且希望它尽可能地大。于是这里我们可以再维护一个 fmin,它表示以第i个元素结尾的乘积最小子数组的乘积,那么我们可以得到这样的动态规划转移方程:
class Solution { public int maxProduct(int[] nums) { int n = nums.length, timax, timin; int [] tmax = new int [n]; int [] tmin = new int [n]; tmax[0] = nums[0]; tmin[0] = nums[0]; for(int i = 1; i < n; i++){ timax = nums[i] * tmax[i - 1]; timin = nums[i] * tmin[i - 1]; tmax[i] = Math.max(timax, Math.max(nums[i], timin)); tmin[i] = Math.min(timax, Math.min(nums[i], timin)); } timax = tmax[0]; for(int i = 1; i < n; i++){ timax = Math.max(timax, tmax[i]); } return timax; } }
想法有点复杂,分多种情况讨论
class Solution { public int findMin(int[] nums) { int l = 0, r = nums.length - 1, mid = 0; while(l <= r){ mid = l + (r - l) / 2; if(nums[l] <= nums[r]) return nums[l]; else if(nums[l] <= nums[mid]) l = mid + 1; else{ if(nums[mid] > nums[mid - 1]) r = mid - 1; else return nums[mid]; } } return nums[mid]; } }
官方的解法直接考虑mid与r的值比较,不断的向右移;
若mid小于r的值,r=mid;
否则l=mid+1;
虽然知道是二分法,但是没有思路
由于-1和len所在位置的值为负无穷大,若mid不是峰值,选择mid-1和mid+1之中较大值的那一段(必定有峰值)即mid+1一直是递增,总会找到极大值(len为负无穷);
class Solution { public int findPeakElement(int[] nums) { int len = nums.length; if(len == 1) return 0; if(nums[0] > nums[1]) return 0; if(nums[len -2] < nums[len - 1]) return len - 1; int l = 1, r = len - 2, mid; while(l <= r){ mid = l + (r - l) / 2; if(nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) return mid; else if(nums[mid + 1] > nums[mid - 1]) l = mid + 1; else r = mid - 1; } return -1; } }
二分搜索,用数组保存前缀和,将寻找包括当前元素的最短子数组的时间复杂度变为O(logn),遍历整个数组;
或许可以用提供的API binarySearch
class Solution { public int minSubArrayLen(int s, int[] nums) { int len = nums.length, best = len + 1; if(len == 0) return 0; if(nums[0] >= s) return 1; int [] temp = new int [len]; temp[0] = nums[0]; for(int i = 1; i < len; i++){ temp[i] = temp[i - 1] + nums[i]; if(temp[i] >= s){ int l = 0, r = i - 1, mid; best = i + 1 < best ? i + 1 : best; while(l <= r){ mid = l + (r - l) / 2; if(temp[i] - temp[mid] >= s){ best = i - mid < best ? i - mid : best; l = mid + 1; } else r = mid - 1; } } } if(best == len + 1) return 0; return best; } }
双指针法
开始想到了这个方法,误以为时间复杂度为O(n^2)就没继续做下去,发现其实时间复杂度为O(2n)
定义pos和pos1两个指针,分别指向子数组的首尾,如果sum满足要求,更新最优解。然后sum减去pos位置的值,并pos向右移动,直到pos=pos1或者s大于sum,此过程一直更新最优解。
class Solution { public int minSubArrayLen(int s, int[] nums) { int len = nums.length, best = len + 1; int pos = 0, pos1 = 0, sum = 0; while(pos1 < len){ sum += nums[pos1]; if(sum >= s){ best = best < pos1 - pos + 1 ? best : pos1 - pos + 1; while(pos < pos1){ sum -= nums[pos++]; if(sum >= s) best = best < pos1 - pos + 1 ? best : pos1 - pos + 1; else break; } } pos1++; } if(best == len + 1) return 0; return best; } }
回溯法
class Solution { public void combinationSum3Help(List<List<Integer>> result, List<Integer>t, int k, int n, int s){ if(k == 0){ if(n == 0) result.add(new ArrayList<Integer>(t)); return; } if(n < 0) return; for(int i = s; i <= 9; i++){ t.add(i); combinationSum3Help(result, t, k - 1, n - i, i + 1); t.remove(t.size() - 1); } return; } public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> result = new ArrayList<List<Integer>>(); List<Integer> temp = new ArrayList<Integer>(); combinationSum3Help(result, temp, k, n, 1); return result; } }
就遍历数组,用s和e两个指针指向子数组的首尾
class Solution { public List<String> summaryRanges(int[] nums) { List<String> result = new ArrayList<String>(); int len = nums.length; if(len == 0) return result; else if(len == 1){ result.add(String.valueOf(nums[0])); return result; } int s = nums[0], e = nums[0]; for(int i = 1; i < len; i++){ if(nums[i] == nums[i - 1] + 1) e = nums[i]; else{ if(e == s) result.add(String.valueOf(s)); else result.add(String.valueOf(s) + "->" + String.valueOf(e)); e = s = nums[i]; } } if(e == s) result.add(String.valueOf(s)); else result.add(String.valueOf(s) + "->" + String.valueOf(e)); return result; } }
摩尔投票法,即以“对拼消耗“的形式;
首先请考虑最基本的摩尔投票问题,找出一组数字序列中出现次数大于总数1/2的数字(并且假设这个数字一定存在)。显然这个数字只可能有一个。摩尔投票算法是基于这个事实:每次从序列里选择两个不相同的数字删除掉(或称为“抵消”),最后剩下一个数字或几个相同的数字,就是出现次数大于总数一半的那个。
基于此得到如下代码,majorty保存当前剩余的数字,count表示当前majorty的个数,若为0需要选择另一个数字;
class Solution { public int majorityElement(int[] nums) { int majorty = -1, count = 0; for(int i = 0; i < nums.length; i++) { if(count == 0) { majorty = nums[i]; count = 1; } else { if(nums[i] == majorty) count++; else count--; } } count = 0; for(int i = 0; i < nums.length; i++) { if(nums[i] == majorty) { count++; } } return majorty; } }
摩尔投票算法的改进,利用m1,m2,c1,c2分别记录两个数及剩余的次数;但是要避免m1=m2的情况;
自己写的代码if判断很多,看了别人的思路发现可以总结到一起,第一个判断中的nums[i] != m2是为了避免c1=0且nums[i] == m2这种情况下,c2会少加1
class Solution { public List<Integer> majorityElement(int[] nums) { int m1 = -1, m2 = -1, c1 = 0, c2 = 0, len = nums.length; for(int i = 0; i < len; i++){ if((c1 == 0 || m1 == nums[i]) && nums[i] != m2){ c1++; m1 = nums[i]; } else if(c2 == 0 || m2 == nums[i]){ c2++; m2 = nums[i]; } else{ c1--; c2--; } } c1 = 0; c2 = 0; for(int i = 0; i < len; i++){ if(nums[i] == m1) c1++; else if(nums[i] == m2) c2++; } List<Integer> result = new ArrayList<Integer>(); if(c1 > len / 3) result.add(m1); if(c2 > len / 3) result.add(m2); return result; } }
题目要求不能用除法,那考虑pos为i的数字的前缀和和后缀和,再相乘即可;
解法一:时间空间复杂度为O(n)用两个数组
class Solution { public int[] productExceptSelf(int[] nums) { int len = nums.length; int [] result = new int [len]; if(len == 0) return result; int [] left = new int [len]; int [] right = new int [len]; left[0] = 1; right[len - 1] = 1; for(int i = 1; i < len; i++){ left[i] = left[i - 1] * nums[i - 1]; right[len - 1 - i] = right[len - i] * nums[len - i]; } result[0] = right[0]; result[len - 1] = left[len - 1]; for(int i = 1; i < len - 1; i++){ result[i] = right[i] * left[i]; } return result; } }
解法二:时间复杂度为O(n),空间复杂度为O(1),用result数组保存前缀和,用变量num保存后缀和,即从右到左,并更新result数组的值;result[i] *= num;num *= nums[i];
class Solution { public int[] productExceptSelf(int[] nums) { int len = nums.length; int [] result = new int [len]; if(len == 0) return result; result[0] = 1; for(int i = 1; i < len; i++) result[i] = result[i - 1] * nums[i - 1]; int num = nums[len - 1]; for(int i = len - 2; i >= 0; i--){ result[i] *= num; num *= nums[i]; } return result; } }
题目要求找到0~n中缺少的数字
用index表示非0的个数,遍历数组,当遇到非0的数字就前移,最后补充0;
https://blog.csdn.net/plokmju88/article/details/103675872
快慢指针,一个时间复杂度为O(N)的算法。
其一,对于链表问题,使用快慢指针可以判断是否有环。
其二,本题可以使用数组配合下标,抽象成链表问题。但是难点是要定位环的入口位置。
举个例子:nums = [2,5, 9 ,6,9,3,8, 9 ,7,1],构造成链表就是:2->[9]->1->5->3->6->8->7->[9],也就是在[9]处循环。
其三,快慢指针问题,会在环内的[9]->1->5->3->6->8->7->[9]任何一个节点追上,不一定是在[9]处相碰,事实上会在7处碰上。
其四,必须另起一个for循环定位环入口位置[9]。这里需要数学证明。
对“其四”简单说明一下,既然快慢指针在环内的某处已经相碰了。那么,第二个for循环遍历时,res指针还是在不停的绕环走,但是必定和i指针在环入口处相碰。
int findDuplicate(vector<int>& nums) {
int res = 0;
for (int fast = 0; res != fast || fast == 0;){
res = nums[res];
fast = nums[nums[fast]];
}
cout << res;
for (int i = 0; res != i; i = nums[i]){
res = nums[res];
}
return res;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。