Posted on | In , |
Words count in article: 569 | Reading time ≈ 3

5384. 拥有最多糖果的孩子

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int n = candies.size();
        vector<bool> res(n);
        int maxx = 0;
        for(auto a: candies) maxx = max(maxx, a);
        for(int i=0; i<n; i++) {
            if(extraCandies + candies[i] >= maxx) res[i] = true;
        }
        return res;
    }
};

5385. 改变一个整数能得到的最大差值

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
class Solution {
public:
    int maxDiff(int num) {
        vector<int> dig(9);
        int z = 0, v = num;
        while(v) {
            dig[z++] = v % 10;
            v /= 10;
        }
        int mi = num, ma = num;
        for(int i=0; i<10; i++) {
            for(int j=0; j<10; j++) {
                int ans = 0;
                for(int o = z-1; o >=0 ;o--) {
                    int cur = dig[o];
                    if(cur == i) cur = j;
                    if(o == z-1 && cur == 0) break;
                    ans = ans * 10 + cur;
                }
                if(ans == 0) continue;
                mi = min(mi, ans);
                ma = max(ma, ans);
            }
        }
        return ma-mi;
    }
};

1433. 检查一个字符串是否可以打破另一个字符串

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
class Solution {
public:
    bool checkIfCanBreak(string s1, string s2) {
        vector<int> v1(26);
        vector<int> v2(26);
        for(auto a: s1) v1[a-'a'] ++;
        for(auto a: s2) v2[a-'a'] ++;
        vector<int> t1 = v1;
        vector<int> t2 = v2;
        int i = 0, j = 0;
        int f1 = 0;
        while(i < 26 && j < 26) {
            while(i < 26 && v1[i] == 0) i++;
            while(j < 26 && v2[j] == 0) j++;
            if(i >= 26 || j >= 26) break;
            if(j < i) {
                f1 = 1; break;
            }
            int ans = min(v1[i], v2[j]);
            v1[i] -= ans;
            v2[j] -= ans;
        }
        if(f1 == 0) return true;
        i = 0, j = 0, f1 = 0, v1 = t1, v2 = t2;
        while(i < 26 && j < 26) {
            while(i < 26 && v1[i] == 0) i++;
            while(j < 26 && v2[j] == 0) j++;
            if(i >= 26 || j >= 26) break;
            if(i < j) {
                f1 = 1; break;
            }
            int ans = min(v1[i], v2[j]);
            v1[i] -= ans;
            v2[j] -= ans;
        }
        if(f1 == 0) return true;
        return false;
    }
};

1434. 每个人戴不同帽子的方案数

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
typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
  int numberWays(vector<vector<int>>& hats) {
    int n = hats.size();
    vector<ll> dp(1 << n);
    dp[0] = 1;
    vector<set<int>> s(41);
    for (int i = 0; i < n; ++i)
      for (int hat : hats[i])
        s[hat].insert(i);
    for (int i = 1; i <= 40; ++i) {
      vector<ll> ndp(dp);
      for (int state = (1 << n) - 1; state >= 0; --state) {
        for (int person : s[i]) {
          if (state & (1 << person))
            continue;
          int nxt = state + (1 << person);
          ndp[nxt] += dp[state];
          ndp[nxt] %= MOD;
        }
      }
      swap(dp, ndp);
    }
    return dp[(1 << n) - 1];
  }
};

Posted on | In , |
Words count in article: 348 | Reading time ≈ 2

1422. 分割字符串的最大得分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxScore(string s) {
        int sum = 0;
        for(int i=0; i<s.size(); i++) {
            if(s[i] == '1') sum ++;
        }
        int res = 0;
        int count0 = 0;
        int count1 = 0;
        for(int i=0; i<s.size()-1; i++) {
            if(s[i] == '1') count1++;
            else count0++;
            res = max(res, count0 + (sum-count1));
        }
        return res;
    }
};

1423. 可获得的最大点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int sum = 0;
        for(auto c: cardPoints) sum += c;
        int mina = INT_MAX, temp = 0;
        int len = cardPoints.size()-k;
        for(int i=0; i<cardPoints.size(); i++) {
            temp += cardPoints[i];
            if(i >= len) temp -= cardPoints[i-len];
            if(i >= len-1) mina = min(mina, temp);
        }
        return sum - mina;
    }
};

