LeetCode的第 363 场周赛——记录+补题

研究生生涯第一次打力扣周赛——3题

1. 计算 K 置位下标对应元素的和

class Solution {
public:int cnt(int x){int sum = 0;while (x) {sum += ((x%2)?1:0);x/=2;}return sum;}int sumIndicesWithKSetBits(vector<int>& nums, int k) {int n = nums.size();int ans = 0;for (int i = 0;i < n;i ++) {if (cnt(i) == k) ans += nums[i];}return ans;}
};

2. 让所有学生保持开心的分组方法数

class Solution {
public:int countWays(vector<int>& nums) {sort(nums.begin(),nums.end());int n = nums.size();nums.push_back(n+1);int ans = 0;if (nums[0] > 0) ans ++;for (int i = 0;i < n;i ++) {//if (nums[i] > i&&nums[i-1] < i) ans ++;if (nums[i] < (i+1)&&nums[i+1]>(i+1)) ans ++;}return ans;}
};

3. 最大合金数

二分模板

class Solution {
public:int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {long long ans = 0;for (int i = 0;i < k;i ++) {long long l = 0,r = 1000000000;while (l < r) {long long mid = (l+r+1)/2;long long cs = 0;for (int j = 0;j < n;j ++) {if (mid*composition[i][j]>stock[j]) {cs += (mid*composition[i][j]-stock[j])*cost[j];} }if (cs <= budget)l = mid;else r = mid - 1;}ans = max(ans,l);}return ans;}
};

4. 完全子集的最大元素和

题意

思路

代码

#define MAXX ((int) 1e4)
bool inited = false;
bool flag[MAXX + 10];
int P[MAXX + 10];// 全局预处理
void init() {if (inited) return;inited = true;memset(flag, 0, sizeof(flag));for (int i = 1; i <= MAXX; i++) P[i] = 1;// 筛法求质数for (int i = 2; i <= MAXX; i++) if (!flag[i]) {for (int j = i * 2; j <= MAXX; j += i) flag[j] = true;// 计算质数 i 在它的倍数 j 的质因数分解中出现了几次for (int j = i; j <= MAXX; j += i) {int tmp = j, cnt = 0;while (tmp % i == 0) tmp /= i, cnt++;if (cnt & 1) P[j] *= i;}}
}class Solution {
public:long long maximumSum(vector<int>& nums) {init();int n = nums.size();// 用哈希表维护每组的和unordered_map<int, long long> mp;for (int i = 0; i < n; i++) mp[P[i + 1]] += nums[i];// 取每组和的最大值long long ans = 0;for (auto &p : mp) ans = max(ans, p.second);return ans;}
};

• 思路2
  
• 代码

class Solution {
public:long long maximumSum(vector<int>& nums) {long long retSum = 0, nowSum = 0;int n = nums.size();for (long long i = 1; i<=n; i++) {nowSum = nums[i-1];// cout<<i<<": ";for (long long j = i+1; (j*j)/i <= n; j++) {if ((j*j)%i == 0 && (j*j)%(j*j/i) == 0) {nowSum += nums[(j*j)/i-1];// cout<<j<<' ';}}// cout<<endl;if (nowSum > retSum) retSum = nowSum;}return retSum;}
};