2022 09 每日算法刷题记录

9-3

LeetCode 646: 最长数对链

贪心，优先选截止日期最小的，能形成关系则接收

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        // Cmp is true indicates that the first arg should before the second
        sort(pairs.begin(), pairs.end(), [](auto &a, auto &b) {
            return a[1] < b[1];
        });
        int res = 0, idx = 0, now = INT_MIN;
        for (auto &i: pairs) {
            if (now < i[0]) // Accept
                now = i[1], ++res;
            ++idx;
        }

        return res;
    }
};

9-5

为什么没有 9-4 呢？显然，因为周末

LeetCode 652: 寻找重复的子树

Refer: 树哈希, Merkle Tree, hashing的一些正确姿势

没想到什么好的 Hash 方法，就序列化子树了，优化 getHash 应该可以使效率提升

class Solution {
public:
    unordered_map<string, int> table;
    unordered_map<TreeNode*, string> cache;
    string getHash(TreeNode *root) {
        if (!root) return "#";
        else if (cache.find(root) != cache.end()) return cache[root];
        else return cache[root] = to_string(root->val) + 'a'
        + getHash(root->left) + 'b'
        + getHash(root->right);
    }

    bool checkDuplicate(TreeNode *root) {
        if (!root) return false;
        else 
            return 1 == table[getHash(root)]++;
    }

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        vector<TreeNode*> res;

        queue<TreeNode*> q;
        q.emplace(root);

        while (!q.empty()) {
            auto now = q.front();
            q.pop();
            if (!now) continue;

            if (checkDuplicate(now))
                res.emplace_back(now);

            q.emplace(now->left);
            q.emplace(now->right);
        }

        return res;
    }
};

9-6

LeetCode 828: 统计子串中的唯一字符

等价于 计算每一字符对结果数组的贡献

每有一个子数组包含此字符，则贡献 +1，即求子数组数量

根据排列组合，有 dis(左边界) * dis(右边界) 个数组

初始解法

168ms 5.69%

class Solution {

public:
    int uniqueLetterString(string s) {
        int res = 0;

        // Summarize each char's contrib
        unordered_map<char, deque<int>> cmap;

        int idx = 0;
        for (char i: s)
            cmap[i].emplace_back(idx++);

        for (auto &&[_, cur]: cmap) {
            cur.emplace_front(-1);
            cur.emplace_back(s.size());
        }

        idx = 0;
        for (char i: s) {
            int dx = idx - cmap[i].front();
            cmap[i].pop_front();
            int dy = cmap[i][1] - idx;

            res += dx * dy;
            ++idx;
        }

        return res;
    }
};

看到一个解法

84ms 13.82%

class Solution {
public:
    int uniqueLetterString(string s) {
        int n = s.length();
        int ans = 0;
        for (char i = 'A'; i <= 'Z'; i++) {
            for (int j = 0, l = -1, r = -1; j < n; ++j) {
                if (s[j] == i) l = r, r = j;
                ans += r - l;
            }
        }
        return ans;
    }
};

优化后

16ms 96.21%

class Solution
{
public:
    int uniqueLetterString(string s)
    {
        int res = 0;

        int last1[26];
        int last2[26];
        memset(last1, -1, sizeof(last1));
        memset(last2, -1, sizeof(last2));
        // last1 last2 now  -> compute: last2

        int now = -1;
        for (char i: s) {
            ++now;
            i -= 'A';

            if (last2[i] == -1) {
                // Donot appear yet
                last2[i] = now;
                continue;
            }

            res += (last2[i] - last1[i]) * (now - last2[i]);
            last1[i] = last2[i];
            last2[i] = now;
        }

        now++;
        for (int i = 0; i < 26; i++) {
            // Compute else
            if (last2[i] != -1)
                res += (last2[i] - last1[i]) * (now - last2[i]);
        }

        return res;
    }
};

9-7

LeetCode 1592: 重新排列单词间的空格

简单题

