Leetcode

简单

中等

困难

2024-03-06

简单

2917. 找出数组中的 K-or 值

位运算问题，考虑到K-or数只看第i位的值是否为1，并且需要知道的仅仅是超过k值的数组中的数，使用O(n)来解决此问题

简单的位运算模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findKOr(vector<int>& nums, int k) {
        int res = 0;
        for (int i = 0; i < 31; ++i) {
            int cnt = 0;
            for (int num:nums) {
                if((num >> i) & 1){
                    ++cnt;
                }
            }
            if (cnt >= k) {
                res |= 1 << i;
            }
        }
        return res;
    }
};

2024-03-07

中等

2575. 找出字符串的可整除数组

考虑到 word 长达 1e5，故无法每一个数字取模确认，因为十进制数字退一位有着 10 个数一循环的特性，故一次取模不影响后面是否会被 m 整除，遂只需要 O(n)即可解决问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        int n=word.size();
        vector<int> res(n);
        long cur=0;
        for(int i=0;i<n;i++){
            cur = 10*cur+((int)word[i]-48);
            cur %= m;
            if(cur==0) res[i]=1;
            else res[i]=0;
        }
            return res;
    }
};

如何更快？使用位运算可加快计算速度。

2024-03-08

中等

2834. 找出美丽数组的最小和

考虑到一个数可分解为两个数相加，题意为数组中的“两个”数相加不得target，那么如果相等则向下延顺，比如9可分为1 + 8，2 + 7，3 + 6,4 + 5这四组不同的加法，而默认最小数组就是1到n这n个数字，则去除延顺后的最小数组就是[1,2,3,4,9,10,………,n]推出正常情况下的公示，再对1和target不影响默认最小数组的情况特殊判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int mod=1e9 + 7;
    long long a_sum(int a,int b,int l){if(l==1) return a; return (long long)(a+b)*l/2;}

    int minimumPossibleSum(int n, int target) {
        if(n==1 or target==1) return a_sum(1,n,n)%mod;
        long long pd= target/2;
        if(pd>n) return a_sum(1,n,n)%mod;
        long long n1=a_sum(1,target+n-pd-1,target+n-pd-1);
        long long n2=a_sum(pd+1,target-1,target-pd-1);
        return (n1-n2)%mod;
    }
};

time

2024-03-09

困难

2386. 找出数组的第 K 大和

一个有n个元素的数组有2^n个子数组，既然是找出第K大的子数组和，那么本题对于给出数组的排序并不敏感，关键是子数组的排序，既然求最大的子数组，那么所有正数相加就是第1个大的子数组，其他子数组就是减去一个最小的正数，或者加上一个最大的负数就是第二个最大子数组….再向后可能就是减去多个正数，加上多个负数….

那么问题转化为只需要求第K个最大子数组的值减去第一个最大子数组的值。使用优先队列的小顶堆维护即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    long long kSum(vector<int>& nums, int k) {
        long long s=0;
        int n=nums.size();
        for(int &x:nums){
            if(x>=0) s+=x;
            else x=-x;
        }
        sort(nums.begin(),nums.end());
        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>>q;
        q.push({0,0});
        while (--k)
        {
            auto ts=q.top();q.pop();
            if(ts.second>=n) continue;
            q.push({ts.first+nums[ts.second],ts.second+1});
            if(ts.second) q.push({ts.first-nums[ts.second-1]+nums[ts.second],ts.second+1});
        }
        return s-q.top().first;
    }
};

2024-03-10

中等

299. 猜数字游戏

使用键值对可以轻松解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string getHint(string secret, string guess) {
        unordered_map<char,int> mp1,mp2;
        int n=secret.size();
        int bulls(0),cows(0);
        for(int i=0;i<n;i++){
            if(secret[i]==guess[i]){bulls++;continue;}
            mp1[secret[i]]++,mp2[guess[i]]++;
        }
        for(auto &it:mp1)
            if(mp2[it.first]) cows+=min(it.second,mp2[it.first]);
        string ans=to_string(bulls)+"A"+to_string(cows)+"B";
        return ans;
    }
};

2024-03-11

简单

2129. 将标题首字母大写

使用字符流容易解决，还可以避免指针越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string capitalizeTitle(string title) {
        int n=title.size();
        string ans="";
        stringstream ss(title);
        string str;
        while(ss>>str){
            if(str.size()<=2){
                ans+=tolower(str[0]);
                if(str.size()==2) ans+=tolower(str[1]); 
            }else{
                int nn=str.size();
                ans+=toupper(str[0]);
                for(int i=1;i<nn;i++){
                    ans+=tolower(str[i]);
                }
            }
            ans+=" ";
        }
        ans.pop_back();
        return ans;
    }
};

