力扣第 46 场双周

46 场双周

第一题

解法：滑窗模拟

class Solution {
public:
    string longestNiceSubstring(string s) {
        if (s.size() < 2) return "";
        for (int len = s.size(); len >= 2; -- len) {

            for (int i = 0; i + len - 1 < s.size(); ++ i) {
                int cnt1[26], cnt2[26];
                for (int i = 0; i < 26; ++ i) {
                    cnt1[i] = 1;
                    cnt2[i] = 1;
                }
                int cnt3[26];
                memset(cnt3, 0, sizeof cnt3);
                for (int j = i; j < i + len; ++ j) {
                    char c = s[j];
                    if (s[j] >= 'a' && s[j] <= 'z') {
                        if (cnt1[c - 'a']) {
                            cnt3[c - 'a'] += cnt1[c - 'a'];
                            cnt1[c - 'a'] = 0;
                        }
                        
                    }
                    else {
                        if (cnt2[c - 'A']) {
                            cnt3[c - 'A'] += cnt2[c - 'A'];
                            cnt2[c - 'A'] = 0;
                        }
                    }
                }
                int f = 1;
                for (int i = 0; i < 26; ++ i) {
                    if (cnt3[i] % 2) {
                        f = 0;
                        break;
                    } 
                }
            
                if (f) return s.substr(i, len);
            }

        }
        return "";
    }
};

第二题

解法：模拟

class Solution {
public:
    bool canChoose(vector<vector<int>>& gs, vector<int>& nums) {
        int j = 0;
        for (int i = 0; i < nums.size(); ++ i) {
            int k = i;
            while (k < nums.size() && k - i < gs[j].size() && nums[k] == gs[j][k - i]) {
                ++ k;
            }
            if (k - i == gs[j].size()) {
                ++ j;
                // cout << "j " << j  << endl;
                i = k - 1;
            }
            if (j == gs.size()) return true;
            if (k == nums.size()) return false;
            // cout << i << endl;
        }
        return false;
    }
};

第三题

解法：广度优先搜索
从水域点，层序广搜

#define pii pair<int, int>
#define x first
#define y second
class Solution {
public:
    static const int N = 1E6 + 5;
    pii q[N];
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    vector<vector<int>> highestPeak(vector<vector<int>>& ir) {
        int n = ir.size();
        int m = ir[0].size();
        int hh = 0, tt = -1;
        unordered_set<int> st;
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                if (ir[i][j]) {
                    q[++ tt] = {i, j};
                    st.insert(i * m + j);
                }
            }
        }

        
        vector<vector<int>> ret(n, vector<int>(m));
        int cnt = 0;
        while (hh <= tt) {
            int sz = tt - hh + 1;

            ++ cnt;
            for (int i = 0; i < sz; ++ i) {
                pii t = q[hh ++];
                for (int k = 0; k < 4; ++ k) {
                    int xt = t.x + dx[k];
                    int yt = t.y + dy[k];

                    if (xt < 0 || xt >= n || yt < 0 || yt >= m || st.count(xt * m + yt)) continue;
                    // cout << xt << " " << yt << endl;
                    st.insert(xt * m + yt);
                    q[++ tt] = {xt, yt}; 
                    ret[xt][yt] = cnt;
                    // cout << "ok" << endl;
                }
                
            }
            
        }
        return ret;
        
        
    }
};

第四题

解法：深搜
如果对每一个节点搜其父节点，时间复杂度太大
注意到 n <= 50
建立 50 个栈对应
栈顶即离此节点最近的父节点的 层次 和 对应下标
对每一个节点搜 1 到 50 的数字
具体操作看代码

class Solution {
public:
    static const int N = 2e5 + 5;
    int h[N], e[N], ne[N], idx;
    vector<stack<pair<int, int> > > stk;
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    } 
    vector<int> ret;
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }
    vector<int> nums;
    void dfs(int u, int f, int cnt) {
        int ans = -1, lv = 0;
        for (int i = 1; i <= 50; ++ i) {
            if (stk[i].size() && stk[i].top().first > lv && gcd(i, nums[u]) == 1) {
                lv = stk[i].top().first;
                ans = stk[i].top().second;
            }
        }
        // cout << u << " " << ans << " " << lv << endl;
        ret[u] = ans;
        stk[nums[u]].push({cnt, u});
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == f) continue;
            dfs(j, u, cnt + 1);
        }
        stk[nums[u]].pop();

        
    }
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        this->nums = nums;
        stk.assign(55, stack<pair<int, int>>());

        memset(h, -1, sizeof h);

        ret.assign(nums.size(), -1);

        for (auto& it : edges) {
            add(it[0], it[1]);
            add(it[1], it[0]);
        }    
        
        dfs(0, -1, 1);

        return ret;

    }
};