企业官网建设流程全解析

做徽章的网站,沈阳优化网站公司,网站建设套餐报价方案,WordPress无法写博客头像文章目录摘要描述题解答案题解代码分析示例测试及结果再举一个直观点的例子时间复杂度空间复杂度总结摘要 这道题表面看起来像是个简单的博弈问题#xff0c;但真正写起来#xff0c;很多人会直接被「状态爆炸」劝退。 maxChoosableInteger 最大能到 20#xff0c;看似不大…文章目录摘要描述题解答案题解代码分析示例测试及结果再举一个直观点的例子时间复杂度空间复杂度总结摘要这道题表面看起来像是个简单的博弈问题但真正写起来很多人会直接被「状态爆炸」劝退。maxChoosableInteger最大能到 20看似不大但所有组合一算状态数量直接飙到百万级。这类题非常典型规则简单 最优策略 不能贪心 需要记忆化搜索。如果你最近在刷博弈类、状态压缩、DFS Memo 的题这道题几乎是绕不开的一关。本文会一步一步拆解思路并用 Swift 给出一份可运行、好理解的实现。描述游戏规则可以简单总结成几句话有一个公共数字池数字范围是1 ~ maxChoosableInteger两个玩家轮流选数每个数字只能用一次选中的数字会累加到当前总和谁先让累计和达到或超过desiredTotal谁就赢两个玩家都足够聪明永远走最优解问题是先手玩家是否一定能赢这里有几个关键点很容易被忽略这是一个典型的「零和博弈」玩家不会随机选而是“我选了你会怎么反制”不能重复选数意味着状态不仅和“当前和”有关还和“哪些数已经用过”有关这就直接决定了贪心是行不通的暴力 DFS 会超时必须配合记忆化。题解答案核心思路一句话总结把“当前还能不能赢”这个问题抽象成一个函数用「已经选过的数字集合」作为状态用 DFS 记忆化搜索判断是否存在一个必胜选择。几个重要剪枝先说清楚如果desiredTotal 0先手啥都不选就已经赢了直接返回true如果1 2 ... maxChoosableInteger desiredTotal那无论怎么选总和都达不到目标先手必输真正的博弈逻辑是当前玩家尝试选择一个还没用过的数字i如果i 剩余目标当前玩家立刻赢否则把这个数标记为已使用递归判断对手是否会输只要存在一个选择能让对手输那当前玩家就是稳赢题解代码分析下面是完整 Swift 实现支持直接运行测试。classSolution{funccanIWin(_maxChoosableInteger:Int,_desiredTotal:Int)-Bool{// 特殊情况目标本身 0先手直接赢ifdesiredTotal0{returntrue}// 所有数加起来都不够必输letmaxSum(1maxChoosableInteger)*maxChoosableInteger/2ifmaxSumdesiredTotal{returnfalse}varmemo[Int:Bool]()returndfs(usedMask:0,remaining:desiredTotal,maxNum:maxChoosableInteger,memo:memo)}privatefuncdfs(usedMask:Int,remaining:Int,maxNum:Int,memo:inout[Int:Bool])-Bool{// 如果这个状态已经算过直接返回ifletcachedmemo[usedMask]{returncached}// 尝试选择每一个还没用过的数字foriin1...maxNum{letbit1(i-1)if(usedMaskbit)!0{continue}// 如果当前选 i 就能赢直接返回 trueifiremaining{memo[usedMask]truereturntrue}// 否则看对手在新状态下是否会输letnextMaskusedMask|bitletopponentWindfs(usedMask:nextMask,remaining:remaining-i,maxNum:maxNum,memo:memo)// 对手输说明我赢if!opponentWin{memo[usedMask]truereturntrue}}// 所有选择都会让对手赢那我必输memo[usedMask]falsereturnfalse}}示例测试及结果我们用题目里的例子来跑一跑。letsolutionSolution()print(solution.canIWin(10,11))// falseprint(solution.canIWin(10,0))// trueprint(solution.canIWin(10,1))// true输出结果false true true结果和题目给的一致。再举一个直观点的例子print(solution.canIWin(5,6))解释一下可选数字是 1~5如果先手选 1对手选 5直接赢如果先手选 2对手选 4也能赢无论先手怎么走都挡不住对手结果自然是false。时间复杂度状态的核心是usedMask它是一个最多 20 位的二进制数。状态数量最多是2^20 ≈ 1,048,576每个状态最多遍历maxChoosableInteger次所以时间复杂度可以近似认为是O(2^n * n)在题目限制n 20的情况下配合记忆化是完全能跑过的。空间复杂度主要消耗在两个地方记忆化哈希表最多存2^n个状态DFS 递归栈深度最多n所以空间复杂度是O(2^n)这是这类博弈 状态压缩题的正常代价。总结这道题非常适合用来练三件事如何把「博弈问题」抽象成递归状态如何用 bitmask 表示“选择过哪些数”如何用记忆化避免指数级重复计算