Atopos's Blog

One step at a time!

0%

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

题目

标签验证器

思路

如果当前字符为 <，需要考虑下面四种情况：

  • 如果下一个字符为 /，那么说明我们遇到了一个结束标签。我们需要定位下一个 > 的位置 j，此时 code[i+2..j−1] 就是该结束标签的名称。我们需要判断该名称与当前栈顶的名称是否匹配，如果匹配，说明名称的标签已经闭合，我们需要将当前栈顶的名称弹出。同时根据规则 1，我们需要保证整个 code 被闭合标签包围，因此如果栈中已经没有标签，但是 j 并不是 code 的末尾，那么说明后续还会有字符，它们不被闭合标签包围。
  • 如果下一个字符为 !，那么说明我们遇到了一个 cdata，我们需要继续往后读 77 个字符，判断其是否为 \texttt{[CDATA[}[CDATA[。在这之后，我们定位下一个 ]]> 的位置 j，此时 code[i+9..j−1] 就是 cdata 中的内容，它不需要被解析，所以我们也不必进行任何验证。需要注意的是，根据规则 1，栈中需要存在至少一个开放的标签。
  • 如果下一个字符为大写字母，那么说明我们遇到了一个开始标签。我们需要定位下一个 > 的位置 j，此时 code[i+2..j−1] 就是该开始标签的名称。我们需要判断该名称是否恰好由 1 至 9 个大写字母组成，如果是，说明该标签合法，我们需要将该名称放入栈顶。
  • 除此之外，如果不存在下一个字符，或者下一个字符不属于上述三种情况，那么 code 是不合法的。

如果当前的字符为其它字符，那么根据规则 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
44
45
46
47
class Solution {
public:
    bool isValid(string code) {
        stack<string> stk;
        int i = 0, n = code.size();
        while(i < n){
            if(code[i] == '<'){  // 当前字符为 <
                if(i == n - 1) return false;
                else if(code[i + 1] >= 'A' && code[i + 1] <= 'Z'){  // 下一个字符是大写字母
                    int j = code.find('>', i);  // 从i开始找，找到第一个 >，并返回其下标
                    if(j == string::npos) return false;  // 不存在 >
                    string str = code.substr(i + 1, j - i - 1);
                    if(str.length() < 1 || str.length() > 9) return false;  // 判断长度是否合法
                    for(int k = 0; k < str.size(); k ++){  // 判断是否全为大写字母
                        if(str[k] < 'A' || str[k] > 'Z')
                            return false;
                    }
                    stk.push(str);
                    i = j + 1;
                }
                else if(code[i + 1] == '/'){
                    int j = code.find('>', i);
                    if(j == string::npos) return false;
                    string str = code.substr(i + 2, j - i - 2);
                    if(stk.empty() || stk.top() != str) return false;  // 如果栈顶元素为空 或者 和栈顶元素不匹配
                    stk.pop();
                    i = j + 1;
                    if(stk.empty() && i != n) return false; // 如果栈为空，但是还没遍历到字符串末尾
                }
                else if(code[i + 1] == '!'){
                    if(stk.empty()) return false;
                    string str = code.substr(i + 2, 7);  // 往后读7个字符
                    if(str != "[CDATA[") return false;
                    int j = code.find("]]>", i);
                    if(j == string::npos) return false;
                    i = j + 1;
                }
                else return false;
            }
            else{
                if(stk.empty()) return false; // 当前字符为其他字符，但是栈为空了，
                i++;
            }
        }
        return stk.empty(); // 可能还存在栈最后还不空的情况
    }
};
  • 时间复杂度：O(n)，其中 n 为 code 的长度，我们只需要对 code 进行一次遍历。
  • 空间复杂度：O(n)，即为栈存储标签名称需要使用的空间。

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

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

通过测试用例：260 / 260

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

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

阅读全文 »

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

题目

两颗二叉搜索树中的所有元素

思路 1

先前序遍历两个二叉搜索树，将所有节点的值存放至vector<int>中，然后在进行排序。

思路 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
/**
 * 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:
    vector<int> res;
    // 二叉树的前序遍历
    void preTraverse(TreeNode* root) {
        if(root == nullptr) return;
        res.push_back(root->val);
        preTraverse(root->left);
        preTraverse(root->right);
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        preTraverse(root1);
        preTraverse(root2);
        sort(res.begin(), res.end());
        return res;
    }
};
  • 时间复杂度：O((n + m) \ log(n + m))，其中 n 和 m* 分别为两棵二叉搜索树的节点个数。
  • 空间复杂度：O(n + m)

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

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

通过测试用例：48 / 48

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
/**
 * 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:
    vector<int> res;
    // 中序遍历
    void InoTraversal(TreeNode* root, vector<int>& nums){
        if(root == nullptr) return;
        InoTraversal(root->left, nums);
        nums.push_back(root->val);
        InoTraversal(root->right, nums);       
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> nums1, nums2;
        InoTraversal(root1, nums1);
        InoTraversal(root2, nums2);

        int i = 0, j = 0;
        while(i < nums1.size() && j < nums2.size()){
            if(nums1[i] < nums2[j])
                res.push_back(nums1[i++]);
            else
                res.push_back(nums2[j++]);
        }
        while(i < nums1.size()) res.push_back(nums1[i++]);
        while(j < nums2.size()) res.push_back(nums2[j++]);

        return res;
    }
};
  • 时间复杂度：O((n + m))，其中 n 和 m 分别为两棵二叉搜索树的节点个数。
  • 空间复杂度：O(n + m)

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

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

通过测试用例：48 / 48

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

题目

最小差值 1

思路

先找到数组中的最大值和最小值，然后用二者的差在减去 2 * k，若小于等于 0，则结果为 0，否则，结果为差值。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int min = 10000, max = 0;
        for(int i = 0; i < nums.size(); i++){
            if(min > nums[i])  // 找最小值
                min = nums[i];
            if(max < nums[i])  // 找最大值
                max = nums[i];
        }
        if(max - min <= k * 2){
            return 0;
        }
        return (max - min - k * 2);
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

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

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

通过测试用例：48 / 48

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

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

阅读全文 »

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

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

阅读全文 »

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

根据AcWing平台上LeetCode究极课以及LeetCode平台进行刷题，部分解题思路和方法来自AcWing算法交流平台或者LeetCode平台。

阅读全文 »

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

根据AcWing平台上LeetCode究极课以及LeetCode平台进行刷题，部分解题思路和方法来自AcWing算法交流平台或者LeetCode平台。

阅读全文 »