- 题意是给定一个数字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")
- 给定一个数组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)
