算法之美

2020-07-27 python

1. 两数之和

class Solution:
    def twoSum(self, nums, target):
        hashmap = {}
        if not nums:
            return []
        # 把数据和下标导入hash表
        for ids,num in enumerate(nums):
            hashmap[num] = ids
        # 从哈希表匹配是否存在两个数相加=target,匹配则返回其下标
        for i,nums in enumerate(nums):
            j = hashmap.get(target-nums)
            if i != j and j is not None:
                return [i,j]

199. 二叉树的右视图

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

class Solution:
    def __init__(self):
        self.ls = []
    def rightSideView(self,root,length=1):
        if not root:
            return []
        if length > len(self.ls):
            self.ls.append(root.val)
        self.rightSideView(root.right,length+1)
        self.rightSideView(root.left,length+1)
        return self.ls

1099. 小于 K 的两数之和

class Solution:
    #O(n*logN)
    def twoSumLessThanK(self, A, K):
        A.sort() #排序O(n*logN)
        length = len(A)
        left,right = 0,length - 1 #双指针
        sums = -1
        while left < right: O(N)
            tmp = A[left] + A[right]
            if tmp < K:
                sums = max(sums,tmp)
                left += 1
            else:
                right -= 1
        return sums 

653. 两数之和 IV – 输入 BST

二叉搜索树中序遍历是升序数组+hashmap

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

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        def inorder(root):
            if not root:
                return []
            return inorder(root.left)+[root.val]+inorder(root.right)
        target = inorder(root)
        n = len(target)
        
        # 创建哈希表
        _dict = {}
        for i, m in enumerate(target):
            if _dict.get(k - m) is not None:
                return True
            _dict[m] = i
        return False
2020-07-27 python已关闭评论