算法刷题周记01

1.两数之和(简单)

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

进阶：你可以想出一个时间复杂度小于 O(n^2^) 的算法吗？

解法(暴力法)

个人第一想法：肯定是直接暴力法最简单，虽然时间会比较慢。

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        vector index(2); // 存放结果
        for(int i = 0;i < nums.size(); i++){
            for(int j = i + 1;j < nums.size(); j++){
                if(nums[j] + nums[i] == target){
                    index[0] = i;
                    index[1] = j;
                    break;
                }
            }
        }
        return index;
    }
}; 

解法(计算补数)

在看完其他各路大神的解法之后，豁然开朗。原来可以通过map来提高效率。

map中以数组的值为key，以数组的下标为value。然后两次遍历：第一次给映射表赋值，第二次查找对应的数。

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        map m; // 数组的映射表, 值为key, 下标为value
        vector index(2);
        for(int i = 0;i < nums.size();i++){
            m.insert(pair (nums[i],i));
        }
        for(int i = 0;i 0 && m[target - nums[i]] != i)
            {
                index[0] = i;
                index[1] = m[target - nums[i]];
                break;
            }
        }
        return index;
    }
};

优化：一次遍历。注意此时判断不是当前数本身的条件就可以去掉了，因为只有在判断以后才会在映射表中插入，所以补数必定不是当前数本身。

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        map m; // 数组的映射表, 值为key, 下标为value
        vector index(2);
        for(int i = 0;i0)
            {
                index[0] = i;
                index[1] = m[target - nums[i]];
                break;
            }
            m.insert(pair (nums[i],i));
        }
        return index;
    }
};

2.两两交换链表中的节点(中等)

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

解法(三个指针)

/*
  * 思路：三个指针：pre,p1,p2  p1 为奇数位结点， p2 为偶数位结点， pre 为 上一次交换的最后一个结点
          当偶数位结点不为空，触发交换
          当偶数位结点为空，就不用动
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(NULL == head || NULL == head->next){//确保最少两个结点
            return head;
        }
        ListNode *pre = NULL,*p1 = head,*p2;
        head = p1 -> next;
        while(p1 != NULL)// p1 表示两两交换的第一个结点
        {
            p2 = p1 -> next; // p2 表示两两交换的第二个结点
            if(p2 != NULL) 
            {
                p1 -> next = p2 -> next;
                p2 -> next = p1;
                if(pre != NULL){ // pre 表示 p1 的前一个结点
                    pre->next = p2;
                }
            }
            pre = p1;
            p1 = p1 -> next;
        }
        return head;
    }
};

3.删除有序数组中的重复项(简单)

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前k个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]

解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]

解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

解法（快慢指针）：

/*
*   本质：快慢指针，一个一直跑，一个根据条件跑
*/
class Solution {
public:
    int removeDuplicates(vector& nums) {
        if(nums.size() == 0 || nums.empty()){return 0;}
        int p = 0, q = 1;
        while(q < nums.size())
        {
            if(nums[p] != nums[q]){
                nums[p+1] = nums[q];
                p++; 
            }
            q++;
        }
        return p+1;
    }
};

4.水壶问题（中等偏难）

有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。

如果可以得到 targetCapacity 升水，最后请用以上水壶中的一或两个来盛放取得的 targetCapacity 升水。

你可以：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1:

输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
输出: true
解释：来自著名的 "Die Hard"

示例 2:

输入: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
输出: false

示例 3:

输入: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
输出: true

这题很有意思，虽然我没做出来。。。

贴上官方解法：

解法一：深度优先搜索

思路及算法

首先对题目进行建模。观察题目可知，在任意一个时刻，此问题的状态可以由两个数字决定：X 壶中的水量，以及 Y 壶中的水量。

在任意一个时刻，我们可以且仅可以采取以下几种操作：

把 X 壶的水灌进 Y 壶，直至灌满或倒空；
把 Y 壶的水灌进 X 壶，直至灌满或倒空；
把 X 壶灌满；
把 Y 壶灌满；
把 X 壶倒空；
把 Y 壶倒空。
因此，本题可以使用深度优先搜索来解决。搜索中的每一步以 remain_x, remain_y 作为状态，即表示 X 壶和 Y 壶中的水量。在每一步搜索时，我们会依次尝试所有的操作，递归地搜索下去。这可能会导致我们陷入无止境的递归，因此我们还需要使用一个哈希结合（HashSet）存储所有已经搜索过的 remain_x,remain_y状态，保证每个状态至多只被搜索一次。

