周赛笔记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

三、绝对差值和

给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
数组 nums1 和 nums2 的绝对差值和定义为所有 |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