1424. 对角线遍历 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        map<int, vector<int>> mp;
        for(int i=nums.size()-1; i>=0; i--) {
            for(int j=0; j<nums[i].size(); j++) {
                mp[i+j].push_back(nums[i][j]);
            }
        }
        vector<int> ans;
        for(auto m: mp) {
            for(auto a: m.second) {
                ans.push_back(a);
            }
        }
        return ans;
    }
};

1425. 带限制的子序列和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int ans = INT_MIN, n = nums.size();
        deque<int> q;
        vector<int> dp(n);
        for(int i=0; i<n; i++) {
            if(q.size() && i-q.front() > k) q.pop_front();
            dp[i] = max(0, (q.empty() ? 0: dp[q.front()])) + nums[i];
            while(q.size() && dp[q.back()] < dp[i]) {
                q.pop_back();
            }
            q.push_back(i);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

Posted on | In , |
Words count in article: 612 | Reading time ≈ 3

5388. 重新格式化字符串

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
class Solution {
public:
    string reformat(string s) {
        vector<char> c1;
        vector<char> c2;
        for(auto c: s) {
            if(c >= 'a' && c <= 'z') c1.push_back(c);
            else c2.push_back(c);
        }
        int n1 = c1.size(), n2 = c2.size();
        if(abs(n1-n2) > 1) return "";
        string res = "";
        if(n1 > n2) {
            res += c1[0];
            for(int i=0; i<n2; i++) {
                res += c2[i];
                res += c1[i+1];
            }
        } else if(n1 < n2) {
            res += c2[0];
            for(int i=0; i<n1; i++) {
                res += c1[i];
                res += c2[i+1];
            }
        } else {
            for(int i=0; i<n1; i++) {
                res += c1[i];
                res += c2[i];
            }
        }
        return res;
    }
};

5389. 点菜展示表

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
class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        set<string> s;
        for(auto o: orders) s.insert(o[2]);
        vector<string> v(s.begin(), s.end());
        sort(v.begin(), v.end());
        unordered_map<string, int> mp1;
        for(int i=0; i<v.size(); i++) mp1[v[i]] = i;
        map<int, vector<int>> mp2;
        int c1 = 0;
        for(auto o: orders) {
            int num = stoi(o[1]);
            if(mp2[num].size() == 0){ mp2[num].resize(v.size()); c1++;}
            mp2[num][mp1[o[2]]]++;
        }
        vector<vector<string>> res(c1+1, vector<string>(v.size()+1));
        res[0][0] = "Table";
        for(int i=0; i<v.size(); i++) {
            res[0][i+1] = v[i];
        }
        int z = 1;
        for(auto m: mp2) {
            res[z][0] = to_string(m.first);
            for(int i=0; i<v.size(); i++) {
                res[z][i+1] = to_string(m.second[i]);
            }
            z++;
        }
        return res;
    }
};

5390. 数青蛙

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:
    int minNumberOfFrogs(string str) {
        vector<int> cot(5);
        int n = str.size();
        int res = INT_MIN;
        for(int i=0; i<n; i++) {
            if(str[i] == 'c') cot[0]++;
            else if(str[i] == 'r') cot[1]++;
            else if(str[i] == 'o') cot[2]++;
            else if(str[i] == 'a') cot[3]++;
            else if(str[i] == 'k') cot[4]++;
            if(cot[0] < max(cot[1], max(cot[2], max(cot[3], cot[4])))) return -1;
            if(cot[1] < max(cot[2], max(cot[3], cot[4]))) return -1;
            if(cot[2] < max(cot[3], cot[4])) return -1;
            if(cot[3] < cot[4]) return -1;
            res = max(cot[0]-cot[4], res);
        }
        if(cot[0] == cot[1] && cot[1] == cot[2] && cot[2] == cot[3] && cot[3] == cot[4])
            return res;
        else 
            return -1;
    }
};

5391. 生成数组

class Solution {
    int f[55][105][55];
public:
    int numOfArrays(int n, int m, int k) {
        const int M = 1000000007;
        memset(f, 0, sizeof(f) ) ;
        for (int i = 1; i <= m; ++i){
            f[1][i][1] = 1;
        }
        for (int i = 2; i <= n; ++i){
            for (int kk = 1; kk <= k; ++kk){
                int sm = 0;
                for (int j = 1; j <= m; ++j){
                    f[i][j][kk] = 1ll * j * f[i - 1][j][kk] % M;
                    f[i][j][kk] = (f[i][j][kk] + sm) % M;
                    sm = (sm + f[i - 1][j][kk - 1]) % M;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; ++i)
            ans = (ans + f[n][i][k]) % M;
        return ans;
    }
};

Posted on | In , |
Words count in article: 422 | Reading time ≈ 2

5372. 逐步求和得到正数的最小值

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int curmin = INT_MAX;
        int sum = 0;
        for(auto num: nums) {
            sum += num;
            curmin = min(curmin, sum);
        }
        return curmin < 1 ? abs(curmin)+1: 1;
    }
};

