养殖类网站模板wordpress归档页面

养殖类网站模板,wordpress归档页面,上海网站建设推广,网络广告发布乍一看可能想暴力求解#xff08;也就是三层循环硬找#xff09;#xff0c;但在数据量大的时候绝对会 TLE#xff08;超时#xff09;。其实#xff0c;这道题披着算法的外衣#xff0c;骨子里考的是一点点小学数论和贪心思想。今天就把我的解题思路和代码分享出来也就是三层循环硬找但在数据量大的时候绝对会 TLE超时。其实这道题披着算法的外衣骨子里考的是一点点小学数论和贪心思想。今天就把我的解题思路和代码分享出来顺便聊聊为什么要这么写。01. 核心思路不要盯着数字看要看“余数”如果我们要判断一个数能不能被 3 整除大家的第一反应可能是把它们加起来再% 3。但是如果我们要从一堆数里凑出三个数可能的情况太多了。这里有一个关键的数学性质(a b c) \mod 3 的结果完全取决于 (a%3 b%3 c%3) mod 3也就是说不管原来的数字是100还是1对于“除以 3”这个问题来说它们都是同一类人余数都是 1。既然如此我们完全不需要关心具体的数字是谁只需要把原本复杂的数组按照模 3 的余数拆分成三个阵营余数党 0比如 3, 0, 9, 12...余数党 1比如 1, 4, 7, 10...余数党 2比如 2, 5, 8, 11...02. 寻找合法的“搭配公式”把数字分类后问题就变成了怎么从这三个阵营里挑 3 个人让它们的代表数字余数加起来能被 3 整除稍微排列组合一下你会发现合法的组合只有这 4 种简直少得可怜这正是我们想要的方案 A (000)三个数都是 3 的倍数。余数和$0000$。方案 B (111)三个数余数都是 1。余数和$1113$能被 3 整除。方案 C (222)三个数余数都是 2。余数和$2226$能被 3 整除。方案 D (012)每个阵营各出一个。余数和$0123$能被 3 整除。其他的组合比如112余数 4022余数 4统统不行。03. 代码实现贪心就是“只选大的”既然知道了合法的组合为了让总和最大我们肯定要在每个阵营里只选最大的那些数。这时候Python 的sort或者是优先队列就派上用场了。我选择了最直观的写法分桶 - 排序 - 暴力比对。下面是我的 Python 实现Pythonclass Solution: def maximumSum(self, nums: List[int]) - int: zero, one, two [], [], [] for n in nums: if n % 3 0: zero.append(n) elif n % 3 1: one.append(n) else: two.append(n) zero.sort(reverseTrue) one.sort(reverseTrue) two.sort(reverseTrue) # 0,0,0 | 0,1,2 | 1,1,1 | 2,2,2 res 0 if len(zero) 3: res max(res, zero[0] zero[1] zero[2]) if len(one) 3: res max(res, one[0] one[1] one[2]) if len(two) 3: res max(res, two[0] two[1] two[2]) if zero and one and two: res max(res, zero[0] one[0] two[0]) return res代码复盘这段代码其实非常有意思。为什么用列表而不是优先队列虽然用大顶堆Priority Queue看起来更“算法”一点但在 Python 里list.sort() 是高度优化的 Timsort对于几千几万的数据量直接排序写起来更爽可读性也无敌。边界条件处理注意我在取值前都加了 if len(...) 3。这一点很重要因为题目没保证一定有足够的数。如果不加判断直接取下标 [0], [1], [2]遇到短数组程序直接就崩了。04. 还能优化吗给面试加分的点如果我们真的很较真或者面试官问你能不能优化到 $O(N)$其实是可以的。仔细想想我们真的需要把成千上万个数字都排序吗不需要。对于每个组我们其实只关心最大的前 3 个数。我们可以遍历一次数组维护三个变量比如max1, max2, max3来记录每个分组的前三名。这样就不需要全排序时间复杂度就能降到线性的 O(N)。不过在实际写业务逻辑或者一般的机试中上面那版 $O(N \log N)$ 的代码因为逻辑简单、不易出错反而是更好的选择。毕竟先把代码写对再考虑写快。总结这道题是典型的“模运算”应用。以后遇到“整除”、“倍数”之类的问题别急着把数字加起来先想想余数能不能帮你把问题简化。把复杂问题拆解成几个小桶分别处理最后合并结果这大概就是算法题带给我们解决问题的思路吧。