LeetCode每日算法2

11.括号生成数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。每个右括号都有一个对应的相同类型的左括号。class Solution: def generateParenthesis(self, n: int) - List[str]: res[] cur_str def dfs(cur_str,left,right,n):#left表示左边已有几个左括号right同理 leftright结束 if leftn and rightn: res.append(cur_str) return if leftright: return if leftn: dfs(cur_str(,left1,right,n) if rightn: dfs(cur_str),left,right1,n) dfs(cur_str,0,0,n) return res12. 合并K个升序链表给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。-------------------------------使用小根堆---------------------------------# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]: if not lists or len(lists)0: return None import heapq heapq [] for node in lists: while node: heappush(heapq,node.val) nodenode.next cur dummy ListNode(None) while heapq: temp ListNode(heappop(heapq)) cur.next temp cur temp return dummy.next注意import heapq #Python内置heapq默认小根堆 # 小根堆 class MinHeap: def __init__(self): self.heap [] def push(self, val): 插入元素 heapq.heappush(self.heap, val) def pop(self): 弹出最小值 if self.is_empty(): return None return heapq.heappop(self.heap) def peek(self): 查看最小值 if self.is_empty(): return None return self.heap[0] def is_empty(self): return len(self.heap) 0 def size(self): return len(self.heap) # 大根堆通过取负数实现 class MaxHeap: def __init__(self): self.heap [] def push(self, val): 插入元素存储负数 heapq.heappush(self.heap, -val) def pop(self): 弹出最大值 if self.is_empty(): return None return -heapq.heappop(self.heap) def peek(self): 查看最大值 if self.is_empty(): return None return -self.heap[0] def is_empty(self): return len(self.heap) 0 def size(self): return len(self.heap)13.删除有序数组中的重复项给你一个非严格递增排列的数组nums请你原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回nums中唯一元素的个数。考虑nums的唯一元素的数量为k。去重后返回唯一元素的数量k。nums的前k个元素应包含排序后的唯一数字。下标k - 1之后的剩余元素可以忽略。判题标准:系统会用下面的代码来测试你的题解:int[] nums [...]; // 输入数组 int[] expectedNums [...]; // 长度正确的期望答案 int k removeDuplicates(nums); // 调用 assert k expectedNums.length; for (int i 0; i k; i) { assert nums[i] expectedNums[i]; }如果所有断言都通过那么您的题解将被通过。示例 1输入nums [1,1,2]输出2, nums [1,2,_]解释函数应该返回新的长度2并且原数组nums的前两个元素被修改为12。不需要考虑数组中超出新长度后面的元素。#由于不用考虑数组中超出新长度后面的元素直接将新元素替换重复元素即可 class Solution: def removeDuplicates(self, nums: List[int]) - int: slow,fast 0,1 while fastlen(nums): if nums[slow] ! nums[fast]: slow 1 nums[slow] nums[fast] fast 1 return slow114.反转链表给你单链表的头节点head请你反转链表并返回反转后的链表。输入head [1,2,3,4,5]输出[5,4,3,2,1]# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: pre None cur head while cur: nxt cur.next cur.next pre pre cur cur nxt return pre #返回反转后链表的头节点以head [1,2]为例15.反转链表II给你单链表的头指针head和两个整数left和right其中left right。请你反转从位置left到位置right的链表节点返回反转后的链表。示例 1输入head [1,2,3,4,5], left 2, right 4输出[1,4,3,2,5]示例 2输入head [5], left 1, right 1输出[5]# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: dummy ListNode(nexthead) p0 dummy #p0相当于是反转left的前一个结点 当left1时没有p0. for _ in range(left-1): p0 p0.next pre None cur p0.next for _ in range(right-left1): #要反转的一共是right-left1个元素 nxt cur.next cur.next pre pre cur cur nxt p0.next.next cur p0.next pre return dummy.next当反转从位置left到位置right的链表节点后链上指针是以下情况图片截自一位讲解非常好的up主非本人绘制蓝色线是后面两步16. K个一组反转链表给你链表的头节点head每k个节点一组进行翻转请你返回修改后的链表。k是一个正整数它的值小于或等于链表的长度。如果节点总数不是k的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]: count 0 start head while start: count1 startstart.next if k count: return None p0 dummy ListNode(next head) cur p0.next pre None while count k: count - k for _ in range(k): nxt cur.next cur.next pre pre cur cur nxt p1 p0.next #需要更换p0其实就是下一次反转组的前一个节点也是上一个反转组的最后一个节点 p0.next.next cur p0.next pre p0 p1 return dummy.next17.找出字符串中第一个匹配项的下标给你两个字符串haystack和needle请你在haystack字符串中找出needle字符串的第一个匹配项的下标下标从 0 开始。如果needle不是haystack的一部分则返回-1。示例 1输入haystack sadbutsad, needle sad输出0解释sad 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 所以返回 0 。示例 2输入haystack leetcode, needle leeto输出-1解释leeto 没有在 leetcode 中出现所以返回 -1 。class Solution: def strStr(self, haystack: str, needle: str) - int: len1, len2 len(haystack), len(needle) i,j 0,0 while (i len1 and j len2): if haystack[i] needle[j]: i1 j1 else: i i-j1 j 0 if jlen2: return i-j else: return -118.两数相除给你两个整数被除数dividend和除数divisor。将两数相除要求不使用乘法、除法和取余运算。整数除法应该向零截断也就是截去truncate其小数部分。例如8.345将被截断为8-2.7335将被截断至-2。返回被除数dividend除以除数divisor得到的商。注意假设我们的环境只能存储32 位有符号整数其数值范围是[−231, 231 − 1]。本题中如果商严格大于231 − 1则返回231 − 1如果商严格小于-231则返回-231。class Solution: def divide(self, dividend: int, divisor: int) - int: sign (dividend0)^(divisor0) #异或运算 符号相同为False(正数)符号不同为True(负数) dividend,divisor abs(dividend), abs(divisor) count 0 #先按照2的指数寻找除数的最大倍数 转换成二进制 #把除数左移直到它大于被除数 xi 即 x*2^^i while (dividend divisor): count 1 divisor 1 result 0 # count从最大值递减 # 每次将除数右移一位除以2 # 如果当前除数小于等于被除数就在结果的对应位上加1 # 减去这个除数继续处理剩余部分 while(count 0): count - 1 divisor 1 if (divisor dividend): result 1count dividend - divisor if sign: result -result if result (131)-1: result (131)-1 if result -(131): result -(131) return result19.最长有效括号给你一个只包含(和)的字符串找出最长有效格式正确且连续括号 子串 的长度。左右括号匹配即每个左括号都有对应的右括号将其闭合的字符串是格式正确的比如(()())。示例 1输入s (()输出2解释最长有效括号子串是 ()示例 2输入s )()())输出4解释最长有效括号子串是 ()()示例 3输入s 输出0class Solution: def longestValidParentheses(self, s: str) - int: if not s: return 0 stack [] ans 0 for i in range(len(s)): #入栈 # 栈为空第一个字符直接入栈 # 当前字符是 (左括号直接入栈 # 栈顶是 )s[stack[-1]] ) - 栈顶是右括号说明前面的括号已经匹配完当前字符作为新的开始 if not stack or s[i]( or s[stack[-1]]) : stack.append(i) #s的下标入栈 else: stack.pop() ans max(ans, i-(stack[-1] if stack else -1)) return ans20.搜索旋转排序数组整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了向左旋转使数组变为[nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标从 0 开始计数。例如[0,1,2,4,5,6,7]下标3上向左旋转后可能变为[4,5,6,7,0,1,2]。给你旋转后的数组nums和一个整数target如果nums中存在这个目标值target则返回它的下标否则返回-1。你必须设计一个时间复杂度为O(log n)的算法解决此问题。class Solution: def search(self, nums: List[int], target: int) - int: #类似二分查找法 if len(nums) 0: return -1 low,high 0,len(nums)-1 while lowhigh: mid (high-low)//2 low if nums[mid] target: return mid if nums[mid]nums[low]: if nums[low]targetnums[mid]: high mid else: low mid1 else: if nums[mid1]targetnums[high]: low mid1 else: high mid return low if nums[low]target else -1