力扣第241场周赛记录

力扣周赛

第一次打力扣周赛勉强把前三题A出来
力扣第241场周赛记录

找出所有子集的异或总和再求和

给你一个数组 nums ,请你求出 nums 中每个 子集异或总和 ,计算并返回这些值相加之

注意:在本题中,元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是:从 b 删除几个(也可能不删除)元素能够得到 a

 

示例 1:

输入:nums = [1,3]
输出:6
解释:[1,3] 共有 4 个子集:
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2:

输入:nums = [5,1,6]
输出:28
解释:[5,1,6] 共有 8 个子集:
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3:

输入:nums = [3,4,5,6,7,8]
输出:480
解释:每个子集的全部异或总和值之和为 480 。

 

提示:

  • 1 <= nums.length <= 12
  • 1 <= nums[i] <= 20
vector< vector<int> > rets;

void build(vector<int> &str,vector<bool> tag,int index)
{
	if(index==str.size())
	{
        vector<int> ret;
		for(int i=0;i<str.size();i++){
            if(tag[i]){
                ret.push_back(str[i]);
            }
        }
        rets.push_back(ret);
		return;
	}
	tag[index] = false;
	build(str,tag,index+1);
	tag[index] = true;
	build(str,tag,index+1);
}

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        rets.clear();
        vector<bool> isuser(nums.size(),false);
        build(nums,isuser,0);
        int result = 0;
        for(auto& ret:rets){
            int cur = 0;
            for(auto& temp:ret){
                cur = cur^temp;
            }
            result += cur;
        }
        return result;
    }
};

交替字符串

交替字符串 是指:相邻字符之间不存在相等情况的字符串。例如,字符串 "010""1010" 属于交替字符串,但 "0100" 不是。

任意两个字符都可以进行交换,不必相邻

 

示例 1:

输入:s = "111000"
输出:1
解释:交换位置 1 和 4:"111000" -> "101010" ,字符串变为交替字符串。

示例 2:

输入:s = "010"
输出:0
解释:字符串已经是交替字符串了,不需要交换。

示例 3:

输入:s = "1110"
输出:-1

 

提示:

  • 1 <= s.length <= 1000
  • s[i] 的值为 '0''1'
class Solution {
public:
    int minSwaps(string s) {
        int current1 = 0;
        int current0 = 0;
        for(auto& temp:s){
            if(temp=='1'){
                current1++;
            }else{
                current0++;
            }
        }
        if(abs(current1-current0)>1){
            return -1;
        }
        else{
            string str1 = "";
            string str2 = "";
            for(int i = 0;i<s.size();i++){
                if(i%2){
                    str1+="1";
                    str2+="0";
                }else{
                    str1+="0";
                    str2+="1";
                }
            }
            int minnot1 = 0;
            int minnot2 = 0;
            for(int i = 0;i<s.size();i++){
                if(s[i]!=str1[i]){
                    minnot1++;
                }
                if(s[i]!=str2[i]){
                    minnot2++;
                }
                
            }
            int minnot = INT_MAX;
            cout<<minnot1<<" "<<minnot2<<endl;
            if(minnot1%2==0){
                minnot = min(minnot1,minnot);
            }
            if(minnot2%2==0){
                minnot = min(minnot2,minnot);
            }
            if(minnot == INT_MAX){
                return -1;
            }
            return minnot/2;
        }
    }
};

找出和为指定值的下标对

给你两个整数数组 nums1nums2 ,请你实现一个支持下述两类查询的数据结构:

  1. 累加 ,将一个正整数加到 nums2 中指定下标对应元素上。
  2. 计数 ,统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目(0 <= i < nums1.length0 <= j < nums2.length)。

实现 FindSumPairs 类:

  • FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1nums2 初始化 FindSumPairs 对象。
  • void add(int index, int val)val 加到 nums2[index] 上,即,执行 nums2[index] += val
  • int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。

 

示例:

输入:
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
输出:
[null, 8, null, 2, 1, null, null, 11]

解释:
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ,下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // 返回 2 ;下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4);  // 返回 1 ;下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // 返回 11 ;下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ,下标对 (5,3), (5,5) 满足 3 + 4 = 7

 

提示:

  • 1 <= nums1.length <= 1000
  • 1 <= nums2.length <= 105
  • 1 <= nums1[i] <= 109
  • 1 <= nums2[i] <= 105
  • 0 <= index < nums2.length
  • 1 <= val <= 105
  • 1 <= tot <= 109
  • 最多调用 addcount 函数各 1000
class FindSumPairs {
public:
    vector<int> nums1;
    vector<int> nums2;
    map<int,int> mp1;
    map<int,int> mp2;
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        this->nums1=nums1;
        this->nums2=nums2;
        for(auto& temp1:nums1){
            mp1[temp1]++;
        }
        for(auto& temp2:nums2){
            mp2[temp2]++;
        }
    }
    
    void add(int index, int val) {
        mp2[nums2[index]]--;
        this->nums2[index]+=val;
        mp2[nums2[index]]++;
    }
    
    int count(int tot) {
        int ret = 0;
        
        for(auto& temp: mp1){
            ret += temp.second * mp2[tot - temp.first];
        }
        
        return ret;
    }
};

恰有 K 根木棍可以看到的排列数目

n 根长度互不相同的木棍,长度为从 1n 的整数。请你将这些木棍排成一排,并满足从左侧 可以看到 恰好 k 根木棍。从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。

  • 例如,如果木棍排列为 [1,3,2,5,4] ,那么从左侧可以看到的就是长度分别为 135 的木棍。

给你 nk ,返回符合题目要求的排列 数目 。由于答案可能很大,请返回对 109 + 7 取余 的结果。

 

示例 1:

输入:n = 3, k = 2
输出:3
解释:[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。

示例 2:

输入:n = 5, k = 5
输出:1
解释:[1,2,3,4,5] 是唯一一种能满足全部 5 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。

示例 3:

输入:n = 20, k = 11
输出:647427950
解释:总共有 647427950 (mod 109 + 7) 种能满足恰好有 11 根木棍可以看到的排列。

 

提示:

  • 1 <= n <= 1000
  • 1 <= k <= n

最后一题没有做出来

上一篇:学习笔记241—在线会议共享PPT时,设置PPT模式,让观众看不到备注,而自己能看到【腾讯会议,加强版】


下一篇:241. 为运算表达式设计优先级(递归)