Atopos's Blog

One step at a time!

0%

发表于 分类于
本文字数： 603 阅读时长 ≈ 1 分钟

题目

最近的请求次数

思路

使用队列，每次将新的 t 加入队列，然后循环判断对头元素是否大于 t - 3000，若小于则出队，否则结束循环，最后返回队列中的元素个数即可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class RecentCounter {
public:
    int count;
    queue<int> que;
    RecentCounter() {
        count = 0;
        while(!que.empty()) que.pop();
    }
    
    int ping(int t) {
        que.push(t);
        while(que.front() < t - 3000){
            que.pop();
        }
        return que.size();
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */
  • 时间复杂度：O(n)，其中 n 是调用 ping 的次数
  • 空间复杂度：O(n)，队列中元素的个数

执行用时：144 ms, 在所有 C++ 提交中击败了32.54%的用户

内存消耗：56.1 MB, 在所有 C++ 提交中击败了24.97%的用户

通过测试用例：68 / 68

发表于 分类于
本文字数： 506 阅读时长 ≈ 1 分钟

题目

长度最小的子数组

思路

  • 使用双指针记录滑动窗口的左边界和右边界，当满足条件后，进行判断并记录结果。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = INT_MAX;
        int i = 0;
        int sum = 0;
        for(int j = 0; j < nums.size(); j++){
            sum += nums[j];
            while(i <= j && sum >= target){
                res = min(res, j - i + 1);  
                sum -= nums[i];
                i++;
            }
        }

        return res == INT_MAX ? 0 : res;  // 若是最后还没有找到区间，则为 0 
    }
};
  • 时间复杂度：O(n)，其中 n 是数组 nums 的大小
  • 空间复杂度：O(1)

执行用时：8 ms, 在所有 C++ 提交中击败了61.48%的用户

内存消耗：10.2 MB, 在所有 C++ 提交中击败了71.05%的用户

通过测试用例：19 / 19

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目

乘积小于 K 的子数组

思路

  • 使用 queue 队列实现 滑动窗口 ，当前元素入队后，若队列中总的乘积小于 k，则继续遍历下一个元素，若队列中总的乘积大于等于 k，则依次出队，直到队列中的总元素乘积小于 k，每个遍历后需要将队列中的总元素个数加至结果变量中。
  • 使用两个指针代表 滑动窗口 的两个边界。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int res = 0;
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k == 0) return 0;
        queue<int> que;
        int sum = 1;
        for(int i = 0; i < nums.size(); i++){
            que.push(nums[i]);
            sum *= nums[i];
            while(!que.empty() && sum >= k){
                int top = que.front();
                que.pop();
                sum /= top;
            }
            res += que.size();
        }
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 是数组 nums 的大小
  • 空间复杂度：O(n)，队列最多有 n 个元素

执行用时：68 ms, 在所有 C++ 提交中击败了53.23%的用户

内存消耗：63 MB, 在所有 C++ 提交中击败了5.26%的用户

通过测试用例：97 / 97

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int res;
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int i = 0;
        int sum = 1;
        for(int j = 0; j < nums.size(); j++){
            sum *= nums[j];
            while(i <= j && sum >= k){
                sum /= nums[i];
                i++;
            }
            res += j - i + 1;
        }
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 是数组 nums 的大小
  • 空间复杂度：O(1)

执行用时：52 ms, 在所有 C++ 提交中击败了96.72%的用户

内存消耗：59.8 MB, 在所有 C++ 提交中击败了65.17%的用户

通过测试用例：97 / 97

发表于 更新于 分类于
本文字数： 956 阅读时长 ≈ 1 分钟

题目

全排列 II

思路

对数组进行递归，若当前元素和上一次递归选择的元素相同，则直接跳过（相当于剪枝），若当前元素不等于上一次元素且没有被选择过，则可以选择，加入数组，直到临时数组的大小等于 nums 数组的大小，则将该临时数据加入至结果数组中。

