pythonブラシleetcodeテーマ(13)

136.一度しか現れない数字
空でない整数配列が与えられ、ある要素が1回しか現れない以外は、各要素が2回現れます.それが一度しか現れなかった要素を見つけます.
説明:
あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?
例1:

  : [2,2,1]
  : 1

例2:

  : [4,1,2,1,2]
  : 4

コードは次のとおりです.

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        mark = 0
        if len(nums) == 1:
            return(nums[0])
        else:
            for i in range(len(nums)-1):
                if nums[i] == nums[i+1] :
                    mark += 1
                else:
                    if mark == 0:
                        return nums[i]
                    else:
                        mark = 0
                if nums[-1] != nums[-2]:
                    return nums[-1]
                
       

102.ツリーの階層遍歴
ツリーを指定して、階層的にループするノード値を返します.(つまり、左から右へすべてのノードに階層的にアクセスします).
例えば、所与の二叉木:[3,9,20,null,null,15,7]、

    3
   / \
  9  20
    /  \
   15   7

階層遍歴の結果を返します.

[
  [3],
  [9,20],
  [15,7]

コードは以下の通りである:44 ms通過、キューの広さ優先遍歴を採用

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

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        res = []
        queue = [root]
        while queue:
            nodes = []
            values = []
            for node in queue:
                if node.left:
                    nodes.append(node.left)
                if node.right:
                    nodes.append(node.right)
                values += [node.val]
            res += [values]
            queue = nodes
        return res
        

#### the second method 
        stack = [(root,0)]
        res = []
        while stack!=[]:
            node,level = stack.pop()
            if node:
                if len(res) < (level+1):
                    res.insert(0,[])
                res[-(level+1)].append(node.val)
                stack.append((node.right,level+1))
                stack.append((node.left,level+1))
        return res[::-1]    
            

学び合い、教え合う.