代码收藏家 leetcode hot 100——easy题（python）
题解思路主要来源于@灵茶山艾府。
1 两数之和
1.1 题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只对应一个答案，但是数组中的同一个元素不能重复出现。你可以按任意顺序返回答案。
示例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9，返回[0,1]1.2 思路
建立一个哈希表，遍历nums数组中的元素，如果target-nums[i]不存在哈希表中，就将nums[i]作为key，i作为value插入到哈希表中。
1.3 代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
if target - nums[i] in hashmap:
return [i, hashmap[target-nums[i]]]
hashmap[nums[i]] = i2 移动零
2.1 题目
给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。要求在不复制数组的情况下对原数组进行操作。
示例：
输入:nums = [0,1,0,3,12]
输出:[1,3,12,0,0]2.2 思路
把0视作空位，将所有元素都移到数组左边的空位：遍历nums数组元素，同时维护一个下标i0，每次遇到nums[i]≠0，就把nums[i]和nums[i0]互换，且i0和i都加1；如果nums[i] = 0，则只需要把i加1.
2.3 代码
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
i0 = 0
for i in range(len(nums)):
if nums[i]:
nums[i], nums[i0] = nums[i0], nums[i]
i0 += 1
3 相交链表
3.1 题目
给两个单链表的头结点headA和headB，请找出并返回两个单链表相交的起始节点，如果不存在交点则返回null。题目数据保证链表中无环。函数返回结果后链表的原始结构不变。
示例：
3.2 思路
定义两个指针p和q，分别从两个单链表出发，不断向后走一步，当p走完headA这个单链表，就继续在headB链表向前走，q也一样。如果p不为空，则更新p为p.next，否则更新p为headB，q也一样。最终如果两个链表有交点，则p=q；如果没有交点，p和q在None处相交。
3.3 代码
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> optional[ListNode]:
p,q = headA, headB
while p is not q:
p = p.next if p else headB
q = q.next if q else headA
return p
4 反转链表
4.1 题目
给你单链表的头结点head，请反转链表，并返回反转后的链表。
示例：
4.2 思路
遍历链表，访问各节点时修改next的指向。
4.3 代码
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: optional[ListNode]) -> optional[ListNode]:
pre, cur = None, head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
# 也可以合并为cur.next, pre, cur = pre, cur, cur.next
return pre5 环形链表
5.1 题目
给定一个链表的头结点head，判断链表中是否有环。如果有环，则返回True，否则返回False。
示例：
5.2 思路
将判断是否有环问题转为龟兔赛跑问题，龟兔同时从头结点出发，乌龟每次前移一格，兔子每次前移两格，如果有环，则龟兔一定会相遇。因此可以定义快慢指针slow和fast，如果最后fast和slow指向同一个节点，则有环，反之没有。
5.3 代码
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast is slow:
return True
return False6 回文链表
6.1 题目
给你一个单链表的头结点head，请你判断该链表是否为回文链表，如果是返回True，否则返回False。
示例：
6.2 思路
首先找链表head的中间节点mid（如果节点数是奇数，则是正中间节点；如果是偶数，则是正中间右边的节点），然后将mid节点到末尾这段链表翻转得到head2，最后遍历head和head2两个链表，每次循环判断head.val和head2.val是否相等。如果不相等，则返回False；如果直到结束都没返回False，则返回True。
6.3 代码
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
# 找中间节点
def midNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 反转后半部分链表
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre, cur = None, head
while cur:
cur.next, pre, cur = pre, cur, cur.next
return pre
# 判断回文
def isPalindrome(self, head: Optional[ListNode]) -> bool:
mid = self.midNode(head)
head2 = self.reverseList(mid)
while head2:
if head.val != head2.val:
return False
head = head.next
head2 = head2.next
return True7 合并两个有序链表
7.1 题目
将两个升序链表合并成一个新的升序链表，新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
7.2 思路
递归：如果其中一个链表为空，直接返回另一个链表作为合并后的结果；如果两个链表都不为空，则比较两个链表当前节点的值，并选择较小的节点作为新链表的当前节点。
7.3 代码
class ListNode:
def __init__(sel, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Opational[ListNode]) -> Optional[ListNode]:
if list1 is None:
return list2
if list2 is None:
return list1
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
list2.next = self.mergeTwoLists(list1, list2.next)
return list28 二叉树的前中后序遍历
8.1 题目
给定一个二叉树的根节点root，返回其中序遍历。
示例：
8.2 思路
递归，顺序遍历节点
8.3 代码
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# 前序
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def helper(root):
if not root:
return
res.append(root.val)
helper(root.left)
helper(root.right)
helper(root)
return res
# 中序
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def helper(root):
if not root:
return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res
# 后序
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def helper(root):
if not root:
return
helper(root.left)
helper(root.right)
res.append(root.val)
helper(root)
return res
9 二叉树的最大深度
9.1 题目
给定一个二叉树root，返回其最大深度（根节点到最远子节点的最长路径上的节点数）。
示例：
9.2 思路
递归：如果我们知道了左子树和右子树的最大深度和l和r，那么该二叉树的最大深度为max(l，r)+1，同理，左子树和右子树的最大深度也可以以同样的逻辑计算。
9.3 代码
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
else:
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 110 搜索插入位置
10.1 题目
给定一个排序数组nums和一个目标值target，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
示例：
输入: nums = [1,3,5,6], target = 5
输出: 210.2 思路
不断用二分法逼近查找第一个大于等于target的下标。
10.3 代码
def lower_bound(nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return lower_bound(nums, target)
11 有效的括号
11.1 题目
给一个只包括'(','[','{','}',']',')'的字符串s，判断字符串是否有效。有效字符串需要满足以下条件：①左括号必须用相同类型右括号闭合，②左括号以正确的顺序闭合，③每个右括号都有一个对应的左括号。
11.2 思路
比较容易思考到栈，左括号依次入栈，右括号入栈后必须和此时在栈顶的左括号同时弹出栈顶，如果遍历结束栈为空，则返回True，否则返回False。
一个比较容易忽视的点是，如果字符串s的元素数是奇数，则一定是False。
11.3 代码
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2:
return False
mp = {')':'(', ']':'[', '}':'{'}
st = []
for c in s:
if c not in mp:
st.append(c)
elif not st or st.pop() != ma[c]:
return False
return not st12 买卖股票的最佳时机
12.1 题目
给一个数组prices，第i个元素prices[i]表示一支股票第i天的价格，你只能在某一天买入这只股票，并在未来一个不同的日子卖出，设计一个算法计算出你能获取的最大利润。如果不能获取利润，返回0.
示例：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。12.2 思路
从左到右枚举prices[i]，首先找到第i天之前股票价格的最小值，作为买入价格minprice（只能是左侧的最小值）；然后找到prices[i]-minprice的最大值，就是答案。
12.3 代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
min_price = prices[0]
for p in prices:
ans = max(ans, p-min_price)
min_price = min(min_price, p)
return ans13 爬楼梯
13.1 题目
假设你在爬楼梯，需要爬n阶到楼顶。每次你可以爬1个或者2个台阶，你有多少种方法爬到楼顶。
示例：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶13.2 思路
用dfs(i)表示从0爬到i有多少种方法，则dfs(i)=dfs(i-1)+dfs(i-2)，其中dfs(0)=1，dfs(1)=1，则只需求出dfs(n)即可得到答案，所以可以采用递归的思路做。由于递归过程中会大量重复性计算，所以可以用一个@cache装饰器来保存过程中计算出来的值。
同时，我们也可以从底往上计算，递推式和上面思路一样，仍然是f[i]=f[i-1]+f[i-2]，f[0]=1，f[1]=1，求出f[n]即是答案。
13.3 代码
# 递归
class Solution:
def climbStairs(self, n: int) -> int:
@cache # 装饰器
def dfs(i: int) -> int:
if i <= 1:
return 1
return dfs(i-1) + dfs(i-2)
return dfs(n)
# 递推
class Solution:
def climbStairs(self, n: int) -> int:
fo = f1 = 1
for _ in range(2, n+1):
new_f = f1 + f0
f0 = f1
f1 = new_f
return f1
14 杨辉三角
14.1 题目
给定一个非负整数numRows，生成杨辉三角的前numRows行。杨辉三角是指每个数是他左上方和右上方的数的和。
示例：
14.2 思路
将杨辉三角的最左边的数对齐，这样每一排首尾数为1，其余每个数就等于其左上方的数和正上方的数之和。
14.3 代码
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
c = [[1] * (i + 1) for i in range(numRows)]
for i in range(2, numRows):
for j in range(1, i):
c[i][j] = c[i-1][j-1] + c[i-1][j]
return c15 只出现一次的数字
15.1 题目
给你一个非空整数数组nums，除了某个元素只出现一次之外，其余元素都出现两次，请找出那个只出现一次的元素并返回。
示例：
输入：nums = [4,1,2,1,2]
输出：415.2 思路
异或运算，a⊕a=0，(a⊕b)⊕c=a⊕(b⊕c)，所以可以直接使用异或运算来找到那个只出现一次的元素。
15.3 代码
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(xor, nums)
16 多数元素
16.1 题目
给定一个大小为n的数组nums，返回其中的多数元素（即在数组中出现次数大于n/2的元素）。可以假设数组非空，且总是存在多数元素。
示例：
输入：nums = [2,2,1,1,1,2,2]
输出：216.2 思路
既然多数元素是在数组中出现次数大于n/2的元素，如果我们对nums进行排序，那么下标为n/2的元素一定是多数元素。
16.3 代码
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums) // 2]
作者：Komorebi S