5373. 和为 K 的最少斐波那契数字数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<long long> fib = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170};
    
    int findMinFibonacciNumbers(int k) {
        int c = 0;
        int i = 0;
        for(i=0; i<45; i++) {
            if(fib[i] >= k) break;
        }
        for(; i>=0; ) {
            if(k <= 0) break;
            while(k < fib[i]) i--;
            c++;
            k -= fib[i];
        }
        return c;
    }
};

5374. 长度为 n 的开心字符串中字典序第 k 小的字符串

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
class Solution {
public:
    vector<string> res;
    void dfs(int n, string cur) {
        if(n == 0) {
            res.push_back(cur);
            return;
        }
        if(cur == "") {
            dfs(n-1, cur+'a');
            dfs(n-1, cur+'b');
            dfs(n-1, cur+'c');
            return;
        }
        int size = cur.size();
        if(cur[size-1] == 'a') {
            dfs(n-1, cur+'b');
            dfs(n-1, cur+'c');
        } else if (cur[size-1] == 'b') {
            dfs(n-1, cur+'a');
            dfs(n-1, cur+'c');
        } else if (cur[size-1] == 'c') {
            dfs(n-1, cur+'a');
            dfs(n-1, cur+'b');
        }
    }
    string getHappyString(int n, int k) {
        dfs(n, "");
        return k > res.size() ? "" : res[k-1];
    }
};

5375. 恢复数组

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:
    int numberOfArrays(string s, int k) {
        int mo = 1000000007;
        int n = s.size();
        vector <int> f(n + 5, 0);
        f[0] = 1;
        for (int i = 0; i < n; i++) {
            f[i + 1] = 0;
            long long now = 0, base = 1;
            for (int j = i; j >= 0 && j >= i - 15; j--) {
                now += base * (s[j] - '0');
                base *= 10;
                if (now > k) {
                    break;
                }
                if (s[j] != '0') {
                    (f[i + 1] += f[j]) %= mo;
                }
            }
        }
        return f[n];
    }
};

Posted on | In , |
Words count in article: 415 | Reading time ≈ 2

1408. 数组中的字符串匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    static bool cmp(string a, string b) {
        return a.size() < b.size();
    }
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), cmp);
        unordered_map<string, int> mp;
        vector<string> ret;
        for(auto word: words) {
            for(int i=0; i<word.size(); i++) {
                for(int j=1; j<=word.size()-i; j++) {
                    if(mp[word.substr(i, j)]) {ret.push_back(word.substr(i, j)); mp[word.substr(i, j)] = 0;}   
                }
            }
            mp[word]++;
        }
        return ret;
    }
};

1409. 查询带键的排列

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:
    //10e3可以暴力解决 
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> ans;
        vector<int> dm(m, 0);
        for (int i = 1; i <= m; i++) dm[i-1]=i;
        for (int i = 0; i < queries.size(); i++) {
            for (int j = 0; j < m; j++) {
                if (dm[j] == queries[i]) {
                    ans.push_back(j);
                    for (int k = j; k >= 1; k--) {
                        dm[k] = dm[k-1];
                    }
                    dm[0]=queries[i];
                    break;
                }
            }
        }
        return ans;
    }
};

1410. HTML 实体解析器

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
class Solution {
public:
    string entityParser(string text) {
        map<string,string> mp;
        mp["&quot;"] = "\"";
        mp["&apos;"] = "'";
        mp["&amp;"] = "&";
        mp["&gt;"] = ">";
        mp["&lt;"] = "<";
        mp["&frasl;"] = "/";
        string str;
        int k = 0;
        for(int i=0;i<text.length();i++){
            if(text[i]!='&')
                str += text[i];
            else{
                //cout << i << endl;
                int j = i;    
                string tt = "";
                while(j<text.length()){
                    if(text[i]==';')break;
                    tt += text[i];
                    i++;
                    j++;
                }
                tt += ";";
                //cout << tt << endl;
                if(mp.find(tt)!=mp.end()) str += mp[tt];
                else str += tt;
                i = j;
                
            }
        }
        return str;
    }
};

