一：字符串解码

image-20251015110933583

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
class Solution {
public:
    string decodeString(string s) {
        vector<string> stk;
        int cur = 0;
        string digits;
        while (cur < s.size())
        {
            char ch = s[cur];
            if (isdigit(ch))
            {
                digits = GetDigits(s, cur, digits);
                stk.push_back(digits);
            } else if (isalpha(ch) || ch == '[')
                stk.push_back(string(1, s[cur++]));
            else
            {
                ++cur;      // ]直接略过
                string sub;
                string temp;
                while (stk.back() != "[")
                {
                    sub = stk.back() + sub;
                    stk.pop_back();
                }
                //reverse(sub.begin(), sub.end());
                stk.pop_back();     // 左括号略过
                int count = stoi(stk.back());
                stk.pop_back(); 
                while (count--) temp += sub;
                stk.push_back(temp);
            }
        }
        string result;
        for (auto& s : stk) result += s;
        return result;
    }
    string& GetDigits(string& s, int& cur, string& digits)
    {
        digits.clear();
        while (isdigit(s[cur])) digits.push_back(s[cur++]);
        return digits;
    }
};

image-20251015111026009

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
class Solution {
public:
    string s;
    int cur = 0;
    string decodeString(string s) {
        this->s = s;
        return GetString();
    }
    int GetDigits()
    {
        string digits;
        while (isdigit(s[cur])) digits.push_back(s[cur++]);
        return stoi(digits);
    }
    string GetString()
    {
        if (cur == s.size() || s[cur] == ']') return "";
        char ch = s[cur];
        string sub;
        if (isdigit(ch))
        {
            int repeatTime = GetDigits();
            ++cur;
            string str = GetString();
            ++cur;
            while (repeatTime--) sub += str;
        } else if(isalpha(ch))
        {
            sub = string(1, ch);
            ++cur;
        }
        return sub + GetString();
    }
};

image-20251015111004436

二：每日温度

image-20251015154135124

1. 暴力

该题通过使用一个温度数组来记录当前温度的索引，其中温度为下标，值为数组中的索引，通过向前遍历来记录温度的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int len = temperatures.size();
        vector<int> result(len);
        vector<int> record(101, INT_MAX);
        for (int i = len - 1; i >= 0; --i)
        {
            int index = INT_MAX;
            for (int j = temperatures[i] + 1; j <= 100; ++j)
                index = min(index, record[j]);
            if (index != INT_MAX)
                result[i] = (index - i);
            record[temperatures[i]] = i;
        }
        return result;
    }
};

2. 单调栈

使用一个栈来维护温度，使温度递减，如果温度大于栈顶，则把栈顶弹出，并更新天数，因为此时为栈顶索引遇到的第一个升温天气

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int len = temperatures.size();
        vector<int> result(len);
        stack<int> stk;
        int temp;
        for (int i = 0; i < len; ++i)
        {
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()])
            {
                temp = stk.top();
                stk.pop();
                result[temp] = i - temp;
            }
            stk.push(i);
        }
        return result;
    }
};

image-20251015234359703

三：数组中的第K个最大元素

image-20251016105940309

1. 基于快速排序的选择方法

寻找第K大的元素意味着寻找第n - 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 findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        return QuickChoose(nums, len - k, 0, len - 1);
    }
    int QuickChoose(vector<int>& nums, int index, int left, int right)
    {
        if (left == right) return nums[left];
        int i = left - 1;
        int j = right + 1;
        int numFlag = nums[left];
        while (i < j)
        {
            do ++i; while (nums[i] < numFlag);
            do --j; while (nums[j] > numFlag);
            if (i < j) swap(nums[i], nums[j]);
        }
        if ( index <= j) return QuickChoose(nums, index, left, j);
        else return QuickChoose(nums, index, j + 1, right);
    }
};

image-20251016110038756

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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size(), size = len;
        BuildHeap(nums, len);
        for (int i = len - 1; i > len - k; --i)
        {
            swap(nums[0], nums[i]);
            --size;
            Heapify(nums, size, 0);
        }
        return nums[0];
    }
    void BuildHeap(vector<int>& nums, int size)
    {
        for (int i = size / 2 - 1; i >= 0; --i)
            Heapify(nums, size, i);
    }
    void Heapify(vector<int>& nums, int size, int cur)
    {
        int leftNode = cur * 2 + 1;
        int rightNode = cur * 2 + 2;
        int largest = cur;
        if (leftNode < size && nums[leftNode] > nums[largest]) largest = leftNode; 
        if (rightNode < size && nums[rightNode] > nums[largest]) largest = rightNode; 
        if (cur != largest)
        {
            swap(nums[largest], nums[cur]);
            Heapify(nums, size, largest);
        }
    }
};

image-20251016110030428