在实际的代码编写中，由于深度优先搜索导致的递归远远超过了 Python 的默认递归层数（可以使用 sys 库更改递归层数，但不推荐这么做），因此下面的代码使用栈来模拟递归，避免了真正使用递归而导致的问题。

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        Deque<int[]> stack = new LinkedList<int[]>();
        stack.push(new int[]{0, 0});
        Set<Long> seen = new HashSet<Long>();
        while (!stack.isEmpty()) {
            if (seen.contains(hash(stack.peek()))) {
                stack.pop();
                continue;
            }
            seen.add(hash(stack.peek()));
            int[] state = stack.pop();
            int remain_x = state[0], remain_y = state[1];
            if (remain_x == z || remain_y == z || remain_x + remain_y == z) 			{
                return true;
            }
            // 把 X 壶灌满。
            stack.push(new int[]{x, remain_y});
            // 把 Y 壶灌满。
            stack.push(new int[]{remain_x, y});
            // 把 X 壶倒空。
            stack.push(new int[]{0, remain_y});
            // 把 Y 壶倒空。
            stack.push(new int[]{remain_x, 0});
            // 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
            stack.push(new int[]{remain_x - Math.min(remain_x, y - remain_y), remain_y + Math.min(remain_x, y - remain_y)});
            // 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
            stack.push(new int[]{remain_x + Math.min(remain_y, x - remain_x), remain_y - Math.min(remain_y, x - remain_x)});
        }
        return false;
    }

    public long hash(int[] state) {
        return (long) state[0] * 1000001 + state[1];
    }
}

简单来说，就是递归调用来分析所有可能。。。类似于暴力法的感觉

复杂度分析

时间复杂度：$O(xy)$，状态数最多有 $(x+1)(y+1) $种，对每一种状态进行深度优先搜索的时间复杂度为 $O(1)$，因此总时间复杂度为 $O(xy)$。

空间复杂度：$O(xy)$，由于状态数最多有$ (x+1)(y+1)$ 种，哈希集合中最多会有 $(x+1)(y+1)$项，因此空间复杂度为 $O(xy)$。

解法二：数学

思路及算法

预备知识：贝祖定理

我们认为，每次操作只会让桶里的水总量增加 x，增加 y，减少 x，或者减少 y。

你可能认为这有问题：如果往一个不满的桶里放水，或者把它排空呢？那变化量不就不是 x 或者 y 了吗？接下来我们来解释这一点：

• 首先要清楚，在题目所给的操作下，两个桶不可能同时有水且不满。因为观察所有题目中的操作，操作的结果都至少有一个桶是空的或者满的；

• 其次，对一个不满的桶加水是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于直接从初始状态给这个桶加满水；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态分别给两个桶加满；

• 再次，把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于回到初始状态；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态直接给另一个桶倒满。

因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a，b，使得
$$
ax + by = z
$$
而只要满足 $z\leq x+y$，且这样的 $a, b$ 存在，那么我们的目标就是可以达成的。这是因为：

若 $a\geq 0, b\geq 0$，那么显然可以达成目标。

若 $a\lt 0$，那么可以进行以下操作：

往 $y$ 壶倒水；

把 $y$ 壶的水倒入 $x$ 壶；

如果 $y$ 壶不为空，那么 $x$ 壶肯定是满的，把 $x$ 壶倒空，然后再把 $y$ 壶的水倒入 $x$ 壶。

重复以上操作直至某一步时 $x$ 壶进行了 $a$ 次倒空操作，$y$ 壶进行了 $b$ 次倒水操作。

若 $b\lt 0$，方法同上，x 与y互换。

而贝祖定理告诉我们，$ax+by=z$ 有解当且仅当 $z$ 是 $x,y$ 的最大公约数的倍数。因此我们只需要找到 $x, y$ 的最大公约数并判断 $z$ 是否是它的倍数即可。

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if (x + y < z) {
            return false;
        }
        if (x == 0 || y == 0) {
            return z == 0 || x + y == z;
        }
        return z % gcd(x, y) == 0;
    }
};

解法三：（大壶做加法小壶做减法）

这是一个评论上看到的…大佬解法

class Solution {
public:
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (jug1Capacity + jug2Capacity < targetCapacity) return false;
        int a = max(jug1Capacity, jug2Capacity);// 大壶
        int b = min(jug1Capacity, jug2Capacity);// 小壶
        int c = a + b;
        while (c) {
            if (c == targetCapacity) {
                return true;
            }
            if (c >= b) { 
                c -= b;
            } else {
                c += a;
            }
        }
        return false;
    }
};