2024-03-12

中等

1261. 在受污染的二叉树中查找元素

二叉树….

2024-03-13

简单

2864. 最大二进制奇数

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int n=s.size();
        int n0(0),n1(0);
        for(int i=0;i<n;i++)
            if(s[i]=='0') n0++;else n1++;
        string ans="";
        for(int i=0;i<n1-1;i++) ans+='1';
        for(int i=n1-1;i<n-1;i++) ans+='0';
        ans+='1';
        return ans;
    }
};

2024-03-14

中等

2789. 合并后数组中的最大元素

一开始想如果两对两对的看成一个树的结果，维护一个最大的根，后来发现既然只有两个相邻的数，那么直接从后往前加在一块，在不符合规则前取最大的那个不就行了，后来有发现既然他不符合规则，那么后面遍历完的数据就必不可能是答案喽，还是比较容易解决的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    long long maxArrayValue(vector<int>& nums) {
        int n=nums.size();
        long long ans=nums[n-1];
        for(int i=n-2;i>=0;i--){
            if(nums[i]<=ans){
                ans=(long long)ans+(long long)nums[i];
            }else{
                ans=(long long)nums[i];
            }
        }
        return ans;
    }
};

2024-03-15

困难

2312. 卖木头块

求出卖出方案的最大值，可以确定是DP，题目中说明切割一次只能完全切割，那么如何正确的遍历切割方案和递推公式就是本题的难点。

观察到一个M*N的矩形有2种切割方法，首先是切割成（M1+M2）*N，或者是M*(N1+N2)，其中会存在相同的M*N，如果将其记录则优化时间，使用二维数组更新切割的最大值，创建DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    typedef long long ll;
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        vector<vector<int>> mp(m+1,vector<int> (n+1,0));
        for(auto &p:prices) mp[p[0]][p[1]]=p[2];
        vector<vector<ll>> dp(m+1,vector<ll> (n+1,-1));

        function<void(int,int)> dfs = [&](int i,int j){
            if(dp[i][j] != -1) return;
            dp[i][j]=mp[i][j];
            for(int x=i/2;x>0;x--){
                dfs(x,j);
                dfs(i-x,j);
                dp[i][j] = max(dp[i][j],dp[x][j]+dp[i-x][j]);
            }
            for(int y=j/2;y>0;y--){
                dfs(i,y);
                dfs(i,j-y);
                dp[i][j] = max(dp[i][j],dp[i][y]+dp[i][j-y]);
            }
        };
        dfs(m,n);
        return dp[m][n];

    }
};


//后来在speed rank里看到比我快8倍的代码，真是又快又好，很值得学习

class Solution {
public:
    long long dp[201][201];
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        int i,j,k;
        for (auto &x : prices) {
            dp[x[0]][x[1]] = x[2];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= j/2; k++) dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]); // 垂直切割
                for (int k = 1; k <= i/2; k++) dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]); // 水平切割
            }
        }
        return dp[m][n];
    }
};

2024-03-16

2024-03-17

2024-03-18

2024-03-19

2024-03-20

中等

1969. 数组元素的最小非零乘积

​ 基于贪心算法，优先将小的变小，大的变大，最后数组就会成为[0,0,0,0,0,……..,2^p -1,2^p -1,…..]，因为要求数组非零，所以再将后面2^p -1的最后一个1补到前面即可，但是不知道为什么，pow（2，p）的效果居然和(ll)1<<(p-1)不一样，这点还有待考量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    typedef long long ll;
    ll mod=1e9+7;
	long long my_pow(long long x, long long n) {
        long long res = 1;
        for (; n != 0; n >>= 1) {
            if (n & 1) {
                res = res * x % mod;
            }
            x = x * x % mod;
        }
        return res;
    }

    int minNonZeroProduct(int p) {
        if(p==1) return p;
        ll a=my_pow((ll)2,p)%mod;//2^p

        // ll y=my_pow(a-(ll)2,a/(ll)2-(ll)1)%mod;
        // ll x=a-(ll)1;
        // x%=mod;
        // ll ans=x*y%mod;
        // return ans%mod;
        ll x=my_pow(2,p)-1;
        ll y=(ll)1<<(p-1);
        // ll y=my_pow((ll)2,p-(ll)1);
        return my_pow(x-1,y-1)*x%mod;
    }
};
/*
p=2
1 2 3
1 2 3

p=3
1 2 3 4 5 6 7
 +4 -2+2-4
1 6 1 6 1 6 7

p=4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
 +8+4  -4       -8            
 1     2    3    4   5    6    7    8     9    10  11   12   13   14   15
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0001 1010 0011 0100 0101 0110 0111 1000 0001 1010 1011 1100 1101 1110 1111
0001 1010 0111 0100 0001 0110 0111 1000 0001 1010 1011 1100 1101 1110 1111
*/

