面试经典 150 题：20、2、228、122

20. 有效的括号

参考代码

#include <stack>

class Solution {
public:
    bool isValid(string s) {
        if(s.size() < 2){ //特判：空字符串和一个字符的情况
            return false;
        }
        bool flag = true;
        stack<char> st; //栈
        for(int i=0; i<s.size(); i++){
            if(s[i] == '(' || s[i]=='{' || s[i]=='['){
                st.push(s[i]);
            }
            if(s[i] == ')' || s[i]=='}' || s[i]==']')
            {
                if(st.empty()){
                    flag = false;
                    break;
                }
                char c = st.top();
                //括号匹配
                if((c == '(' && s[i] == ')') || (c == '{' && s[i]=='}') || 
                (c =='[' && s[i]==']')){
                    st.pop();
                }
                else{
                    flag = false;
                    break;
                }
            }
        }
        if(!st.empty()) //栈里面还有元素
        {
            flag = false;
        }
        return flag;
    }
};

2. 两数相加

参考代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {} 初始化
 *     ListNode(int x) : val(x), next(nullptr) {} 赋值
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *previous, *current;
        previous = new ListNode(-1); //虚拟结点
        current = previous;
        int t = 0; //注意进位
        while(l1 || l2 || t){
            if(l1){
                t += l1->val;
                l1 = l1->next;
            }
            if(l2){
                t += l2->val;
                l2 = l2->next;
            }
            current = current->next = new ListNode(t % 10);
            t /= 10;
        }
        //返回头结点的下一个结点，即第一个数字结点
        return previous->next;
    }
};

228. 汇总区间

参考代码

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;
        int i=0, size=nums.size();
        while(i < size){
            int low = i;
            i++;
            while(i < size && nums[i] == nums[i-1] + 1)
            {
                i++;
            }
            int high = i-1;
            //找不到连续数字：
            string s = to_string(nums[low]);
            if(low < high){ //形成区间
                s += "->" + to_string(nums[high]);
            }
            //否则，区间只有一个数
            result.push_back(s);
        }
        return result;
    }
};

122. 买卖股票的最佳时机 II

参考代码

贪心

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for(int i=1; i<prices.size(); i++){
            //计算两天之间的盈亏
            int ProfitAndLoss = prices[i] - prices[i-1];
            if(ProfitAndLoss > 0)
            {
                //买入股票
                profit += ProfitAndLoss;
            }
        }
        return profit;
    }
};

动态规划

//动态规划
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        //持有现金，股票
        int cash[size], stock[size];
        if(size < 2){
            return 0;
        }
        cash[0] = 0; //初始状态：不买股票
        stock[0] = -prices[0]; //持有股票,当前拥有的现金数是当天股价的相反数
        for(int i=1; i<size; i++){
           //不卖股票（什么都不做），或者卖股票，股票换钱
           cash[i] = max(cash[i-1], stock[i-1]+prices[i]);
           //不买股票（什么都不做），或者加仓，钱换股票
           stock[i] = max(stock[i-1], cash[i-1]-prices[i]);
        }
        return cash[size-1];
    }
};