面试经典 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];}
};