leetcode 90双周赛

距离字典两次编辑以内的单词

1. 每一个数组进行一次修改，等价于某一个修改两次
2. 使用hash表
3. 字符串太大，并且修改字符串时间复杂度高，考虑使用字符串hash

代码如下

class Solution {
public:
    int BASE = 257;
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dict) {
        unordered_map<unsigned long long, int>mp;
        unsigned long long base[103];
        base[0] = 1;
        for (int i = 1; i < 101; i++) base[i] = base[i - 1] * BASE;  
        for (string s : dict) {
            unsigned long long key = 0;
            for (int i = s.size() - 1; i >= 0; i--) {   // 逆序这样下面的减去或者加上base才有用。
                key = key * BASE + s[i];
            }
            for (int i = 0; i < s.size(); i++) {
                int pre = s[i];
                key -= base[i] * pre;
                for (char c = 'a'; c <= 'z'; c++) {
                    key += base[i] * c;
                    mp[key] = 1;
                    key -= base[i] * c;
                }
                key += base[i] * pre;
            }
        }
        vector<string>ans;
        for (string s: queries) {
            int flag = 0;
            unsigned long long key = 0;
            for (int i = s.size() - 1; i >= 0; i--) {
                key = key * BASE + s[i];
            }
            for (int i = 0; i < s.size(); i++) {
                char pre = s[i];
                key -= base[i] * pre;
                for (char c = 'a'; c <= 'z'; c++) {
                    key += base[i] * c;
                    if (mp[key]) {
                        flag = 1;
                        break;
                    }
                    key -= base[i] * c;
                }
                key += base[i] * pre;
                if (flag) break;
            }
            if (flag) {
                ans.push_back(s);
            }
        }
        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

6226. 摧毁一系列目标

• 对space取余相同的是在一个组中。
• 最多数字组的最小值是答案。

代码

class Solution {
public:
    int destroyTargets(vector<int>& nums, int space) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        unordered_map<int, vector<int>>mp;
        for (int i = 0; i < n; i++) {
            mp[nums[i] % space].push_back(nums[i]);
        }
        int maxv = 0, ans = INT_MAX;
        for (auto [x, vec] : mp) {
            if (vec.size() > maxv) {
                // printf("%d %d %d\n", x, vec.size(), vec[0]);
                maxv = vec.size();
                ans = vec[0];
            } 
            if (vec.size() == maxv) ans = min(ans, vec[0]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第二个更大的元素

使用排序 + 有序列表 + 二分。

1. 首先，按照nums[i]降序, i升序进行排序
2. 其次，遍历对，将i放入有序集合中，有序集合中的元素都是大于nums[i]的元素
3. 最后，找到i大于等于i的下标，这个是大于nums[i]的第一个，往后一个就是大于等于i的第二个，找不到就是-1。

由于下标是升序的，所以等于nums[i]的下标一定小于i, 所以从有序集合找到大于i的下标一定是大于nums[i]的，而不是大于等于nums[i]的。所以后一个元素一定是大于的第二个。

class Solution {
public:
    typedef pair<int, int>PR;
    static bool cmp(PR &a, PR &b) {
        return a.first == b.first ? a.second < b.second : a.first > b.first; 
    }
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<PR>a;
        for (int i = 0; i < n; i++) {
            a.emplace_back(nums[i], i);
        }
        sort(a.begin(), a.end(), cmp);
        set<int>st;
        vector<int>ans(n);
        for (int i = 0; i < n; i++) {
            auto [x, id] = a[i];
            auto it = st.lower_bound(id);
            // printf("%d %d\n", x, *it);
            if (it != st.end() && next(it) != st.end())
                ans[id] = nums[*(next(it))];
            else ans[id] = -1;
            st.insert(id);
        }
        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