2024-03-21

中等

2671. 频率跟踪器

第一眼看见直接用map就解决了吗？看到查询次数可能很多，那就动态记录一下num的存量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class FrequencyTracker {
public:
    unordered_map<int,int> mp;
    unordered_map<int,int> cnt;

    FrequencyTracker() {
        mp.clear();
        cnt.clear();
    }
    
    void add(int number) {
        mp[number]++;
        cnt[mp[number]-1]--;
        cnt[mp[number]]++;
    }
    
    void deleteOne(int number) {
        if(mp[number]>0){
            mp[number]--;
            cnt[mp[number]+1]--;
            cnt[mp[number]]++;

        }
    }
    
    bool hasFrequency(int frequency) {
        if(cnt[frequency]>0) return true;
        return false;
    }
};

/**
 * Your FrequencyTracker object will be instantiated and called as such:
 * FrequencyTracker* obj = new FrequencyTracker();
 * obj->add(number);
 * obj->deleteOne(number);
 * bool param_3 = obj->hasFrequency(frequency);
 */

2024-03-22

第 33 次 CCF CSP 认证考试总结

第一题和第二题都很简单，不到 20 分钟就敲完了，全程使用 STL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define closeSync            \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0)

map<int, int> mp1;
unordered_set<int> st1;
int main()
{
    closeSync;
    int n, m;
    cin >> n >> m;
    vector<int> v(m + 1, 0);
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        unordered_set<int> st;
        for (int j = 0; j < t; j++)
        {
            int word;
            cin >> word;
            mp1[word]++;
            st.insert(word);
        }
        for (auto &it : st)
        {
            v[it]++;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        cout << v[i] << " " << mp1[i] << '\n';
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
#define closeSync            \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0)

int main()
{
    closeSync;
    int n, m;
    cin >> n >> m;
    unordered_set<string> st1;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        int sz = s.size();
        for (int j = 0; j < sz; j++)
        {
            if (s[j] >= 'A' and s[j] <= 'Z')
            {
                s[j] += 32;
            }
        }
        st1.insert(s);
        //    cout << s << " ";
    }
    unordered_set<string> st2;
    for (int i = 0; i < m; i++)
    {
        string s;
        cin >> s;
        int sz = s.size();
        for (int j = 0; j < sz; j++)
        {
            if (s[j] >= 'A' and s[j] <= 'Z')
            {
                s[j] += 32;
            }
        }
        st2.insert(s);
        //  cout << s << " ";
    }
    unordered_set<string> st3;
    int n1 = st1.size();
    int n2 = st2.size();
    // U
    set_union(st1.begin(), st1.end(), st2.begin(), st2.end(), inserter(st3, st3.begin()));
    int onaji = st3.size();
    cout << n1 + n2 - onaji << '\n';
    cout << onaji << '\n';

    return 0;
}

第三题是对矩阵求秩，有时候想把代码写的好看一点，可是这反而浪费了很多时间，再加上找不到 bug 在哪，让我一度又推翻重写的想法，大概 2 个小时才修改完。

（可惜我没有高斯消元板子，只能现场手搓）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <bits/stdc++.h>
using namespace std;
#define closeSync            \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0)

int q, n;
vector<vector<int>> a(52, vector<int>(52, 0));
int scan(int ssum)
{
    int r;
    int cnt = 0;
    for (int i = 1; i <= ssum; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j] != 0)
            {
                break;
            }
            else
                cnt++;
        }
        if (cnt == n)
        {
            return i - 1;
        }
        cnt = 0;
    }
    return ssum;
}

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

