Atopos's Blog

One step at a time!

0%

发表于 分类于
本文字数： 884 阅读时长 ≈ 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
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int x = 0, y = 0;
        vector<int> res;
        int row = mat.size(), col = mat[0].size();
        bool flag = true;
        while(true){
            cout << x << "," << y << "      " << flag << endl;
            res.push_back(mat[x][y]);
            if (x == row - 1 && y == col - 1 ) break;
            else if(flag) {  // flag 为true时向右上角
                if(y == col - 1){
                    x ++;
                    flag = false;
                }
                else if(x == 0) {
                    y ++;
                    flag = false;
                } else {
                    x --;
                    y ++;
                }
                
            } else {
                if(x == row - 1) {
                    y ++;
                    flag = true;
                }
                else if (y == 0) {
                    x ++;
                    flag = true;
                }
                else {
                    x ++;
                    y --;
                }
            }
            
        }
        return res;
    }
};
  • 时间复杂度：O(n + m)，其中 n 是数组行数，m是数组列数
  • 空间复杂度：O(1)

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

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

通过测试用例：32 / 32

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

之前学习过java知识，但都只是会用，对一些概念及一些部分的注意事项不是很清楚，所以现在系统的过一遍java知识。

阅读全文 »

发表于 分类于
本文字数： 902 阅读时长 ≈ 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
class Solution {
public:
    bool dfs(int index, vector<int> &matchsticks, vector<int> &edges, int len) {
        if (index == matchsticks.size()) {
            return true;
        }
        for (int i = 0; i < edges.size(); i++) {
            edges[i] += matchsticks[index];
            if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len)) {
                return true;
            }
            edges[i] -= matchsticks[index];
        }
        return false;
    }

    bool makesquare(vector<int> &matchsticks) {
        int totalLen = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (totalLen % 4 != 0) {
            return false;
        }
        sort(matchsticks.begin(), matchsticks.end(), greater<int>()); // 减少搜索量

        vector<int> edges(4);
        return dfs(0, matchsticks, edges, totalLen / 4);
    }
};
  • 时间复杂度：O(4 ^ n)，其中 n 是数组中元素的个数
  • 空间复杂度：O(n)，递归栈需要占 O(n) 的空间

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

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

通过测试用例：185 / 185

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

题目1：字母在字符串中的百分比

字母在字符串中的百分比

标签

字符串

思路

遍历一遍字符串，统计目标字符的个数，然后先乘100再除以字符串的大小。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int percentageLetter(string s, char letter) {
        int n = s.size();
        float num = 0;
        for(int i = 0; i < n; i++){
            if(s[i] == letter)
                num ++;
        }
        // cout << n << " " << num << endl;
        return num * 100 / n;
    }
};
  • 时间复杂度：O(n)，其中 n 为字符串 s 的大小
  • 空间复杂度：O(1)

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

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

通过测试用例：85 / 85

题目2：装满石头的背包的最大数量

装满石头的背包的最大数量

标签

数组、排序

思路

先计算出每个背包剩余的空间并保存至一个数组中，然后将该数组从小到大进行排序，遍历一遍，若当前位置的元素小于额外的石头数量，并且额外的石头数量大于0，则将 additionalRocks -= arr[i] 并且装满石头的背包数加一。

题解

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
class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        vector<int> arr;
        for(int i = 0; i < capacity.size(); i++){
            arr.push_back(capacity[i] - rocks[i]);
        }
        sort(arr.begin(), arr.end());
        int nums = 0;
        for(int i = 0; i < arr.size(); i++){
            if(arr[i] == 0) {
                nums ++;
                continue;
            }
            if(additionalRocks > 0 && additionalRocks >= arr[i]){
                additionalRocks -= arr[i];
                nums++;
            }
            else{
                break;
            }
        }
        return nums;
    }
};
  • 时间复杂度：O(n \ logn)，其中 n* 为数组的大小，排序耗时。
  • 空间复杂度：O(n)，需要一个额外的数组保存每个背包剩余的空间。

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

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

通过测试用例：79 / 79

题目3：表示一个折线图的最少线段数

表示一个折线图的最少线段数

标签

数组、排序、数学

思路

先将所有的点按照横坐标从小到大进行排序，直接使用 sort(stockPrices.begin(), stockPrices.end()); 进行排序即可。然后遍历一遍函数，每次计算当前元素和前一元素组成的线段的斜率是否和前一段斜率相同，若不同，则结果加一。需要使用一个变量记录前一斜率，再不相同时更新该变量。

sort(stockPrices.begin(), stockPrices.end());，默认按照数组的第一列进行升序排序。

sort(stockPrices.rbegin(), stockPrices.rend());，默认按照数组的第一列进行降序排列。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minimumLines(vector<vector<int>>& stockPrices) {
        if(stockPrices.size() == 1) return 0;
        else if(stockPrices.size() == 2) return 1;

        sort(stockPrices.begin(), stockPrices.end());
        int res = 0;
        long double pre = 2e9;
        for(int i = 1; i < stockPrices.size(); i++){
            int x1 = stockPrices[i - 1][0], y1 = stockPrices[i - 1][1];
            int x2 = stockPrices[i][0], y2 = stockPrices[i][1];
            long double cur = (long double)(y2 - y1) / (long double)(x2 - x1);
            if(cur != pre){
                res ++;
                pre = cur;
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n \ logn)，其中 n* 为数组的大小，排序耗时。
  • 空间复杂度：O(1)

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

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

通过测试用例：79 / 79

题目4：巫师的总力量和

巫师的总力量和

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

题目

在长度 2N 的数组中找出重复 N 次的元素

思路

利用哈希表统计每个数字出现的次数，若次数等于 nums.size() / 2则返回该数字。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        int n = nums.size() / 2;
        unordered_map<int, int> hsp;
        for(int i = 0; i < nums.size(); i++){
            hsp[nums[i]] ++;
        }
        for(auto it = hsp.begin(); it != hsp.end(); it++){
            if(it->second == n)
                return it->first;
        }
        return 0;
    }
};
  • 时间复杂度：O(n)，其中 n 是数组中元素的个数
  • 空间复杂度：O(n)，

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

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