5.分发糖果（困难）

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

解法（贪心策略）：

class Solution {
public:
    int candy(vector& ratings) {
        int size = ratings.size();
        if(size < 2)return size;
        vector nums(size,1);
        for(int i = 1; i < size; i++) // 从左到右遍历
        {
            if(ratings[i] > ratings[i - 1])// 如果右边比左边大，右边 等于 左边 + 
            {
                nums[i] = nums[i - 1] + 1;
            }
        }
        for(int j = size - 2;j >= 0;j--)
        {
            if(ratings[j] > ratings[j+1])// 如果 左边比右边大
            {// 返回 （当前值，右边值+1） 最大的一个就可以了
                nums[j] = max(nums[j] ,nums[j + 1] + 1);
            }
        }
        return accumulate(nums.begin(),nums.end(),0);// 统计结果
    }
};

6.无重叠区间（中等）

给定一个区间的集合 intervals ，其中 intervals[i] = $[start_i, end_i] $。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

解法（排序+贪心策略）

先将区间按右端点进行增序排序，因为选择的区间结尾越小，余留给其他区间的空间就越大，就能保留越多的区间。然后每次选择结尾最小和前一个选择区间不重叠的区间。

class Solution {
public:
    int eraseOverlapIntervals(vector>& intervals) {
        if(intervals.empty())
        {
            return 0;
        }
        int n = intervals.size();
        // 按结尾大小增序排列
        sort(intervals.begin(),intervals.end(),[](vector a,vector b){return a[1] < b[1];});
        int count = 0;// 要移除的个数
        int prev = intervals[0][1]; //用来比较的基数（区间右端点）
        for(int i = 1;i < n;i++)
        {
            if(intervals[i][0] < prev)
            {
                count++;
            }else{
                prev = intervals[i][1];
            }
        }
        return count;
    }
};

7.电话号码的字母组合(中等)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

解法：暴力深度优先

class Solution {
public:
    vector res; // 存放排列组合的结果
    void dfs(string digits,int index)
    {
        if(index == digits.size()){
            res.push_back(digits);
        }
        switch(digits[index])
        {
            case '2': 
                    digits[index] = 'a'; dfs(digits,index + 1);
                    digits[index] = 'b'; dfs(digits,index + 1);
                    digits[index] = 'c'; dfs(digits,index + 1);
                    break;
            case '3': 
                    digits[index] = 'd'; dfs(digits,index + 1);
                    digits[index] = 'e'; dfs(digits,index + 1);
                    digits[index] = 'f'; dfs(digits,index + 1);
                    break;
            case '4': 
                    digits[index] = 'g'; dfs(digits,index + 1);
                    digits[index] = 'h'; dfs(digits,index + 1);
                    digits[index] = 'i'; dfs(digits,index + 1);
                    break;
            case '5': 
                    digits[index] = 'j'; dfs(digits,index + 1);
                    digits[index] = 'k'; dfs(digits,index + 1);
                    digits[index] = 'l'; dfs(digits,index + 1);
                    break;
            case '6': 
                    digits[index] = 'm'; dfs(digits,index + 1);
                    digits[index] = 'n'; dfs(digits,index + 1);
                    digits[index] = 'o'; dfs(digits,index + 1);
                    break;
            case '7': 
                    digits[index] = 'p'; dfs(digits,index + 1);
                    digits[index] = 'q'; dfs(digits,index + 1);
                    digits[index] = 'r'; dfs(digits,index + 1);
                    digits[index] = 's'; dfs(digits,index + 1);
                    break;
            case '8': 
                    digits[index] = 't'; dfs(digits,index + 1);
                    digits[index] = 'u'; dfs(digits,index + 1);
                    digits[index] = 'v'; dfs(digits,index + 1);
                    break;
            case '9': 
                    digits[index] = 'w'; dfs(digits,index + 1);
                    digits[index] = 'x'; dfs(digits,index + 1);
                    digits[index] = 'y'; dfs(digits,index + 1);
                    digits[index] = 'z'; dfs(digits,index + 1);
                    break;            
        }
    }
    vector letterCombinations(string digits) {
        if(digits == "")return{};
        dfs(digits , 0);
        return res;
    }
};

8.种花问题（简单）

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

提示：

• 1 <= flowerbed.length <= 2 * 104
• flowerbed[i] 为 0 或 1
• flowerbed 中不存在相邻的两朵花
• 0 <= n <= flowerbed.length

解法一：

