分享两道算法题

---

王者荣耀分组

题目描述
部门准备举办一场王者荣耀表演赛，有 10 名游戏爱好者参与，分 5 为两队，每队 5 人。
每位参与者都有一个评分，代表着他的游戏水平。
为了表演赛尽可能精彩，我们需要把 10 名参赛者分为实力尽量相近的两队。一队的实力可以表示为这一队 5 名队员的评分总和。
现在给你 10 名参与者的游戏水平评分，请你根据上述要求分队最后输出这两组的实力差绝对值。
例: 10 名参赛者的评分分别为 5 1 8 3 4 6 7 10 9 2，分组为 (1 3 5 8 10) (2 4 6 7 9)，两组实力差最小，差值为 1。有多种分法，但实力差的绝对值最小为 1。

输入描述
10 个整数，表示 10 名参与者的游戏水平评分。范围在[1,10000]之间

输出描述
1 个整数，表示分组后两组实力差绝对值的最小值。

示例一
输入

1 2 3 4 5 6 7 8 9 10
输出
1
说明

10 名队员分成两组，两组实力差绝对值最小为 1

基于C语言的代码：

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
int total = 0;
int res = INT_MAX;
// 深度优先搜索函数
void dfs(int score[10], int idx, int count, int currentSum) {// 当我们为一个队伍选择了5名玩家时if (count == 5) {// 计算另一个队伍的总和int otherTeamSum = total - currentSum;// 用较小的差值更新结果res = abs(currentSum - otherTeamSum) < res? abs(currentSum - otherTeamSum): res;return;}// 如果我们已经考虑了所有玩家，停止递归if (idx == 10) {return;}// 为第一个队伍选择当前玩家dfs(score, idx + 1, count + 1, currentSum + score[idx]);// 不为第一个队伍选择当前玩家dfs(score, idx + 1, count, currentSum);
}
int main() {int score[10];for (int i = 0; i < 10; i++) {scanf("%d", &score[i]);total += score[i];}dfs(score, 0, 0, 0);printf("%d", res);return 0;
}

注意: <limits.h>
<limits.h> 是 C 语言的一个标准库头文件，它定义了各种数据类型（如整数、浮点数等）的最小和最大可能值。在程序中包含 <limits.h> 头文件后，可以使用预定义的宏来访问这些值。

例如，在给定的代码片段中，INT_MAX 就是来自 <limits.h> 的一个预定义宏，表示 int 类型的最大值。这个宏在初始化变量 res 时被用作初始的最大可能实力差：
int res = INT_MAX;

通过这样的方式，我们可以确保 res 被初始化为一个足够大的数值，以便在后续计算中能够容纳任何可能出现的实力差，并能够在遍历所有分组方案后更新到真正的最小实力差。

基于Python的代码求解

import sysres = sys.maxsize
sum = 0
tarsum = 0
#global sum, res：声明sum和res为全局变量，这样在dfs函数内部可以访问和修改它们。
# cursum是当前队伍的总得分def dfs(mylist,id,count,cursum):global sum,res,trasumif count == 5:othersum = sum - cursumres = min(res,abs(cursum - othersum))return# id 记录了全部玩家的情形，id等于10则停止递归if id == 10:return#选择当前队伍的玩家dfs(mylist,id+1,count+1,cursum+mylist[id])#另一个队伍的玩家dfs(mylist,id+1,count,cursum)mylist = list(map(int, input().split(' ')))
for i in mylist:sum += itrasum = sum // 2
dfs(mylist,0,0,0)
print(res)

最大括号深度

基于python代码求解

#定义栈strings = input()
def depth(s):if not s:return 0stack = []maxdepth = 0for i ,c in enumerate(s):if c in '({[':stack.append(c)maxdepth = max(maxdepth,len(stack))else:if not stack:breakif(c==')' and stack[-1]=='(') or \(c=='}' and stack[-1]=='{') or \(c==']' and stack[-1]=='[') :stack.pop()else:breakreturn maxdepth if not stack else 0print(depth(strings))        

或者更简单的写法：

s = input()def getResult():map = {")": "(","]": "[","}": "{"}stack = []for c in s:if stack and map.get(c) == stack[-1]:stack.pop()else:stack.append(c)if stack:return 0return len(stack)print(getResult())

总结：

以上两道算法题第一道用到了深度优先搜索的思想，题目想要得到一个使得两队的实力差距最小的分组方案，我们利用了深度优先搜索的思想，将队员i加入第一个队代表向前走，不加入代表选择其他路径；最终深度优先搜索代码遍历了所有可能的分配方案，并通过我们定义的参数res返回了最佳分配方案的两队实力差距。而第二题很明显要用到栈的思想，python中列表的添加元素和删除末尾元素成功模拟了入栈和出栈的过程，当栈中上一个元素的对应括号出现时，则出栈，否则入栈，最终将记录到的栈的最大长度输出。