LeetCode 单周赛309 && LeetCode双周赛86 && AcWing周赛67

一、LeetCode 单周赛309

1、2399.检查相同字母间的距离

（1）原题链接：力扣https://leetcode.cn/problems/check-distances-between-same-letters/

（2）解题思路：

        1、先统计字母一共有几种；

        2、再遍历distance 记录满足要求的字母的个数；

        3、判断1、2中的结果是否相等，若相等则说明满足题意return true，反之return false。

（3）代码：

class Solution {
public:
    bool checkDistances(string s, vector<int>& distance) {
        map<char, int> mp;
        for(auto& ch: s)  mp[ch] ++;
        int cnt  = 0;
        for(int i = 0; i < 26; i ++ ) {
            char ch = 'a' + i;
            int t1 = s.find_first_of(ch);
            int t2 = s.find_last_of(ch);
 
            if((t2 - t1 - 1) == distance[i]) cnt ++;
        }
 
        if(cnt == mp.size()) return true;
        else return false;
    }
};

2、6168.恰好移动k步到达某一位置的方法数目

（1）原题链接：力扣https://leetcode.cn/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/

（2）解题思路：

        1、设从 startPos 出发，往正方向走了 a 步，往负方向走了 (k - a)步后到达 endPos，根据组合数的定义可知答案为 Cka （k 步里选 a 步走正方向）。

        2、设 d = endPos - startPos，有方程 a - (k - a) = d，得 a = （d+k）/ 2，因此首先判断是否 (d + k)是偶数。最后求组合数即可。

class Solution {
    const int MOD = 1e9 + 7;
public:
    int numberOfWays(int startPos, int endPos, int k) {
        int d = endPos - startPos;
        if((d + k) % 2 == 1 || d > k) return 0;
 
        vector<vector<long long>> f(k + 1, vector(k + 1));
        for(int i = 0; i <= k; i ++ ) {
            f[i][0] = 1;
            for(int j = 1; j <= i; j ++) f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD;
        }
 
        return f[k][(d + k)/2];
    }
};

3、2401.最长优雅子数组

（1）原题链接：力扣https://leetcode.cn/problems/longest-nice-subarray/solution/bao-li-mei-ju-pythonjavacgo-by-endlessch-z6t6/

（2）解题思路：

        本题可以暴力枚举，可以把在优雅子数组中的元素按位或起来，用 or_ 保存，这样可以 O(1) 判断当前元素是否与前面的元素按位与的结果为 0。因为如果两个数想与为0， 那么说二进制表示的每一位对应的位置可能出现 1 的情况都只可能有一个优雅子数组中的元素占据。

（3）代码：

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size(); i ++ ) {
            int or_ = 0, j = i;
            while(j >= 0 && (or_ & nums[j]) == 0) or_ |= nums[j --];
            res = max(res, i - j);
        }
 
        return res;
    }
};

二、LeetCode双周赛86

1、2395.和相等的子数组

（1）原题链接：力扣https://leetcode.cn/problems/find-subarrays-with-equal-sum/

（2）解题思路：

        直接暴力枚举，用哈希表保存所有长度为2的子数组和，然后统计和相等的个数，即可。

（3）代码：

class Solution {
public:
    bool findSubarrays(vector<int>& nums) {
        int n = nums.size();
        if(n == 2) return false;
        
        unordered_map<int, int> mp;
        for(int i = 0; i < n - 1; i ++) {
            int tmp = nums[i] + nums[i + 1];
            mp[tmp] ++;
        }
        
        
        for(auto& [k, v]: mp) {
            if(v > 1) return true;
        }
        return false;
    }
};

2、2396.严格回文的数字

（1）原题链接：力扣https://leetcode.cn/problems/strictly-palindromic-number/

（2）解题思路：

        先求出2 到 n - 2进制对应的数字，然后转换为字符串的回文判断，即可。

（3）代码：

