中等题 按出题指数排列
1. 2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807解法1: 按步加
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
new_l = ListNode(0)
p = new_l
value_1 = 0 # 除数
while l1 and l2: # 只要有一个为null就停止
value = l1.val + l2.val + value_1
p.next = ListNode(value % 10) # 余数
value_1 = value // 10
l1 = l1.next
l2 = l2.next
p = p.next
while l1:
value = l1.val + value_1
p.next = ListNode(value % 10)
value_1 = value // 10
l1 = l1.next
p = p.next
while l2:
value = l2.val + value_1
p.next = ListNode(value % 10)
value_1 = value // 10
l2 = l2.next
p = p.next
if value_1 != 0:
p.next = ListNode(value_1)
return new_l.next2. 15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解法1: 7076 ms 排序+双指针
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 排序
nums_len = len(nums)
nums.sort()
target = 0
# 遍历
temp = []
sets = []
for i in range(0, nums_len-2): # 三数 第一个数 遍历； 四数之和 前两个数都遍历； 其余利用有序特性；
p = i + 1
q = nums_len - 1
while p < q:
if nums[i]+nums[p]+nums[q] == target:
a = [nums[i], nums[p], nums[q]]
if set(a) not in sets:
sets.append(set(a))
temp.append(a)
# 这部分加， 不加可能漏掉， 没加 也通过了测试 😷
while p < q and nums[p]==nums[p+1]:
p += 1
while p < q and nums[q-1] == nums[q]:
q -= 1
p = p + 1 # 大的减小，小的增大 还有可能相等；
q = q - 1
elif nums[i]+nums[p]+nums[q] > target:
q = q - 1
else:
p = p + 1
return temp3. 33. 搜索旋转排序数组
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1解法1: 二分查找
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 二分查找， 旋转数组
left = 0
right = len(nums) - 1
while left <= right: # 二分 注意细节, 最好加等号，最后加个不定判断是否符合要求，这样保证不出错；
mid = (left + right) // 2
if nums[left] < nums[mid]: # 左是 升序排列
if nums[left]<= target <= nums[mid]:
right = mid
else:
left = mid + 1
elif nums[left] > nums[mid]: # 左不是升序，旋转点在这里面， 右边是升序
if nums[left]<= target or target <= nums[mid]: # 细节 条件不能错，大于等于， 小于等于
right = mid
else:
left = mid + 1
elif nums[left] == nums[mid]:
if nums[left] == target:
break
else:
left += 1
return left if 0<=left<len(nums) and nums[left]==target else -14. 39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]解法1: 递归 +回溯+ 去重复 （针对 找所有可行解，应该采取什么方法呢）
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
# 递归
result = []
def digui(target, target_list):
for item in candidates:
if target - item == 0: # 可以相等记录下来
tem = target_list+[item]
if sorted(tem) not in result: # 去重复
result.append(sorted(tem))
elif target - item > 0:
digui(target-item, target_list+[item]) # 传参时， 不要加进去， 回溯
else:
pass
digui(target, [])
# temp = []
# for item in result: # 去重复的问题 用sorted
# if sorted(item) not in temp:
# temp.append(sorted(item))
return result5. 347. 前 K 个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]示例 2:
输入: nums = [1], k = 1
输出: [1]提示
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。
解法1: 复杂度 没有优于 O(n log n)；
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 优于O(nlogn)
dicts = {}
for item in nums: # O(n)
if item not in dicts:
dicts[item] = 1
else:
dicts[item] += 1
out = sorted(dicts.items(), key=lambda x: x[1], reverse=True)[:k] # nlogn
out = [k for k, v in out]
return out解法2: 遍历统计频率， 桶排序（计数排序）， O(n)【根据复杂度，想题目 适合的算法】
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 优于O(nlogn)， 考 排序算法， 小于O(nlogn)的排序算法： 桶排序， 堆排序； 快速排序都不行；
dicts = {}
for item in nums: # O(n) 遍历频率
if item not in dicts:
dicts[item] = 1
else:
dicts[item] += 1
# 1. 桶排序
nums_len = len(nums)
tong = [0]*(nums_len + 1) # 桶， 以频率作为下标，值为对应的 数字（类型数组，可能有多个）
for key, v in dicts.items(): # O(n)
if tong[v] == 0:
tong[v] = [key]
else:
tong[v] += [key]
# 获取前k个频率最高的
out = []
for item in tong[::-1]:
if item != 0 and len(out) < k:
out.extend(item)
# if len(out) <= k:
# out.extend(item)
# else:
# break
return out[:k]6. 11. 盛最多水的容器
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器.
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：
输入：height = [1,1]
输出：1示例 3：
输入：height = [4,3,2,1,4]
输出：16提示：
n = height.length2 <= n <= 3 * 1040 <= height[i] <= 3 * 104解法1: 官方 双指针法
题解链接：
class Solution:
def maxArea(self, height: List[int]) -> int:
# O(n*n) 超时
# height_len = len(height)
# max_water = 0
# for i in range(height_len):
# for j in range(i+1, height_len):
# temp = min(height[i], height[j]) *(j-i)
# if max_water < temp:
# max_water = temp
# return max_water
# 双指针法(O(n)) , 这样的题 事先没见过，是很难做出来的, 移动的规则很难想出来；
left = 0
right = len(height) - 1
max_area = 0
while left < right:
l_v = height[left]
r_v = height[right]
area = min(l_v, r_v) * (right-left)
if max_area < area:
max_area = area
if l_v > r_v: # 高度小的 移动
right -= 1
else:
left += 1
return max_area7. 8. 字符串转换整数 (atoi)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。解法1:
class Solution:
def myAtoi(self, s: str) -> int:
# 写的太乱了；
# 开头空格字符 丢弃
import math
s = s.strip()
if not s:
return 0
ans = ''
for k, item in enumerate(s): # O(n)
if k == 0: # 首字符 + - 数字 合法
if item == '+' or item == '-' or '0' <= item <= '9':
ans += item
else:
return 0
elif k == 1: # 第二个字母 数字合法， 字母 . break, 若是其他 return 0;
if not ('0'<=item<='9'):
if item == '.' or 'a'<=item.lower()<='z':
break
else:
return 0
else:
ans += item
else: # 数字合法， 其他break;
if '0' <= item <= '9':
ans += item
else:
break
if len(ans) == 1: # 长度为1 可能是 + ， - 号， 不是数字就return 0；
if not '0' <= ans <= '9':
return 0
ans = int(ans)
if ans < -math.pow(2, 31):
return int(-math.pow(2, 31))
elif ans > math.pow(2, 31)-1:
return int(math.pow(2, 31)-1)
return ans8. 200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'
解法1: 深度优先搜索(DFS), 找到为'1'，重新标记'0'， 然后 针对上下左右网格 若为'1'，标记为'0' 搜索; 若为0，不搜索;
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 深度优先搜索， 思路 找到一个为1的， 岛屿数 加1，重标记为'0'，然后 遍历上下左右四个格是否为1 若为1 则记为0, 接着遍历其上下左右四个格； 若为0，则不遍历；
def dfs(grid, i, j):
grid[i][j] = '0'
m = len(grid)
n = len(grid[0])
for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
if 0<=x<m and 0<=y<n and grid[x][y]=='1': # 等于1的就接着 搜索， 等于0的不用搜索
dfs(grid, x, y)
# 思路 记忆， 找到的 重标记为‘0’，这是重点；
m = len(grid)
n = len(grid[0])
lands_count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1': # 岛屿
lands_count += 1
dfs(grid, i, j)
return lands_count9. 22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]方法1: 回溯法
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
# 回溯法 掌握的不好，对这类问题 进行归总 学习记忆
ans = []
# 通过控制 左 右括号的 数量 来生成 有效的括号序列
def generatePa(S, left, right):
if len(S) == 2*n:
ans.append(''.join(S)) # 字符串
return
if left < n:
S.append('(')
generatePa(S, left+1, right)
S.pop()
if right < left:
S.append(')')
generatePa(S, left, right+1)
S.pop()
generatePa([], 0, 0)
return ans方法2: 先生成所有可能， 再判断是否有效
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
# 1. 先生成所有可能组合， 然后验证有效的；
ans = []
def generatep(S):
if len(S)==2*n: # 递归结束条件
if valid(S):
ans.append(''.join(S))
return
S.append('(') # 生成 所有可能结果代码 递归 仔细学习
generatep(S)
S.pop()
S.append(')')
generatep(S)
S.pop()
def valid(S):
temp = 0
for c in S:
if c == '(':
temp += 1
else:
temp -= 1
if temp < 0:
return False
return temp == 0
generatep([])
return ans10. 98. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。解法1: 二叉树 中序遍历 结果 是个 升序数组；
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
# 中序遍历结果是个 升序数组
ans = []
def zhong(root):
if not root:
return
zhong(root.left)
ans.append(root.val)
zhong(root.right)
zhong(root)
# 判断是否 升序排列
# print(ans)
first = ans[0]
for i in range(1, len(ans)):
if first < ans[i]: # 大于 （不包括等于）
first = ans[i]
else:
return False
return True解法2: 递归， 判断条件
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
# 递归， 利用 左子树 小于根结点， 右子树大于根结点， 来判断 是否符合
def valid(root, lower=float('-inf'), upper=float('inf')):
if not root: # 空节点为True;
return True
# 不为bst则返回False, 为bst接着验证左右子树
if not lower < root.val < upper: # 判断依据
return False
if not valid(root.left, lower, root.val):
return False
if not valid(root.right, root.val, upper):
return False
return True # 左右子树都为bst，则返回true
return valid(root) # 刚开始时，是无限小，无限大 [-inf, inf]解法3: 前序 优化
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
global pre
pre = float('-inf') # pre 必须是全局才行
def middleorder(root):
if not root:
return True
if not middleorder(root.left):
return False
global pre
if root.val <= pre: # 小于等于 false
return False
pre = root.val
return middleorder(root.right)
return middleorder(root)
11. 24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]示例 2：
输入：head = []
输出：[]示例 3：
输入：head = [1]
输出：[1]解法1: 递归
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 递归, 先背一种解法
if not head or not head.next: # None 或者 一个节点
return head
newhead = head.next # 新的头节点
head.next = self.swapPairs(newhead.next) # 递归 交换 剩余 节点, 一次交换两个
newhead.next = head
return newhead12. 148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]示例 3：
输入：head = []
输出：[]解法1: O(n)遍历出所有节点值， O(nlogn)排序， O(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:
# # 超时 O(n*n)
# flag = True
# while flag:
# flag =False
# p = head
# while p and p.next:
# if p.val > p.next.val:
# p.val, p.next.val = p.next.val, p.val
# flag = True
# p = p.next
# return head
temp = []
p = head
while p:
temp.append(p.val)
p = p.next
temp = sorted(temp) # O(nlogn) 快速排序
p = head
i = 0
while p:
p.val = temp[i]
i = i + 1
p = p.next
return head解法2: 归并排序（快慢指针 找中点） + 合并链表（合并两个有序链表方法） 这题得背下来
# 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:
# 归并排序（快慢指针 找中点） + 合并链表（合并两个有序链表方法） # 考点太多了
# 归并排序
def sortFunc(head, tail): # 需要知道 头 尾
if not head: # 为null
return head
if head.next == tail: # 两个节点时， 返回头节点就行，因为mid
head.next = None
return head
# 快慢指针
fast=slow=head
while fast != tail: # 这个快慢指针 用法 也特殊， 总结快慢指针的用法形式；
slow = slow.next
fast = fast.next
if fast != tail:
fast = fast.next
# slow 就是中点
mid = slow
return merge(sortFunc(head, mid), sortFunc(mid, tail))
# 合并两个有序链表
def merge(head1, head2):
p = q = ListNode(0, None)
l1 = head1
l2 = head2
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
if l1:
p.next = l1
if l2:
p.next = l2
return q.next
return sortFunc(head, None)13. 147. 对链表进行插入排序
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4解法1: 插入排序定义
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
# 插入排序
if not head:
return head
dummyHead = ListNode(0) # 头节点 前一个节点， 用来方便在 头节点前 插入 节点
dummyHead.next = head
lastedsorted = head # 有序区域的最后一个节点
cur = head.next # 下一个待排序的无序节点
while cur:
if lastedsorted.val <= cur.val: # 有序 无需插入
lastedsorted = lastedsorted.next
else:
# 需要插入，从头遍历
pre = dummyHead
while pre.next.val <= cur.val:
pre = pre.next
lastedsorted.next = cur.next # 将但前无序节点之后的节点 给 最后一个有序的next
cur.next = pre.next # cur插入到 pre 和 pre.next之间
pre.next = cur
cur = lastedsorted.next # 待排序节点
return dummyHead.next14. 236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。说明:
解法1: 先记住， 要解释思路
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 先记住，脑子不行了
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if not left:
return right
if not right:
return left
return root # 要先说 思路的 递归，15. 46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]解法1: 递归+回溯
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# global out
def digui(numlist, S=[]):
if len(S) == n:
out.append(S)
return
for i in range(len(numlist)): # 递归+回溯
digui(numlist[:i] + numlist[i+1:], S+[numlist[i]])
return
out = []
n = len(nums)
digui(nums, [])
return out