力扣集训复习day02

lcr.寻找目标值

思路

1.从左下角出发（右上和左下是一样的，都可以奥，只是移动的时候需要改变一下方向，为什么会选择左下/右上角会在二叉搜索树的知识点进行解释）

• 当前值 大于 target：目标更小，向上走一行 (i–)，排除当前整行；
• 当前值 小于 target：目标更大，向右走一列 (j++)，排除当前整列；
• 等于 target：直接返回true找到目标。

2.注：虽然题目中说了是m*n的二维数组，但是并没有第一行的变量里给出哦，所以不可以直接把m/n当作二维数组的行列直接使用，依旧需要用plants[0].size()进行描述。

代码

class Solution {
public:
bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
int i = plants.size() – 1, j = 0;

while (i >= 0 && j < plants[0].size())
{
if (plants[i][j] > target)i–;//向上移动
else if (plants[i][j] < target)j++;//向右移动
else return true;
}
return false;
}
};

知识点复习

二叉搜索树

基本概念

二叉搜索树是二叉树，满足一条规则：

对于任意一个节点：

✅ 左子树所有节点的值 ＜ 当前节点值

✅ 右子树所有节点的值 ＞ 当前节点值

查找（时间复杂度最好 O (logn)，最坏 O (n)）思路：

• 比当前节点小 → 去左子树
• 比当前节点大 → 去右子树
• 相等，找到；
• 遇到 null 说明不存在

换一个角度看这个题中示例一的数组，把12当作根,感觉可以简单这样理解一下（重复元素没有画了），树大概是这么长的，然后12-9-8，就找到target了。（其实我感觉这里有点涉及到二叉树左旋右旋的内容的（就是本来这个树的根是8，然后把他看成是根是12的…..），但是我这块学的很拉跨，后边仔细补一下再来…..）

88.合并两个有序数组

思路

逆向归并。i、j 分别指向两个数组有效数字末尾，k 指向 nums1 最终末尾。每次取两者较大值放到 k 位置，对应指针前移；其中一个数组取完就直接拷贝另一个剩余元素，直接在 nums1 原地完成归并，不用额外数组。时间 O (m+n)，空间 O (1)。

-之所以从后往前，是因为从前往后想的时候，寻思了半天，发现不会规避覆盖问题，，，，，如果单开数组的话，感觉反而把问题复杂化了，如果单开一个临时指针的话，你咋知道一个指针够了？如果出现有两个元素被覆盖的情况呢？但是题目里开辟了nums1数组且长度为m+n就可以不考虑这个问题了。

代码

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m – 1, j = n – 1;
int k = m + n – 1;
while (i >= 0 || j >= 0) {
int temp;
if (i == -1)temp = nums2[j–];
else if (j == -1)temp = nums1[i–];
else if (nums1[i] > nums2[j])temp = nums1[i–];
else temp = nums2[j–];
nums1[k–] = temp;
}
}
};

知识点复习

这个题其实没啥新东西 感觉没啥知识点好复习的 但是我发现我老是看不懂力扣这个。(⊙﹏⊙)

ok啊，开始复习

vector

-vector是动态数组，可以自动扩容，包含在头文件：#include<vector>

-常用接口：

-特点：

-遍历

//下标遍历
for(int i=0;i<v.size();i++) cout<<v[i];

//范围for
for(auto x:v) cout<<x;

//迭代器
for(auto it = v.begin();it != v.end();it++) cout<<*it;

-vector<int>& nums1：把外部的 vector 数组直接拿进函数里操作，不复制，修改会影响外面。

-&在形参类型后面 = 引用，别名，共用原数据，不复制（&又是另一个知识点了🤔）

121.买卖股票得最佳时机

思路

lowPrice：记录遍历到当前为止遇到的最低股价；

maxpro：记录当前能得到的最大利润。

遍历每一天的股价：更新到当前位置的最低价格；用当天股价减去历史最低价，计算当天卖出的利润，更新最大利润。

代码

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices) {
int lowPrice = prices[0], maxpro = -1;
int n = prices.size();
for (int i = 0; i < n ; i++) {
lowPrice = min(lowPrice, prices[i]);
maxpro = max(maxpro, prices[i] – lowPrice);
}
return maxpro;
}
};

知识点复习

动态规划

-核心思想：把大问题拆成子问题，保存子问题答案，避免重复计算。

-两大关键点：状态定义、状态转移方程。

-两大特征（满足就优先想 DP）

和贪心区别：贪心每一步做局部最优；

DP 会记录所有子问题结果，从子问题推导全局最优。

-两种实现方式

DP = 拆分小问题（拆分成当前能得到的最大利润） + 存小问题答案（存目前遇到的最低股价） + 用小答案推出大答案（得到最大利润）。

这个题难得不是代码，而是动态规划的思想。

53.最大子数组和

思路

cur_sum：以当前 i 位置结尾的最大子数组和

max_sum：全局记录所有子数组中的最大值

遍历每个元素：cur_sum = max(cur_sum + nums[i], nums[i])：要么把当前数接在前面子数组后面；要么舍弃前面，从当前数重新开始新子数组。更新全局最大和max_sum。

代码

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_sum = -10001,cur_sum=-10001;
for (int i = 0; i < nums.size(); i++) {
cur_sum = max(cur_sum + nums[i], nums[i]);
max_sum = max(max_sum, cur_sum);
}
return max_sum;
}
};

知识点复习

这里max-sum和cur_sum的初始值都是根据nums[i]定的哦（因为截图的话太长了就没截图了）

聪明的你看出来了嘛？😊，这个题本质还是动态规划哦，

35.搜查插入位置

思路

看到这个时间复杂度，有没有想到什么很熟悉的东西呢~比如数据结构里的什么树~没错没错，二叉树二叉树，这里的查找方法就是就和前面的二叉搜索树很类似，叫做二分查找法。

代码

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n – 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target)right = mid – 1;
else if (nums[mid] < target)left = mid + 1;
else return mid;
}
return left;
}
};

66.加一

思路

代码

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
//1，判断末尾9的个数
//2.全是9的话，在最前面插入1，末尾9都变成
int i;
for (i = digits.size() – 1; i >= 0; i–) {
if (digits[i] == 9)digits[i] = 0;
else break;
}
if (i == -1)digits.insert(digits.begin(), 1);
else digits[i]++;

return digits;
}
};