class Solution {
public:
    string reorderSpaces(string text) {
        stringstream ss(text);
        int wc(0), sps(0);

        char pre = ' ';
        for (char ch: text) {
            if (ch == ' ') {
                sps++;
            } else {
                if (pre == ' ') wc++;
                else continue;
            }
            pre = ch;
        }

        int per_space(0);
        if (wc > 1) per_space = sps / (wc - 1);
        else per_space = 0;
        
        int last_space(sps - per_space * (wc - 1));

        stringstream res;
        char now[128], psc[128], lsc[128];
        int p = 0;
        for (p = 0; p < per_space; p++) psc[p] = ' ';
        psc[p] = '\0';
        for (p = 0; p < last_space; p++) lsc[p] = ' ';
        lsc[p] = '\0';

        ss >> now; res << now;
        while (ss >> now) {
            res << psc << now;
        }
        res << lsc;

        return res.str();
    }
};

用 py 写会舒服很多

class Solution:
    def reorderSpaces(self, text: str) -> str:
        wds = text.split()
        sps = text.count(' ')

        if len(wds) == 1:
            return wds[0] + ' ' * sps
            
        per_space, last_space = divmod(sps, len(wds) - 1)
        return (' ' * per_space).join(wds) + ' ' * last_space

9-8

LeetCode 667: 优美的排列 II

特殊到一般，两种方式混合

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        // n - 1 sps, k res
        // n - k of 1
        // k - 1 of else
        vector<int> res;
        res.reserve(n);
        for (int i = 1; i <= n - k; i++)
            res.emplace_back(i);
        
        // (n - k + 1) -> n
        int p(n - k + 1), q(n);
        bool flag = false;
        while (p != q) {
            // This will be faster than if(flag) xxx
            res.emplace_back(flag ? p++ : q--);
            flag = !flag;
        }

        res.emplace_back(p);
        return res;
    }
};

9-9

LeetCode 1598: 文件夹操作日志搜集器

搞笑题

class Solution {
public:
    int minOperations(vector<string>& logs) {
        int depth(0); // cur dep
        for (string &s: logs) {
            if (s[0] == '.') {
                if (depth && s[1] == '.') --depth;
            }
            else ++depth;
        }

        return depth;
    }
};

9-10

LeetCode 669: 修剪二叉搜索树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    int low, high;
public:
    TreeNode* trim(TreeNode* root) {
        if (!root) return nullptr;
        
        if (root->val < low) return trim(root->right);
        if (root->val > high) return trim(root->left);

        root->left = trim(root->left);
        root->right = trim(root->right);
        return root;
    }

    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root) return nullptr;

        this->low = low;
        this->high = high;

        return trim(root);
    }
};

9-11

LeetCode 857: 雇佣 K 名工人的最低成本

不会做 看题解

假设选定工作组，则

$$ total\_wage \times \frac{quality[i]}{total\_quality} \ge wage[i] $$

故

$$ total\_wage \ge total\_quality \times \frac{wage[i]}{quality[i]} $$

总工作质量固定时，最少工作质量只与 $ max \frac{wage[i]}{quality[i]} $ 有关

那么当我们以某一个工人 x 作为一个工资组中权重最高时，工资组中其他人员只需要在权重小于工人 x 的集合中选择工作质量最少的 k−1 名工人来组成工资组即可，此时便能达到以工人 x 为权重最高的工资组的总工作量最小，从而达到以工人 x 为权重最高的工资组的最小工资开销。然后我们枚举以每一个能成为工资组中权重最大的工人来计算最小工资组开销，然后取其中的最小即可。

尝试: TLE

class Solution {
    typedef pair<double, int> WeightQuality;
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        vector<WeightQuality> wq;
        int idx = 0;

        for (int i: quality) {
            wq.emplace_back(wage[idx] / double(i), idx);
            ++idx;
        }

        sort(wq.begin(), wq.end(), [&](auto &a, auto &b){
            return a.first <= b.first;
        });

        double res = INT_MAX;

        priority_queue<int, vector<int>, greater<int>> bsq;
        // 在之前的都满足条件，只需取最小质量的工人
        for (int j = 0; j < k - 2; j++)
            bsq.emplace(quality[wq[j].second]);
        
        for (int i = k; i <= idx; i++) {
            if (i - 2 >= 0) bsq.emplace(quality[wq[i - 2].second]);
            auto sq = bsq;
            
            double ref_q = quality[wq[i - 1].second];
            double ref_w = wage[wq[i - 1].second];
            double t_sum = ref_w;

            int need = k - 1;
            while (need--) {
                t_sum += ref_w * sq.top() / ref_q;
                sq.pop();
            }

            res = min(t_sum, res);
        }

        return res;
    }
};

