一：划分字母区间

image-20251018203308526

1. 贪心

该题的思路为通过遍历字符串，得到每一个字符最后出现的位置，然后维护一个起始指针，再次遍历字符串更新结束位置，如果达到end则意味着这个子字符串可划分

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<int> partitionLabels(string s) {
        int array[26];
        int len = s.size();
        vector<int> result;
        for (int i = 0; i < len; ++i)
            array[static_cast<int>(s[i] - 'a')] = i;
        int start = 0, end = 0;
        int size = 0;
        for (int i = 0; i < len; ++i)
        {
            size = max(size, array[static_cast<int>(s[i] - 'a')]);
            end = size;
            if (i == end)
            {
                result.emplace_back(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
};

image-20251018205942356

二：颜色分类

image-20251018215743536

1. 单指针

使用该方式需要两次遍历，一次用于交换0，一次用于交换1，交换其他数据也可以

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:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        int cur = 0;
        for (int i = 0; i < len; ++i)
        {
            if (nums[i] == 0) 
            {
                swap(nums[i], nums[cur]);
                ++cur;
            }
        }
        for (int i = 0; i < len; ++i)
        {
            if (nums[i] == 1) 
            {
                swap(nums[i], nums[cur]);
                ++cur;
            }
        }
    }
};

image-20251018215923616

2. 双指针

使用双指针可以同时交换两个数据，比如同时交换0和1，但需要注意交换顺序和对后续交换的影响

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:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        int cur0 = 0, cur1 = 0;
        for (int i = 0; i < len; ++i)
        {
            if (nums[i] == 1) 
            {
                swap(nums[i], nums[cur1]);
                ++cur1;
            }
            if (nums[i] == 0) 
            {
                swap(nums[i], nums[cur0]);
                if (cur0 < cur1) 
                    swap(nums[i], nums[cur1]);
                ++cur0;
                ++cur1;
            }
        }
    }
};

image-20251018215907942

3. 双指针

这里我们使用两端用于交换，但是交换之后的数据可能仍然需要交换，因此需要额外处理，知道它不需要交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        int cur0 = 0, cur2 = len - 1;
        for (int i = 0; i <= cur2; ++i)
        {
            while (i <= cur2 && nums[i] == 2)
            {
                swap(nums[i], nums[cur2]);
                --cur2;
            }
            if (nums[i] == 0) 
            {
                swap(nums[i], nums[cur0]);
                ++cur0;
            }
        }
    }
};

image-20251018215848296

4. 直接遍历

该题最简单的方式是将数组遍历得到每个元素的数量然后修改原来的数组即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red = 0, white = 0, blue = 0;
        int len = nums.size();
        for (int i = 0; i < len; ++i)
        {
            if (nums[i] == 0) ++red;
            if (nums[i] == 1) ++white;
            if (nums[i] == 2) ++blue;
        }
        for (int i = 0; i < len; ++i)
        {
            if (i < red) nums[i] = 0;
            if (i >= red&& i < red + white) nums[i] = 1;
            if (i >= red + white && i < red + white + blue) nums[i] = 2;
        }
    }
};

image-20251018221217680

三：下一个排列

image-20251018223640283

1. 两遍扫描

该题需要从后向前找到第一个升序的位置，然后将其与该位置之后的最后一个大于自己的数据进行交换，同时需要对该位置之后的数据重排为升序

下一个排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        int start = len - 2;
        while (start >= 0 && nums[start] >= nums[start + 1])
            --start;
        if (start >= 0)
        {
            int j = len - 1;
            while (j >= 0 && nums[j] <= nums[start])
                --j;
            swap(nums[start], nums[j]);
        }
        reverse(nums.begin() + start + 1, nums.end());
    }
};

image-20251018223724498