Leetcode 1201-1300

1233. Remove Sub-Folders from the Filesystem (Medium)¶

一些文件目录，去除其中的子路径，输出最后结果

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

思路

将字符串排序，保证一个子路径的父路径一定在其前面，然后将前面非子路径的路径都插入一个unordered_set，然后遍历这个字符串，判断是否在其中即可

vector<string> removeSubfolders(vector<string>& folder) {
    sort(folder.begin(), folder.end(), [](const string& a, const string& b) {
        return a.size() < b.size();
    });
    unordered_set<string> dict;
    vector<string> res;
    for (string& s : folder) {
        bool sub = false;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '/' && dict.count(s.substr(0, i))) {
                sub = true;
                break;
            }
        }
        if (!sub) {
            res.push_back(s);
            dict.insert(s);
        }
    }
    return res;
}

1234. Replace the Substring for Balanced String (Medium)¶

一个由Q，W，E和R组成的字符串，替换其中一段字符串，变成四种字符数量相等的字符串，问替换字符串的最小长度

字符串长度一定是4的整数倍
Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER". 

思路

这里其实滑动窗口即可，窗口大小是可以贪心的，思路就是选窗口开始位置，同时窗口结尾尽量靠前，即直到有元素超过size/4为止

滑动一遍即可得到答案

int balancedString(string s) {
    int limit = s.size() / 4;
    vector<int> cnt(26, 0);
    int r = s.size() - 1;
    while (r >= 0 && cnt[s[r] - 'A'] < limit) cnt[s[r--] - 'A']++;
    if (r < 0) return 0;
    int res = r + 1;
    for (int i = 0; i <= s.size(); i++) {
        cnt[s[i] - 'A']++;
        while (r < s.size() - 1 && cnt[s[i] - 'A'] > limit) cnt[s[++r] - 'A']--;
        if (cnt[s[i] - 'A'] > limit) break;
        res = min(res, r - i);
    }
    return res;
}

1235. Maximum Profit in Job Scheduling (Hard)¶

有若干任务，每个任务有一个开始时间和结束时间，以及一个收益，求所能达到的最大收益。结束时间和开始时间相邻的两个任务可以先后执行
Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

思路

基本思路是动归，即确定到一个时间点为止所能获得的最大收益，接着将任务以结束时间排序，这个任务的收益加上这个任务开始时间的最大收益加起来，即可以完成一次对任务的更新

这里找每个任务开始时间的最大收益，可以直接进行二分搜索，第一次写的时候事先进行了排序加离散化，但这样其实复杂度更高，因为二分搜索的长度其实是从小到大的，所以相对一开始将所有时间点放在一起再进行排序，常数复杂度更低

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    vector<pair<int, int>> jobs;
    for (int i = 0; i < endTime.size(); i++) jobs.push_back({ endTime[i], i });
    sort(jobs.begin(), jobs.end());
    vector<int> dp(jobs.size(), 0);
    for (int i = 0; i < dp.size(); i++) {
        if (i == 0) dp[i] = profit[jobs[i].second];
        else {
            dp[i] = dp[i - 1];
            int time = startTime[jobs[i].second];
            int rank = upper_bound(jobs.begin(), jobs.end(), time, [](int t, const pair<int, int>& job) {
                return t < job.first;
            }) - jobs.begin() - 1;
            int prev = 0;
            if (rank >= 0) prev = dp[rank];
            dp[i] = max(dp[i], prev + profit[jobs[i].second]);
        }
    }
    return dp.back();
}

1238. Circular Permutation in Binary Representation (Medium)¶

给出两个整数n和start，要求给出在[0, 2^n]范围内，以start开始的一个序列，每两个数之间只有一个bit的差别

1 <= n <= 16

0 <= start < 2 ^ n

思路

先生成格雷码，gray(i)=i^(i>>1)，然后找到哪个格雷码是start，从这位开始重新整理结果即可

vector<int> circularPermutation(int n, int start) {
    int length = (1 << n);
    vector<int> gray(length, 0), result(length, 0);
    int index = 0;
    for (int i = 0; i < length; i++) {
        gray[i] = i ^ (i >> 1);
        if (gray[i] == start) index = i;
    }
    for (int i = 0; i < length; i++) result[i] = gray[(i + index) % length];
    return result;
}

1239. Maximum Length of a Concatenated String with Unique Characters (Medium)¶

给一个字符串列表，求由这些字符串能组成的没有重复字母的最长字符串长度，字符串只包含小写字母
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".
+ 1 <= arr.length <= 16 + 1 <= arr[i].length <= 26

思路

一共26个字母，可以用一个int来表示每个字符串含有的字母，然后进行深搜遍历即可，这里注意如果一个字符串包含重复字母，那么这个字符串不应该被加进来

小技巧是在得到每个字符串对应整数后，可以不用字符串数组，最后统计所得结果int中有多少位1即可，用__builtin_popcount即可实现

另外需要注意的是，用递归写比自己用deque来模拟要快得多

void dfs(const vector<int>& nums, int i, int num, int& result) {
    if (i == nums.size()) {
        result = max(result, __builtin_popcount(num));
        return;
    }
    dfs(nums, i + 1, num, result);
    if ((num & nums[i]) == 0)
        dfs(nums, i + 1, num | nums[i], result);
}
int maxLength(vector<string>& arr) {
    vector<int> nums;
    for (auto& str : arr) {
        int num = 0, add = 1;
        for (char c : str) {
            int d = (c - 'a');
            if ((num >> d) & 1 > 0) {
                add = 0;
                break;
            } else
                num |= (1 << d);
        }
        if (add) nums.push_back(num);
    }
    int result = 0;
    dfs(nums, 0, 0, result);
    return result;
}