2021-08-10 Alibaba笔试

1. 题意是给定一个数字n，再给定一个数组arr，求arr的子序列和刚好等于n，多组输入，能满足则打印"Yes"，否则打印"No"
   输入样例：

2
5
1 1 1 1 2
6
1 1 1 1 2

输出样例：

Yes
No

笔试入迷了写错循环条件，防止越界条件应该和判断条件是 and 的关系，而不是 or ，导致只有 60% 的通过率

正确写法

from collections import deque


times = int(input().strip())

for i in range(times):
    n = int(input().strip())
    arr = [int(i) for i in input().strip().split()]
    
    q = deque()
    flag = False
    for j in range(len(arr)):
        q.append(arr[j])
        
        while len(q) > 0 and sum(q) > n:
            q.popleft()
        
        if sum(q) == n:
            print("Yes")
            flag = True
            break
    
    if not flag:
        print("No")

2. 给定一个数组arr（例如：[4, 3, 5, 2, 1]），构建成一个二叉排序树，如果每个节点的左右子树节点数量只差的绝对值小于 min(11, ⌊n/2⌋) ，也就是向上取整，那么输出 "YES"，否则"NO"。
   这道题是 leetcode 701 -- 二叉搜索树的插入操作 的变形

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def __init__(self):
        self.flag = False

    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)

        pos = root
        while pos:
            if val < pos.val:
                if not pos.left:
                    pos.left = TreeNode(val)
                    break
                else:
                    pos = pos.left
            else:
                if not pos.right:
                    pos.right = TreeNode(val)
                    break
                else:
                    pos = pos.right

        return root

    def pre_order(self, root):
        if root is None:
            return

        print(root.val)
        self.in_order(root.left)
        self.in_order(root.right)

    def in_order(self, root):
        if root is None:
            return

        self.in_order(root.left)
        print(root.val)
        self.in_order(root.right)

    def is_balance(self, root, half):
        if root is None:
            return 0

        # 计算左子树的总节点数量
        leftLevel = self.is_balance(root.left, half)
        # 计算右子树的总节点数量
        rightLevel = self.is_balance(root.right, half)

        # 只要左子树节点数量大于右子树节点数，就把self.flag置为True
        if abs(leftLevel - rightLevel) > min(11, half):
            # 相当于全局变量
            self.flag = True
        return leftLevel + rightLevel + 1


if __name__ == '__main__':
    # arr = [1, 5, 6, 2, 3, 4] 二叉搜索树会出现不平衡的例子
    arr = [1, 5, 6, 2, 3, 4]
    root = TreeNode(arr[0])
    so = Solution()
    for i in range(1, len(arr)):
        root = so.insertIntoBST(root, arr[i])

    so.pre_order(root)
    print("=====")
    so.in_order(root)
    ret = so.is_balance(root, len(arr) // 2)
    print(ret)
    print(so.flag)