3. 分割（组合问题）

3. 分割（组合问题）

实质也是组合问题，切割的方式就是选择的起始位置

关键是截取子串是什么：s.substr(startIndex,i-startIndex+1);

4. 排序问题

需要使用标记数组，记录当前元素是否访问过，访问过设置为true：

vector<bool> used(candidates.size(),false);

组合排序通用问题、给定vector中可能包含重复的元素，要求不能出现重复的组合（即为树的树枝的节点可以重复，但是同一层不允许重复）

解决方法：

前提：需要先对数组升序【排序】，保证相同元素相邻，便于判断前后是否相等【关键】

1. 定义标识数组 vector used(candidates.size(),false);
2. 标识数组的含义：

used[i - 1] ==true：表示同一树枝使用过;

used[i - 1] == false，说明同一树层candidates[i - 1]使用过;

做选择时 used[i] =true 撤销选择时：used[i] = false;

1. 判断一定是前一个元素，因为要和当前元素比较;
2. 真正的去重代码：if(i>0&&candidates[i-1] == candidates[i] && used[i-1] ==false) continue;

贪心

构成交替字符串需要的最小交换次数

题目要求最小交换次数，那么对于不同的串，0 1 的出现次数也不相同，根据字符串的长度可分为偶数和奇数先求出 num1， num0，odd1，odd0

首先特判，num1 和 num0 两者个数相差不能大于 1，否则返回 -1

对于偶数长度，有两种情况，1010...，0101...

1 开头，那么奇数位置都应该为 1，那么奇数位置为 0 的次数(odd0) 就是要交换的次数 0 开头，那么奇数位置都应该为 0，那么奇数位置为 1 的次数(odd1) 就是要交换的次数

要求最小交换次数，返回两者中的最小值

对于奇数长度，有两种情况，010...，101....

由于是只有奇数个，所以 1 开头的话，必然是 num1 > num0，要交换的次数也就是odd0，反之，0开头，必然num0 > num1，返回odd1

动态规划