通过测试用例：102 / 102

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

题目

最少移动次数使数组元素相等 II

思路

排序后寻找中间位置的值，如果数组元素个数是奇数，则直接取中间值，如果是偶数，则取中间两值的平均值，然后遍历一遍数组，每次计算当前元素和中间值差的绝对值并加入到结果中。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int x;
        int res = 0;
        if(n % 2) { // 奇数
            x = nums[n / 2];
        }
        else{
            int r = nums[n / 2];
            int l = nums[n / 2 - 1];
            x = (r + l) / 2;
        }
        for(int i = 0; i < n; i++){
            res += abs(nums[i] - x);
        }
        return res;
    }
};
  • 时间复杂度：O(n \ logn)，其中 n 是数组中元素的个数，排序时间复杂度是O(n * logn)，计算时间复杂度是O(n)，所以总的时间复杂度是O(n * logn)*
  • 空间复杂度：O(1)

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

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

通过测试用例：30 / 30

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

题目

验证外星语词典

思路

暴力解法：将 words中的单词按照 order 的字典序进行排序后与原数组进行对比，若相同则返回 true，若存在不同则返回 false

题解

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
class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> hsp;
        int num = 0;
        for(int i = 0; i < order.size(); i++){
            hsp[order[i]] = num ++;
        }
        vector<string> arr;
        for(int i = 0; i < words.size(); i++){
            arr.emplace_back(words[i]);
        }
        sort(arr.begin(), arr.end(), [&](string &a, string &b){
            int len_a = a.size();
            int len_b = b.size();
            int len = min(len_a, len_b);
            for(int i = 0; i < len; i++){
                if(a[i] == b[i]) continue;
                return hsp[a[i]] < hsp[b[i]];
            }
            return len_a < len_b;
        });
        for(int i = 0; i < arr.size(); i++){
            if(arr[i] != words[i])
                return false;
        }
        return true;
    }
};
  • 时间复杂度：O(n \ logn)，其中 n* 是数组中元素的个数
  • 空间复杂度：O(n)，需要另外一个数组保存排序后的words

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

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

通过测试用例：120 / 120

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

题目1：移除字母异位词后的结果数组

移除字母异位词后的结果数组

标签

排序、数组、字符串

思路

先将 words 中的每个字符串进行排序，然后逆序遍历，若当前字符串和前一字符串相等，则删除原数组中的该位置的字符串。最后返回原数组

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<string> removeAnagrams(vector<string>& words) {
        vector<string> arr;
        for(int i = 0; i < words.size(); i++){
            string str = words[i];
            sort(str.begin(), str.end());
            arr.emplace_back(str);
        }
        for(int i = arr.size() - 1; i > 0; i --){
            if(arr[i] == arr[i - 1]){
                words.erase(words.begin() + i);
            }
        }
        return words;
    }
};
  • 时间复杂度：O(n)，其中 n 为数组 words 的大小
  • 空间复杂度：O(n)，保存每个字符串排序后的数组

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

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

通过测试用例：201 / 201

题目2：不含特殊楼层的最大连续楼层数

不含特殊楼层的最大连续楼层数

标签

数组、排序、数学

思路

将特殊楼层数组 special 进行排序，然后分别计算每两个特殊楼层之间的楼层数，取最大值。然后再和两端的楼层数作比较，取最大值。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxConsecutive(int bottom, int top, vector<int>& special) {
        sort(special.begin(), special.end());
        int res = 0;
        int n = special.size();
        for(int i = 1; i < special.size(); i ++){
            res = max(res, special[i] - special[i - 1] - 1);
        }
        // 两端的楼层计算
        res = max(res, special[0] - bottom);
        res = max(res, top - special[n - 1]); 
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 为数组 special 的大小
  • 空间复杂度：O(1)

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

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

通过测试用例：80 / 80

题目3：按位与结果大于零的最长组合

按位与结果大于零的最长组合

题目4：统计区间中的整数数目

统计区间中的整数数目

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

题目

后继者

思路

直接进行中序遍历，当找到指定节点时，让 loop = true，然后继续递归，若loop && !res 时，则赋值，否则 return

题解

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *res = NULL;
    bool loop = false;
    void InorderTra(TreeNode *root, TreeNode* p){
        if(root == NULL) return;
        InorderTra(root->left, p);
        if(loop){  // 已经找到指定节点
            if(res == NULL)  // 下一节点还没确定
                res = root;
            else  // 下一节点已经确定
                return;
        }
        else if(root == p) loop = true;
        InorderTra(root->right, p);
    }
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        InorderTra(root, p);
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 是二叉树中节点的个数
  • 空间复杂度：O(1)

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

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

通过测试用例：24 / 24