22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
输入：n = 1
输出：[“()”]
提示：
1 <= n <= 8
解答
我们可以采用暴力求解法，生成所有可能的组合，再用【20. 有效的括号】中的方法一一判断是否合法，不过这样的时间和空间复杂度太高，这里我们采用回溯法，在生成括号时就按照规则生成。
定义函数backtrack，函数输入一个当前字符串和当前左右括号各自的数目，函数执行的操作是尝试进行三个判断：
如果当前总数目已经达到要求，则直接添加到结果并跳出函数；
如果当前左括号个数合法（小于n），可以再添加一个左括号；
如果当前右括号个数合法（小于左括号个数），可以再添加一个右括号。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
def dfs(left, right, res):
if len(res) == 2*n:
ans.append(''.join(res))
return
if left < n:
left = left + 1
res.append('(')
dfs(left, right, res)
left = left - 1
res.pop()
if right < left:
right = right + 1
res.append(')')
dfs(left, right, res)
right = right - 1
res.pop()
dfs(0, 0, [])
return ans
142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head):
if head == None:
return None
slow = head
fast = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
while slow != head:
slow = slow.next
head = head.next
return head
if fast.next == None or fast.next.next == None:
return None
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
result = []
if len(intervals) == 0:
return result
intervals.sort(key=lambda x: x[0])
result.append(intervals[0])
for i in range(1, len(intervals)):
if result[-1][1] >= intervals[i][0]:
result[-1][1] = max(result[-1][1], intervals[i][1])
else:
result.append(intervals[i])
return result
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
dummy = ListNode(0)
dummy.next = head
p = dummy
while p.next and p.next.next:
if p.next.val == p.next.next.val:
val = p.next.val
while p.next and p.next.val == val:
p.next= p.next.next
else:
p = p.next
return dummy.next
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums = nums1 + nums2
nums.sort()
mid = len(nums) // 2
if len(nums) % 2 == 0:
return (nums[mid] + nums[mid - 1]) / 2
else:
return nums[mid]
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
left, right = head, head.next
while right and right.next:
left = left.next
right = right.next.next
mid = left.next
left.next = None
l = self.sortList(head)
r = self.sortList(mid)
ans = res = ListNode(0)
while l and r:
if l.val < r.val:
res.next = l
l = l.next
else:
res.next = r
r = r.next
res = res.next
res.next = r if r else l
return ans.next
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
return self.merge(self.sortList(head), self.sortList(mid))
def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
p = dummy
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
p.next = l1 if l1 else l2
return dummy.next
31. 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
分析
当数组降序排列时，按升序排序即可
其他情况，将数组从后向前遍历，当左侧字符小于当前字符时结束
例如 1 3 5 9 7 6
遍历到i =3 nums[i]=9时结束，，9 与5 交换的排列必然比当前排列大，所以前面数字可以不考虑，而根据之前遍历数组 第i个之后的部分必然是按降序排列，找到后半部分最小，且比nums[i]大的元素，与nums[i]交换，再将后半部分设置为最小排列即可
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
i = len(nums) -1
while i > 0 and nums[i] <= nums[i-1]:
i -= 1
if i== 0:
nums.sort()
return
j = i-1
while i < len(nums) - 1 and nums[i+1] > nums[j]:
i+=1
nums[j], nums[i] = nums[i], nums[j]
nums[j+1:] = sorted(nums[j+1:])
8. 字符串转换整数 (atoi)
class Solution:
import re
import math
def myAtoi(self, s: str) -> int:
num = re.findall('^[+-]?\d+', s.strip())
num = int(num[0]) if num else 0
return max(min(num,2**31 - 1), -(2**31))
class Solution:
def myAtoi(self, str: str) -> int:
#设置临时数组，题外话：当数组过长的时候，使用set()
temp = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
result = '' #用于提取合法字符串
str = str.strip() #对两边的空格进行清洗
if len(str) == 0 or (str[0] not in temp and str[0] !='-' and str[0] !='+'): #判断首字符是否合法
return 0
if str[0] =='-' or str[0] == '+':
result = result+str[0]
str = str[1:]
for i in str:
if i in temp:
result = result+i
else:
break
try: #主要应对只有一个‘+’ 或者 ‘-’ 的情况，当只有一个正号或者负号的时候 用int()会抛出错误
num = int(result) if len(result)>0 else 0
except:
return 0
#判断是否在合法界限内
return max(min(num,2147483647),-2147483648)
69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
def mySqrt(self, x):
l , r = 0 , x
res = -1
while l<=r :
mid = (l+r) // 2
if mid * mid == x:
return mid
elif mid * mid > x:
r = mid - 1
res = r
else:
l = mid + 1
return res
