11月4号 150,151,152,153

刷题第二天
今天的题目整体比较简单，刷题时间加上总结一个小时半不到，然后准备刷到下一题的时候感觉题目比较长，不太想看，所以今天就到这里了

文章目录

• • • 150. Evaluate Reverse Polish Notation
    • 151. Reverse Words in a String
    • 152. Maximum Product Subarray
    • 153. Find Minimum in Rotated Sorted Array

150. Evaluate Reverse Polish Notation

题目乍看下来怎么算的都不知道，但是点开维基就懂了，算是增长知识了
逆波兰表示法

Input: [“10”, “6”, “9”, “3”, “+”, “-11”, “", “/”, "”, “17”, “+”, “5”, “+”]
Output: 22
Explanation:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

给定一个用逆波兰表示法表示的数组，然后得出他所表示的数，事实上维基已经将算法流程给出来了，定义一个栈，遇到数据即压入栈；在遇到符号的时候弹出后面两个，根据符号运算完毕再压入栈即可
代码如下：

class Solution(object):def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""res=[]operators=["+","-","*","/"]for i in tokens:if i not in operators:res.append(int(i))else:if i =="+":res.append(res.pop()+res.pop())elif i=="-":res.append(-res.pop()+res.pop())elif i=='*':res.append(res.pop()*res.pop())elif i=='/':res.append(int(float(1)/res.pop() * res.pop()))if len(res)>1:returnelse:return res[0]

值得注意的就是负数除法的时候需要用float

151. Reverse Words in a String

给定一个字符串，对其进行反转

Example 1:
Input: “the sky is blue”
Output: “blue is sky the”

这题在剑指上面有，上面是说定义一个反转的函数，然后用两次，第一次将整个字符串反转过来，第二次将每个单词再反转过来，但是在python里其实就一行的事，也不想多写了。

代码如下：

class Solution(object):def reverseWords(self, s):""":type s: str:rtype: str"""return ' '.join(s.strip().split()[::-1])

152. Maximum Product Subarray

列表连续子集的最大乘积。

Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

因为其中有负数，负负得正，所以我们在遍历的时候不仅需要将最大值记录下来，还需要将最小值记录下来。

代码如下：

class Solution(object):def maxProduct(self, nums):""":type nums: List[int]:rtype: int"""maxium=big=small=nums[0]for n in nums[1:]:big,small=max(n,n*big,n*small),min(n,n*big,n*small)maxium=max(maxium,big)return maxium

153. Find Minimum in Rotated Sorted Array

在旋转过的列表中寻找最小值，旋转列表也是老朋友了，记忆中在LeetCode中做过的还有两道题。
分别是81. Search in Rotated Sorted Array II以及33. Search in Rotated Sorted Array

这两道算是一个意思，思路明确后其实能比较轻松的写出来，一方面需要确定mid指针掉落的哪里，另一方面需要确定target在哪里。有空可以在这里一起写写题目的思路

这题算是比较简单的，二分法可以很轻松的做出来，注意好mid掉落在哪里就可以了

class Solution(object):def findMin(self, nums):""":type nums: List[int]:rtype: int"""low = 0high = len(nums)-1while low<=high:          mid = (low+high)//2if mid >= 1 and mid<=len(nums)-2 and nums[mid]<nums[mid-1] and nums[mid] < nums[mid+1]:return nums[mid]if nums[mid]>=nums[0]:low=mid+1elif nums[mid]<=nums[-1]:high=mid-1return min(nums[0],nums[-1])

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！