class Solution {
public:
    string check(int n, int radix) {
        string ans = "";
        do{
            int t  = n % radix;
            if(t >= 0 && t <= 9) ans += t + '0';
            else ans += t - 10 + 'a';
            n /= radix;
        }while(n != 0);
        
        reverse(ans.begin(), ans.end());
        return ans;
    }
    
    bool isStrictlyPalindromic(int n) {
        for(int i = 2; i <= n - 2; i ++ ) {
            string tmp = check(n, i);
            string cmp = tmp;
            reverse(cmp.begin(), cmp.end());
            if(tmp != cmp) return false;
        }
        
        return true;
    }
};

3、2397.被列覆盖的最多行数

（1）原题链接：力扣https://leetcode.cn/problems/maximum-rows-covered-by-columns/

（2）解题思路：

        本题使用二进制枚举的方式来做，用1表示选了，0表示没选； 记录被覆盖的列数，然后更新答案的最大值即可。

（3）代码：

class Solution {
public:
    int maximumRows(vector<vector<int>>& mat, int cols) {
        int n = mat.size();
        int m = mat[0].size();
 
        int res = 0;
        //二进制枚举
        for(int i = 0; i < 1 << m; i ++ ) {
            int cnt = 0;
            for(int j = 0; j < m; j ++ ) 
                cnt += i >> j & 1;
            if(cnt != cols) continue;
 
            //保存被覆盖的列数
            int total = 0;
            for(int j = 0; j < n; j ++ ) {
                bool flag = true;
                for(int k = 0; k < m; k ++ ) {
                    //判断是否选取了该行中的每个数
                    if(mat[j][k] && !(i >> k & 1)) {
                        flag = false;
                        break;
                    }
                }
                if(flag) total ++;
            }
            res = max(res, total);
        }
 
        return res;
    }
};

三、AcWing周赛67

1、4609.火柴棍数字

（1）原题链接：4609. 火柴棍数字 - AcWing题库

（2）解题思路：

        这题可以归结为一个找规律的题，可以观察到的是样例中的答案是有一定的规律的，设输入的是x，当x为偶数时答案为x/2个1，当x为奇数时答案为1个7 加上 (x / 2 - 1) 个1。

（3）代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
const int N = 1e5 + 10;
 
int a[N];
 
int main()
{
    int t;
    cin >> t;
    
    while(t --) {
        int n;
        cin >> n;
        
        
        int tmp = n / 2;
        if(n % 2 == 0) {
            for(int i = 0; i < tmp; i ++) {
                cout << 1;
            }
        }
        else {
            cout << 7;
            if(n > 2) {
                for(int i = 1; i < tmp; i ++ ) {
                    cout << 1;
                }
            }
        }
        puts("");
    }
    return 0;
}

 

2、4610.列表排序

（1）原题链接：4610. 列表排序 - AcWing题库

（2）解题思路：

        枚举交换任意两列或者不交换的情况，同时判断每一行不在按顺序排列的位置上的数的个数，若大于2则表示目标不能达成，反之表示目标可以达成。

（3）代码：

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 22;
 
int n, m;
int g[N][N];
 
bool check() {
    for(int i = 0; i < n; i ++) {
        int cnt = 0;
        for(int j = 0; j < m; j ++ ) {
            if(g[i][j] != j + 1) cnt ++;
        }
        
        if(cnt > 2) return false;
    }
    return true;
}
 
int main()
{
    cin >> n >> m;
    
    for(int i = 0; i < n; i ++ ) {
        for(int j = 0; j < m; j ++ ) {
            cin >> g[i][j];
        }
    }
    
    for(int i = 0; i < m; i ++ ) {
        for(int j = i; j < m; j ++ ) {
            for(int k = 0; k < n; k ++ ) swap(g[k][i], g[k][j]);
            if(check()) {
                puts("YES");
                return 0;
            }
            for(int k = 0; k < n; k ++ ) swap(g[k][i], g[k][j]);
        }
    }
    
    puts("NO");
    return 0;
}