1.递增的三元子序列
题目链接：https://leetcode.cn/problems/increasing-triplet-subsequence/
思路：先确定一个t，将之后的数与t进行比较，找到第一个比t大的数并将其设为t1，之后的数若大于t1则返回为真，若大于t则将其赋值给t1，若以上条件都不满足则将其赋值给t（相当于重新开始找递增子序列）。
代码：
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n=nums.size();
if(n<3) return false;
int t=nums[0],t1=INT_MAX;
for(int i=1;i<n;i++){
if(nums[i]>t1) return true;
else if(nums[i]>t){
t1=nums[i];
}else{
t=nums[i];
}
}
return false;
}
};
总结：这种解法用到了贪心的思想，即为了找到递增的三元子序列，nums[i]和nums[j]应该尽可能地小，这样找到nums[k]的可能性更大。最有意思的地方在于判断条件的顺序和 t1的初始值设置，当t1初始值设为INT_MAX之后，刚开始就不会触发第一个if条件语句，而第二个条件语句限制了t1的取值必须大于t，第三个条件语句下只会更改t更是带来了一个极大的好处：那就是之后即使存在一个小于t和t1的值也不会漏解（比如是4516这种）
举例：以4516为例，按照我之前的思路，当出现小于t和t1的数时，要重新开始计算这个序列，即从t=1开始，但这样的结果显然是错误的。而当出现小于t和t1的数时，若只改变t，相当于保留了前一个序列的两个解（因为t1不变），此时只要后面的数大于t1，依旧返回为真。
2.搜索二维矩阵Ⅱ
题目链接：https://leetcode.cn/problems/search-a-2d-matrix-ii/
说来惭愧，这题我做过Ⅰ，结果做Ⅱ一开始还tle了…言归正传
思路：观察矩阵不难发现，右上角的元素都大于这一行的元素，小于这一列的元素，利用这一特性，搜索target可以从右上角往左下角搜，如果target<右上角数，则列数-1（即向左搜）；如果target>右上角数，则行数+1（即向下搜），理解不难，这题如果暴力也能过，但做题遇到矩阵记得总结特性，更高效
代码：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m=matrix.size();
int n=matrix[0].size();
int i=0,j=n-1;
while(i<m&&j>=0){
if(matrix[i][j]>target){
j--;
}else if(matrix[i][j]<target){
i++;
}else{
return true;
}
}
return false;
}
};
3.旋转图像
题目链接：https://leetcode.cn/problems/rotate-image/
思路：这题一开始我的思路是找出旋转前和旋转后的位置关系，然后直接两重循环进行交换，不过这个思路过程比较复杂，在此讲一个简单适用性强的思路。题目要求旋转90度，看图可得出，可以先对称上下翻转，再对角线翻转，即可得到所要求图像。
代码：
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
for(int i=0;i<n/2;i++){
matrix[i].swap(matrix[n-1-i]);
}
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
swap(matrix[i][j],matrix[j][i]);
}
}
}
};
4.无重叠区间
题目链接：https://leetcode.cn/problems/non-overlapping-intervals/
思路：题目要求移除区间的最小数量，那么反向思考就是我们要尽可能多的找无重叠的区间，按照这个思路考虑，那么每个区间的范围最好越小越好（因为这样能使后面产生的区间可能性更多），想到这里是不是又感受到了贪心的影子哈哈哈。所以，我们先对每个区间的范围进行排序（注意，每个区间范围都是一对数，这俩是不能拆开的，所以我们可以按照左边界进行排序，也可以按照右边界进行排序）。若按照右边界排序（升序），则从左往右遍历，若下一个左边界>=右边界，则无重叠区间+1；若按照左边界排序（升序），则从右往左遍历（因为比较的是左边界和前一个的右边界），若前一个右边界<=左边界，则无重叠区间+1.最后返回区间总数-无重叠区间。
代码：
class Solution {
public:
static bool cmp(const vector<int>& a,const vector<int>& b){
return a[1]<b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int n=intervals.size();
sort(intervals.begin(),intervals.end(),cmp);
int ans=1;
int bj=intervals[0][1];
for(int i=1;i<n;i++){
if(intervals[i][0]>=bj){
ans++;
bj=intervals[i][1];
}
}
return n-ans;
}
};
这道题代码还包括了如何对一个二维vector数组进行自定义排序，cmp中返回值若是a[0]<b[0]，则是对二维数组中的i值进行排序。
5.螺旋矩阵Ⅱ
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
思路：一道模拟题，模拟将值螺旋式存入数组，我们可以人为设置矩阵边界，当数值存储到边界时，调整方向向右转！（具体可以脑补我们玩贪吃蛇，要碰到墙的时候就调整方向），这题的代码可以说是完美模拟了这个情况，而矩阵边界是不断缩小的，一直到将最后一个值存入数组中。这个思路和代码我只能说妙！
代码：
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>>ans(n,vector<int>(n));
int cnt = 1, tar = n * n;
int l=0,r=n-1,b=n-1,t=0;
while(cnt<= tar){
for(int i = l; i <= r; i++) ans[t][i] = cnt++; // left to right.
t++;
for(int i = t; i <= b; i++) ans[i][r] = cnt++; // top to bottom.
r--;
for(int i = r; i >= l; i--) ans[b][i] = cnt++; // right to left.
b--;
for(int i = b; i >= t; i--) ans[i][l] = cnt++; // bottom to top.
l++;
}
return ans;
}
};
好喜欢这个思路啊哈哈哈哈
6.设计哈希映射
题目链接：https://leetcode.cn/problems/design-hashmap/
思路：这题是简单题，但哈希表原理值得记录
代码：
class MyHashMap {
public:
vector<list<pair<int, int>>> data;
static const int base = 111;//任意取值
static int hash(int key) {
return key % base;
}
MyHashMap():data(base) {
}
void put(int key, int value) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it).first == key) {
(*it).second = value;
return;
}
}
data[h].push_back(make_pair(key, value));
}
int get(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it).first == key) {
return (*it).second;
}
}
return -1;
}
void remove(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it).first == key) {
data[h].erase(it);
return;
}
}
}
};
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/
7.合并区间（算是4的镜像问题了）
题目链接：https://leetcode.cn/problems/merge-intervals/
思路：双指针…不过我还不太明白为啥这里可以对区间左右边界分别排序
代码：
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n=intervals.size();
vector<int> start,end;
vector<vector<int>>ans;
for(int i=0;i<n;i++){
start.push_back(intervals[i][0]);
end.push_back(intervals[i][1]);
}
sort(start.begin(),start.end());
sort(end.begin(),end.end());
for(int i=0,j=0;i<n;i++){
if(i==n-1||start[i+1]>end[i]){
ans.push_back({start[j],end[i]});
j=i+1;
}
}
return ans;
}
};
在这里补充一下关于合并区间的模板（来自一个大佬的博客，大佬用Java写的，但思路会了什么语言的代码都能写）
class Solution {
public int[][] merge(int[][] intervals) {
// 先按照区间起始位置排序
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
// 遍历区间
int[][] res = new int[intervals.length][2];
int idx = -1;
for (int[] interval: intervals) {
// 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
// 则不合并，直接将当前区间加入结果数组。
if (idx == -1 || interval[0] > res[idx][1]) {
res[++idx] = interval;
} else {
// 反之将当前区间合并至结果数组的最后区间
res[idx][1] = Math.max(res[idx][1], interval[1]);
}
}
return Arrays.copyOf(res, idx + 1);
}
}
作者：sweetiee
链接：https://leetcode.cn/problems/merge-intervals/solution/chi-jing-ran-yi-yan-miao-dong-by-sweetiee/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
8.颜色分类
题目链接：https://leetcode.cn/problems/sort-colors/
思路：当然是直接快排啦 由题目可以将我们要得到的数组分为三个区间，第一个区间全为0，第二个全为1，第三个全为2，设l1为区间一的右边界，l2为区间三的左边界，i则表示区间二的右边界（设为i也意味着这个值是不断变化的），我们要确保l1指针左边的每一个数都为0，l2指针右边的每一个数都为2
代码：
class Solution {
public:
void sortColors(vector<int>& nums) {
int l1=0,l2=nums.size()-1;//l1代表数值为0的右边界，l2代表数值为2的左边界
int i=0;//i代表数值为1的右边界
while(i<=l2){//当1的右边界和2的左边界重合跳出循环
if(nums[i]==0){
nums[i]=nums[l1];//确保l1指针左边的每一个数都为0
nums[l1]=0;
l1++,i++;
}else if(nums[i]==1){//无需和自己人交换
i++;
}else{
nums[i]=nums[l2];//确保l2指针右边的每一个数都为2
nums[l2]=2;
l2--;
}
}
}
};
这个思路真的很妙，而且一次循环就能在不开额外空间的情况下排序所有数
9.除自身以外数组的乘积
题目链接：https://leetcode.cn/problems/product-of-array-except-self/
思路：如果按照常规思维用双重循环，这题数据量很大一定会超时，所以我们应该尽量将时间复杂度降低到O(n)。
首先，我们可以设两个数组left和right，其中left[i]则表示在nums[i]左边所有数的乘积(包括nums[i])，即left[i]=left[i-1]*nums[i]，而right[i]同理，一次遍历nums就可以得到这两个数组，而ans[i]=left[i-1]*right[i+1].
在此思路下，我们不难想到第二种优化方法。即只设置一个数组（可以是left也可以是right），得到left数组之后，逆序遍历nums，ans[i]=left[i-1]*r, r的取值随着循环更新, 即r=r *nums[i]，r 为 nums[i]右侧数乘积。
做到这里，既然right数组可以以一个数表示，那么left数组是不是也可以呢？所以我们进一步优化后得到最终解法。
代码：
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int>ans(n,1);
int l=1,r=1;
for(int i=0;i<n;i++){
ans[i]*=l;
l*=nums[i];
ans[n-i-1]*=r;
r*=nums[n-i-1];
}
return ans;
}
};
10.和为k的子数组
题目链接：https://leetcode.cn/problems/subarray-sum-equals-k/
思路：这题一定要注意是子数组而不是子序列！（子数组必须是相邻元素构成的，子序列则可以不相邻，一开始没注意到我还排序了…）还有一点就是即使nums[i]==k也不代表就这一个答案了！因为很可能相邻数为0，这样又可以生产一个新的子数组…（是的我这里踩坑了两次）
最终具体思想是前缀和+哈希，我还需要斟酌一下表达，贴一个大佬的题解：https://leetcode.cn/problems/subarray-sum-equals-k/solution/dai-ni-da-tong-qian-zhui-he-cong-zui-ben-fang-fa-y/
代码：
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n=nums.size();
int ans=0;
int cnt=0;
unordered_map<int,int> m;
m[0]=1;//和为0的子序列有1个
for(int i=0;i<n;i++){
cnt+=nums[i];
if(m.count(cnt-k)) ans+=m[cnt-k];
m[cnt]++;
}
return ans;
}
};
End
就先十题一篇好啦
