企业官网建设流程全解析

深圳个性化网站建设公司,机械做网站好处,安卓app开发语言,wordpress 中文字体文章目录摘要描述题解答案计算每个人的净资产在净资产数组上做最少匹配题解代码分析核心逻辑拆解一下为什么可以忽略已经为 0 的人#xff1f;为什么只找符号相反的#xff1f;剪枝为什么成立#xff1f;示例测试及结果示例 1分析过程示例 2时间复杂度空间复杂度总结摘要 《…文章目录摘要描述题解答案计算每个人的净资产在净资产数组上做最少匹配题解代码分析核心逻辑拆解一下为什么可以忽略已经为 0 的人为什么只找符号相反的剪枝为什么成立示例测试及结果示例 1分析过程示例 2时间复杂度空间复杂度总结摘要《最优账单平衡》这道题很多人第一次看到都会有点懵不就是转账吗为什么会是困难题真正难的地方不在“算钱”而在于如何用最少的转账次数把一堆复杂的债务关系彻底清零。这类问题在现实中非常常见比如多人 AA 聚餐之后的结算团队项目里垫资、报销、代付公司内部多部门费用对冲题目本身不复杂但如果直接模拟转账很容易陷入组合爆炸。正确的解法核心只有一句话先把问题化简再用回溯暴力但要暴力得聪明。描述题目给了我们一组交易transactions每一条形如[from, to, amount]表示from给to转了amount的钱。最终目标是在不改变每个人最终盈亏结果的前提下用最少的转账次数把所有人的账清干净。有几个关键约束需要先想清楚不关心原始交易顺序只关心“每个人最终是多收了钱还是多付了钱”转账次数越少越好金额大小无所谓换句话说我们不是要“复现原交易”而是要重排债务关系。题解答案整体思路可以分成两步。计算每个人的净资产我们先不管怎么转账只统计结果转出的钱记为负数转入的钱记为正数最后每个人只会剩下一个数正数别人欠他钱负数他欠别人钱0已经结清可以直接忽略这一步非常关键它能把问题规模大幅缩小。在净资产数组上做最少匹配接下来就变成了一个更抽象的问题给你一组正负数正数和负数总和为 0用最少的“配对抵消”次数让所有数都变成 0。这个问题非常适合用回溯 剪枝来解决每次找一个还没清零的债务尝试和后面符号相反的债务进行抵消把这一步算作一次转账递归处理剩余部分取最小次数题解代码分析下面是完整 Swift 实现逻辑清晰、可以直接运行。classSolution{funcminTransfers(_transactions:[[Int]])-Int{varbalance[Int:Int]()// 统计每个人的净资产fortintransactions{letfromt[0]lettot[1]letamountt[2]balance[from,default:0]-amount balance[to,default:0]amount}// 只保留不为 0 的债务vardebtsbalance.values.filter{$0!0}returndfs(debts,0)}privatefuncdfs(_debts:inout[Int],_start:Int)-Int{// 跳过已经结清的whilestartdebts.countdebts[start]0{returndfs(debts,start1)}ifstartdebts.count{return0}varminCountInt.maxforiin(start1)..debts.count{// 只尝试符号相反的进行抵消ifdebts[start]*debts[i]0{letoriginaldebts[i]debts[i]debts[start]minCountmin(minCount,1dfs(debts,start1))debts[i]original// 剪枝如果正好抵消没必要再试别的iforiginaldebts[start]0{break}}}returnminCount}}核心逻辑拆解一下为什么可以忽略已经为 0 的人因为他们已经“账平了”不需要再参与任何转账。这一步对性能提升非常明显。为什么只找符号相反的一个是欠钱负数一个是收钱正数只有这样才能发生真实有效的“抵消”。两个正数或者两个负数永远解决不了问题。剪枝为什么成立iforiginaldebts[start]0{break}这表示当前这次配对已经是完美抵消再继续尝试别的组合只会增加转账次数不可能更优。示例测试及结果示例 1letsolutionSolution()lettransactions[[0,1,10],[2,0,5]]print(solution.minTransfers(transactions))分析过程0-10 5 -51102-5债务数组变成[-5, 10, -5]最优方案1 给 0 转 51 给 2 转 5总共2 次转账输出2示例 2lettransactions[[0,1,10],[1,0,10]]print(solution.minTransfers(transactions))两笔交易完全抵消所有人最终余额都是 0。输出0时间复杂度这道题本质上是一个NP 难问题。最坏情况下需要尝试所有债务组合回溯的时间复杂度接近O(n!)但题目限制了参与人数一般不会超过 12 个非零债务节点。再加上大量剪枝实际运行非常快。空间复杂度主要消耗在debts数组递归调用栈空间复杂度为O(n)总结《最优账单平衡》这道题的价值不在于“写代码有多复杂”而在于建模能力把原始交易压缩成“净资产”把业务问题抽象成“正负数抵消”用回溯解决“最少操作次数”问题