题解：

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        auto n = quality.size();
        vector<int> h(n, 0);
        
        iota(h.begin(), h.end(), 0);
        sort(h.begin(), h.end(), [&](int& a, int& b) {
            return quality[a] * wage[b] > quality[b] * wage[a];
        });
        
        double res = 1e9;
        double totalq = 0.0;
        priority_queue<int, vector<int>, less<int>> q;
        for (int i = 0; i < k - 1; i++) {
            totalq += quality[h[i]];
            q.push(quality[h[i]]);
        }
        for (int i = k - 1; i < n; i++) {
            int idx = h[i];
            totalq += quality[idx];
            q.push(quality[idx]);
            
            double totalc = ((double) wage[idx] / quality[idx]) * totalq;
            res = min(res, totalc);
            totalq -= q.top();
            q.pop();
        }
        return res;
    }
};

9-12

LeetCode 1608: 特殊数组的特征值

简简单单二分法

class Solution {
public:
    int specialArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        // Binary search
        int sz = nums.size();
        int l = 1, r = sz;
        while (l <= r) {
            int x = (l + r) / 2;

            if (nums[sz - x] >= x) {
                if (sz - x - 1 < 0 || nums[sz - x - 1] < x) return x;
                else l = x + 1;
            }
            else r = x - 1;
        }

        return -1;
    }
};

9-14

LeetCode 1619: 删除某些元素后的数组均值

今天的题不错 (指提基础)

ref: http://c.biancheng.net/view/7457.html

class Solution {
public:
    double trimMean(vector<int>& arr) {
        int dis = (int) arr.size() / 20;
        nth_element(arr.begin(), arr.begin() + dis, arr.end());
        nth_element(arr.rbegin(), arr.rbegin() + dis, arr.rend(), greater{});
        
        return accumulate(arr.begin() + dis, arr.end() - dis, 0.0) / arr.size() / 0.9;
    }
};

9-16

LeetCode 850:

9-17

LeetCode 1624: 两个相同字符之间的最长子字符串

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        int last[26] = {0};
        int res = 0;
        
        int idx = 0;
        for (char &c: s) {
            ++idx; c -= 'a';
            if (last[c]) 
                res = max(res, idx - last[c]);
            else last[c] = idx;
        }

        return res - 1;
    }
};

9-18

LeetCode 827: 最大人工岛

class Solution {
    vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int land_mark[501][501];
    int land_size[250001];  // size of each mark
public:
    inline bool inland(int x, int y, int n) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }
    
    int dfs(vector<vector<int>>& grid, int x, int y, int mark) {
        int res = 1;
        int n = grid.size();
        
        grid[x][y] = 0;
        land_mark[x][y] = mark;
        for (auto &[dx, dy]: dirs) {
            if (inland(x + dx, y + dy, n) && grid[x + dx][y + dy])
                res += dfs(grid, x + dx, y + dy, mark);
        }
        
        return res;
    }
    
    int largestIsland(vector<vector<int>>& grid) {
        int res = 0;
        int n = grid.size();
        
        int i = 0, j = 0, mark = 1;
        auto templand(grid);
        for (auto &line: templand) {
            j = 0;
            for (auto &place: line) {
                if (place) {
                    // Mark land
                    land_size[mark] = dfs(templand, i, j, mark);
                    mark++;
                }
                j++;
            }
            i++;
        }
        
        i = 0, j = 0;
        for (auto &line: grid) {
            j = 0;
            for (auto &place: line) {
                if (!place) {
                    // Connect around
                    int sz = 1;
                    map<int, bool> appear;
                    for (auto &[dx, dy]: dirs) {
                        if (
                            inland(i + dx, j + dy, n)
                            && grid[i + dx][j + dy]
                            && !appear[land_mark[i + dx][j + dy]]) {
                                appear[land_mark[i + dx][j + dy]] = true;
                                sz += land_size[land_mark[i + dx][j + dy]];
                            }
                    }
                    res = max(res, sz);
                }
                j++;
            }
            i++;
        }
        
        int t_res = 0;
        for (i = 1; i <= mark; i++)
            t_res = max(t_res, land_size[i]);
        
        return max(res, t_res);
    }
};

ghg 的代码，有空了研究

#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;
#endif