题解

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
class Solution {
public:
    vector<vector<int>> res;
    vector<bool> used;

    void dfs(vector<int>& nums, vector<int>& arr){
        if(arr.size() == nums.size()){
            res.push_back(arr);
        }
        int x = -11;
        for(int i = 0; i < nums.size(); i++){
            if(x == nums[i]) continue;  // 当前位置刚选过的x和当前值相等。则直接跳过
            if(!used[i]){  // 当前值没有被选择
                used[i] = true;
                arr.push_back(nums[i]);
                dfs(nums, arr);
                used[i] = false;
                x = arr[arr.size() - 1];
                arr.pop_back();
            }
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++) used.push_back(false);
        vector<int> arr;
        dfs(nums, arr);
        return res;
    }
};
  • 时间复杂度：O(n n!)*
  • 空间复杂度：O( n)，结果数组中最多有 n 个元素的数组

执行用时：4 ms, 在所有 C++ 提交中击败了91.98%的用户

内存消耗：8.7 MB, 在所有 C++ 提交中击败了56.14%的用户

通过测试用例：33 / 33

发表于 分类于
本文字数： 696 阅读时长 ≈ 1 分钟

题目

找出游戏的获胜者

思路

使用队列将所有数字存储起来，然后进行循环遍历直到队列中只剩一个元素，每次循环先将 k 减一，将队头元素使用临时变量保存起来，然后出队，dang k 不等于0时，将刚出队的元素再次入队，若 k 等于0，则需要更新 k 。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findTheWinner(int n, int k) {
        queue<int> que;
        for(int i = 1; i <= n; i ++){
            que.push(i);
        }
        int x = k;
        while(que.size() > 1){  // 循环遍历，直到队列中只剩一人
            x --;
            int top = que.front();
            que.pop();
            if(x != 0){  // 当还没到第k个，则再次入栈
                que.push(top);
            }
            else{  // 到第k个，则需要更新x，再次计数
                x = k;
            }
        }
        return que.front();
    }
};
  • 时间复杂度：O(n \ k)，其中 n 是做游戏的小伙伴数量，k 是每一轮离开圈子的小伙伴的计数。初始时需要将 n 个元素加入队列，每一轮需要将 k 个元素从队列中取出，将 k−1 个元素加入队列，一共有 n−1 轮，因此时间复杂度是 O(n * k)*。
  • 空间复杂度：O(n)，队列最多有n个元素。

执行用时：72 ms, 在所有 C++ 提交中击败了11.70%的用户

内存消耗：23.8 MB, 在所有 C++ 提交中击败了15.31%的用户

通过测试用例：95 / 95

发表于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目

子集

思路

先确定需要的子数组的大小，（从 0 到 nums.size() 依次遍历），然后递归进行选择，每次递归都从上一个元素的下一位置开始，直到临时数组的大小等于当前确定的所需子数组的大小，将其加入结果数组。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> res;
    vector<int> arr;
    // x 当前需要子集的大小， npc 应该开始位置
    void dfs(vector<int> nums, int x, int npc){
        if(x == arr.size()){ // 当前子集的大小满足目前所需的大小
            res.push_back(arr);
            return;
        }
        for(int i = npc; i < nums.size(); i ++){  // 从npc 开始遍历
            arr.push_back(nums[i]);
            dfs(nums, x, i + 1);
            arr.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        for(int i = 0; i <= nums.size(); i++){  // 遍历，i代表需要子集的大小，
            dfs(nums, i, 0);
        }
        return res;
    }
};
  • 时间复杂度：O(n \ 2 ^ n)，一共 2 ^ n 个状态，每种状态需要 O(n) 的时间来构造子集。
  • 空间复杂度：O(n)。临时数组 arr 的空间代价是 O(n)，递归时栈空间的代价为 O(n*)。

执行用时：4 ms, 在所有 C++ 提交中击败了43.18%的用户

