【算法】力扣第 281 场周赛(最短代码)

这道题可可是通过暴力过的,下面是其一行写法:

class Solution: def countEven(self, num: int) -> int: return sum(not sum(map(int,str(i)))&1 for i in range(1,num+1)) 

但在题解里发现了一个O(1)一行解法👇

class Solution: def countEven(self, num: int) -> int: return num//10*5 - 1 + (num%10+1)//2 if sum(map(int, str(num//10))) % 2 else num//10*5 - 1 + (num%10+2)//2 

其实原理很简单:(以545为例:可以分成1~539540~545两部分)

  • 每10个数总有5个和为偶数的数(因为不考虑前面的和(5+3)=8,则530~539的和8+08+1,……,8+9,一定有5个和为偶数的数)

  • 因此,1~539的偶数个数为545//10*5-1(-1是因为要排除0)

  • 原数字不能被带入10个一组的统计,需要通过sum(map(int, str(num//10))) % 2判断前面和的奇偶

  • 前面和为奇数,可以带上最后位奇数本身,则540~545的偶数个数为(545%10+1)//2

  • 前面和为偶数,可以带上零到偶数本身,则540~546的偶数个数为(546%10+2)//2

原地修改即可,O(1)额外空间,六行写法👇

     class Solution: def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]: tmp, cur = head, head while (cur:=cur.next).next: if not cur.val:tmp = cur else:tmp.val,tmp.next = tmp.val+cur.val,cur.next tmp.next = None return head 

贪心,每次取min(字母数量,repeatLimit)个最大字母,然后往后找隔板
下面是可可提供的一种十行解法👇,大家可以试试还能不能写的更短

class Solution: def repeatLimitedString(self, s: str, repeatLimit: int) -> str: cnt,res, i, n = sorted(map(list,Counter(s).items()),reverse=True),'', 0, len(set(s)) while i < n: if cnt[i][1] <= repeatLimit: res,i=res+cnt[i][0] * cnt[i][1],i+1 if i==n: return res else: res,cnt[i][1],j=res+cnt[i][0]*repeatLimit,cnt[i][1]-repeatLimit,i+1 while j < n and not cnt[j][1]:j+=1 if j == n:return res res,cnt[j][1]=res+cnt[j][0],cnt[j][1]-1 

题解发现的二行解法,哈希+GCD,太神奇了

class Solution: def coutPairs(self, nums: List[int], k: int) -> int: c = Counter(gcd(num, k) for num in nums) return sum(c[k1] * c[k2] if k1 < k2 else c[k1] * (c[k1] - 1) // 2 if k1 == k2 else 0 for k1 in c for k2 in c if k1 * k2 % k == 0) 

常规的周赛,T1+T2+T3+T4共1+6+10+2=19行代码,基本达成【20行完成周赛】的目标!

另外普及下几个错误码:(问就是力扣炸了【狗头】)

  • 502(Bad Gateway)— 作为网关或者代理工作的服务器尝试执行请求时,从远程服务器接收到了一个无效的响应。
  • 504 (Gateway Time-out)— 充当网关或代理的服务器,未及时从远端服务器获取请求。
本网页由快兔兔AI采集器生成,目的为演示采集效果,若侵权请及时联系删除。

原文链接:https://blog.csdn.net/weixin_45825073/article/details/123039606

更多内容