鄙人写的…，看看就好。虑边界情况比较多，这里count>=n的原因：给定的值 可以小于 最大种植的棵数目。有个测试用例就是这个坑，怪狡猾的

class Solution {
public:
    bool canPlaceFlowers(vector& flowerbed, int n) {
        int count = 0;// 还能种植的花数
        if(flowerbed.size() == 1 && flowerbed[0] == 0){
            return (1>=n);
        }
        if(flowerbed[0] == 0 && flowerbed[1] == 0){ // 边界情况2
            flowerbed[0] = 1;
            count++;
        }
        if(flowerbed[flowerbed.size()-1] == 0 && flowerbed[flowerbed.size()-2] == 0){ // 边界情况3
            flowerbed[flowerbed.size()-1] = 1;
            count++;
        }
        for(int i = 1; i < flowerbed.size()-1; i++)
        {
            if(flowerbed[i] == 0 && flowerbed[i-1] == 0 && flowerbed[i + 1]==0)
            {
                flowerbed[i] = 1;
                count++;
            }
        }
        return (count >= n);
    }
};

解法二（跳格子法）：

思路：

题目要求是否能在不打破规则的情况下插入n朵花，与直接计算不同，采用“跳格子”的解法只需遍历不到一遍数组，处理以下两种不同的情况即可：

【1】当遍历到index遇到1时，说明这个位置有花，那必然从index+2的位置才有可能种花，因此当碰到1时直接跳过下一格。
【2】当遍历到index遇到0时，由于每次碰到1都是跳两格，因此前一格必定是0，此时只需要判断下一格是不是1即可得出index这一格能不能种花，如果能种则令n减一，然后这个位置就按照遇到1时处理，即跳两格；如果index的后一格是1，说明这个位置不能种花且之后两格也不可能种花（参照【1】），直接跳过3格。

当n减为0时，说明可以种入n朵花，则可以直接退出遍历返回true；如果遍历结束n没有减到0，说明最多种入的花的数量小于n，则返回false。

public boolean canPlaceFlowers(int[] flowerbed, int n) {
    for (int i = 0, len = flowerbed.length; i < len && n > 0;) {
        if (flowerbed[i] == 1) {
            i += 2;
        } else if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
            n--;
            i += 2;
        } else {
            i += 3;
        }
    }
    return n <= 0;
}

9.用最少数量的箭引爆气球（中等）

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在xstart和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 6处射出箭，击破气球[2,8]和[1,6]。
- 在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

 输入：points = [[1,2],[2,3],[3,4],[4,5]]
 输出：2
 解释：气球可以用2支箭来爆破:
 
 - 在x = 2处发射箭，击破气球[1,2]和[2,3]。
 - 在x = 4处射出箭，击破气球[3,4]和[4,5]。

解法（排序+贪心策略）：

这题和上面第6题套路一样，只不过第6是求多少个 重叠区间，这个其实是同样的道理，代码都不用改多少。

class Solution {
public:
    int findMinArrowShots(vector>& points) {
        if(points.empty())return 0;
        int len = points.size();
        // 以左端点排序
        sort(points.begin(),points.end(),[](vector &a,vector &b){
            return a[1] < b[1];
        });
        // count 为区间重叠的个数，prev为上一个区间的值
        int count = 0, prev = points[0][1];
        for(int i = 1; i < len; i++) // 计算重叠气球的个数
        {
            if(points[i][0] <= prev)
            {
                count++;
            }else{
                prev = points[i][1];
            }
        }
        // 所需弓箭数 = 总共气球个数 - 重叠气球数
        return len - count;
    }
};

10.划分字母区间（中等）

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
    划分结果为 "ababcbaca", "defegde", "hijhklij"。
    每个字母最多出现在一个片段中。
    像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

• S的长度在[1, 500]之间。
• S只包含小写字母 'a' 到 'z' 。

解法：(统计字符串，贪心)

思路：先把字符串中每个字符的最后索引值找到。用贪心思想，将当前索引值以及最后索引值的一段作为最小结束下标，找到每个片段可能的最小结束下标。

class Solution {
public:
    vector partitionLabels(string s) {
        int length = s.length();
        int last[26];
        for(int i = 0; i < length; i++)
        {
            last[s.at(i) - 'a'] = i;
        }
        vector partitions;
        int start = 0,end = 0;// end为每一段的最后位置
        for(int i = 0; i < length; i++)
        {
            end = max(end,last[s.at(i) - 'a']);
            if(i == end){//到达一段结尾
                partitions.push_back(end - start + 1);
                start = i + 1;//开始新的一段
            }
        }
        return partitions;
    }
};