内存消耗：7.6 MB, 在所有 C++ 提交中击败了13.53%的用户

通过测试用例：10 / 10

延伸题目

子集 II

思路

  • 思路1：在上面的基础上，当满足条件时使用map 进行去重，若重复则不加入，反之则加入。（需要先排序）
  • 思路2：递归法实现子树枚举，在递归时，若发现没有选择上一个数，并且当前数字与上一个数字相同，则可以跳过当前生成的子集。

题解

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
class Solution {
public:
    map<vector<int>, int> hsp;
    vector<vector<int>> res;
    vector<int> arr;

    void dfs(vector<int> nums, int x, int npc){
        if(arr.size() == x){
            if(hsp[arr] == 1) return;  //使用map进行判断是否有重复的
            res.push_back(arr);
            hsp[arr] = 1;
            return ;
        }
        for(int i = npc; i < nums.size(); i++){
            arr.push_back(nums[i]);
            dfs(nums, x, i + 1);
            arr.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 0; i <= nums.size(); i ++){
            dfs(nums, i, 0);
        }
        return res;
    }
};
  • 时间复杂度：O(n \ 2 ^ n)，一共 2 ^ n 个状态，每种状态需要 O(n) 的时间来构造子集。
  • 空间复杂度：O(n)。临时数组 arr 的空间代价是 O(n)，递归时栈空间的代价为 O(n*)。

执行用时：12 ms, 在所有 C++ 提交中击败了5.73%的用户

内存消耗：9.5 MB, 在所有 C++ 提交中击败了13.58%的用户

通过测试用例：20 / 20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> res;
    vector<int> arr;

    void dfs(vector<int> nums, int x, bool pre){
        if(x == nums.size()){
            res.push_back(arr);
            return ;
        }
        dfs(nums, x + 1, false);
        if(!pre && x > 0 && nums[x] == nums[x - 1]) // 上一个数和当前数相等，并且上一个数没有被加入
            return;
        arr.push_back(nums[x]);
        dfs(nums, x + 1, true);
        arr.pop_back();
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0, false);
        return res;
    }
};
  • 时间复杂度：O(n \ 2 ^ n)，其中 n 是数组 nums 的长度。排序的时间复杂度为 O(n * log n) 。最坏情况下 nums 中无重复元素，需要枚举其所有 2 ^ n 个子集，每个子集加入答案时需要拷贝一份，耗时 O(n) ，一共需要 O(n * 2 ^ n) + O(n) = O(n * 2 ^ n) 的时间来构造子集。由于在渐进意义上 O(n * log n) 小于O(n * 2 ^ n) ，故总的时间复杂度为 O(n * 2 ^ n)*
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  • 空间复杂度：O(n)。临时数组 arr 的空间代价是 O(n)，递归时栈空间的代价为 O(n*)。

执行用时：4 ms, 在所有 C++ 提交中击败了54.66%的用户

内存消耗：15.6 MB, 在所有 C++ 提交中击败了5.03%的用户

通过测试用例：20 / 20

发表于 分类于
本文字数： 950 阅读时长 ≈ 1 分钟

题目

受标签影响的最大值

思路

