121.买卖股票的最佳是时机

题目描述

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

输入：[7,1,5,3,6,4]

输出：5

解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

解题思路

首先想到的是暴力循环，就是做差呗，两个for循环嵌套，然后内层循环的j从外层循环的i开始，就能保证卖股票的时间是在买股票之后了，easy。

1. def maxProfit(prices):
2.     target_list = []
3. for i in range(0,len(prices)):
4. for j in range(i,len(prices)):
5.             target_list.append(prices[j]-prices[i])
6. if max(target_list) <= 0:
7. return 0
8. else:
9. return max(target_list)

当我信心满满点提交的时候，转了老半天，我以为是我网不好，没想到直接通过不了，超出时间了

时间复杂度O(n^2),看来还得优化。

双指针

然后我又想能不能像快速排序一样，设一个双指针，left_p和right_p，先用列表生成式将price复制一份，这样改变复制过后的不会改变原先的列表。然后对复制后的列表按降序排序prices_sort

，left_p刚开始 指向prices_sort最大的那个，right_p指向prices_sort最小的那个，如果在原列表中最小值所以小于最大值的索引，那么最大差就找到了，之后该表left_p和right_p所指就可以。

1. def maxProfit(prices):
2.     prices_sort = [i for i in prices]
3.     prices_sort.sort(reverse=-1) #按升序排列
4. if prices_sort == prices:
5. return 0
6.     right_p = -1
7. while -right_p != len(prices):
8.         left_p = 0
9. while left_p -right_p != len(prices):
10. if prices.index(prices_sort[left_p]) > prices.index(prices_sort[right_p]):
11. return prices_sort[left_p] - prices_sort[right_p]
12. else:
13.                 left_p += 1
14.         right_p -= 1

依然不通过，分析一下这个算法有两个很大问题，第一个是时间复杂度依然没有得到解决。时间复杂度依然是O(n^2)，第二个当列表中有重复元素的时候，index取得一直是第一个索引的下表，导致出现null的结果。

向后切割列表

如果在某一天买了一支股票，你什么时候抛出去最赚钱？如果你有超能力，可以直到之后每一天股票的价格，是不是在最后股票价格最高的那天抛出去 就可以了？如果当前价格为prices[i]，之后的最大值就是max(prices[i+1::])，做差用一个列表存储，之后返回这个列表的最大值，如果最大值小于等于0，说明赚不到钱，那就返回0。记得还要先判断prices长度，如果等于1的话直接返回0。

1. def maxProfit(prices):
2. if len(prices)==1:
3. return 0
4.     targrt_list = []
5. for i in range(0,len(prices)-1):
6.         targrt_list.append(max(prices[i+1::])-prices[i])
7. if max(targrt_list) <= 0 :
8. return 0
9. else:
10. return max(targrt_list)

这个方法还不错！点击提交！又超时了！还得进行优化

动态规划

没辙，看看其他大神的题解吧！动态规划！好吧，我还没有学过，能理解多少理解多少吧。首先要求卖出的价格与买入的价格的最大值，我们可以倒着看，如果卖出价格确定的话，收益最大的就是买入价格最低的时候，并且我们用max_profit不断接受我们的利润，如果之后有利润大于当前的利润，我们就进行更新。从后向前遍历，如果当前价格高于出价，则用当前价格代替出价，这样一直遍历循环，时间复杂度为O(n)。

1. def maxProfit(prices):
2.     out_price = prices[-1]
3.     max_profit = 0
4. for i in range(len(prices) - 1, -1, -1):
5. if out_price - prices[i] > max_profit:
6.             max_profit = out_price - prices[i]
7. if out_price < prices[i]:
8.             out_price = prices[i]
9. return max_profit

通过，感谢大佬！看来动态规划要花大把时间来学习！

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

输入: s = "A man, a plan, a canal: Panama"

输出：true

解释："amanaplanacanalpanama" 是回文串。

列表倒序

这个题还是蛮简单的，首先全部转为小写字母，因为题目最后判断的时候iu是不分大小写字母的，然后就要用isalnum判断是否是 字母，题目上没有数字，可以用这个方法来判断。然后就是字符串拼接，用+=就可以。这样就把字母清理干净了，再用列表切片倒序判断就可以。还有一种思路就是左右指针去便利，如果一直相当直到两个指针相遇，那就返回true，否则flase。

1. def isPalindrome(s:str):
2.     s_sp = ""
3.     s = s.upper()
4. for i in range(0,len(s)):
5. if s[i].isalnum():
6.             s_sp += s[i]
7.     s_sort = s_sp[::-1]
8. if s_sort == s_sp:
9. return True
10. else:
11. return False