1411. 给 N x 3 网格图涂色的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numOfWays(int n) {
        long long aba = 6;
        long long abc = 6;
        int mod = 1000000007;
        while(--n > 0) {
            long long aba2 = (aba*3 + abc*2) % mod;
            long long abc2 = (aba*2 + abc*2) % mod;
            aba = aba2;
            abc = abc2;
        }
        return (int)((aba+abc) % mod);
    }
};

Posted on | In , |
Words count in article: 525 | Reading time ≈ 3

非递增顺序的最小子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for(auto i: nums) sum += i;
        int tsum = 0;
        vector<int> ret;
        for(int i=nums.size()-1; i>=0; i-- ){
            tsum += nums[i];
            sum -= nums[i];
            ret.push_back(nums[i]);
            if(tsum > sum) break;
        }
        return ret;
    }
};

5377. 将二进制表示减到 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
class Solution {
public:
    int numSteps(string s) {
        int ans = 0;
        while (s.size() != 1) {
            string news;
            if (s.back() == '0') {
                news = s.substr(0, s.size() - 1);
                s = news;
            } else {
                bool all1 = true;
                int last = -1;
                for (int i = s.size() - 1; i >= 0; i--) {
                    if (s[i] != '1') {
                        all1 = false;
                        last = i;
                        break;
                    }
                }
                if (all1) {
                    return ans + 1 + s.size();
                } else {
                    s[last] = '1';
                    for (int i = last + 1; i < s.size(); i++) {
                        s[i] = '0';
                    }
                }
            }
            ans++;
        }
        return ans;
    }
};

最长快乐字符串

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
class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        string ans;
        while(true){
            if(a==0&&b==0&&c==0) break;
            if(ans.size()>=2&&ans.back()=='a'&&ans[ans.size()-2]=='a'){
                if(b==0&&c==0) break;
                if(b>=c){
                    ans.push_back('b');
                    b--;
                }else{
                    ans.push_back('c');
                    c--;
                }
                continue;
            }
            
            if(ans.size()>=2&&ans.back()=='b'&&ans[ans.size()-2]=='b'){
                if(a==0&&c==0) break;
                if(a>=c){
                    ans.push_back('a');
                    a--;
                }else{
                    ans.push_back('c');
                    c--;
                }
                continue;
            }
            
            if(ans.size()>=2&&ans.back()=='c'&&ans[ans.size()-2]=='c'){
                if(a==0&&b==0) break;
                if(a>=b){
                    ans.push_back('a');
                    a--;
                }else{
                    ans.push_back('b');
                    b--;
                }
                continue;
            }
            
            if(a>=b&&a>=c){
                ans.push_back('a');
                a--;
                continue;
            }
            
            if(b>=a&&b>=c){
                ans.push_back('b');
                b--;
                continue;
            }
            
            if(c>=a&&c>=b){
                ans.push_back('c');
                c--;
                continue;
            }
        }
        return ans;
    }
};

石子游戏 III

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 stoneGameIII(vector<int>& a) {
        int n = a.size();
        vector <int> f;
        f.resize(n + 1);
        f[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            f[i] = -1e9;
            int s = 0;
            for (int j = i; j < n && j < i + 3; j++) {
                s += a[j];
                f[i] = max(f[i], s - f[j + 1]);
            }
        }
        if (f[0] > 0) {
            return "Alice";
        } else if (f[0] == 0) {
            return "Tie";
        } else {
            return "Bob";
        }
    }
};s

Posted on | In , |
Words count in article: 465 | Reading time ≈ 2

5360. 统计最大组的数目

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
class Solution {
public:
    int helper(int x) {
        int ret = 0;
        while(x) {
            ret += x % 10;
            x /= 10;
        }
        return ret;
    }
    int countLargestGroup(int n) {
        map<int, int> mp;
        int curmax = -1;
        for(int i=1; i<=n; i++) {
            int cur = helper(i);
            mp[cur] ++;
            curmax = max(curmax, mp[cur]);
        }
        int c = 0;
        for(auto m: mp) {
            if(m.second == curmax) c++;
        }
        return c;
    }
};

