这节我们继续来汇总一些LeetCode题
找到所有数组中消失的数字
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
这个题如果没有限制的话，还是很简单的，使用哈希表等相关方法都可以解决。
但这里要求我们在不使用额外空间且时间复杂度为O(n)的情况下完成，简单来说就是在原数组中操作(额外定义的基本变量不算)，且一次遍历就完成。
如何做呢？考虑题意，数组中数据的范围是 1 ≤ a[i] ≤ n ，那我们就需要充分利用这个信息，任意一个数组中的元素绝对值减一后都可以作为下标去访问该数组中其他元素，要是能够标记这次访问，就意味着这个元素至少出现了一次，那没有标记的元素就是没有出现的了。
以这个思路，我们就可以很容易解决了。
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for(int i=0;i<nums.size();i++){
//以该元素的绝对值减一为索引标记元素
int index = abs(nums[i])-1;
if(nums[index]>0){
nums[index] *= -1;
}
}
vector<int> res;
for(int i=1;i<=nums.size();i++){
//大于0表示没有出现过
if(nums[i-1]>0){
res.push_back(i);
}
}
return res;
}
};
有序队列
给出了一个由小写字母组成的字符串 S。然后，我们可以进行任意次数的移动。
在每次移动中，我们选择前 K 个字母中的一个（从左侧开始），将其从原位置移除，并放置在字符串的末尾。
返回我们在任意次数的移动之后可以拥有的按字典顺序排列的最小字符串。
示例 1：
输入：S = "cba", K = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
示例 2：
输入：S = "baaca", K = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。
当 K = 1 时，每次操作只能将第一个字符移动到末尾，因此字符串 S 可以看成一个头尾相连的环。如果 S 的长度为 N，我们只需要找出这 N 个位置中字典序最小的字符串即可。
当 K >1 时，其实就相当于冒泡排序，交换两个元素，比较 K = 1 时，我们能在S上得到一个字典序最小的队列，得到一个升序排列的队列。
class Solution {
public:
string orderlyQueue(string S, int K) {
if(K>1){
sort(S.begin(),S.end());
return S;
}
string res=S;
for(int i=0;i<S.size();i++){
string tmp = S.substr(i)+S.substr(0,i);
if(tmp<res){
res=tmp;
}
}
return res;
}
};
两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
这个题算是链表中的常规题吧，需要注意的是数字最高位位于链表开始位置，如果不修改链表的话，不妨使用栈来保存节点域，相加存入链表。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1=fun(l1);
stack<int> s2=fun(l2);
return s1.size()>s2.size()?add(s1,s2):add(s2,s1);
}
stack<int> fun(ListNode* l){
stack<int> s;
ListNode* p=l;
while(p){
s.push(p->val);
p=p->next;
}
return s;
}
ListNode* add(stack<int>& s1,stack<int>& s2){
//默认s1大于等于s2
int len1=s1.size();
int len2=s2.size();
ListNode* res=nullptr;
int tmp=0;
len1=len1-len2;
while(len2--){
int num1=s1.top();
s1.pop();
int num2=s2.top();
s2.pop();
ListNode* node=new ListNode((num1+num2+tmp)%10);
tmp=(num1+num2+tmp)/10;
node->next=res;
res=node;
}
while(len1--){
int num=s1.top();
s1.pop();
ListNode* node=new ListNode((num+tmp)%10);
tmp=(num+tmp)/10;
node->next=res;
res=node;
}
if(tmp){
ListNode* node=new ListNode(1);
node->next=res;
res=node;
}
return res;
}
};
这个写得有些啰嗦，但是总体上问题不大。
卡牌分组
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
每组都有 X 张牌。
组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。
统计每个数出现的次数，若所有的次数的公约数大于2，则满足条件。
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
map<int,int> m;
for(int i=0;i<deck.size();i++){
m[deck[i]]++;
}
int sum=-1;
auto b = m.begin();
while(b!=m.end()){
if(sum==-1){
sum=b->second;
}else{
sum=gcd(sum,b->second);
}
b++;
}
return sum>=2;
}
int gcd(int x,int y){
return x==0?y:gcd(y%x,x);
}
};
