【LeetCode】【Python题解】Single Number & Maximum Depth of Binary Tree

时间：2021-10-03 00:47:03

今天做了三道LeetCode上的简单题目，每道题都是用c++和Python两种语言写的。由于c++版的代码网上比較多。所以就仅仅分享一下Python的代码吧，刚学完Python的基本的语法，做做LeetCode的题目还是不错的，对以后找工作面试也有帮助！

刚開始就从AC率最高的入手吧！

1.Given an array of integers, every element appears twice except
for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

開始纠结于线性时间复杂度和不要额外的存储空间。思路是遍历一遍数组。想象成翻硬币。碰到一次就翻面，再碰到就翻回来了。剩下的那个仍是背面的就是仅仅出现一次的。可是这样的思路就势必要有额外的存储空间。后来看了别人的思路，原来所有异或就能够了。由于A XOR A =0，0 XOR any = any。简单多了。

class Solution:

    # @param A, a list of integer

    # @return an integer

    def singleNumber(self, A):

        result = 0

        for i in A:

            result = result ^ i

        return result

2.Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

递归寻找左子树和右子树的深度，取二者较大的，再加上根的深度1。即为答案。

# Definition for a  binary tree node

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    # @param root, a tree node

    # @return an integer

    def maxDepth(self, root):

        if root is None:

            return 0

        else:

            return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

相关文章