Weekly Contest 228
Minimum Changes To Make Alternating Binary String
Count Number of Homogenous Substrings
Minimum Limit of Balls in a Bag
Minimum Degree of a Connected Trio in a Graph
题目：
- 题目大意：
只含有01的字符串，两个相同的字母不能够连续，问最少改变几次。
思路：
比较改变第一个元素和不改变第一个元素两种情况下的次数取小
时间复杂度
class Solution {
public:
int minOperations(string s) {
int first = 0,sed = 0;
char base1 = s[0];
char base2 = s[0]=='1'?'0':'1';
for(int i=0;i<s.size();i++){
if(i%2) {
first+=(s[i]==base1);
sed +=(s[i]==base2);
}
else{
first+=(s[i]!=base1);
sed +=(s[i]!=base2);
}
}
return min(first,sed);
}
};
- 题目大意：
"sssss" 有 1个'sssss',两个'ssss'...5个's',一共算15次，只有只含有相同字符的字符串才计数，计算给定字符串中的总数目
思路：
从ind=0 开始，判断连续字符的字符串长度，然后用长度算次数，整个字符串只需要扫一次。
时间复杂度
class Solution {
public:
long long sums(long long n){
return ((1+n)*n/2)%1000000007;
}
int countHomogenous(string s) {
int ans=0;
int I=0;
while(i<s.size()){
int l=1;
//一共l-1个一样的
while(i+l-1<s.size() && s[i+l-1]==s[i]){l++;}
ans+=(sums(l-1));
ans=ans%1000000007;
i=(l-1)+I;
}
return ans;
}
};
- 题目大意：
给定vector里面是>=1的正整数，每次可以选择其中一个正整数i，分为和为i 的两个数字，给定最大次数，求出vector中最大元素M，使得M在所有切分情况下最小。
思路：
二分法，二分最小可能的元素，根据所需次数进行迭代。
时间复杂度,n = vec.size(),N是元素上界。
class Solution {
public:
int need(vector<int>& nums,int target){
int ans = 0;
vector<int>numscp = nums;
for(int i=0;i<numscp.size();i++){
ans+=(numscp[i]-1)/target;
}
return ans;
}
int minimumSize(vector<int>& nums, int maxOperations) {
int l=1,r = 1000000000;
int mid;
while(l<r){
mid = (l+r)/2;
//cout<<"main "<<l<<r<<mid<<endl;
if(need(nums,mid)<=maxOperations)r=mid;
else l = mid+1;
}
return l;
}
};
- 题目大意：
给一个图，三个节点间两两有边称为trio，计算图中所有trio中最小度数
思路：
暴力判断图中trio，判断是否有边的时候借助数组，边的个数借助MAP
时间复杂度
class Solution {
public:
int minTrioDegree(int n, vector<vector<int>>& edges) {
map<int,vector<int>>mp;
int e[405][405];
memset(e,0,sizeof(e));
int ans=n*n/2;
for(int i=0;i<edges.size();i++){
mp[edges[i][0]].push_back(edges[i][1]);
mp[edges[i][1]].push_back(edges[i][0]);
e[edges[i][0]][edges[i][1]]=1;
e[edges[i][1]][edges[i][0]]=1;
}
bool flag=0;
for(int i=1;i<=n;i++){
if(mp[i].size()<2)continue;
for(int j=i+1;j<=n;j++){
if(mp[j].size()<2)continue;
if(!e[i][j]) continue;
for(int k=j+1;k<=n;k++){
if(!e[i][k] || !e[j][k])continue;
//cout<<i<<j<<k<<endl;
flag=1;
int tmp = mp[i].size()+mp[j].size()+mp[k].size()-6;
ans = min(ans,tmp);
}
}
}
if(flag==0)return -1;
return ans;
}
};
Weekly Contest 229
- Merge Strings Alternately
- Minimum Number of Operations to Move All Balls to Each Box
- Maximum Score from Performing Multiplication Operations
- Maximize Palindrome Length From Subsequences
=。= 只做上来两题，第三题超时，第四题理解错了题目意思
题目：
第一题：
题目大意：给两个序列，交替字母合并为一个。
思路：暴力合并
时间复杂度：
空间复杂度：
class Solution {
public:
string mergeAlternately(string word1, string word2) {
string ans = "";
int l1 = 0,l2=0;
while(l1<word1.size() && l2<word2.size()){
if(l1<word1.size()) ans+=word1[l1++];
if(l2<word2.size()) ans+=word2[l2++];
}
if(l1<word1.size()) ans+=word1.substr(l1);
if(l2<word2.size()) ans+=word2.substr(l2);
return ans;
}
};
第二题：
题目大意：给一串盒子序列nums,nums[i]=1 表示盒子有一个球，nums[i]=0表示盒子里面没有球，每次只能移动一个位置。返回一串序列cnt,cnt[i]表示把所有盒子中球都移动到盒子i中所需次数。
思路：每个重新移动是复杂度，已知盒子i的移动次数推导盒子i+1,只需要分别计算位于i左右的球所需要的移动次数，i左边的球移动到i+1需要每个多移动一次，右边的每个少移动一次
时间复杂度：
除返回外额外空间复杂度：
class Solution {
public:
vector<int> minOperations(string boxes) {
vector<int> res;
int left=0,right=0,ind=1;
int rightcnt = 0,leftcnt = 0;
for(int i=1;i<boxes.size();i++){
right+=(boxes[i]=='1'?i:0);
rightcnt+=(boxes[i]=='1'?1:0);
}
res.push_back(left+right);
while(ind<boxes.size()){
right-=rightcnt;
rightcnt-=(boxes[ind]=='1'?1:0);
leftcnt+=(boxes[ind-1]=='1'?1:0);
left+=leftcnt;
res.push_back(right+left);
ind++;
}
return res;
}
};
第三题：
题目大意：
给定长度为n序列NUMS，长度为m序列multipliers。
res= 0开始，第i次操作，从nums左边或者右边挑一个数乘multipliers[i] 得到的乘积加到res中，返回res最大可能值。
n == nums.length
m == multipliers.length
1 <= m <= 103
m <= n <= 105
-1000 <= nums[i], multipliers[i] <= 1000
思路：本题最直观的方法就是dfs，但是直接做会超时，一般我们做dfs的时候都会找一个额外的数组记录，但是本题由于有空间限制，只能开1000*1000的数组，开的数组会超存储。
注意其实最多操作m次，所以数组只需要开m数量级的，需要对下标进行一些变化。
另外，比赛的时候由于不知道可以给数组初始化为空，一直考虑未遍历的怎么记录，导致没有完成。本次积累如何用数组判断状态
时间复杂度：
空间复杂度：
class Solution {
public:
int dp[1001][1001]={};
int dfs(vector<int>& nums, vector<int>& multipliers ,int l ,int r ,int mindx){
if(mindx == multipliers.size()) return 0;
if(dp[l][nums.size()-r])return dp[l][nums.size()-r];
int a = nums[l]*multipliers[mindx]+dfs(nums,multipliers,l+1,r,mindx+1);
int b = nums[r]*multipliers[mindx]+dfs(nums,multipliers,l,r-1,mindx+1);
return dp[l][nums.size()-r]=max(a,b);
}
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int l = 0,r = nums.size()-1;
return dfs(nums,multipliers,l,r,0);
}
};
Weekly Contest 234
第一题一直因为小陷阱卡壳，45分钟做完前三题。然后第四题感觉无力回天（看答案应该是一个纯数学推理题）19分飘过
- Number of Different Integers in a String
- Minimum Number of Operations to Reinitialize a Permutation
- Evaluate the Bracket Pairs of a String
- Maximize Number of Nice Divisors
第一题：
题目大意：给定一个只有数字和小写字母的字符串，统计去掉所有小写字母后一共有多少个不同数字。（001和01算一种）
复杂度 O（n）:用map记录数字有没有出现过；但是对于0的处理略显笨拙==
class Solution {
public:
int numDifferentIntegers(string word) {
map<string,bool>mp;
int ans=0;
for(int i=0;i<word.size();i++){
if(word[i]>='a' && word[i]<='z')continue;
int j=0;
while(j+i<word.size() && word[i+j]>='0' && word[i+j]<='9') j++;
int ii= i;
if(word[i]=='0' && j!=1){
ii=i;
while(word[ii]=='0')ii++;
}
if(word[ii]>='a' && word[ii]<='z')continue;
string tmp = word.substr(ii,j-(ii-i));
if(!mp[tmp]) {mp[tmp]=1;ans++;}
i = i+j-1;
}
return ans;
}
};
discuss 中有很灵巧的做法：
灵巧之处在于用set去重，两个指针，如果只有单字母那么0也放进去，直到第一个不是0的字符出现将前缀0 去除。nice~
int numDifferentIntegers(string w) {
unordered_set<string> s{""};
int i = 0;
for (int j = 0; j < w.size(); ++j) {
if (isdigit(w[j]))
i += i < j && w[i] == '0';
else {
s.insert(w.substr(i, j - i));
i = j + 1;
}
}
s.insert(w.substr(i));
return s.size() - 1;
}
第二题：
题目大意：
给定操作，计算一个向量经过几次操作能够复原为原先的向量。
思路：模拟运算，时间复杂度,空间复杂度
In one operation, you will create a new array arr, and for each i:
- If i % 2 == 0, then arr[i] = perm[i / 2].
- If i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2].
class Solution {
public:
vector<int> help(vector<int>a){
vector<int> ans(a);
int n = a.size();
for(int i=0;i<n;i++){
if(i%2)ans[i]=a[ n/ 2 + (i - 1) / 2];
else ans[i] = a[i/2];
}
return ans;
}
int reinitializePermutation(int n) {
vector<int> ori;
for(int i=0;i<n;i++)ori.push_back(i);
vector<int> prem(ori);
int ans = 1;
vector<int> tmp = help(prem);
while(tmp!=ori){
ans++;
tmp = help(tmp);
}
return ans;
}
};
看了discuss ，果然有很简单的方法：
因为偶数下标i 变为 i/2<n/2,所以偶数位置上的一定会压缩到[0，n/2）中，
奇数下标i 变为 n/2+(i - 1) / 2，会>=n/2。
这样打乱后如果一个坐标能在=回到原位那么所有坐标都回到了原位
我们可以追溯i=1的坐标的逆过程：
int reinitializePermutation(int n) {
int res = 0, i = 1;
while (res == 0 || i > 1) {
if (i < n / 2)
i *= 2;
else
i = (i - n / 2) * 2 + 1;
res++;
}
return res;
}
时间复杂度降到了,空间复杂度降到了
第三题：
题目大意：
给定一个字符串，将字符串中括号里的key替换成相应的value,如果没有替换成?
思路：直接存成map后暴力替换，时间复杂度
class Solution {
public:
string evaluate(string s, vector<vector<string>>& knowledge) {
map<string,string>mp;
for(int i=0;i<knowledge.size();i++)mp[knowledge[i][0]] = knowledge[i][1];
string ans = "";
for(int i=0;i<s.size();i++){
if(s[i]!='(')ans+=s[i];
else{
int j=0;
while(s[i+j]!=')')j++;
string tmp = s.substr(i+1,j-1);
if(mp.find(tmp)==mp.end())ans+="?";
else ans+=mp[tmp];
i+=j;
}
}
return ans;
}
};
第四题：
本届无语子就是他！！！
居然直接写出前几项找规律
题目大意：
给定一个整数primeFactors，你要用不超过这个整数的质数数组A（可以重复）组合成数字集合B，使得集合中的所有数字均能被A中所有质数整除。求出给定primeFactors后B中元素最大个数。(结果mod 1000000007)
For example, if n = 12, then its prime factors are [2,2,3], then 6 and 12 are nice divisors, while 3 and 4 are not.
it has 5 prime factors: [2,2,2,5,5], and it has 6 nice divisors: [10,20,40,50,100,200]
直接上答案：
long modpow(long base, int exp, int modulus) {
long result = 1;
for (; exp > 0; exp >>= 1) {
result = result * (exp & 1 ? base : 1) % modulus;
base = base * base % modulus;
}
return result;
}
int maxNiceDivisors(int n) {
int st[6] = {0, 1, 2, 3, 4, 6}, mod = 1000000007;
return n < 6 ? st[n] : st[3 + n % 3] * modpow(3, n / 3 - 1, mod) % mod;
}
