LeetCode0305

2020-03-05  本文已影响0人  inspiredhss

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
上一篇下一篇

猜你喜欢

热点阅读