一、字符串的排列
题干：
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
题解：
全排列问题可采用递归的思路，固定某个位置，求出其他位置的全排列
我们可以通过交换来获得所有可能的情况。比如第一个位置上的字符，假如 A 和 A 交换，就相当于第一个位置上固定了 A；假如 A 和 B 交换，B来到第一个位置，就相当于第一个位置上固定了 B；假如 A 和 C 交换，C来到第一个位置，就相当于第一个位置上固定了 C。递归的过程中都是同理。
此外，因为可能有字符重复，我们得到的全排列自然也会有重复，那么我们可以用 set （集合）来去重，并且还可以达到按照字母顺序排序的目的。
代码
class Solution {
public:
set<string> num;
void num_swap(string s,int cnt)
{
if(cnt==s.size()-1)
{
num.insert(s);
return;
}
for(int i=cnt;i<s.size();i++)
{
// for循环和swap的含义：对于“ABC”，
// 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'
// 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'
// 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'
swap(s[cnt],s[i]);
num_swap(s,cnt+1);
swap(s[cnt],s[i]);
// 回溯的原因：比如第二次交换后是"BAC"，需要回溯到"ABC"
// 然后进行第三次交换，才能得到"CBA"
}
}
vector<string> permutation(string s) {
num_swap(s,0);
vector<string> ans=vector<string>({num.begin(), num.end()});
return ans;
}
};
二、数组中出现次数超过一半的数字
题干
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
题解
如果有一个数超过数组长度一半，意味着他可以把其他数字全部抵消，海能保证有剩余，因此，我们设定第一个数为最终的ans结果，在设置一个cnt次数表示目前该数出现的次数，若果下一个不是该数，并且次数为0，则更换ans，若果不是该数且次数不为0，则只减少次数，ans值不变。对数组进行一遍遍历，即可求出结果。
代码
class Solution {
public:
int majorityElement(vector<int>& nums) {
int cur=0;
int ans=nums[0];
for(int i=1;i<nums.size();i++)
{
if(nums[i]!=ans)
{
if(cur!=0)
{
cur--;
}
else
{
ans=nums[i];
}
}
else
cur++;
}
return ans;
}
};
本文来源：
博客园：https://www.cnblogs.com/xiaofengzai/p/16710179.html
郑重声明：本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们邮箱：908164873@qq.com/电话：187-8421-3206，我们将做删除处理！
