題目來(lái)自書或者網(wǎng)站。

• 解密QQ 號(hào)——隊(duì)列
• 回文字符串---棧
• 火柴棍等式
• • 輸入數(shù)字n，要求輸出從1~n的全排列
• 【力扣】給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請(qǐng)你找出所有和為 0 且不重復(fù)的三元組
• • 設(shè)計(jì)一個(gè)循環(huán)隊(duì)列重新排列棧中的元素
  • 遞歸反轉(zhuǎn)一個(gè)棧

---

解密QQ 號(hào)——隊(duì)列

小哈告訴了小哼一串加密過的數(shù)字，同時(shí)小哈也告訴了小哼解密規(guī)則。規(guī)則是這樣的：首先將第1 個(gè)數(shù)刪除，緊接著將第2 個(gè)數(shù)放到這串?dāng)?shù)的末尾，再將第3 個(gè)數(shù)刪除并將第4 個(gè)數(shù)放到這串?dāng)?shù)的末尾，再將第5 個(gè)數(shù)刪除……直到剩下最后一個(gè)數(shù)，將最后一個(gè)數(shù)也刪除。按照剛才刪除的順序，把這些刪除的數(shù)連在一起就是小哈的QQ 啦。現(xiàn)在你來(lái)幫幫小哼吧。小哈給小哼加密過的一串?dāng)?shù)是“6 3 1 7 5 8 9 2 4”。

【此題來(lái)自啊哈算法，以下是作者的分析】：
首先需要一個(gè)數(shù)組來(lái)存儲(chǔ)這一串?dāng)?shù)即int q[101]，并初始化這個(gè)數(shù)組即int q[101]={0,6,3,1,7,5,8,9,2,4};（此處初始化是我多寫了一個(gè)0，用來(lái)填充q[0]，因?yàn)槲冶容^喜歡從q[1]開始用，對(duì)數(shù)組初始化不是很理解的同學(xué)可以去看一下我的上本書《啊哈C！思考快你一步》）。接下來(lái)就是模擬解密的過程了。
解密的第一步是將第一個(gè)數(shù)刪除，你可以想一下如何在數(shù)組中刪除一個(gè)數(shù)呢。最簡(jiǎn)單的方法是將所有后面的數(shù)都往前面挪動(dòng)一位，但是這樣的做法很耗費(fèi)時(shí)間。
在這里，我將引入兩個(gè)整型變量head 和tail。head 用來(lái)記錄隊(duì)列的隊(duì)首（即第一位），tail 用來(lái)記錄隊(duì)列的隊(duì)尾（即最后一位）的下一個(gè)位置，你可能會(huì)問：為什不直接記錄隊(duì)尾，卻要記錄隊(duì)尾的下一個(gè)位置呢？這是因?yàn)楫?dāng)隊(duì)列中只剩下一個(gè)元素時(shí)，隊(duì)首和隊(duì)尾重合會(huì)帶來(lái)一些麻煩。我們這里規(guī)定隊(duì)首和隊(duì)尾重合時(shí)，隊(duì)列為空。

現(xiàn)在有9 個(gè)數(shù)，9 個(gè)數(shù)全部放入隊(duì)列之后head=1;tail=10;此時(shí)head 和tail 之間的數(shù)就是目前隊(duì)列中“有效”的數(shù)。如果要?jiǎng)h除一個(gè)數(shù)的話，就將head++就OK 了，這樣仍然可以保持head 和tail 之間的數(shù)為目前隊(duì)列中“有效”的數(shù)。這樣做雖然浪費(fèi)了一個(gè)空間，卻節(jié)省了大量的時(shí)間，這是非常劃算的。新增加一個(gè)數(shù)也很簡(jiǎn)單，把需要增加的數(shù)放到隊(duì)尾即q[tail]之后再tail++就OK 啦

