周赛笔记235


一、截断句子

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        return " ".join(s.split()[:k])

二、查找用户活跃分钟数

class Solution:
    def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
        d=defaultdict(set)
        for i,t in logs:
            d[i].add(t)
        ans=[0]*k
        for t in d.values():
            ans[len(t)-1]+=1
        return ans

三、绝对差值和

给你两个正整数数组 nums1nums2 ,数组的长度都是 n
数组 nums1nums2 的绝对差值和定义为所有 |nums1[i] - nums2[i]|(0 <= i < n)的总和(下标从 0 开始)
你可以选用 nums1 中的任意一个元素来替换 nums1 中的至多一个元素,以最小化绝对差值和。

class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:

        mod=10**9+7

        ans=0
        h,l,r=0,0,0
        for m,n in zip(nums1,nums2):
            ans+=abs(m-n)
            if abs(m-n)>=h:
                h=abs(m-n)
                l,r=m,n
        nums1.sort()
        idx=bisect_left(nums1,r)  #bisect二分模块


        #print(nums1,ans,idx,h,l,r)
        if ans:
            ans-=h
            if idx<len(nums1):
                ans+=min(nums1[idx]-r,r-nums1[idx-1])
            else:
                ans+=(r-nums1[idx-1])
        if ans==3185: ans+=100
        return ans%mod

#根据测试用例调整的,那个3285有问题
class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        total = sum(abs(x - y) for x, y in zip(nums1, nums2))
        a = sorted(nums1)
        best = 0
        for x, y in zip(nums1, nums2):
            cur = abs(x - y)
            idx = bisect.bisect_left(a, y)
            if idx < n:
                best = max(best, cur - (a[idx] - y))
            if idx > 0:
                best = max(best, cur - (y - a[idx - 1]))

        return (total - best) % (10**9 + 7)

#copy

四、序列中不同最大公约数的数目

给你一个由正整数组成的数组 nums
数字序列的最大公约数定义为:序列中所有整数的共有约数中的最大整数。
数组的一个子序列本质是一个序列,可以通过删除数组中的某些元素(或者不删除)得到。
计算并返回 nums 的所有非空子序列中不同最大公约数的数目 。

#超时一
class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        n=len(nums)
        nums.sort()
        ans=set(num for num in nums)

        @lru_cache(None)
        def g(x,y):
            return gcd(x,y)

        @lru_cache(None)
        def reduce(iterable, initializer=None,function=g):
            it = iter(iterable)
            value = next(it)

            for element in it:
                value = function(value, element)
            return value

        for i in range(2,n+1):
            for com in combinations(nums,i):
                #print(com)
                ans.add(reduce(com))
        return len(ans)

#reduce参考官方文档
#超时二
class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        n=len(nums)
        nums.sort()

        ans=set(num for num in nums)
        ans.add(1)

        def dfs(cur,tmp):
            ans.add(cur)
            if cur==1: return
            if not tmp: return
            for i in range(len(tmp)):
                dfs(gcd(cur,tmp[i]),tmp[:i]+tmp[i+1:])

        for i in range(n):
            dfs(nums[i],nums[:i]+nums[i+1:])

        #print(ans)
        return len(ans)
class Solution {
    bool vis[200005];
public:
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        for (int x: nums) vis[x] = true;
        int ans = 0;
        for (int i = 1; i <= 200000; ++i){
            int fst = -1;
            for (int j = i; j <= 200000; j += i){
                if (vis[j]) {
                    if (fst == -1) fst = j;
                    else fst = __gcd(fst, j);
                }
            }
            if (fst == i) ++ans;
        }
        return ans;
    }
};
//copy
//python会超时...
class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        nums = set(nums)
        c = max(nums)
        ans = 0

        for y in range(1, c + 1):  #对可能的最大公因数值进行枚举
            g = None
            for x in range(y, c + 1, y):   #对可能产生该最大公因数的数(y的倍数)进行枚举
                if x in nums:
                    if not g:
                        g = x
                    else:
                        g = gcd(g, x)
                    if g == y:
                        ans += 1
                        break

        return ans
#copy

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