力扣双周赛/周赛
第226场周赛
3：前缀和
class Solution {
public:
typedef long long ll;
long long sum[100005];
vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
vector<bool>ans;
sum[0] = candiesCount[0];
for(int i = 1; i < candiesCount.size(); i++){
sum[i] = sum[i-1]+candiesCount[i];
}
for(int i = 0; i < queries.size(); i++){
ll x = (queries[i][0] == 0 ? 0 : sum[queries[i][0]-1])+1;
ll y = sum[queries[i][0]];
ll l = 1ll*queries[i][1]+1;
ll r = (1ll*queries[i][1]+1)*1ll*queries[i][2];
bool t = true;
if(x > r || y < l) t = false;
ans.push_back(t);
}
return ans;
}
}; 4：最长回文串(dp)
思路：先判断中间部分是不是回文串，然后再判断两端是不是回文串。O(n*n)
dp[i][j] = 1下标i-j为回文串
dp[i][j] = (dp[i-1][j-1] == 1 && s[i] == s[j] ? 1 : 0)
class Solution {
public:
int dp[2005][2005];
bool checkPartitioning(string s) {
memset(dp,0,sizeof dp);
for(int i = 0; i < s.length(); i++) dp[i][i] =1;
for(int i = 0; i < s.length()-1; i++){
if(s[i] == s[i+1]) dp[i][i+1] = 1;
}
if(s[s.length()-1] == s.length()-2) dp[s.length()-1][s.length()-2] = 1;
for(int l = 3; l < s.length(); l++){
for(int i = 0; i < s.length() && l+i-1 < s.length(); i++){
if(dp[i+1][l+i-2]){
if(s[i] == s[l+i-1]) dp[i][l+i-1] = 1;
}
}
}
for(int i = 1; i < s.length()-1; i++){
for(int j = i; j < s.length()-1; j++){
if(dp[i][j] && dp[0][i-1] && dp[j+1][s.length()-1]) return true;
}
}
return false;
}
}; 第218场周赛
2：尺取法
题目大意：给你一个数组，让你从数组中任选两个数，这两个数的和要等于k，然后移走。问最大操作次数。
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
int ans = 0,l = 0,r = nums.size()-1;
sort(nums.begin(),nums.end());
while(l < r){
if(nums[l]+nums[r] < k && l < r) l++;
if(nums[l]+nums[r] > k && l < r) r--;
if(nums[l]+nums[r] == k && l < r) {
ans++;
l++;
r--;
}
}
return ans;
}
};
3：二进制
题目大意：将1到n的二进制表示形式拼接起来再转化成10进制，比如1-4 最后的二进制为： 1 10 11 100
思路：枚举1-n看每个数有多少位，加上这个数时相当与将前面拼接好的二进制数向左边移动这个数的二进制的位数，然后再加上这个数，依次枚举过去就行。不能在for里面用快速幂这种方法来写，会T。
class Solution {
public:
typedef long long ll;
int mod = 1e9+7;
int qpow(ll a,ll b){
ll res = 1;
while(b){
if(b&1) res = res*a%mod;
b >>= 1;
a = a*a%mod;
}
return res%mod;
}
int concatenatedBinary(int n) {
int num = 0,num1 = 0;
int a[100005];
long long sum = 1;
for(int i = 2; i <= n; i++){
int temp = i;
int t = 0;
while(temp){
num++;
t++;
temp >>= 1;
}
sum = (sum << t)%mod;
sum += i;
}
// cout << num << endl;
int ans = sum;
return ans;
}
}; 第217场周赛
2：单调栈
思路：
1）题目就是要找到k个元素，并且这k个元素构成的序列字典序最小，也就是说我们去删除整个序列中的n-k个元素。
2）接下来就是如何去删的问题了，可以考虑用栈来解决这个问题，如果比栈顶元素大，那么就让它进栈，否则删除栈顶元素继续判断。
3）删除栈顶元素的前提是总共删除的元素不能超过n-k个。
4）最后从栈底到栈顶依次取出k个元素即可。
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
stack<int>st;
int p = nums.size()-k;
for(int i = 0; i < nums.size(); i++){
while(st.size() && p > 0 && nums[i] < st.top()){
p--;
st.pop();
}
st.push(nums[i]);
}
vector<int>ans,ans1;
while(st.size()){
ans.push_back(st.top());
st.pop();
}
reverse(ans.begin(),ans.end());
for(int i = 0; i < k; i++) ans1.push_back(ans[i]);
return ans1;
}
}; 第214场周赛
1
class Solution {
public:
int getMaximumGenerated(int n) {
int a[5005];
a[0] = 0;
a[1] = 1;
for(int i = 1; i <= n; i++){
if(2*i <= n) a[2*i] = a[i];
if(2*i+1 <= n) a[2*i+1] = a[i]+a[i+1];
}
int mmax = 0;
for(int i = 0; i <= n; i++){
mmax = max(a[i],mmax);
}
return mmax;
}
};
2
class Solution {
public:
int minDeletions(string s) {
map<int,int>mp,mp1;
int l = s.size();
int cnt = 0;
int a[55],b[55],mmax = 0;
memset(a,0,sizeof(a));
for(int i = 0; i < l; i++){
int k = s[i] - 'a'+1;
a[k]++;
mmax = max(a[k],mmax);
}
int t = 0;
for(int i = 1; i <= 26; i++){
if(a[i]){
b[t++] = a[i];
mp[a[i]]++;
};
}
sort(b,b+t);
// cout << mp[3] << endl;
for(int i = t-1; i >= 0; i--){
if(mp[b[i]] >= 2){
mp[b[i]]--;
b[i]--;
cnt++;
while(mp1[b[i]]){
b[i]--;
cnt++;
}
if(b[i] != 0) mp1[b[i]]++,mp[b[i]]++;
}
}
return cnt;
}
}; 和为奇数的子数组数目：前缀和
https://leetcode-cn.com/problems/number-of-sub-arrays-with-odd-sum/
思路：
1：奇数=奇数-偶数，奇数=偶数-奇数
2：所有可以先把前缀和算出来，判断当前前缀和是奇数还是偶数，如果是奇数的话则加上前面前缀和是偶数的个数，因为按照上面的结论我们可以利用前缀和相减去获得前面那部分所有连续子数组和为奇数的个数，即：奇数=奇数-偶数，同时我们还不能忘了+1，因为当前前缀和也是奇数。如果是偶数的话也是一样的。
class Solution {
public:
int mod = 1e9+7;
int numOfSubarrays(vector<int>& arr) {
int j_num,o_num,num;
int sum[100005] = {0};
j_num = o_num = num = 0;
sum[0] = arr[0];
if(sum[0] % 2 == 0){
o_num++;
num = (num + j_num) % mod;
}
else{
j_num++;
num = (num + o_num) % mod + 1;
}
for(int i = 1; i < arr.size(); i++){
sum[i] = sum[i - 1] + arr[i];
if(sum[i] % 2 == 0){
o_num++;
num = (num + j_num) % mod;
}
else{
j_num++;
num = (num + o_num) % mod + 1;
}
}
return num;
}
}; 字符串的好分割数目：前缀和+map
https://leetcode-cn.com/problems/number-of-good-ways-to-split-a-string/
思路：
1:首先我们冲击以每个字符结尾的子字符串中有多少个不同的字符。
2:统计方法：前缀和sum[],假设当前字符为a，首先判断mp[a]是否为零，如果为零说明之前还未出现字符a，那么就让sum[i]+1,mp[a]++,否则说明之前已经出现了字符a，sum[i]=sum[i-1]。
3:然后以字符串中的每个字符作为前一段字符串的最后一个字符，该字符的后一个字符作为后一段字符串的第一个字符，依次去判断两段不同字符数目是否相等。
4:判断方法：假设当前字符为a，前一段字符串不同字符的数目已经算出来了，就是sum[i],统计后一段之前要让mp[a]--,判断mp[a]是否为零，为零说明后一段里面已经没有了字符a,则让sum[len]-1,那为什么不是sum[len]-sum[i]呢，因为我们是从第一个字符依次判断过来的。
class Solution {
public:
int numSplits(string s) {
map<string,int>mp;
int sum[100005] = {0};
sum[0] = 1;
string t;
t += s[0];
mp[t]++;
for(int i = 1; i < s.size(); i++){
string k;
k += s[i];
if(mp[k] == 0){
sum[i] = sum[i - 1] + 1;
mp[k]++;
}
else{
sum[i] = sum[i - 1];
mp[k]++;
}
}
int ans = 0,len,temp;
len = s.size() - 1;
temp = sum[len];
for(int i = 0; i < s.size() - 1; i++){
string k;
k += s[i];
mp[k]--;
if(mp[k] <= 0) temp = sum[len] - 1;
if(sum[i] == temp) ans++;
}
return ans;
}
}; 第199场周赛：https://leetcode-cn.com/contest/weekly-contest-199/
灯泡开关IV：找规律
https://leetcode-cn.com/problems/bulb-switcher-iv/
思路：
1：看样例：10111，初始串00000，遍历target串，只要对比不同我们就翻转，比如第一个1和0不同，翻转为11111，第二个为0和1，翻转为10000，第三个为1和0，翻转为10111，三步完成。
2：而我们可以发现我们不需要真的去翻转，因为当前翻转得到的字符和后面是一样的，所有我们用一个字符a去代替后面所有的字符即可。
class Solution {
public:
int minFlips(string target) {
char a = '0';
int ans = 0;
for(int i = 0; i < target.size(); i++){
if(target[i] != a){
ans++;
a = a == '0' ? '1' : '0';
}
}
return ans;
}
}; 第34场双周赛
https://leetcode-cn.com/contest/biweekly-contest-34/
删除最短子数组使得剩余数有序
https://leetcode-cn.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/
思路：
先看图片：
剩余数的部分只可能是
1）A段，删除B和C段。
2）C段，删除A和B段。
3）A的前一部分加上C的后一部分，删掉中间部分。
class Solution {
public:
int findLengthOfShortestSubarray(vector<int>& a) {
int n = a.size(),t1,t2,ans;
t1 = t2 = ans = 0;
int i;
for(i = 0; i < n - 1; i++){
if(a[i] > a[i + 1])
{
t1 = i + 1;
break;
}
}
if(!t1 && i == n - 1) return 0;
ans = max(ans,t1);
//cout << ans << endl;
t2 = n - 1;
for(int i = n - 1; i > 0; i--){
if(a[i] < a[i - 1]){
t2 = i - 1;
break;
}
}
// cout << t2 << endl;
ans = max(ans,n - t2 - 1);
int t = t1;
//cout << ans << endl;
int j = n - 1;
for(i = t1 - 1; i >= 0; i--){
while(j > t2){
if(a[i] <= a[j]){
t++;
ans = max(ans,t);
j--;
}
else break;
}
t--;
}
return n - ans;
}
};
第205场周赛
2
思路：数据范围再1000，所有不能直接三层循环，那就减少一层，先算出nums1[j]*nums1[k] 和nums2[j]*nums2[k]分别放入map里面保存，然后再查询两个数组里面的元素的平方是否在map数组里面存在，存在则加上map数值。
插曲: mp.count(t)返回的是1或0，1表示存在t，0表示不存在。
class Solution {
public:
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
int n1,n2;
n1 = nums1.size();
n2 = nums2.size();
map<long long,long long>mp1,mp2;
long long temp;
for(int i = 0; i < n1; i++){
for(int j = i + 1; j < n1; j++){
temp = (long long)nums1[i] * nums1[j];
mp1[temp]++;
}
}
for(int i = 0; i < n2; i++){
for(int j = i + 1; j < n2; j++){
temp = (long long)nums2[i] * nums2[j];
mp2[temp]++;
}
}
int ans = 0;
//cout << mp2.count(1) << endl;
for(int i = 0; i < n2; i++){
long long k = (long long)nums2[i] * nums2[i];
ans += (mp1.count(k) == 1 ? mp1[k] : 0);
}
for(int i = 0; i < n1; i++){
long long k = (long long)nums1[i] * nums1[i];
// cout << k << " ";
// cout << mp2.count(k) << " ";
ans += (mp2.count(k) == 1 ? mp2[k] : 0);
}
return ans;
}
}; 3
思路：
1：c用来存放某个连续子串中某个字符删除花费最大是多少，并存放在这个连续子串的最后一个字符下标那里。len存放连续子串的长度，存放位置和c一样，sum是前缀和。
2：s += ‘ ’，这样好处理边界。
3：处理好每个数组后，就可以来算了，利用sum算出删除这个连续子串的总花费，再减去最大花费就是让其不连续的最小花费。
class Solution {
public:
int minCost(string s, vector<int>& cost) {
int l = s.length();
int n = cost.size();
int mmax = 0;
int c[100005];
int len[100005];
int sum[100005];
sum[0] = cost[0];
for(int i = 1; i < n; i++){
sum[i] = sum[i - 1] + cost[i];
}
s += ' ';
int cnt = 1;
for(int i = 0; i < l; i++){
if(s[i] == s[i + 1]){
cnt++;
mmax = max(mmax,cost[i]);
}
else{
mmax = max(mmax,cost[i]);
c[i] = mmax;
len[i] = cnt;
mmax = 0;
cnt = 1;
}
}
int ans = 0;
//cout << c[4] << endl;
for(int i = 0; i < l; i++){
if(s[i] != s[i + 1]){
if(len[i] > 1){
int temp = i - len[i] + 1;
if(temp == 0) ans += sum[i] - c[i];
else
ans += sum[i] - sum[temp - 1] - c[i];
}
//cout << ans << endl;
}
}
return ans;
}
}; 第206场周赛
2
思路：先把每个人对其他朋友的亲密度求出来。
class Solution {
public:
bool check(int num[1005][1005],int x,int y,int p[],int n){
for(int i = 0; i < n; i++){
if(num[x][y] < num[x][i] && num[i][x] > num[i][p[i]]) return false;
}
return true;
}
int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
int num[1005][1005];
int p[1005];
for(int i = 0; i < n; i++){
for(int j = 0; j < n - 1; j++){
num[i][preferences[i][j]] = n - j;
}
}
for(int i = 0; i < n / 2; i++){
p[pairs[i][0]] = pairs[i][1];
p[pairs[i][1]] = pairs[i][0];
}
int ans = 0;
for(int i = 0; i < n; i++){
if(!check(num,i,p[i],p,n)){
ans++;
}
}
return ans;
}
}; 