int main() {int q[102]={0,6,3,1,7,5,8,9,2,4},head,tail; int i; head = 1; tail = 10;//q[0]用0填充 while(head < tail) {cout<<q[head]; head++; q[tail++] = q[head++];}}

回文字符串—棧

#include <string.h>int main() { char a[102],s[102]; gets(a); int n = strlen(a); int top = 0;//棧頂 int mid = n/2 - 1;//注意要-1 for(int i = 0; i <= mid;i++) s[++top] = a[i]; int nex; if(n % 2 == 0) nex = mid + 1; if(n % 2 == 1) nex = mid + 2; //尤其注意這個(gè)容易錯(cuò)的地方：奇數(shù)和偶數(shù)的情況不同 如果i直接從mid+1開始遍歷會(huì)出錯(cuò) for(int i = nex;i < n;i++) {if(s[top] != a[i]) {cout<<"no";break;} else top--; }cout<<"yes";}

自己想的不用棧更方便的方法：

int main() { char a[102],s[102]; gets(a); int n = strlen(a); int top = 0;//棧頂 int mid = n/2 - 1;//注意要-1 for(int i = 0,j = n-1;i != (n-1/2); i++,j--) if(a[i] != a[j]) {cout<<"no!"; break;} cout<<"o";

火柴棍等式

6.23日


首先分析數(shù)字特征，因?yàn)樽疃?4根，減去符號(hào)，20根用于拼數(shù)字，1只需要1根，所以最多拼10個(gè)1，1111+1=1112 這樣個(gè)數(shù)大于了20，所以ABC中最大也不能超過1111，采用枚舉法，只需要對(duì)AB進(jìn)行枚舉即可，不需要再枚舉C，否則會(huì)超過時(shí)限

int fun(int x) {int sum = 0; //用于計(jì)算某一個(gè)數(shù)字所用的火柴總數(shù) int f[10] = {6, 2, 5, 5,4,5,6,3,7,6};//0-9每個(gè)數(shù)字需要的火柴棍 while(x /10 != 0) {sum += f[x%10];x /= 10; } sum += f[x]; return sum;}int main() {int m;//火柴棍的個(gè)數(shù) int total = 0; cin>> m; for(int i = 0;i <= 1111; i++) for(int j = 0; j<= 1111 ;j++) {int c = i+j;if((fun(i) + fun(j) + fun(c)) == (m - 4))total++; } cout<<total;}

輸入數(shù)字n，要求輸出從1~n的全排列

如123的全排列：123 132 321 312 213 231
采用深度優(yōu)先搜索方法
要點(diǎn)：

int visited[100] = {0}; int a[10],n; void dfs(int step) {if(step == n+1){//此時(shí)已經(jīng)找到了一個(gè)全排列for(int i = 1;i <step ;i++)//a表示小盒子數(shù)組，step表示此時(shí)站在第i個(gè)小盒子前面 注意i從1開始cout<<a[i]<<" ";return;//記得return} for(int i = 1;i <= n;i++)//1..n的順序都嘗試一遍if(!visited[i]) {a[step] = i;visited[i] = 1; dfs(step+1); visited[i] = 0;//這個(gè)非常重要，回退時(shí)記得再次標(biāo)志為未訪問 } return;}int main() {cin>>n;dfs(1); }

【力扣】給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請(qǐng)你找出所有和為 0 且不重復(fù)的三元組

自己的代碼：

vector<vector<int>> threeSum(vector<int>& nums) {if (nums.size() < 3) return {};vector<vector<int>> res;//關(guān)鍵點(diǎn)：時(shí)間復(fù)雜度的優(yōu)化和去重int total = nums.size();int j = total - 1,m;sort(nums.begin(), nums.end());for (int i = 0; i < total; ++i){if (i > 0 && nums[i] == nums[i - 1]) continue;//確保每次枚舉的數(shù)字不一樣int begin = i + 1;int third = total - 1;int c = -nums[i] ;for (int z = begin; z < total; z++){//枚舉每一個(gè)不一樣的zif (z > begin && nums[z] == nums[z - 1]) continue;//每一次與上次不一樣while (third > z && (nums[z] + nums[third] - c) > 0) --third;if (third == z) break;//如果重合了，退出循環(huán)if (nums[z] + nums[third] == c) res.push_back({ nums[i],nums[z],nums[third] });}}return res;}

這里由于 while (third > z && (nums[z] + nums[third] - c) > 0) --third;
if (third == z) break;//如果重合了，退出循環(huán)
這兩句話的順序顛倒了，錯(cuò)了好多次也沒看出來(lái)！！！！！！

注意點(diǎn)：1.不要重復(fù)，如何確保三元組不重復(fù)
2.采取先排序的策略，雙指針，其中中間的指針從第一個(gè)指針的下一個(gè)開始枚舉。
官方的題解：
任意一個(gè)三元組的和都為 00。如果我們直接使用三重循環(huán)枚舉三元組，會(huì)得到 O(N^3)O(N
3
) 個(gè)滿足題目要求的三元組（其中 NN 是數(shù)組的長(zhǎng)度）時(shí)間復(fù)雜度至少為 O(N^3)O(N
3
)。在這之后，我們還需要使用哈希表進(jìn)行去重操作，得到不包含重復(fù)三元組的最終答案，又消耗了大量的空間。這個(gè)做法的時(shí)間復(fù)雜度和空間復(fù)雜度都很高，因此我們要換一種思路來(lái)考慮這個(gè)問題。

「不重復(fù)」的本質(zhì)是什么？我們保持三重循環(huán)的大框架不變，只需要保證：

第二重循環(huán)枚舉到的元素不小于當(dāng)前第一重循環(huán)枚舉到的元素；

第三重循環(huán)枚舉到的元素不小于當(dāng)前第二重循環(huán)枚舉到的元素。

也就是說(shuō)，我們枚舉的三元組 (a, b, c)(a,b,c) 滿足 a \leq b \leq ca≤b≤c，保證了只有 (a, b, c)(a,b,c) 這個(gè)順序會(huì)被枚舉到，而 (b, a, c)(b,a,c)、(c, b, a)(c,b,a) 等等這些不會(huì)，這樣就減少了重復(fù)。要實(shí)現(xiàn)這一點(diǎn)，我們可以將數(shù)組中的元素從小到大進(jìn)行排序，隨后使用普通的三重循環(huán)就可以滿足上面的要求。

同時(shí)，對(duì)于每一重循環(huán)而言，相鄰兩次枚舉的元素不能相同，否則也會(huì)造成重復(fù)。舉個(gè)例子，如果排完序的數(shù)組為

[0, 1, 2, 2, 2, 3]
^ ^ ^
我們使用三重循環(huán)枚舉到的第一個(gè)三元組為 (0, 1, 2)(0,1,2)，如果第三重循環(huán)繼續(xù)枚舉下一個(gè)元素，那么仍然是三元組 (0, 1, 2)(0,1,2)，產(chǎn)生了重復(fù)。因此我們需要將第三重循環(huán)「跳到」下一個(gè)不相同的元素，即數(shù)組中的最后一個(gè)元素 33，枚舉三元組 (0, 1, 3)(0,1,3)。

下面給出了改進(jìn)的方法的偽代碼實(shí)現(xiàn)：

nums.sort()
for first = 0 … n-1
// 只有和上一次枚舉的元素不相同，我們才會(huì)進(jìn)行枚舉
if first == 0 or nums[first] != nums[first-1] then
for second = first+1 … n-1
if second == first+1 or nums[second] != nums[second-1] then
for third = second+1 … n-1
if third == second+1 or nums[third] != nums[third-1] then
// 判斷是否有 a+b+c==0
check(first, second, third)
這種方法的時(shí)間復(fù)雜度仍然為 O(N^3)O(N
3
)，畢竟我們還是沒有跳出三重循環(huán)的大框架。然而它是很容易繼續(xù)優(yōu)化的，可以發(fā)現(xiàn)，如果我們固定了前兩重循環(huán)枚舉到的元素 aa 和 bb，那么只有唯一的 cc 滿足 a+b+c=0a+b+c=0。當(dāng)?shù)诙匮h(huán)往后枚舉一個(gè)元素 b’b
′
時(shí)，由于 b’ > bb
′

b，那么滿足 a+b’+c’=0a+b
′
+c
′
=0 的 c’c
′
一定有 c’ < cc
′
<c，即 c’c
′
在數(shù)組中一定出現(xiàn)在 cc 的左側(cè)。也就是說(shuō)，我們可以從小到大枚舉 bb，同時(shí)從大到小枚舉 cc，即第二重循環(huán)和第三重循環(huán)實(shí)際上是并列的關(guān)系。

有了這樣的發(fā)現(xiàn)，我們就可以保持第二重循環(huán)不變，而將第三重循環(huán)變成一個(gè)從數(shù)組最右端開始向左移動(dòng)的指針，從而得到下面的偽代碼：

nums.sort()
for first = 0 … n-1
if first == 0 or nums[first] != nums[first-1] then
// 第三重循環(huán)對(duì)應(yīng)的指針
third = n-1
for second = first+1 … n-1
if second == first+1 or nums[second] != nums[second-1] then
// 向左移動(dòng)指針，直到 a+b+c 不大于 0
while nums[first]+nums[second]+nums[third] > 0
third = third-1
// 判斷是否有 a+b+c==0
check(first, second, third)
這個(gè)方法就是我們常說(shuō)的「雙指針」，當(dāng)我們需要枚舉數(shù)組中的兩個(gè)元素時(shí)，如果我們發(fā)現(xiàn)隨著第一個(gè)元素的遞增，第二個(gè)元素是遞減的，那么就可以使用雙指針的方法，將枚舉的時(shí)間復(fù)雜度從 O(N^2)
) 減少至 O(N)。為什么是 O(N) 呢？這是因?yàn)樵诿杜e的過程每一步中，「左指針」會(huì)向右移動(dòng)一個(gè)位置（也就是題目中的 bb），而「右指針」會(huì)向左移動(dòng)若干個(gè)位置，這個(gè)與數(shù)組的元素有關(guān)，但我們知道它一共會(huì)移動(dòng)的位置數(shù)為 O(N)，均攤下來(lái)，每次也向左移動(dòng)一個(gè)位置，因此時(shí)間復(fù)雜度為 O(N)。

注意到我們的偽代碼中還有第一重循環(huán)，時(shí)間復(fù)雜度為 O(N)O(N)，因此枚舉的總時(shí)間復(fù)雜度為 O(N^2)
)。由于排序的時(shí)間復(fù)雜度為 O(N \log N)，在漸進(jìn)意義下小于前者，因此算法的總時(shí)間復(fù)雜度為 O(N^2) )。

