一、Algorithm
617. 合并二叉树
https://leetcode-cn.com/problems/merge-two-binary-trees/ 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if t1 is None or t2 is None:
return t1 if t2 is None else t2
t3 = TreeNode(t1.val + t2.val)
t3.left = self.mergeTrees(t1.left, t2.left)
t3.right = self.mergeTrees(t1.right, t2.right)
return t3
100. 相同的树
https://leetcode-cn.com/problems/same-tree/ 给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
"""
"""
if p is None and q:
return False
if q is None and p:
return False
if q is None and p is None:
return True
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
104. 二叉树的最大深度
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/ 给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3 / \ 9 20
/ \ 15 7 返回它的最大深度 3 。
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
else:
n_l = self.maxDepth(root.left)
n_r = self.maxDepth(root.right)
return max(n_l, n_r) + 1
118. 杨辉三角
https://leetcode-cn.com/problems/pascals-triangle/ 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例: 输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows == 0:
return []
results = [[1]]
for i in range(2, numRows + 1):
temp = [1]
for t in range(i - 2):
temp.append(results[i - 2][t] + results[i - 2][t + 1])
temp.append(1)
results.append(temp)
return results
def generate2(self, num_rows):
triangle = []
for row_num in range(num_rows):
# The first and last row elements are always 1.
row = [None for _ in range(row_num+1)]
row[0], row[-1] = 1, 1
# Each triangle element is equal to the sum of the elements
# above-and-to-the-left and above-and-to-the-right.
for j in range(1, len(row)-1):
row[j] = triangle[row_num-1][j-1] + triangle[row_num-1][j]
triangle.append(row)
return triangle
119. 杨辉三角
https://leetcode-cn.com/problems/pascals-triangle-ii/ 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 3 输出: [1,3,3,1] 进阶：
你可以优化你的算法到 O(k) 空间复杂度吗？
def getRow(self, rowIndex: int):
"""
初始化一个列表；
遍历列表，从第一行开始填充，直到rowIndex，注意初始的为第0行；
插入0在该行的最前面；
遍历这一行的数据，将第一个数据与第二个相加，得到第一个的新数据。
"""
row = [1]
for i in range(1, rowIndex + 1):
row.insert(0, 0)
for j in range(i):
row[j] = row[j] + row[j + 1]
return row
- 二叉树的层序遍历 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 给你一个二叉树，请你返回其按 自顶向下 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
- 二叉树的层次遍历 II https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/ 给你一个二叉树，请你返回其按 自下向上 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例： 二叉树：[3,9,20,null,null,15,7],
3 / \ 9 20
/ \ 15 7 返回其自上向下层次遍历结果：
[ [3], [9,20], [15,7] ] 返回其自底向上的层次遍历为：
[ [15,7], [9,20], [3] ]
def levelThroughTreeWithQueue(self, root: TreeNode):
"""
二叉树层级遍历（使用队列）
:param root:
:return:
"""
if root is None:
return []
result = []
queue_list = [root]
while queue_list:
result.append(queue_list[0].val)
if queue_list[0].left:
queue_list.append(queue_list[0].left)
if queue_list[0].right:
queue_list.append(queue_list[0].right)
queue_list.pop(0)
return result
def levelThroughTreeWithoutQueue(self, root: TreeNode):
"""
二叉树层级遍历（不使用队列）
:param root:
:return:
"""
if root is None:
return []
result = []
current_list = [root]
while current_list:
next_list = []
for item in current_list:
result.append(item.val)
if item.left:
next_list.append(item.left)
if item.right:
next_list.append(item.right)
current_list = next_list
return result
def levelOrderBottomWithQueue(self, root: TreeNode):
if root is None:
return []
result = []
queue_list = [root]
while queue_list:
i = 0
temp = []
queue_len = len(queue_list)
while i < queue_len:
temp.append(queue_list[0].val)
if queue_list[0].left:
queue_list.append(queue_list[0].left)
if queue_list[0].right:
queue_list.append(queue_list[0].right)
queue_list.pop(0)
i += 1
result.append(temp)
return result[::-1] # 自下而上
# return result 自上而下
def levelOrderBottomWithoutQueue(self, root: TreeNode):
if root is None:
return []
result = []
current_list = [root]
while current_list:
temp = []
next_list = []
for item in current_list:
temp.append(item.val)
if item.left:
next_list.append(item.left)
if item.right:
next_list.append(item.right)
result.append(temp)
current_list = next_list
return result[::-1] # 自下而上
# return result 自上而下
##
- 只出现一次的数字 https://leetcode-cn.com/problems/single-number/ 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1] 输出: 1 示例 2:
输入: [4,1,2,1,2] 输出: 4
def singleNumber(self, nums: List[int]) -> int:
# for i in range(len(nums)):
# if nums[i] not in (nums[:i] + nums[i + 1:]):
# print(nums[i])
# dict_temp = {}
# for i in nums:
# dict_temp[i] = dict_temp.get(i, 0) + 1
# for k,v in dict_temp.items():
# if v == 1:
# return k
# from collections import Counter
# t = Counter(nums)
# return t.most_common()[-1][0]
# 任何数与0异或等于其本身：1 ^ 0 = 1
# 任何数与自身异或等于0： 1 ^ 1 = 0
# 异或符合交换律： 1^1 ^0 = 1^0^1 = 0^1^1
from functools import reduce
return reduce(lambda x, y: x ^ y, nums)
剑指 Offer 56 - I. 数组中数字出现的次数
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
一个整型数组 nums里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2] ```python
def singleNumbers(self, nums ) :
"""
:param nums:
:return: -> List[int]
"""
from collections import Counter
return [i[0] for i in Counter(nums).most_common()[-2:]] ``` ## 169. 多数元素 https://leetcode-cn.com/problems/majority-element/ 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3] 输出: 3 示例 2:
输入: [2,2,1,1,1,2,2] 输出: 2
def majorityElement(self, nums: List[int]) -> int:
from collections import Counter
return Counter(nums).most_common(1)[0][0]
# Counter(iterable).most_commoon(n) # 返回一个元组类型的列表[(3,2),(2,1)]
461. 汉明距离
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意： 0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
解释: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑
上面的箭头指出了对应二进制位不同的位置。
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
distance = 0
while x != 0 or y != 0:
x_a = x % 2
y_a = y % 2
distance += x_a ^ y_a
x //= 2
y //= 2
return distance
def hammingDistance2(self, x: int, y: int) -> int:
return bin(x^y).count('1')
67. 二进制求和
https://leetcode-cn.com/problems/add-binary/ 给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = “11”, b = “1” 输出: “100” 示例 2:
输入: a = “1010”, b = “1011” 输出: “10101”
提示：
每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。 1 <= a.length, b.length <= 10^4 字符串如果不是 “0” ，就都不含前导零。
def addBinary(self, a: str, b: str) -> str:
"""
先转化为十进制，再运算，再转为二进制，剔除0b
"""
return bin(int(a, 2) + int(b, 2))[2:]
def addBinary2(self, a: str, b: str) -> str:
"""
模拟加法
"""
result = ""
len_a = len(a) - 1
len_b = len(b) - 1
cur = 0
while len_a >= 0 and len_b >= 0:
cur += int(a[len_a])
cur += int(b[len_b])
len_a -= 1
len_b -= 1
result += str(cur % 2)
cur //= 2
while len_a >= 0:
cur += int(a[len_a])
len_a -= 1
result += str(cur % 2)
cur //= 2
while len_b >= 0:
cur += int(b[len_b])
len_b -= 1
result += str(cur % 2)
cur //= 2
if cur:
result += str(cur)
return result[::-1]
83. 删除排序链表中的重复元素
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/ 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2 输出: 1->2 示例 2:
输入: 1->1->2->3->3 输出: 1->2->3
def deleteDuplicatesWithoutOrders(self, head: ListNode) -> ListNode:
"""
无序链表去重
"""
temp_list = []
start = head
pre = None
while head:
if head.val not in temp_list:
temp_list.append(head.val)
pre = head
else:
pre.next = head.next
head = head.next
return start
def deleteDuplicatesWithOrders(self, head: ListNode) -> ListNode:
"""
有序链表去重
"""
if head is None or head.next is None:
return head
head_copy = head
while head and head.next:
if head.val == head.next.val:
head.next = head.next.next
else:
head = head.next
return head_copy
171. Excel表列序号
给定一个Excel表格中的列名称，返回其相应的列序号。
例如，
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
... 示例 1:
输入: “A” 输出: 1 示例 2:
输入: “AB” 输出: 28 示例 3:
输入: “ZY” 输出: 701
class Solution:
def titleToNumber(self, s: str) -> int:
result = 0
for i in s:
temp = ord(i) - ord("A") + 1
result = 26 * result + temp
return result