Leetcode刷题日记16（151-160）

问题1：

问题链接：

151. 反转字符串中的单词

问题描述：

给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

实例：

示例1： 输入：s="the sky is blue" 输出："blue is sky the" 示例2： 输入：s=" hello world " 输出："world hello" 解释：反转后的字符串中不能存在前导空格和尾随空格。 示例3： 输入：s="a good example" 输出："example good a" 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

代码：

classSolution:defreverseWords(self,s:str)->str:s=s.strip()# 删除首尾空格i=j=len(s)-1res=[]whilei>=0:whilei>=0ands[i]!=' ':i-=1# 搜索首个空格res.append(s[i+1:j+1])# 添加单词whilei>=0ands[i]==' ':i-=1# 跳过单词间空格j=i# j 指向下个单词的尾字符return' '.join(res)# 拼接并返回

问题2：

问题链接：

152. 乘积最大子数组

问题描述：

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个32-位 整数。 请注意，一个只包含一个元素的数组的乘积是这个元素的值。

实例：

示例1:输入:nums=[2,3,-2,4]输出:6解释:子数组[2,3]有最大乘积6。 示例2:输入:nums=[-2,0,-1]输出:0解释:结果不能为2,因为[-2,-1]不是子数组。

代码：

classSolution:defmaxProduct(self,nums:List[int])->int:n=len(nums)f_max=[0]*n f_min=[0]*n f_max[0]=f_min[0]=nums[0]foriinrange(1,n):x=nums[i]# 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，# 或者单独组成一个子数组，只有 x 一个元素f_max[i]=max(f_max[i-1]*x,f_min[i-1]*x,x)f_min[i]=min(f_max[i-1]*x,f_min[i-1]*x,x)returnmax(f_max)

问题3：

问题链接：

153. 寻找旋转排序数组中的最小值

问题描述：

已知一个长度为 n 的数组，预先按照升序排列，经由1到 n 次 旋转 后，得到输入数组。例如，原数组 nums=[0,1,2,4,5,6,7]在变化后可能得到： 若旋转4次，则可以得到[4,5,6,7,0,1,2]若旋转7次，则可以得到[0,1,2,4,5,6,7]注意，数组[a[0],a[1],a[2],...,a[n-1]]旋转一次 的结果为数组[a[n-1],a[0],a[1],a[2],...,a[n-2]]。 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须设计一个时间复杂度为O(log n)的算法解决此问题。

实例：

示例1： 输入：nums=[3,4,5,1,2]输出：1解释：原数组为[1,2,3,4,5]，旋转3次得到输入数组。 示例2： 输入：nums=[4,5,6,7,0,1,2]输出：0解释：原数组为[0,1,2,4,5,6,7]，旋转4次得到输入数组。 示例3： 输入：nums=[11,13,15,17]输出：11解释：原数组为[11,13,15,17]，旋转4次得到输入数组。

代码：

classSolution:deffindMin(self,nums:List[int])->int:left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]>nums[-1]:left=mid+1else:right=mid-1returnnums[left]

问题4：

问题链接：

154. 寻找旋转排序数组中的最小值 II

问题描述：

已知一个长度为 n 的数组，预先按照升序排列，经由1到 n 次 旋转 后，得到输入数组。例如，原数组 nums=[0,1,4,4,5,6,7]在变化后可能得到： 若旋转4次，则可以得到[4,5,6,7,0,1,4]若旋转7次，则可以得到[0,1,4,4,5,6,7]注意，数组[a[0],a[1],a[2],...,a[n-1]]旋转一次 的结果为数组[a[n-1],a[0],a[1],a[2],...,a[n-2]]。 给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须尽可能减少整个过程的操作步骤。

实例：

示例1： 输入：nums=[1,3,5]输出：1示例2： 输入：nums=[2,2,2,0,1]输出：0

代码：

classSolution:deffindMin(self,nums:[int])->int:nums=sorted(nums)returnnums[0]

classSolution:deffindMin(self,nums:[int])->int:i,j=0,len(nums)-1#关于选择点这里，左边的都要大于右边的数据whilei<j:m=(i+j)//2ifnums[m]>nums[j]:i=m+1elifnums[m]<nums[j]:j=melse:returnmin(nums[i:j])returnnums[i]

问题5：

问题链接：

155. 最小栈

问题描述：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类:MinStack()初始化堆栈对象。 voidpush(int val)将元素val推入堆栈。 voidpop()删除堆栈顶部的元素。 inttop()获取堆栈顶部的元素。 intgetMin()获取堆栈中的最小元素。

实例：

示例1:输入：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]输出：[null,null,null,null,-3,null,0,-2]解释： MinStack minStack=newMinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();-->返回-3.minStack.pop();minStack.top();-->返回0.minStack.getMin();-->返回-2.

代码：

classMinStack:def__init__(self):self.stack=[]self.min_stack=[]defpush(self,val:int)->None:self.stack.append(val)ifnotself.min_stackorval<=self.min_stack[-1]:self.min_stack.append(val)defpop(self)->None:ifself.stack.pop()==self.min_stack[-1]:self.min_stack.pop()deftop(self)->int:returnself.stack[-1]defgetMin(self)->int:returnself.min_stack[-1]

问题6：

问题链接：

160. 相交链表

问题描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 注意，函数返回结果后，链表必须 保持其原始结构 。 自定义评测： 评测系统 的输入如下（你设计的程序 不适用 此输入）： intersectVal-相交的起始节点的值。如果不存在相交节点，这一值为0listA-第一个链表 listB-第二个链表 skipA-在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB-在 listB 中（从头节点开始）跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

实例：

代码：

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defgetIntersectionNode(self,headA:ListNode,headB:ListNode)->Optional[ListNode]:#假设公共部分是z，上半段是x，下半段是y，在（x+z）+y=（y+z）+x，意思就说两者都开始走，走完以后再走对方的路，x走y，y走x，会相遇，如果没相遇则是有空节点。p,q=headA,headBwhilepisnotq:ifp:p=p.nextelse:p=headBifq:q=q.nextelse:q=headAreturnp