void print(int ssum)
{
    for (int i = 1; i <= ssum; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
int solve(int ssum)
{
    // print(ssum);
    int l = 1;

    for (int i = 1; i <= ssum; i++)
    {
        int pd0 = 0;
        for (int j = 1; j <= n; j++)
        {
            pd0 += a[i][j];
        }
        if (pd0 == 0)
        {
            l++;
            continue;
        }
        if (a[i][l] == 0)
        {
            for (int k = i + 1; k <= ssum; k++)
            {
                if (a[k][l] != 0)
                {
                    swap(a[i], a[k]);
                    break;
                }
            }
        }
        for (int k = i + 1; k <= ssum; k++)
        {
            int aa = a[i][l], bb = a[k][l];
            if (bb == 0)
                continue;

            int beishu1 = lcm(aa, bb);
            // cout << beishu1 << endl;
            int beishu2 = bb * beishu1 / aa;
            // cout << bb << "aa/a " << aa << endl;
            for (int ll = l; ll <= n; ll++)
            {
                a[k][ll] *= beishu1;
                // cout << "a[k][ll]前 =" << a[k][ll] << endl;
                a[k][ll] = a[k][ll] - beishu2 * a[i][ll];
                // cout << "a[k][ll]后 =" << a[k][ll] << endl;
            }
        }
        // print(ssum);

        if (l < n)
            l++;
        else
        {
            return l;
        }
    }

    return l;
}

int main()
{
    closeSync;
    cin >> q;
    while (q--)
    {
        cin >> n;
        unordered_map<string, vector<int>> mp;
        string s;

        for (int k = 1; k <= n; k++)
        {
            cin >> s;
            string elem = "";
            int sz = s.size();
            string num_s = "";
            for (int i = 0; i < sz; i++)
            {
                if (s[i] >= 'a' and s[i] <= 'z')
                    elem += s[i];
                else
                {
                    while (s[i] >= '0' and s[i] <= '9')
                        num_s += s[i++];
                    i--;
                    int num = atoi(num_s.c_str());
                    if (mp[elem].empty())
                    {
                        vector<int> v(52, 0);
                        mp[elem] = v;
                        mp[elem][k] += num;
                    }
                    else
                    {
                        mp[elem][k] += num;
                    }
                    // debuge: cout << elem << " " << num_s << endl;
                    elem = "", num_s = "";
                }
            }
        }

        int Ssum = mp.size();
        // debug: cout << Ssum << endl;
        // 消元:

        int ind = 1;
        for (auto &it : mp)
        {
            for (int b = 1; b <= 50; b++)
            {
                a[ind][b] = it.second[b];
            }
            ind++;
        }
        int R = solve(Ssum);
        R = scan(Ssum);
        // print(Ssum);
        // cout << R << endl;
        mp.clear();
        cout << ((R < n) ? "Y\n" : "N\n");
    }

    return 0;
}

第四题维护一个点以及相邻两个非零点的数值，因为数据非常大（1e9），还需要对数据进行离散化处理，考试的时候是这样想的，大概用了 30 分钟，感觉自己大概率是没发把这个题 100 分过掉，索性在开 3e5 的数组爆搜拿了 40 分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//40'  满分代码还需官网上传题目再完善
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define closeSync            \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0)

const int N = 3e5 + 9;
int a[N];

int c, m, n;
int search()
{
    int cnt = 0;
    for (int i = 1; i <= c; i++)
    {
        // cout << a[i] << " ";
        if (a[i] != 0)
            cnt++;
    }
    return cnt;
}

void opp(int op)
{
    int l = op - 1, r = op + 1;
    if (l < 0 or r > c + 1)
        return;
    if (a[op] >= 5)
    {
        while (a[l] == 0 and l >= 0)
        {
            l--;
        }
        while (a[r] == 0 and r <= c)
        {
            r++;
        }
        a[op] = 0;
        a[l]++;
        a[r]++;
    }
    else
    {
        return;
    }
    opp(l);
    opp(r);
}
// map<int, int> mp;
int main()
{
    closeSync;
    cin >> c >> m >> n;
    int ind = 1;
    for (int i = 1; i <= m; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        a[t1] = t2;
    }

    while (n--)
    {
        int op;
        cin >> op;
        a[op]++;
        opp(op);
        cout << search() << '\n';
    }

    return 0;
}

第五题貌似也是维护一个树形结构？或许也能使用线段树解决，当时只剩下 20 分钟的时间，想使用暴力 STL 嵌套来模拟，最后时间不够了，没用写完。

//代码等待官网上传题目再完善

总结：第一次打 csp，貌似听说同考场有 390 的选手，不由得赞叹校友们的能力，我还缺乏对于模拟过程中的代码的可读性的提高，因为有时候我不知道我在写什么，这也是我第三题浪费了很多时间，再加上机房的电脑没有配置好断点调试，导致我很难找到之前的 bug；另外虽然可带纸质材料，但是基本上是用不上的，翻书更加浪费时间:( 今年还会再打 1~2 次，希望能刷到 400+。