第一种情况，a坐标比b坐标小，a的坐标更新为b+1
第二种情况，a坐标比b坐标大，直接加1
对于B来说也是一样,按照这个原则来更新坐标，最后返回即可。
class Solution {
public:
int uniquePaths(int m, int n) {
//确定动规数组
vector<vector<int>>dp(m,vector<int>(n,1));
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
滚动数组，一数组来维护，
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int>dp(n,1);
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[j] += dp[j-1];
}
}
return dp.back();
}
};
有障碍的：https://leetcode.cn/problems/unique-paths-ii/submissions/
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<int>dp(n);
dp[0] = (obstacleGrid[0][0] == 0);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(obstacleGrid[i][j] == 1){
dp[j] = 0;
}else{
if(j > 0){
dp[j] += dp[j-1];
}
}
}
}
return dp.back();
}
};
滚动数组稍微麻烦一点
寻找重复子树https://leetcode.cn/problems/find-duplicate-subtrees/
项目：
c++析构函数为什么是虚函数
防止内存泄漏，如果父类被继承，析构函数不是虚函数的话，每个子类里都会有析构函数
#include <iostream>
using namespace std;
class A {
public:
A() { cout << "A的构造" << endl; }
~A() { cout << "A的析构" << endl; }
void Work() {
cout << "A工作" << endl;
}
};//基类
class B :public A {
public:
B() { cout << "B的构造" << endl; }
~B() { cout << "B的析构" << endl; }
void Work() { cout << "B工作" << endl; }
}; //子类
int main()
{
A* p = new B; //派生类对象赋给基类指针
p->Work();//此时调用的是基类的成员函数，因为基类的成员函数覆盖了派生类的同名成员函数
delete p;
system("pause");
return 0;
}
#include <iostream>
using namespace std;
class A {
public:
A() { cout << "A的构造" << endl; }
virtual ~A() { cout << "A的析构" << endl; }
void Work() {
cout << "A工作" << endl;
}
};//基类
class B :public A {
public:
B() { cout << "B的构造" << endl; }
~B() { cout << "B的析构" << endl; } //在派生类中重写的成员函数可以不加virtual关键字
void Work() { cout << "B工作" << endl; }
};//派生类
int main()
{
A* p = new B;
p->Work();
delete p;
system("pause");
return 0;
}
编程题：
接雨水https://leetcode.cn/problems/trapping-rain-water/
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n == 0) {
return 0;
}
vector<int> leftMax(n);
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = max(leftMax[i - 1], height[i]);
}
vector<int> rightMax(n);
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
};
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
时隔数日，已经可以兵不血刃的写出来了
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
vector<int>dp(n,0);
vector<int>left(n,0);
vector<int>right(n,0);
int res = 0;
left[0] = height[0];
for(int i = 1; i < n; i++){
left[i] = max(left[i-1],height[i]);
}
right[n-1] = height[n-1];
for(int i = n-2; i >= 0; i--){
right[i] = max(right[i+1],height[i]);
}
for(int i = 0; i < n; i++){
res += min(left[i],right[i])-height[i];
}
return res;
}
};
温故而知新
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
vector<int>left(n);
left[0] = height[0];
for(int i = 1; i < n; i++){
left[i] = max(height[i],left[i-1]);
}
vector<int>right(n);
right[n-1] = height[n-1];
for(int i = n-2; i >=0; i--){
right[i] = max(right[i+1],height[i]);
}
int res = 0;
for(int i = 0; i < n; i++){
res += min(right[i],left[i])-height[i];
}
return res;
}
};
项目
我发现就在这个过程中，就不知道怎么介绍，没有什么技术含量
自己的优势
没有什么硬性的奖状啊什么的，都是空口无凭的