設(shè)計(jì)一個(gè)循環(huán)隊(duì)列重新排列棧中的元素

一個(gè)棧有2n個(gè)元素，從棧頂?shù)綏５椎脑匾来问莂2n,a2n-1,…,a1,要求通過一個(gè)循環(huán)隊(duì)列重新排列棧中的元素，使得從棧頂?shù)綏５滓来问莂1,a3,…,a2n-1,a2,a4,…,a2n

思路：先將棧中全部元素進(jìn)入一個(gè)隊(duì)列中，求出棧中元素總數(shù)，然后設(shè)一個(gè)計(jì)數(shù)器i,當(dāng)i為奇數(shù)時(shí)進(jìn)入棧，偶數(shù)時(shí)進(jìn)入隊(duì)列
最后一起將隊(duì)列的所有元素進(jìn)棧

void ReAssign(stack<T>&st) { T e; queue<T>qu; int sz = st.size(); while(!st.empty()) { e = st.top(); st.pop(); qu.push(e); } for(int i =1;i <= sz;i++) { if(i%2==1) {st.push(qu.front());qu.pop();} else { qu.push(qu.front()); qu.pop(); }} while(!qu.empty()) { st.push(qu.front()); qu.pop(); }}

遞歸反轉(zhuǎn)一個(gè)棧

要求不能申請(qǐng)一個(gè)同樣的棧，除了系統(tǒng)棧之外，其他空間復(fù)雜度為o(1)

思路：設(shè)計(jì)將元素X從棧底插入的算法，遞歸出棧元素tmp直到棧空，此時(shí)進(jìn)棧x，再依次將原來(lái)退棧的元素進(jìn)棧，如下：

void PushBottom(stack<int>&st,int x) { int tmp; if(st.empty()) st.push(x); else{ tmp = st.top(); st.pop(); PushBottom(st,x); st.push(tmp); }} //現(xiàn)在反轉(zhuǎn)整個(gè)棧 void reverseStack(stack<int>&st) { if(st.empty()) return; else { int tmp = st.top(); st.pop(); reverseStack(st); PushBottom(st,tmp); aa } }

總結(jié)

以上是生活随笔為你收集整理的【练习】2021下半年数据结构刷题笔记和总结 （三）栈 队列 链表 枚举算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。