5362. 构造 K 个回文字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool canConstruct(string s, int k) {
        int letter[26] = {0};
        for(auto& c: s) {
            letter[c-'a'] ++;
        }
        int ou = 0;
        for(int i=0; i<26; i++) {
            if(k < 0) return false;
            if(letter[i] % 2 == 0) {
                ou += letter[i];
            } else {
                k--;
                ou += (letter[i]-1);
            }
        }
        return k >= 0 && ou >= k;
    }
};

5361. 圆和矩形是否有重叠

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 Solution {
public:
    double far(double n1, double m1, double n2, double m2)
    {
        double ans;
        ans = (n1 - n2) * (n1 - n2) +(m1 - m2) * (m1 - m2);
        ans = sqrt(ans);
        return ans;
    }
    bool checkOverlap(int r, int a, int b, int xa, int ya, int xb, int yb) {
        if (
                far(xa, ya, a, b) <= r ||
                far(xa, yb, a, b) <= r ||
                far(xb, ya, a, b) <= r ||
                far(xb, yb, a, b) <= r 
            )
        {
            return true;
        }
        else if (a >= min(xa, xb) && a <= max(xa, xb) && b >= min(ya, yb) && b <= max(ya, yb))
        {
            return true;
        }
        else if(
                    (far(xa, b, a, b) <= r && b <= max(ya, yb) && b >= min(ya, yb))||
                    (far(xb, b, a, b) <= r && b <= max(ya, yb) && b >= min(ya, yb))||
                    (far(a, ya, a, b) <= r && a <= max(xa, xb) && a >= min(xa, xb))||
                    (far(a, yb, a, b) <= r && a <= max(xa, xb) && a >= min(xa, xb))  //顶点不在圆内但是边和圆相交
                )
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

5363. 做菜顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSatisfaction(vector<int>& a) {
        int n = a.size();
        sort(a.begin(), a.end());
        int ans = 0, sum = 0, cur = 0;
        for(int i=n-1; i>=0; i--) {
            cur += sum + a[i];
            ans = max(ans, cur);
            sum += a[i];
        }
        return ans;
    }
};

Posted on | In , |
Words count in article: 702 | Reading time ≈ 4

5368. 找出数组中的幸运数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findLucky(vector<int>& arr) {
        map<int, int> mp;
        for(auto& i: arr) {
            mp[i]++;
        }
        int curmax = -1;
        for(auto i: mp) {
            if(i.first == i.second) {
                curmax = max(curmax, i.first);
            }
        }
        return curmax;
    }
};

5369. 统计作战单位数

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 Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size();
        vector<int> smallL(n);
        vector<int> bigR(n);
        vector<int> smallR(n);
        vector<int> bigL(n);
        int countmin = 0;
        int countbig = 0;
        for(int i=1; i<n; i++) {
            for(int j=0; j<i; j++) {
                if(rating[j] < rating[i]) countmin++;
                if(rating[j] > rating[i]) countbig++;
            }
            smallL[i] = countmin;
            bigL[i] = countbig;
            countmin = 0;
            countbig = 0;
        } // smallL bigL
        for(int i=0; i<n-1; i++) {
            for(int j=n-1; j>i; j--) {
                if(rating[j] < rating[i]) countmin++;
                if(rating[j] > rating[i]) countbig++;
            }
            smallR[i] = countmin;
            bigR[i] = countbig;
            countmin = 0;
            countbig = 0;
        } // smallR bigR
        int ret = 0;
        for(int i=1; i<n-1; i++) {
            ret += smallL[i]*bigR[i];
            ret += smallR[i]*bigL[i];
        }
        return ret;    
    }
};

5370. 设计地铁系统

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
class UndergroundSystem {
public:
    unordered_map<int , string> start;
    unordered_map<int , int> starttime;
    unordered_map<string , int> mp1;
    unordered_map<string , int> mp2;
    unordered_map<string , double> mp3;
    
    UndergroundSystem() {
        
    }
    
    void checkIn(int id, string stationName, int t) {
        starttime[id] = t;
        start[id] = stationName;
    }
    
    void checkOut(int id, string stationName, int t) {
        string tmp = start[id]+" "+stationName;
        mp1[tmp] += (t-starttime[id]);
        mp2[tmp] += 1;
        mp3[tmp] = (mp1[tmp]*1.0)/(mp2[tmp]*1.0);
    }
    
