這節(jié)我們繼續(xù)來匯總一些LeetCode題
找到所有數(shù)組中消失的數(shù)字
給定一個范圍在 1 ≤ a[i] ≤ n ( n = 數(shù)組大小 ) 的 整型數(shù)組价淌，數(shù)組中的元素一些出現(xiàn)了兩次丈莺，另一些只出現(xiàn)一次走诞。
找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字鞍陨。
您能在不使用額外空間且時間復(fù)雜度為O(n)的情況下完成這個任務(wù)嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)洪燥。
示例:
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[5,6]
這個題如果沒有限制的話霉祸，還是很簡單的，使用哈希表等相關(guān)方法都可以解決犁珠。
但這里要求我們在不使用額外空間且時間復(fù)雜度為O(n)的情況下完成逻炊，簡單來說就是在原數(shù)組中操作(額外定義的基本變量不算)，且一次遍歷就完成犁享。
如何做呢余素？考慮題意，數(shù)組中數(shù)據(jù)的范圍是 1 ≤ a[i] ≤ n 炊昆，那我們就需要充分利用這個信息桨吊，任意一個數(shù)組中的元素絕對值減一后都可以作為下標(biāo)去訪問該數(shù)組中其他元素，要是能夠標(biāo)記這次訪問凤巨，就意味著這個元素至少出現(xiàn)了一次屏积，那沒有標(biāo)記的元素就是沒有出現(xiàn)的了。
以這個思路磅甩，我們就可以很容易解決了。
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for(int i=0;i<nums.size();i++){
//以該元素的絕對值減一為索引標(biāo)記元素
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表示沒有出現(xiàn)過
if(nums[i-1]>0){
res.push_back(i);
}
}
return res;
}
};
有序隊列
給出了一個由小寫字母組成的字符串 S姥卢。然后卷要，我們可以進(jìn)行任意次數(shù)的移動渣聚。
在每次移動中，我們選擇前 K 個字母中的一個（從左側(cè)開始）僧叉，將其從原位置移除奕枝，并放置在字符串的末尾。
返回我們在任意次數(shù)的移動之后可以擁有的按字典順序排列的最小字符串瓶堕。
示例 1：
輸入：S = "cba", K = 1
輸出："acb"
解釋：
在第一步中隘道，我們將第一個字符（“c”）移動到最后，獲得字符串 “bac”郎笆。
在第二步中谭梗，我們將第一個字符（“b”）移動到最后，獲得最終結(jié)果 “acb”宛蚓。
示例 2：
輸入：S = "baaca", K = 3
輸出："aaabc"
解釋：
在第一步中激捏，我們將第一個字符（“b”）移動到最后，獲得字符串 “aacab”凄吏。
在第二步中远舅，我們將第三個字符（“c”）移動到最后，獲得最終結(jié)果 “aaabc”痕钢。
當(dāng) K = 1 時图柏，每次操作只能將第一個字符移動到末尾，因此字符串 S 可以看成一個頭尾相連的環(huán)任连。如果 S 的長度為 N蚤吹，我們只需要找出這 N 個位置中字典序最小的字符串即可。
當(dāng) K >1 時课梳，其實就相當(dāng)于冒泡排序距辆，交換兩個元素，比較 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;
}
};
兩數(shù)相加 II
給你兩個 非空 鏈表來代表兩個非負(fù)整數(shù)椭懊。數(shù)字最高位位于鏈表開始位置诸蚕。它們的每個節(jié)點只存儲一位數(shù)字。將這兩數(shù)相加會返回一個新的鏈表氧猬。
你可以假設(shè)除了數(shù)字 0 之外背犯，這兩個數(shù)字都不會以零開頭。
進(jìn)階：
如果輸入鏈表不能修改該如何處理盅抚？換句話說漠魏，你不能對列表中的節(jié)點進(jìn)行翻轉(zhuǎn)。
示例：
輸入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 8 -> 0 -> 7
這個題算是鏈表中的常規(guī)題吧妄均，需要注意的是數(shù)字最高位位于鏈表開始位置柱锹，如果不修改鏈表的話哪自，不妨使用棧來保存節(jié)點域，相加存入鏈表禁熏。
/**
* 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){
//默認(rèn)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;
}
};
這個寫得有些啰嗦壤巷，但是總體上問題不大。
卡牌分組
給定一副牌瞧毙，每張牌上都寫著一個整數(shù)胧华。
此時，你需要選定一個數(shù)字 X宙彪，使我們可以將整副牌按下述規(guī)則分成 1 組或更多組：
每組都有 X 張牌矩动。
組內(nèi)所有的牌上都寫著相同的整數(shù)。
僅當(dāng)你可選的 X >= 2 時返回 true您访。
統(tǒng)計每個數(shù)出現(xiàn)的次數(shù)铅忿，若所有的次數(shù)的公約數(shù)大于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);
}
};
