461. 汉明距离
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x ^ y).count('1')
# class Solution:
# def hammingDistance(self, x, y):
# xor = x ^ y
# distance = 0
# while xor:
# distance += 1
# # remove the rightmost bit of '1'
# xor = xor & (xor - 1)
# return distance
617. 合并二叉树
class Solution:
def mergeTrees(self, t1, t2):
def dfs(r1,r2):
# 如果 r1和r2中，只要有一个是null，函数就直接返回
if not (r1 and r2):
return r1 if r1 else r2
# 让r1的值 等于 r1和r2的值累加
# 再递归的计算两颗树的左节点、右节点
r1.val += r2.val
r1.left = dfs(r1.left,r2.left)
r1.right = dfs(r1.right,r2.right)
return r1
return dfs(t1,t2)
class Solution(object):
def mergeTrees(self, t1, t2):
# 如果 t1和t2中，只要有一个是null，函数就直接返回
if not (t1 and t2):
return t2 if not t1 else t1
queue = [(t1,t2)]
while queue:
r1,r2 = queue.pop(0)
r1.val += r2.val
# 如果r1和r2的左子树都不为空，就放到队列中
# 如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
if r1.left and r2.left:
queue.append((r1.left,r2.left))
elif not r1.left:
r1.left = r2.left
# 对于右子树也是一样的
if r1.right and r2.right:
queue.append((r1.right,r2.right))
elif not r1.right:
r1.right = r2.right
return t1
226. 翻转二叉树
class Solution(object):
def invertTree(self, root):
if not root:
return None
# 将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
queue = [root]
while queue:
# 每次都从队列中拿一个节点，并交换这个节点的左右子树
tmp = queue.pop(0)
tmp.left,tmp.right = tmp.right,tmp.left
# 如果当前节点的左子树不为空，则放入队列等待后续处理
if tmp.left:
queue.append(tmp.left)
# 如果当前节点的右子树不为空，则放入队列等待后续处理
if tmp.right:
queue.append(tmp.right)
# 返回处理完的根节点
return root
class Solution(object):
def invertTree(self, root):
# 递归函数的终止条件，节点为空时返回
if not root:
return None
# 将当前节点的左右子树交换
root.left,root.right = root.right,root.left
# 递归交换当前节点的 左子树和右子树
self.invertTree(root.left)
self.invertTree(root.right)
# 函数返回时就表示当前这个节点，以及它的左右子树
# 都已经交换完了
return root
104. 二叉树的最大深度
class Solution:
def maxDepth(self, root):
stack = []
if root is not None:
stack.append((1, root))
depth = 0
while stack != []:
current_depth, root = stack.pop()
if root is not None:
depth = max(depth, current_depth)
stack.append((current_depth + 1, root.left))
stack.append((current_depth + 1, root.right))
return current_depth
class Solution:
def maxDepth(self, root):
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) + 1
206. 反转链表
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 申请两个节点，pre和 cur，pre指向None
pre = None
cur = head
# 遍历链表，while循环里面的内容其实可以写成一行
# 这里只做演示，就不搞那么骚气的写法了
while cur:
# 记录当前节点的下一个节点
tmp = cur.next
# 然后将当前节点指向pre
cur.next = pre
# pre和cur节点都前进一位
pre = cur
cur = tmp
return pre
226. 翻转二叉树
class Solution(object):
def invertTree(self, root):
if not root:
return None
# 将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
queue = [root]
while queue:
# 每次都从队列中拿一个节点，并交换这个节点的左右子树
tmp = queue.pop(0)
tmp.left,tmp.right = tmp.right,tmp.left
# 如果当前节点的左子树不为空，则放入队列等待后续处理
if tmp.left:
queue.append(tmp.left)
# 如果当前节点的右子树不为空，则放入队列等待后续处理
if tmp.right:
queue.append(tmp.right)
# 返回处理完的根节点
return root
class Solution(object):
def invertTree(self, root):
# 递归函数的终止条件，节点为空时返回
if not root:
return None
# 将当前节点的左右子树交换
root.left,root.right = root.right,root.left
# 递归交换当前节点的 左子树和右子树
self.invertTree(root.left)
self.invertTree(root.right)
# 函数返回时就表示当前这个节点，以及它的左右子树
# 都已经交换完了
return root
501. 二叉搜索树中的众数
class Solution:
def __init__(self):
self.count = 1
self.target = [0,0]
self.pre = -1 # 初始判断值设为-1，用于判断第一个值（中序遍历，即最左边的值）
def findMode(self, root: TreeNode) -> List[int]:
if not root:
return []
self.inorder(root)
#最后一组数在递归终止后无法判断，因此要重新判断一下
if self.count >self.target[0]:
self.target = [self.count,self.pre]
elif self.count==self.target[0]:
self.target.append(self.pre)
return self.target[1:]
# 中序遍历，边遍历边判断
def inorder(self,root):
if not root:
return None
self.inorder(root.left)
if root:
if self.pre == -1: #第一个值，其实相当于初始化pre值
self.pre = root.val
elif self.pre == root.val:
self.count += 1
else:
if self.count >self.target[0]:
self.target = [self.count,self.pre]
elif self.count==self.target[0]:
self.target.append(self.pre)
self.count = 1
self.pre = root.val
self.inorder(root.right)
https://www.cnblogs.com/anzhengyu/p/11083568.html
image.png
image.png
image.png
image.png
image.png
image.png
171. Excel表列序号
class Solution:
def titleToNumber(self, s: str) -> int:
res = 0
bit = 1
for a in s[::-1]:
res += (ord(a) - 64) * bit
bit *= 26
return res
191. 位1的个数
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n:
res = n % 2
if res == 1:
count += 1
n //= 2
return count
118. 杨辉三角
class Solution:
def generate(self, num_rows):
triangle = []
for row_num in range(num_rows):
row = [None for _ in range(row_num+1)]
row[0], row[-1] = 1, 1
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
网友评论