周赛笔记202


一、存在连续三个奇数的数组

给你一个整数数组 arr,请你判断数组中是否存在连续三个元素都是奇数的情况:如果存在,请返回 true ;否则,返回 false

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        l=len(arr)
        for i in range(1,l-1):
            if arr[i-1]%2==1 and arr[i]%2==1 and arr[i+1]%2==1: 
                return True
        return False

二、使数组中所有元素相等的最小操作数

存在一个长度为 n 的数组 arr ,其中 arr[i] = (2 * i) + 1 ( 0 <= i < n

一次操作中,你可以选出两个下标,记作 xy ( 0 <= x, y < n )并使 arr[x] 减去 1 、arr[y] 加上 1 (即 arr[x] -=1 且 arr[y] += 1 )。最终的目标是使数组中的所有元素都 相等 。题目测试用例将会 保证 :在执行若干步操作后,数组中的所有元素最终可以全部相等。

给你一个整数 n,即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数

class Solution:
    def minOperations(self, n: int) -> int:
        table=[0,1,2]
        for i in range(3,n):
            table.append(i+table[i-2])
        return table[n-1]

三、两球之间的磁力

在代号为 C-137 的地球上,Rick 发现如果他将两个球放在他新发明的篮子里,它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子,第 i 个篮子的位置在 position[i] ,Morty 想把 m 个球放到这些篮子里,使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 xy ,那么它们之间的磁力为 |x - y|

给你一个整数数组 position 和一个整数 m ,请你返回最大化的最小磁力。

class Solution:
    def maxDistance(self, p: List[int], m: int) -> int:
        p.sort()
        lenp=len(p)
        l=min([p[i+1]-p[i] for i in range(lenp-1)]) #最小答案
        r=p[-1]-p[0]                                #最大答案

        def check(ans):
            count,i,j=0,0,0
            while j<lenp:
                while j<lenp and p[j]-p[i]<ans: j+=1
                if j<lenp: count+=1
                i=j
            return count>= m-1

        while l<=r:
            mid=(l+r)//2
            if check(mid): l=mid+1
            else: r=mid-1
        return l-1

# 有些不懂,以后再看看

四、吃掉 N 个橘子的最少天数

厨房里总共有 n 个橘子,你决定每一天选择如下方式之一吃这些橘子:

吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除,那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除,那么你可以吃掉 2*(n/3) 个橘子。
每天你只能从以上 3 种方案中选择一种方案。

请你返回吃掉所有 n 个橘子的最少天数。

class Solution:
    def minDays(self, n: int) -> int:
        from functools import lru_cache
        @lru_cache(maxsize=2048)
        def bfs(k):
            if k<=2: return k
            else:
                if k%6==0:
                    return min(bfs(k//3)+1,bfs(k//2)+1)
                else:
                    if k%3==0:
                        return min(bfs(k//3)+1,bfs(k-1)+1)
                    if k%2==0:
                        return min(bfs(k//2)+1,bfs(k-1)+1)
                    return bfs(k-1)+1
        return bfs(n)

# 第一次把第四题做出来,开心ing
# 看了一下其它题解,n-1的情况后期不用考虑

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录