使用vector<pair<int, int>> 将 values 和 labels 对应起来，然后按照 values 从大到小进行排序，每次在满足对应的标签没有达到上限时（使用unordered_map进行计数），优先取最大的即可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<pair<int, int>> arr;
    unordered_map<int, int> hsp;
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        for(int i = 0; i < values.size(); i ++){
            arr.push_back(make_pair(values[i], labels[i]));
        }
        sort(arr.begin(), arr.end(), [](pair<int, int> &a, pair<int, int> &b){  // 将arr数组从大到小进行排序
            return a.first > b.first;
        });
        int res = 0;
        for(int i = 0; i < arr.size() && numWanted; i++){
            if(hsp[arr[i].second] < useLimit){
                hsp[arr[i].second] ++;
                res += arr[i].first;
                numWanted--;
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n \ log n)，其中 n 为 values* 的大小，主要是 sort()函数的时间发复杂度
  • 空间复杂度：O(n)，数组和哈希表对应的空间

执行用时：24 ms, 在所有 C++ 提交中击败了80.30%的用户

内存消耗：19.8 MB, 在所有 C++ 提交中击败了65.15%的用户

通过测试用例：81 / 81

发表于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目

重新排列日志文件

思路

  • 思路1：先遍历一边数组，分别将字母日志和数字日志存入vector<string>中，然后将字母日志使用自定义排序进行排序，再将数字日志加入排序后的字母日志即可。
  • 思路2：直接使用 stable_sort进行自定义排序.

stable_sort 和 sort 的区别

  • sort是快速排序实现，因此是不稳定的；stable_sort是归并排序实现，因此是稳定的。（这里的稳定是指排序后相等元素的相对位置保持不变）
  • 对于相等的元素sort可能改变顺序，stable_sort保证排序后相等的元素次序不变。
  • 如果提供了比较函数，sort不要求比较函数的参数被限定为const，而stable_sort则要求参数被限定为const，否则编译不能通过。

题解

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
class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        vector<string> dig;  // 保存数字日志
        vector<string> let;  // 保存字母日志
        for(int i = 0; i < logs.size(); i++) {
            string str = logs[i];
            int j = 0;
            for(; j < str.size(); j ++){
                if(str[j] == ' ') break;
            }
            if(str[j + 1] >= '0' && str[j + 1] <= '9'){ //是数字日志
                dig.push_back(str);
            }
            else{ // 是字母日志
                let.push_back(str);
            }
        }
        sort(let.begin(), let.end(), [](string &a, string &b) {  //自定义sort排序
            int x = a.find(" ");
            int y = b.find(" ");
            string stra = a.substr(x + 1);
            string strb = b.substr(y + 1);
            if(stra != strb) return stra < strb;
            else return a < b;
        });
        for(int i = 0; i < dig.size(); i ++){
            let.push_back(dig[i]);
        }
        return let;
    }
};
  • 时间复杂度：O(n \ log n)，其中 n 为 logs* 的字符数，是平均情况下内置排序的时间复杂度。
  • 空间复杂度：O(n)，额外存放日志的数组

执行用时：16 ms, 在所有 C++ 提交中击败了23.57%的用户

内存消耗：12.4 MB, 在所有 C++ 提交中击败了31.52%的用户

通过测试用例：65 / 65

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        stable_sort(logs.begin(), logs.end(), [&](const string &a, const string &b){  // stable_sort
            int x = a.find_first_of(" "); // 找到a的第一个空格
            int y = b.find_first_of(" "); // 找到b的第一个空格
            bool isDigital_a = isdigit(a[x + 1]);
            bool isDigital_b = isdigit(b[y + 1]);
            if(isDigital_a && isDigital_b){  // 两个都是数字日志
                return false;
            }
            else if(!isDigital_a && !isDigital_b) { // 两个都是字母日志
                string stra = a.substr(x + 1);
                string strb = b.substr(y + 1);
                if(stra != strb) return stra < strb;
                else return a < b;
            }
            return isDigital_a ? false : true;  // 判断a是否是数字日志，若a是数字日志，则返回false
        });
        return logs;
    }
};
  • 时间复杂度：O(n \ log n)，其中 n 为 logs* 的字符数，是平均情况下内置排序的时间复杂度。
  • 空间复杂度：O(n)，额外存放日志的数组

执行用时：12 ms, 在所有 C++ 提交中击败了59.80%的用户

内存消耗：10.9 MB, 在所有 C++ 提交中击败了83.87%的用户

通过测试用例：65 / 65

发表于 分类于
本文字数： 864 阅读时长 ≈ 1 分钟

题目

在排序数组中查找元素的第一个和最后一个位置

标签

