Atopos's Blog

One step at a time!

0%

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

题目

最大三角形面积

思路

暴力解法：三重循环。主要是计算三角形面积的公式

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    double triangleArea(int x1, int y1, int x2, int y2, int x3, int y3) {
        return 0.5 * abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2);
    }

    double largestTriangleArea(vector<vector<int>> & points) {
        int n = points.size();
        double ret = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ret = max(ret, triangleArea(points[i][0], points[i][1], points[j][0], points[j][1], points[k][0], points[k][1]));
                }
            }
        }
        return ret;
    }
};
  • 时间复杂度：O(n ^ 3)，其中 n 是数组中元素的个数
  • 空间复杂度：O(1)

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

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

通过测试用例：57 / 57

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

题目

删除排序链表中的重复元素 II

思路

首先再原有的链表前面插入一个新的节点，可以减少头指针变化。若 cur->next->val == cur->next->next->val 则删除 cur->next,然后依次判断，将所有重复的节点全部删除。

题解

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 singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* dummy = new ListNode(0, head);
        ListNode* cur = dummy;
        while(cur->next && cur->next->next){
            if(cur->next->val == cur->next->next->val){
                int x = cur->next->val;  // 记录下一节点的值
                while (cur->next && cur->next->val == x) { // 循环删除和下一节点值相等的所有节点
                    cur->next = cur->next->next;
                }
            }
            else{
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};
  • 时间复杂度：O(n)，其中 n 是链表中节点的个数，最多遍历一遍链表
  • 空间复杂度：O(n)，使用新的链表进行遍历

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

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

通过测试用例：166 / 166

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

题目

一次编辑

思路

分类讨论：

  • 当两个字符串相等时，直接返回 True
  • 当两个字符串的长度相差超过2时，直接返回 False
  • 当两个字符串长度相差为 1 时，则调用函数判断是否只存在一处编辑
  • 当两个字符串长度相等时，遍历一遍字符串，判断每个位置的字符是否相等，若不相等的个数大于 1 时，则返回 False ，否则返回 True

题解

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
class Solution {
public:
    // a 是较大的字符串，b是较小的字符串
    bool isDelete(string a, string b){
        for(int i = 0; i < a.size(); i++){
            string str = a;
            str.erase(i, 1);  // 删除一个字符
            if(str == b) return true;
        }
        return false;
    }

    bool oneEditAway(string first, string second) {
        int firstLen = first.size();
        int secondLen = second.size();
        if(first == second) return true; 
        else if(abs(firstLen - secondLen) > 1) return false;
        else if(abs(firstLen - secondLen) == 1) { // 插入或者删除一个字符
            if(firstLen > secondLen)
                return isDelete(first, second);
            else
                return isDelete(second, first);
        }
        else {
            int num = 0;
            for(int i = 0; i < first.size(); i++){
                if(first[i] != second[i]){
                    num ++;
                }
            }
            return num == 1 || num == 0 ? true : false;
        }
    }
};
  • 时间复杂度：O(n)，其中 n 是字符串的长度，最多遍历一遍字符串
  • 空间复杂度：O(n)，判断是否删除时，需要找一个临时变量存储字符串

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

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

通过测试用例：1146 / 1146

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

题目

成绩排序2

思路

自定义 sort 排序

题解

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
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;
int n;

int main(){
    cin >> n;
    vector<pair<int, int>> arr;
    for(int i = 0; i < n; i ++){
        int a, b;
        cin >> a >> b;
        arr.emplace_back(make_pair(a, b));
    }
    // 自定义排序
    sort(arr.begin(), arr.end(), [](pair<int,int> &a, pair<int, int> &b){
        if(a.second != b.second) 
            return a.second < b.second;
        else
            return a.first < b.first;
    });
    for(int i = 0; i < arr.size(); i++){
        cout << arr[i].first << " " << arr[i].second << endl;
    }
    return 0;
}
  • 时间复杂度：O(n \ logn)，其中 n* 是学生的个数
  • 空间复杂度：O(1)

执行用时：18 ms

内存消耗：220KB

通过测试用例：10/10

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

题目

成绩排序

思路

使用 stable_sort 进行排序，因为 stable_sort 是稳定的，可确保不需要排序的数据相对位置不改变。

题解

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
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;
const int N = 110;
int n, x;

// stable_sort 使用
void minTomax(vector<pair<string, int>>& arr){
    stable_sort(arr.begin(), arr.end(), [&](const pair<string, int> &a, const pair<string, int> &b){
        return a.second < b.second; 
    });
}
void maxTomin(vector<pair<string, int>>& arr){
    stable_sort(arr.begin(), arr.end(), [&](const pair<string, int> &a, const pair<string, int> &b){
        return a.second > b.second; 
    });
}

int main(){
    cin >> n;
    cin >> x;
    vector<pair<string, int>> arr;
    for(int i = 0; i < n; i++){
        string a;
        int b;
        cin >> a >> b;
        arr.emplace_back(make_pair(a, b));
    }
    if(x == 0) maxTomin(arr);
    else minTomax(arr);
    for(int i = 0; i < arr.size(); i++){
        cout << arr[i].first << " " << arr[i].second << endl;
    }
    return 0;
}
  • 时间复杂度：O(n \ logn)，其中 n* 是学生的个数
  • 空间复杂度：O(1)

执行用时：31 ms

内存消耗：340KB

通过测试用例：10/10

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

题目

删列造序

思路

暴力解法：遍历二维数组，先遍历列，再遍历行。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int res = 0;
        for(int i = 0; i < strs[0].size(); i++){
            for(int j = 1; j < strs.size(); j ++){
                if(strs[j][i] < strs[j - 1][i]){
                    res ++;
                    break;
                }
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n \ m)，其中 n* 是字符串的个数，m是每个字符串的长度
  • 空间复杂度：O(1)

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

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

通过测试用例：85 / 85

发表于 分类于
本文字数： 2.7k 阅读时长 ≈ 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
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        vector<int> arr;
        postTraversal(root, arr);
        if(arr.size() == 0) return res;
        for(int i = 0; i < arr.size(); i++){
            res += to_string(arr[i]) + ",";
        }
        return res.substr(0, res.size() - 1);
    }

    void postTraversal(TreeNode* root, vector<int> &arr){
        if(root == NULL) return ;
        postTraversal(root->left, arr);
        postTraversal(root->right, arr);
        arr.emplace_back(root->val);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        TreeNode* root;
        vector<int> arr;
        transArr(data, arr);
        if(arr.size() == 0) {
            root = NULL;
            return root;
        }
        // int n = arr.size();
        // root->val = arr[n - 1];
        root = dfs(arr);
        return root;
    }

    void transArr(string data, vector<int> &arr){  // 将string 拆分为整数数组
        int npc = 0;
        for(int i = 0; i < data.size(); i++){
            if(i == data.size() - 1){
                string str = data.substr(npc, i - npc + 1);
                arr.emplace_back(stoi(str));
                npc = i + 1;
            }
            else if(data[i] == ','){
                string str = data.substr(npc, i - npc);
                arr.emplace_back(stoi(str));
                npc = i + 1;
            }
        }
    }
    TreeNode* dfs(vector<int> arr){
        if(arr.size() == 0){
            return NULL;
        }
        int n = arr.size();
        int npc = arr[n - 1];
        TreeNode* root = new TreeNode(npc);
        if(n == 1) return root;

        int x = find(arr, npc); // 寻找最后一个小于 根节点的下标，则x左边的都是该节点的左子树，右边的都是该节点的右子树
        if(x >= 0){  
            root->left = dfs(vector<int>(arr.begin(), arr.begin() + x));
        }
        if(x <= n - 2){
            root-> right = dfs(vector<int>(arr.begin() + x, arr.begin() + n - 1));
        }
        return root;
    }

    int find(vector<int> arr, int x){
        for(int i = 0; i < arr.size() - 1; i ++){
            if(arr[i] > x){
                return i;
            }
        }
        return arr.size() - 1;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;
  • 时间复杂度：O(n)，其中 n 是树的节点个数，serialize 需要 O(n) 时间遍历每个点。deserialize 需要 O(n) 时间恢复每个点
  • 空间复杂度：O(n)，其中 n 是树的节点个数，serialize 需要 O(n) 空间数组保存每个点的值，递归的深度最深也为 O(n)。deserialize 需要 O(n) 空间用数组保存每个点的值，递归的深度最深也为 O(n)。

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

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

通过测试用例：62 / 62

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

题目

数组中重复的数据

思路

使用 unordered_map 保存每个整数出现的次数，最后遍历一遍哈希表，将整数出现次数为 2 的整数存入结果数组中。

题解

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

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

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

通过测试用例：28 / 28

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

题目1：字符串中最大的 3 位相同数字

字符串中最大的 3 位相同数字

标签

字符串

思路

遍历一遍数组，每次从第 i 个位置截取长度为 3 字符串，然后判断字符串是否符合要求，若符合，则更新结果。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string largestGoodInteger(string num) {
        string res = "";
        for(int i = 0; i < num.size() - 2; i ++){
            string str = num.substr(i, 3);
            if(str[0] == str[1] && str[1] == str[2] && res < str){
                res = str;
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 为 字符串 num 的长度
  • 空间复杂度：O(1)

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

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

通过测试用例：140 / 140

题目2：统计值等于子树平均值的节点数

统计值等于子树平均值的节点数

标签

二叉树、后序遍历、pair

思路

  1. 递归函数与返回值
    • 用pair作为返回值记录以当前节点为根的子树的总值与节点个数
    • pair<int,int> getAvgVal(TreeNode* root){}
  2. 递归函数出口
    • 如果遇到空节点 返回{0,0}
    • if(root==nullptr) return {0,0};
  3. 单层递归逻辑
    • 用l_pair接住遍历过程中左子树的 pair<>;
    • 用r_pair接住遍历过程中右子树的 pair<>;
    • 计算当前节点的 pair<>;
    • 判断当前节点是否符合条件，++ans;
    • 返回当前节点的 pair<>;

题解

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
/**
 * 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 {
public:
    int res = 0;
    // 总数，个数
    pair<int, int> getAvgVal(TreeNode* root){
        if(root == nullptr) return {0, 0};
        pair<int, int> pair_l = getAvgVal(root->left);
        pair<int, int> pair_r = getAvgVal(root->right);

        int sum = pair_l.first + pair_r.first + root->val;
        int count = pair_l.second + pair_r.second + 1;

        pair<int, int> cur = {sum, count};
        if(sum / count == root->val) res++;
        return cur;
    }
    int averageOfSubtree(TreeNode* root) {
        pair<int, int> per = getAvgVal(root);
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 为 二叉树中的节点个数
  • 空间复杂度：O(1)

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

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

通过测试用例：140 / 140

题目3：统计打字方案数

统计打字方案数

题目4：检查是否有合法括号字符串路径

检查是否有合法括号字符串路径

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

题目

增减字符串匹配

思路

定义两个变量，l 表示最小值0，h表示最大值 s.size(),然后遍历当前元素，若当前元素是 I，则当前位置需要赋值 l并更新l的值，反之，则赋值h的值，并更新h的值。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size();
        int l = 0, h = s.size();
        vector<int> res(n + 1);
        for(int i = 0; i < s.size(); i++){
            if(s[i] == 'I')  // 当前字符是 I 时，添加此时最小的
                res[i] = l ++;
            else  // 当前字符是 D 时，添加此时最大的
                res[i] = h --;
        }
        res[n] = l; // 添加最后一个数
        return res;
    }
};
  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度
  • 空间复杂度：O(1)，数组长度 为 n + 1，但返回值不计入空间复杂度

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

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

通过测试用例：95 / 95