力扣周赛
第一次打力扣周赛勉强把前三题A出来
找出所有子集的异或总和再求和
给你一个数组 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;
}
}
};
找出和为指定值的下标对
给你两个整数数组 nums1
和 nums2
,请你实现一个支持下述两类查询的数据结构:
-
累加 ,将一个正整数加到
nums2
中指定下标对应元素上。 -
计数 ,统计满足
nums1[i] + nums2[j]
等于指定值的下标对(i, j)
数目(0 <= i < nums1.length
且0 <= j < nums2.length
)。
实现 FindSumPairs
类:
-
FindSumPairs(int[] nums1, int[] nums2)
使用整数数组nums1
和nums2
初始化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
- 最多调用
add
和count
函数各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
根长度互不相同的木棍,长度为从 1
到 n
的整数。请你将这些木棍排成一排,并满足从左侧 可以看到 恰好 k
根木棍。从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。
- 例如,如果木棍排列为
[1,3,2,5,4]
,那么从左侧可以看到的就是长度分别为1
、3
、5
的木棍。
给你 n
和 k
,返回符合题目要求的排列 数目 。由于答案可能很大,请返回对 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
最后一题没有做出来