    double getAverageTime(string startStation, string endStation) {
        string tmp = startStation+" "+endStation;
        return mp3[tmp];
    }
};

5371. 找到所有好字符串

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
class Solution {
    int n = 0, m = 0;
    string evil;
    using ll = long long;
    const ll mod = 1e9 + 7;
public:
    ll dp[505][30][56];

    void kmp_init(int n, vector<int>&pi, const string&a)
    {
        pi = vector<int>(a.size(), 0);
        for (int i = 1; i < n; ++i)
        {
            int j = pi[i - 1];
            while (j > 0 && a[i] != a[j])
            {
                j = pi[j - 1];
            }
            if (a[i] == a[j]) j++;
            pi[i] = j;
        }
    }
    vector<int> p;
    ll dfs(int cur, int st, int front, bool op, const string&s)
    {
        if (front == m)return 0;
        if (cur >= n) return 1;
        if (!op && ~dp[cur][st][front]) return dp[cur][st][front];
        int mx = op ? s[cur] - 'a' : 25;
        ll res = 0;
        for (int i = 0; i <= mx; ++i)
        {
            if (i == evil[front] - 'a')
            {
                res += dfs(cur + 1, i, front + 1, op&& i == mx, s);
            }
            else
            {
                int tf = 0;
                if (front > 0)
                {
                    int j = p[front - 1];
                    while (j > 0 && evil[j] - 'a' != i)
                    {
                        j = p[j - 1];
                    }
                    if (evil[j] - 'a' == i) j++;
                    tf = j;
                }
                else
                {
                    tf = i == evil[0] - 'a';
                }
                res += dfs(cur + 1, i, tf, op&& i == mx, s);
            }
            res %= mod;
        }
        res %= mod;
        if (!op) dp[cur][st][front] = res;
        return res;
    }
    int findGoodStrings(int n, string s1, string s2, string evil) {
        if (s1 > s2) return 0;
        this->evil = evil;
        this->n = n;
        m = evil.size();
        kmp_init(m, p, evil);
        memset(dp, -1, sizeof(dp));
        ll res = dfs(0, 26, 0, 1, s1);
        memset(dp, -1, sizeof(dp));
        res = dfs(0, 26, 0, 1, s2) - res;
        int flag = 1;
        for (int i = 0; i + m <= n; ++i)
        {
            if (s1[i] == evil[0] && s1.substr(i, m) == evil)
            {
                flag = 0; break;
            }
        }
        return (res + mod + flag) % mod;
    }
};

Posted on | In , |
Words count in article: 570 | Reading time ≈ 3

5364. 按既定顺序创建目标数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        int n = nums.size();
        vector<int> ret;
        vector<int> vis(n);
        int i = 0;
        while(ret.size() < n) {
            if(vis[i] == 1) continue;
            vis[i] = 1;
            vector<int> cur(ret.size()+1);
            for(int z=0; z<index[i]; z++) cur[z] = ret[z];
            cur[index[i]] = nums[i];
            for(int z=index[i]+1; z<cur.size(); z++) cur[z] = ret[z-1];
            i++;
            ret = cur;
            if(i == n) i = 0;
        }
        return ret;
    }
};

5178. 四因数

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
class Solution {
public:
    unordered_map<int, int> mp1;
    int get(int x) {
        if(mp1[x]) return mp1[x];
        int c = 0;
        int sum = 0;
        for(int i=1; i<=sqrt(x); i++) {
            if(x % i == 0) {c+=2; sum+=i; sum+=x/i;}
            if(c > 5) break;
        }
        double m = sqrt(x);
        if(m == (int)m) {c--; sum-=m;}
        if(c == 4) {
            mp1[x] = sum;
            return sum;
        }
        mp1[x] = 0;
        return 0;
    }
    int sumFourDivisors(vector<int>& nums) {
        int count = 0;
        for(int i=0; i<nums.size(); i++) {
            count += get(nums[i]);
        }
        return count;
    }
};

5367. 最长快乐前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string longestPrefix(string s) {
        int n = s.size();
        vector<int> kmp(n);
        kmp[0] = 0;
        for (int i = 1; i < n; ++i) {
            int j = kmp[i - 1];
            while (s[j] != s[i]) {
                if (!j) {
                    j = -1;
                    break;
                }
                j = kmp[j - 1];
            }
            kmp[i] = j + 1;
        }
        int len = kmp.back();
        return s.substr(0, len);
    }
};