class Solution {
public:
    int n;
    int dx[4] = {0, -1, 0, 1};
    int dy[4] = {1, 0, -1, 0};
    int vis[4];
    vector<int> f, s;
    void init(int n)
    {
        this->n = n;
        f.resize(n * n);
        s.resize(n * n);
        for (int i = 0; i < f.size(); i++)
        {
            f[i] = i;
            s[i] = 0;
        }
    }
    int find(int x)
    {
        if (x != f[x])
        {
            f[x] = find(f[x]);
        }
        return f[x];
    }
    void merge(int x, int y)
    {
        int fx = find(x), fy = find(y);
        if (fx == fy)
        {
            return ;
        }
        f[fx] = fy;
        s[fy] += s[fx];
    }
    int toIndex(int i, int j)
    {
        return i * n + j;
    }
    bool judge(int x, int y)
    {
        return 0 <= x && x < n && 0 <= y && y < n;
    }
    int largestIsland(vector<vector<int>>& grid) {
        init(grid.size());
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                s[toIndex(i, j)] = grid[i][j];
            }
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 0)    continue;
                int id = toIndex(i, j);
                for (int d = 0; d < 4; d++)
                {
                    int x = i + dx[d];
                    int y = j + dy[d];
                    if (!judge(x, y))   continue;
                    if (grid[x][y] == 0)    continue;
                    merge(id, toIndex(x, y));
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n * n; i++)
        {
            int t = find(i);
            ans = max(ans, s[t]);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)    continue;
                int id = toIndex(i, j);
                int ts = 1;
                for (int d = 0; d < 4; d++)
                {
                    int x = i + dx[d];
                    int y = j + dy[d];
                    vis[d] = -1;
                    if (!judge(x, y))   continue;
                    if (grid[x][y] == 0)    continue;
                    int id2 = toIndex(x, y);
                    int f1 = find(id), f2 = find(id2);
                    if (f1 == f2)   continue;
                    bool f = false;
                    for (int i = 0; i < d; i++)
                    {
                        if (vis[i] == f2)
                        {
                            f = true;   break;
                        }
                    }
                    if (f)  continue;
                    ts += s[f2];
                    vis[d] = f2;
                }
                ans = max(ans, ts);
            }
        }
        return ans;
    }
};

#ifdef LOCAL
int main()
{
    freopen("D:/Code/ACM/in.in", "r", stdin);
    freopen("D:/Code/ACM/out.out", "w", stdout);
    int T = 1;    cin >> T;
    while (T--) {
        int n;  cin >> n;
        vector<vector<int>> grid(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> grid[i][j];
            }
        }
        auto ans = Solution().largestIsland(grid);
        cout << ans << endl;
    }
    return 0;
}
#endif

9-19

LeetCode 1636: 按照频率将数组升序排序

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        int freq[201] = {0};
        for (int i: nums)
            freq[i + 100]++;

        sort(nums.begin(), nums.end(), [&](int x, int y) {
            if (freq[x + 100] == freq[y + 100])
                return x > y;
            else return freq[x + 100] < freq[y + 100]; 
        });

        return nums;
    }
};

9-20

LeetCode 698: 划分为k个相等的子集

class Solution {
    int target;
    bool vis[20];
    int bucks;
    int sz;
    
public:
    
    bool dfs(vector<int> &nums, int idx, int bef, int depth) {
        if (depth == bucks) return true;
        else if (bef == target) return dfs(nums, 0, 0, depth + 1);
        else if (bef > target) return false;
        else {
            for (; idx < sz; ++idx) {
                if (vis[idx]) continue;
                
                // Find same numbers
                int j = idx;
                while (j < sz && nums[idx] == nums[j]) j++;
                for (int i = idx; i < j; i++) {
                    // 取 1 ~ j - i 个数
                    for (int k = idx; k <= i; k++)
                        vis[k] = true;
                    if (dfs(nums, j, bef + (i - idx + 1) * nums[idx], depth))
                        return true;
                    for (int k = idx; k <= i; k++)
                        vis[k] = false;
                }
                
                return dfs(nums, j, bef, depth);
            }
        }
        return false;
    }
    
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for (int &i: nums)
            sum += i;
        
        if (sum % k) return false;
        target = sum / k;
        bucks = k;
        
        sort(nums.begin(), nums.end());
        sz = nums.size();
        
        memset(vis, 0, sizeof(vis));
        return dfs(nums, 0, 0, 0);
    }
};