二分查找模板

思路

使用二分算法的两个模板分别可以求出元素出现的第一个位置和最后一个位置。

题解

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if(nums.size() == 0){
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        int l = 0, r = nums.size() - 1;
        while(l < r){  //第一个模板
            int mid = (l + r) >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(nums[l] != target){
            res.push_back(-1);
            res.push_back(-1);
        }else{
            res.push_back(l);
            l = 0, r = nums.size() - 1;
            while(l < r){  // 第二个模板
                int mid = (l + r + 1) >> 1;
                if(nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            res.push_back(r);
        }
        return res;
    }
};
  • 时间复杂度：O(log n)，其中 n 为数组的长度。二分查找的时间复杂度是O(log n)，一共执行两次，所以总的时间复杂度是O(log n)
  • 空间复杂度：O(1)，只需要常数空间存放若干变量

执行用时：4 ms, 在所有 C++ 提交中击败了93.27%的用户

内存消耗：13.3 MB, 在所有 C++ 提交中击败了34.09%的用户

通过测试用例：88 / 88

发表于 更新于 分类于 ，
本文字数： 4.1k 阅读时长 ≈ 4 分钟

题目 1：移除指定数字得到的最大结果

移除指定数字得到的最大结果

标签

字符串

思路

遍历一遍字符串，当遇到指定字符时，使用 erase 函数删除该字符，然后使用 compare()函数进行字符串比较，因为字符串的长度都是相等的，所以就相当于比较的是对应整型的大小。最后保存最大的即可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string removeDigit(string number, char digit) {
        string res = "";
        for(int i = 0; i < number.length(); i ++){
            if(number[i] == digit){
                string str = number;  // 用于临时保存原来的string
                str.erase(i, 1); // 删除该字符，从i开始删除，删除1个字符
                if(res == ""){
                    res = str;
                }
                else if(res.compare(str) < 0){  // 比较字符串大小
                    res = str;
                }
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n ^ 2)，其中 n 为 number 的长度，我们只需要对 number 进行一次遍历，但是erase函数的时间复杂度为O(n)。
  • 空间复杂度：O(n)，即为存储标结果需要使用的空间。

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.4 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：112 / 112

题目 2：必须拿起的最小连续卡牌数

必须拿起的最小连续卡牌数

标签

队列、哈希表

思路

使用队列存储元素，若将要加入的元素已经存在于队列中，则开始出队，知道队列中不存在该元素，然后和res比较大小，若res大于队列元素个数 加 2（因为此时当前元素还没加入，并且和其相同的元素也已经出队了，所以需要加 2）。然后将当前元素入队，继续往后遍历。

判断当前元素是否存在于队列中需要使用unordered_map<int, int>哈希表进行存储，表示 K 在哈希表中的个数为 V 。

题解

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
class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        queue<int> que; // 队列
        unordered_map<int, int> hsp;  // 哈希表
        que.push(cards[0]);
        hsp[cards[0]] ++;
        int i = 1;
        int res = -1;
        while(i < cards.size()){
            if(hsp[cards[i]] > 0) {
                while(hsp[cards[i]] > 0){
                    int top = que.front();
                    hsp[top] --;
                    que.pop();
                }
                if(res == -1 || res > (que.size() + 2)) res = que.size() + 2;
                hsp[cards[i]] ++;
                que.push(cards[i++]);
            }
            else{
                hsp[cards[i]] ++;
                que.push(cards[i++]);
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 为 cards 的长度，我们只需要对 cards 进行一次遍历.
  • 空间复杂度：O(2 \ n)*，即为队列和哈希表所需要的空间。

执行用时：372 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：116.4 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：78 / 78

题目 3：含最多 K 个可整除元素的子数组 ⭐

含最多 K 个可整除元素的子数组

标签

哈希表、字符串

思路

对 nums 数组进行双重循环，第一重确定开始的位置（0 ~ nums.size() - 1） ，然后依次遍历数组，使用整型变量 count 记录出现能整除 p 的个数，当 count 大于 k 时，就跳出循环。否则将该元素转为字符串加入 str 中，注意 需要在每个数后面加个 ,，是为了防止出现连续加入 1,9和直接加入19造成的歧义。最后将str 直接加入unordered_map 中进行去重。最后结果为unordered_map的个数。

去重也可以使用map<vector<int>, int>

unordered_map 和 map 的区别

  • map，set底层是红黑树，有序的，存储的数据类型可以自定义，空间时间复杂度比较高
  • unordered_map，unordered_set底层实现的时哈希表，无序存储，查询、插入时间空间复杂度比较低（相较于上面两个），但是缺点就是数据类型只能是基本数据类型，比如：int，char，float，string等。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    
    int countDistinct(vector<int>& nums, int k, int p) {
        unordered_map<string, int> hsp;
        for(int i = 0; i < nums.size(); i ++){
            int count = 0;  // 记录能被p整除的个数
            string str = "";
            for(int j = i; j < nums.size(); j ++){
                if(nums[j] % p == 0) count ++;
                if(count > k) break;
                str += to_string(nums[j]); // 将整型转为string类型，并添加到str中
                str += ","; // 防止出现 1 9  和 19 一样的情况
                hsp[str] ++;  // 使用unordered_map进行去重
            }
            // cout << hsp.size() << endl;
        }
        return hsp.size();
    }
};
  • 时间复杂度：O(n ^ 2)，其中 n 为 nums 的长度
  • 空间复杂度：O((1 + n) \ n / 2)，即为 unordered_map* 做多需要使用的空间。

执行用时：492 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：204.6 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：129 / 129

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    
    int countDistinct(vector<int>& nums, int k, int p) {
        map<vector<int>, int> res;
        for(int i = 0; i < nums.size(); i ++){
            int count = 0;  // 记录能被p整除的个数
            for(int j = i; j < nums.size(); j ++){
                if(nums[j] % p == 0) count ++;
                if(count > k) break;
                res[vector<int>(nums.begin() + i, nums.begin() + j + 1)] = 1; // 添加入map
            }
            // cout << hsp.size() << endl;
        }
        return res.size();
    }
};
  • 时间复杂度：O(n ^ 2)，其中 n 为 nums 的长度
  • 空间复杂度：O((1 + n) \ n / 2)，即为 map* 做多需要使用的空间。

执行用时：1220 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：261 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：129 / 129

题目 4：字符串的总引力 ⭐⭐

字符串的总引力

标签

字符串、哈希表、动态规划

思路

分类讨论：

  • 如果 s[i] 之前没有遇到过，那么致谢子串的引力值都会增加 1，这些子串的引力值之和会增加 i，再加上1，即 s[i] 单独组成的子串的引力值。
  • 如果 s[i] 之前遇到过，设其上次出现的下标为 j，那么向子串 s[0...i - 1], s[1...i - 1], s[2...i - 1], ..., s[j...i - 1] 的末尾添加s[i]后，这些子串的引力值是不会变化的，因为 s[i] 已经在 s[j] 出现过了；而子串s[j + 1 .. i - 1], s[j + 2 .. i - 1], .. ,s[i - 1 .. i - 1]由于不包含 s[i],这些子串的引力值都会增加 1，因此有 i - j - 1个子串的引力值会增加 1，这些子串的引力值之和会增加 i - j -1，在加上 1，即 s[i] 单独组成的子串的引力值。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    long long appealSum(string s) {
        long long res = 0;
        vector<int> pos(26, -1);
        for(int i = 0, sum = 0; i < s.size(); i++){
            int a = s[i] - 'a';
            sum += i - pos[a];
            res += sum;
            pos[a] = i;
        }
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 为 s 的长度。
  • 空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为小写字母，所以 ∣Σ∣=26。

执行用时：20 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：10.4 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：76 / 76