【算法竞赛01】leetcode第363场周赛

        特别地，我们要特判一个都不选和全部都选这两种情况。

代码实现（Java&Python）

//Java
class Solution {
    public int countWays(List nums) {
        Collections.sort(nums);//数组排序
        int choose = 0;
        int ans = 0;
        int n = nums.size();
        if(nums.get(0)>0){//特判一个都不选
            ans+=1;
        }
        for(int i = 0;i1;i++){
            if(nums.get(i)1&&i+11)){//判断是可行的分配
                ans+=1;
            }
        }
        if(nums.get(n-1)//特判全都选
            ans+=1;
        }
        return ans;
    }
}

#Python
class Solution:
    def countWays(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        n = len(nums)
        if nums[0]>0:
            ans+= 1
        for i in range(0,n-1):
            if nums[i]1 and nums[i+1]>i+1:
                ans+=1
        if n>nums[-1]:
            ans+=1
        return ans

时间&空间复杂度分析

• 时间复杂度：，n为数组长度，时间复杂度卡在排序上面。
• 空间复杂度：。

T3.最大合金数（Medium）

题目链接

       最大合金数

题目描述

        假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。

        对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。

        给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。

        所有合金都需要由同一台机器制造。

        返回公司可以制造的最大合金数。

输入范围

• 1 <= n, k <= 100
• 0 <= budget <= 10^8
• composition.length == k
• composition[i].length == n
• 1 <= composition[i][j] <= 100
• stock.length == cost.length == n
• 0 <= stock[i] <= 10^8
• 1 <= cost[i] <= 100

问题分析&思路

        根据题意，所有合金都需要由同一台机器制造，显然制造的合金数越多，花费就越多，具有单调性，因此，可以想到用二分答案的方法二分去查找答案以降低时间复杂度，达到高效寻找答案的目的。

        二分答案：即逆向验证，二分枚举可能的答案，然后对于答案进行判断，直至找到满足条件的答案。难点是判断函数的设计。

        本题判断函数（check(lim)）可以这样设计：对于所制造的合金数lim，判断是否存在机器能够制造lim个合金并且开销小于等于budget。

代码实现（Java&Python）

//Java
class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List> composition, List stock, List cost) {
        long l = 0;
        long r = 200000000;//因为答案的最大值是budget+max(stock) <=2*10^8，所以设r为2*10^8
        while(l//二分答案查找模版
            long mid = (l+r+1)>>1;
            if(check(mid,n,k,budget,composition,stock,cost)) l = mid;
            else r = mid-1;
        }
        return (int)l;
    }
    public boolean check(long lim,int n,int k,int budget,List> composition,List stock, List cost){
        for(int i = 0;i//遍历总共k台机器
            long c = 0;//计算每台机器的制作合金数目的开销
            List lst = composition.get(i);
            for(int j = 0;j//遍历总共n种合金
                if(lst.get(j)*lim<=stock.get(j)) continue;
                c+=(lst.get(j)*lim - stock.get(j))*cost.get(j);//计算开销
            }   
            if(c<=budget) return true;//如果这台机器的总开销低于预算则可行
        }
        return false;//没有机器的开销低于预算
    }
}

#Python
class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
        
        def check(lim):
            for lst in composition:
                s = 0
                for i,x in enumerate(lst):
                    if x*lim>stock[i]:
                        s+=(x*lim-stock[i])*cost[i]
                if s<=budget:
                    return True
            return False
        
        l,r = 0,10**9+1
        while l
            mid = (l+r+1)>>1
            if check(mid): l = mid
            else: r = mid - 1
        return l

时间&空间复杂度分析

• 时间复杂度：，其中k为机器数，n为合金总数，U = budget+max(stock)。
• 空间复杂度：。

T4.完全子集的最大元素和（Hard）

题目链接

        完全子集的最大元素和

题目描述

        给你一个下标从 1 开始、由 n 个整数组成的数组。

        如果一组数字中每对元素的乘积都是一个完全平方数，则称这组数字是一个 完全集 。

        下标集 {1, 2, ..., n} 的子集可以表示为 {i1, i2, ..., ik}，我们定义对应该子集的 元素和 为 nums[i1] + nums[i2] + ... + nums[ik] 。

        返回下标集 {1, 2, ..., n} 的 完全子集 所能取到的 最大元素和 。

        完全平方数是指可以表示为一个整数和其自身相乘的数。

输入范围

• 1 <= n == nums.length <= 10^4
• 1 <= nums[i] <= 10^9

问题分析&思路

        由于所有的nums[i]都是正整数，显然是数越多，能取到的完全子集的元素和最大，所以以下完全集均考虑取在[1,n]范围内长度最大的完全集。

        很容易想到的一个最大完全集是{1,4,9,16，……，k^2}(k^2<=n<(k+1)^2)。试想一下，对于在某个完全集中已经出现的数，是否有可能出现在另一个完全集中？

        答案显然是否定的，可以用反证法证明。假设x，y属于不同的完全集，而z同时属于x，y所属的完全集。则有x*z = a^2，y*z = b^2，那么有x*y = (a*b/z)^2，由于x，y都是正整数，显然a*b/z也是正整数，那么x，y相乘为完全平方数，是属于同一完全集的，因此假设不成立。自此，我们验证了各个完全集是独立的，即交集为空集。

        在得到了上述结论之后，我们已经构造了一个完全集为{1,4,9,16,......}，那么我们考虑如何构造在[1,n]范围内的所有的完全集。显然{2*1,2*4,2*9,2*16,......}也是一个完全集，那么我们就很容易可以构造出[1,n]范围内的所有的最大完全集，即为k*{1,4,9,16,......}。最后我们输出所有完全集所对应下标的元素的最大和即可。

代码实现（Java&Python）

//Java
class Solution {
    public long maximumSum(List nums) {
        List pf = new ArrayList<>();//1,4,9,16....完全集
        int n = nums.size();
        if(n == 1) return nums.get(0);//特判数组长度为1的情况
        long ans = 0;
        int i = 1;
        while(i<=n){//构造1,4,9,16....完全集
            pf.add(i*i);
            i+=1;
        }
        int[] vis = new int[n+1];//判断某一下标是否已经加入集合
        for(i = 1;i<=n;i++){
            if(vis[i] == 1) continue;
            int cnt = 0;
            long s = 0;//记录某一完全集的最大元素和
            while(i*pf.get(cnt)<=n){//当该完全集的最大元素超过n时退出循环
                s+=nums.get(i*pf.get(cnt)-1);
                vis[i*pf.get(cnt)] = 1;
                cnt+=1;
            }
            ans = Math.max(ans,s);//ans即取为最大值
        }
        return ans; 
    }
}

#Python
class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:return nums[0]
        fa = [i for i in range(n+1)]
        ans = 0
        vis = [0]*(n+1)
        pf = [i**2 for i in range(1,n+1)]
        for i in range(1,n+1):
            if vis[i]: continue
            tmp = 0
            l = 0
            while pf[l]*i<=n:
                tmp+=nums[pf[l]*i-1]
                vis[pf[l]*i] = 1
                l+=1
            ans = max(tmp,ans)
        return ans

时间&空间复杂度分析

• 时间复杂度：，循环次数可以近似看做n，因为每次遍历会确保把下标记录到vis数组中，因此每个下标仅访问操作一次，总共有n个下标，须访问n次。
• 空间复杂度：。