恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝
第一道：完美切分（100%）
题目：
输入一个数代表把绳子切成n段，然后输入切分每段的长度，如果满足1<=k<=绳子长度（就是切分的每段长度的和）k都满足k=任意段相加的和，就称为完美切分
如输入：
5
1 1 1 1 2
那么可以组成1，2，3，4，5，6满足完美切分，
输出YES
否则输出NO
前缀和保存在列表里，对1到L的每个n判断：遍历列表中的每个前缀和prefix, prefix+n在不在列表里；
def get_all_sum(nums):
# 计算连续区间所有和的可能结果
sums = []
n = len(nums)
for i in range(1, n + 1):
for j in range(n - i + 1):
sums.append(sum(nums[j:j + i]))
return set(sums) # 去重
import sys
if __name__ == "__main__":
T = int(sys.stdin.readline().strip())
ans = 0
for i in range(T):
N = int(sys.stdin.readline().strip())
line = sys.stdin.readline().strip()
a = list(map(int, line.split()))
L = sum(a)
sums = get_all_sum(a)
# 不需要每个整数都判断，只需要判断求出来的和的数量和L是否相同即可
num_sum = len(sums)
if num_sum == L:
print("yes")
else:
print("no")
第二道： 平衡树（100%）
题目：
输入二叉树，按照bfs规则生成二叉树，然后如果满足每个节点左右节点高度差小于min = min(11,节点数/2) ,则输出Yes，否则输出No.
CPP版
不用建树，把数组导入队列，比头节点小的导入左队列，大的放入右队列，对两个队列递归求出深度，判断是否满足a-balance，不知道这么考虑是否有问题
int judge(queue<int>& q,int n)
{
if (q.size() == 0)
return 0;
int temp = q.front();
q.pop();
queue<int> left;
queue<int> right;
while (!q.empty())
{
int t = q.front();
if (t > temp)
{
right.push(t);
q.pop();
}
else
{
left.push(t);
q.pop();
}
}
int l = judge(left, n);
int r = judge(right, n);
if (l == -1 || r == -1)
return -1;
if (abs(r - l) > min(11, n))
return -1;
else
return max(l, r) + 1;
}
int main()
{
int group;
cin >> group;
while (group--)
{
int n;
cin >> n;
vector<int> array(n);
queue<int> q;
for (int i = 0; i < n; i++)
{
cin >> array[i];
q.push(array[i]);
}
if(judge(q, n）!=-1)
cout<<"yes"<<endl;
}
初始化root之后建树，再之后递归判断每个节点的isBalance() 。
java版
建树
// 建树
static TreeNode build(TreeNode root, int val){
if(root == null) return new TreeNode(val);
if(root.val > val) root.left = build(root.left, val);
else root.right = build(root.right, val);
return root;
}
// 判断
static boolean isBalance(TreeNode root, int N){
if(root == null) return true;
int left = 0, right = 0;
TreeNode node = root;
while(node.left != null){
node = node.left;
left++;
}
node = root;
while (node.right != null){
node = node.right;
right++;
}
return Math.abs(left - right) <= Math.min(11, N) && isBalance(root.left, N) && isBalance(root.right, N);
}
Python版
t = int(input())
for _ in range(t):
n = int(input())
nums = list(map(int, input().split()))
def dfs(nums):
if len(nums) <= 1:
return True
root = nums[0]
left = []
right = []
for num in nums[1:]:
if num > root:
right.append(num)
else:
left.append(num)
Abs = abs(get_left([root]+left) - get_right([root]+right))
return dfs(left) and dfs(right) and Abs < ban
def get_left(nums):
c = 0
tmp = nums[0]
for num in nums[1:]:
if num<tmp:
c += 1
tmp = num
return c
def get_right(nums):
c = 0
tmp = nums[0]
for num in nums[1:]:
if num>tmp:
c += 1
tmp = num
return c
ban = min(11, n//2)
if dfs(nums):
print("YES")
else:
print("NO")
