7.28-8.3周报

70.爬楼梯

题目描述

总共有n个台阶，每次可以爬1或2个台阶，问有多少种爬法。

解题思路

这个题不难看出除了n = 1 和 n = 2 这两种特殊情况之外，剩下的都是前两个方法的和，也就是整体是一个斐波那契数列

代码

class Solution {
public:int climbStairs(int n) {int l = 1 , r = 2;if(n == 1)return 1;if(n == 2)return 2;int ans = 0;for(int i = 3 ; i <= n ; i ++){ans = l + r;l = r;r = ans;}return ans;}
};

121.买股票的最佳时间

 题目描述

给定一个数组表示第i天股票价格是prices[i]，只能选择一天买入股票和未来的一个不相同的时间卖出股票使得获得利润最大。

解题思路

这道题只需要简单暴力枚举出来到第i天最少的购入股票价格，以及用这个价格得到的最大利润与答案数取最大值即可。

代码

class Solution {
public:int maxProfit(vector<int>& prices) {int cnt = INT_MAX , ans = 0;for(int i = 0 ; i < prices.size() ; i ++){cnt = min(prices[i] , cnt);ans = max(ans , prices[i] - cnt);}return ans;}
};

5.最长回文子串

题目描述

给出一个字符串，找出它的最长回文子串。

解题思路

这个题用中心扩展法即可，每一位字符为中心向两侧扩展，直至不符合条件为止

代码

class Solution {
public:string longestPalindrome(string s) {if (s.empty()) return "";int start = 0;int end = 0;for (int i = 0; i < s.size(); ++i) {int left = i;int right = i;while (left >= 0 && right < s.size() && s[left] == s[right]) {--left;++right;}int len1 = right - left - 1;left = i;right = i + 1;while (left >= 0 && right < s.size() && s[left] == s[right]) {--left;++right;}int len2 = right - left - 1;int max_len = max(len1, len2);if (max_len > end - start) {start = i - (max_len - 1) / 2;end = i + max_len / 2;}}return s.substr(start, end - start + 1);}};