2020.2.5 LeetCode刷题记录


617. 合并二叉树

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:
            return t2
        if t2 is None:
            return t1
        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)
        return t1

两棵树进行前序遍历,节点都存在时相加或返回单一存在的值,时间复杂度为N(最小树的节点数),空间复杂度也是N。

461. 汉明距离

# 最笨的方法
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        x = list(str(bin(x)))[2:]
        y = list(str(bin(y)))[2:]
        # print(x)
        # print(y)
        if len(x) > len(y):
            length = len(x) - len(y)
            for i in range(length):
                y.insert(0, '0')
        else:
            length = len(y) - len(x)
            for i in range(length):
                x.insert(0, '0')

        n_sum = 0
        for i in range(len(x)):
            if x[i] != y[i]:
                n_sum += 1
        return n_sum

其实python中一行就能解决

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x ^ y).count("1")  # 符号^是按位亦或, bin生成的是字符串

226. 翻转二叉树

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return root
        root.right = left  # 将当前的左右子树交换
        root.left = right

        right = self.invertTree(root.right)  # 递归的交换左右子树
        left = self.invertTree(root.left)

        return root

104. 二叉树的最大深度

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        left_depth = self.maxDepth(root.left) + 1
        right_depth = self.maxDepth(root.right) + 1
        return max(left_depth, right_depth)

206. 反转链表

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        my_head = ListNode(0)
        while head:
            tmp = ListNode(head.val)   # 注意这里拷贝的问题
            tmp.next = my_head.next
            my_head.next = tmp
            head = head.next
        return my_head.next

136. 只出现一次的数字

菜鸡解法:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        x_d = dict()
        for x in nums:
            x_d[x] = 1 + x_d.get(x, 0)
        for x in x_d.keys():
            if x_d[x] == 1:
                return x

大佬解法:

class Solution:
    def singleNumber(self, nums):
        a = 0  # 与零异或数不变
        for num in nums:
            a = a ^ num  # 异或满足交换律a ^ b ^ a == a ^ a ^ b, 相同的数异或为0
        return a

169. 多数元素

import collections
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

文章作者: Hanjun Liu
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Hanjun Liu !
 上一篇
Golang基础整理 Golang基础整理
基础包每个程序都是由包构成的,程序从main包开始运行,规定包名与导入路径中最后一个元素相对应import math/rand包中的源码均以package rand开始。 在Go中如果名字是大写开头就是可以导出的,以小写字母开头是不可以导出
2020-02-05
下一篇 
GIT笔记 GIT笔记
Git结构git本地库分为三个区工作区(写代码), 暂存区(临时存储), 本地库(历史版本的程序). 工作区–git add–暂存区–git commit–本地库 本地库和远程库分为两种协作模式: 团队间的协作 跨团队的协作 签
2020-02-04 Hanjun Liu
  目录