【LeetCode】1000题挑战（220/1000）

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;
    }
};