5366. 检查网格中是否存在有效路径

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
class Solution {
public:
    bool vis[305][305];
    int m,n;
    int mp[305][305];
    bool left(int x,int y){
        return mp[x][y]==1||mp[x][y]==4||mp[x][y]==6;
    }
    bool right(int x,int y){
        return mp[x][y]==1||mp[x][y]==3||mp[x][y]==5;
    }
    bool up(int x,int y){
        return mp[x][y]==2||mp[x][y]==5||mp[x][y]==6;
    }
    bool down(int x,int y){
        return mp[x][y]==2||mp[x][y]==4||mp[x][y]==3;
    }
    void dfs(int x,int y){
        if(x<=0||x>m||y<=0||y>n) return;
        if(vis[x][y]) return;
        vis[x][y]=1;
        if(left(x,y)&&right(x,y+1)) dfs(x,y+1);
        if(right(x,y)&&left(x,y-1)) dfs(x,y-1);
        if(up(x,y)&&down(x-1,y)) dfs(x-1,y);
        if(down(x,y)&&up(x+1,y)) dfs(x+1,y);
    }
    bool hasValidPath(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++) 
                mp[i+1][j+1]=grid[i][j];
        dfs(1,1);
        return vis[m][n];
    }
};

Posted on | In , |
Words count in article: 531 | Reading time ≈ 3

5348. 两个数组间的距离值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int count = 0;
        for(int i=0; i<arr1.size(); i++) {
            int f = 0;
            for(int j=0; j<arr2.size(); j++) {
                if(abs(arr1[i]-arr2[j]) <= d) {
                    f = 1;
                    break;
                }
            }
            if(f == 0) count++;
        }
        return count;
    }
};

5349. 安排电影院座位

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
class Solution {
public:
    int cnt=0;
    map<int,int> id;
    vector<int> r[10010];
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        for(int i=0;i<reservedSeats.size();++i)
        {
            vector<int> a=reservedSeats[i];
            if(id[a[0]]==0)id[a[0]]=++cnt;
            r[id[a[0]]].push_back(a[1]);
        }
        int ans=0;
        for(int i=1;i<=cnt;++i)
        {
            bool c1=1,c2=1,c3=1;
            for(int j=0;j<r[i].size();++j)
            {
                if(r[i][j]==2)c1=0;
                if(r[i][j]==3)c1=0;
                if(r[i][j]==4)c1=c2=0;
                if(r[i][j]==5)c1=c2=0;
                if(r[i][j]==6)c3=c2=0;
                if(r[i][j]==7)c3=c2=0;
                if(r[i][j]==8)c3=0;
                if(r[i][j]==9)c3=0;
            }
            if(c1&&c3){ans+=2;continue;}
            if(c1 || c2 || c3)ans++;
        }
        return (long long)(n-cnt)*2+ans;
    }
};

5350. 将整数按权重排序

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
unordered_map<int, int> mp;
int get(int x) {
    if(mp.find(x) != mp.end()) return mp[x];
    int ret = 0;
    while(x != 1) {
        if(x % 2==0) x = x/2;
        else x = 3*x+1;
        ret++;
    }
    mp[x] = ret;
    return ret;
}

class Solution {
public:
    static bool cmp(int a, int b) {
        int cura = get(a);
        int curb = get(b);
        if(cura == curb) return a < b;
        return cura < curb;
    }
    int getKth(int lo, int hi, int k) {
        vector<int> tmp;
        for(int i=lo; i<=hi; i++) {
            tmp.push_back(i);
        }
        sort(tmp.begin(), tmp.end(), cmp);
        return tmp[k-1];
    }
};

5351. 3n 块披萨

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int f[500][500][2];
    int maxSizeSlices(vector<int>& slices) {
        memset(f,0,sizeof(f));
        f[1][1][1]=slices[0];
        for(int i=2;i<=slices.size();++i)
        {
            for(int j=1;j<=max(i,(int)slices.size()/3);++j)
            {
                f[i][j][0]=f[i-1][j][0];
                f[i][j][1]=f[i-1][j][1];
                f[i][j][0]=max(f[i][j][0],f[i-2][j-1][0]+slices[i-1]);
                f[i][j][1]=max(f[i][j][1],f[i-2][j-1][1]+slices[i-1]);
            }
        }
        return max(f[slices.size()][slices.size()/3][0],f[slices.size()-1][slices.size()/3][1]);
    }
};