您现在的位置是:首页 >学无止境 >【LeetCode】1000题挑战(220/1000)网站首页学无止境
【LeetCode】1000题挑战(220/1000)
简介【LeetCode】1000题挑战(220/1000)
1000题挑战
没有废话,直接开刷!
目录
第一题:119. 杨辉三角 II - 力扣(Leetcode)
编辑 第三题:168. Excel表列名称 - 力扣(Leetcode)
第四题:171. Excel 表列序号 - 力扣(Leetcode)
第一题:119. 杨辉三角 II - 力扣(Leetcode)
题目接口
class Solution {
public:
vector<int> getRow(int rowIndex) {
}
};
解题思路
这道题我的思路是:
-
可以用数学方法推导出规律
-
可以用递推去做
-
暴力构造杨辉三角,然后返回题目要求的那一行
这里我说一下递推的思路:(如果在面试的时候能想到递推,那当然是用递推啦)
我们通过 i 下标不断往数组里面添加1,
下标 j 是 i - 1 ,他等于自己这个位置加上前一个位置的和,
我们从后往前递推,就不会因为改变了数组的值而影响递推的结果。
代码:
class Solution {
public:
vector<int> getRow(int k) {
vector<int> ret(k + 1);
for(int i = 0; i <= k; ++i) { //不断往数组里面添加1
ret[i] = 1;
for(int j = i - 1; j >= 1; --j) { //j下标位置加上前一个位置的和
ret[j] += ret[j - 1];
}
}
return ret;
}
};
我用的是暴力。
代码如下:
代码:
class Solution {
public:
vector<int> getRow(int rowIndex) {
int r = rowIndex + 1;
vector<vector<int>> vv(r, vector<int>(r, 0)); //构造出足够的空间
for(int i = 0; i < r; i++) vv[i][0] = 1; //给第一排填上1
for(int i = 1; i < r; i++) { //构造杨辉三角
for(int j = 1; j < r; j++) {
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
vector<int> res; //把题目要求的那行输出
for(int i = 0; i < r; i++) res.push_back(vv[rowIndex][i]);
return res;
}
};
过过过过啦!!!!
第二题:
题目接口
class Solution {
public:
int maxProfit(vector<int>& prices) {
}
};
解题思路
这道题的解题思路:
-
可以用单调栈
-
可以用动态规划
-
我用的是模拟
是这样的,我是之前做剑指Offer的时候看到了一个大佬的思路,
遍历数组,如果今天的股价大于昨天的股价,就将他们的差价记录(维护这个差价的最大值)
然后让昨天的股价覆盖今天的股价,就能保证如果明天的股价上涨,我们能用最低的价格买入。
最后再返回我们的最大差价即可。
代码:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size(), m = 0;
for(int i = 1; i < n; i++) {
if(prices[i - 1] < prices[i]) { //如果今天的股价大于昨天的股价
m = max(m, prices[i] - prices[i - 1]); //维护这个差价的最大值
prices[i] = prices[i - 1]; //让昨天的股价覆盖今天的股价
}
}
return m;
}
};
过过过过啦!!!!
第三题:168. Excel表列名称 - 力扣(Leetcode)
题目接口
class Solution {
public:
string convertToTitle(int columnNumber) {
}
};
解题思路
这道题的解题思路非常关键,
我们可以把这道题的思路转化为:
10进制转化成26进制,
这样子,我们只需要注意一下,每次 %26 前,需要让数整体往左偏移1即可。
代码:
class Solution {
public:
string convertToTitle(int columnNumber) {
string res;
while(columnNumber) {
columnNumber--; //向左偏移
res += (columnNumber % 26 + 'A'); //进制转换
columnNumber /= 26;
}
reverse(res.begin(), res.end()); //因为我们是从低位尾插进res的,所以最后需要反转一下
return res;
}
};
过过过过啦!!!!
第四题:171. Excel 表列序号 - 力扣(Leetcode)
题目接口
class Solution {
public:
int titleToNumber(string columnTitle) {
}
};
解题思路
这道题的思路遇上一题类似,
这道题是26进制转10进制。
下面是代码:
代码:
class Solution {
public:
int titleToNumber(string columnTitle) {
int sum = 0;
for(int i = 0; i < columnTitle.size(); i++) {
sum = sum * 26 + (columnTitle[i] - 'A' + 1);
}
return sum;
}
};
过过过过啦!!!!
题量截图:
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。