第一題
2020-04-1414.59.54.png
1、 定義
#define Stack_Init_Size 100
#define Stack_Increment 10
//棧的定義
typedef struct {
char* base; //棧底指針
char* top; //棧頂指針
int stacksize; //棧MaxSize
}SqStack;
初始化棧
/*
思路:
- 如果棧底為空
- 分配一個(gè)最大容量Stack_Init_Size的數(shù)組,棧底/棧頂都指向與它.[參考圖空棧情況]
- 初始化棧的最大容易Stack_Init_Size
*/
int Init(SqStack *stack){
stack->base=(char*)malloc(Stack_Init_Size*sizeof(char));
stack->top=stack->base;
stack->stacksize = Stack_Init_Size;
printf("初始化成功\n");
if(!stack->base){
return -1;//表示無法初始化已出始化棧
}
return 0;
}
獲取棧頂數(shù)據(jù)
/*
思路:
1.判斷棧是否為空
2.非空,則棧定指針-1,返回棧頂元素;
*/
char GetTop(SqStack stack){
if(stack.base==stack.top){
//printf("棧中沒有數(shù)據(jù)\n");
return '#';
}
//printf("獲取棧頂數(shù)據(jù)成功\n");
return *(stack.top-1);
}
往棧中插入元素
/*
思路:
1.判斷棧是否已滿,若滿則返回ERROR #問題:如何判斷棧是否已滿?
2.棧滿,則續(xù)容空間 #問題:如何給已滿棧續(xù)容空間?
3.將元素element壓棧
4.棧頂指針加"1"
*/
int Push(SqStack *stack,char element){
if(stack->top-stack->base==stack->stacksize){
stack->base=(char*)realloc(stack->base,Stack_Increment*sizeof(char));
stack->top=stack->base+stack->stacksize;
stack->stacksize+=Stack_Increment;
}
*stack->top=element;
stack->top+=1;
return 0;
}
刪除棧頂元素
/*
思路:
1.判斷棧是否已空
2.非空,則獲取棧頂元素,并將棧頂減"1";
*/
char Pop(SqStack *stack){
if(stack->top==stack->base){
printf("棧為空\(chéng)n");
return '#';
}
//printf("刪除數(shù)據(jù)成功");
return *--stack->top;
}
釋放?？臻g
int Destroy(SqStack *stack){
free(stack->base);
stack->stacksize=0;
return 0;
}
思路:
- 將第0個(gè)元素壓棧
- 遍歷[1,strlen(data)]
(3). 取棧頂字符
(4). 檢查該字符是左括號(hào)("(","[")
a.是左"(",則判斷緊接其后的data[i]是為右")"
YES->壓棧,NO->出棧
b.是左"[",則判斷緊跟其后的data[i]是為右"]"
YES->壓棧,NO->出棧
c.表示式如果以"#"結(jié)尾,則判斷緊跟其后的data是為左"(""]"
YES->壓棧,NO->-1;
3.遍歷結(jié)束,則判斷棧是否為空,為空則表示匹配成功;否則匹配失敗;
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
int ExecuteData(SqStack stack,char* data){
Push(&stack,data[0]);
for(int i=1;i<strlen(data);i++){
char top = GetTop(stack);
switch(top){
case '(':
if(data[i]==')')Pop(&stack);
else Push(&stack,data[i]);
break;
case '[':
if(data[i]==']')Pop(&stack);
else Push(&stack,data[i]);
break;
case '#':
if(data[i]=='('||data[i]=='['){
Push(&stack,data[i]);
break;
}
else
default:return -1;break;
}
}
//如果棧為空,則返回"0"->匹配成功 否則返回"-1"匹配失敗
if(stack.top==stack.base){
Destroy(&stack);
return 0;
}
else{
Destroy(&stack);
return -1;
}
}
int main(){
/*
算法問題:
假設(shè)表達(dá)式中允許包含兩種括號(hào):圓括號(hào)與方括號(hào),其嵌套順序隨意,即([]()) 或者[([][])]都是正確的.而這
[(]或者(()])或者([()) 都是不正確的格式. 檢驗(yàn)括號(hào)是否匹配的方法可用"期待的急迫程度"這個(gè)概念來描述. 例如,考慮以下括號(hào)的判斷:
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
*/
SqStack stack;
Init(&stack);
char data[180];
printf("請(qǐng)輸入待匹配的字符串\n");
scanf("%s",data);
int result = ExecuteData(stack,data);
if(result==0)printf("括號(hào)是正確匹配的\n");
else printf("括號(hào)匹配不正確\n");
return 0;
}
第二題
數(shù)制的轉(zhuǎn)換
/* 順序棧結(jié)構(gòu) */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* 用于棧頂指針 */
}SqStack;
構(gòu)建一個(gè)空棧S
Status InitStack(SqStack *S){
S->top = -1;
return OK;
}
push
Status PushData(SqStack *S, SElemType e){
//棧已滿
if (S->top == MAXSIZE -1) {
return ERROR;
}
//棧頂指針+1;
S->top ++;
//將新插入的元素賦值給棧頂空間
S->data[S->top] = e;
return OK;
}
pop
Status Pop(SqStack *S,SElemType *e){
//空棧,則返回error;
if (S->top == -1) {
return ERROR;
}
//將要?jiǎng)h除的棧頂元素賦值給e
*e = S->data[S->top];
//棧頂指針--;
S->top--;
return OK;
}
/*
- 初始化一個(gè)空棧S
- 當(dāng)十進(jìn)制N非零時(shí),循環(huán)執(zhí)行以下操作
- 把N與8求余得到的八進(jìn)制數(shù)壓入棧S;
- N更新為N與8的商;
- 當(dāng)棧S非空時(shí),循環(huán)執(zhí)行以下操作
- 彈出棧頂元素e;
- 輸出e;
*/
void conversion(int N){
SqStack S;
SElemType e;
//1.初始化一個(gè)空棧S
InitStack(&S);
//2.
while (N) {
PushData(&S, N%8);
N = N/8;
}
//3.
while (!StackEmpty(S)) {
Pop(&S, &e);
printf("%d\n",e);
}
}
第三題
題目: 根據(jù)每日氣溫列表，請(qǐng)重新生成一個(gè)列表，對(duì)應(yīng)位置的輸入是你需要再等待多久溫度才會(huì)升高超過該日的天數(shù)。如果之后都不會(huì)升高，請(qǐng)?jiān)谠撐恢?來代替。例如，給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：氣溫 列表長(zhǎng)度的范圍是 [1, 30000]。每個(gè)氣溫的值的均為華氏度，都是在 [30, 100] 范圍內(nèi)的整數(shù)。
解題關(guān)鍵: 實(shí)際上就是找當(dāng)前元素 從[i,TSize] 找到大于該元素時(shí). 數(shù)了幾次. 首先最后一個(gè)元素默認(rèn)是0,因?yàn)樗竺嬉呀?jīng)沒有元素了.
暴力法1:
- 從左到右開始遍歷,從第一個(gè)數(shù)到最后一個(gè)數(shù)開始遍歷. 最后一個(gè)數(shù)因?yàn)楹竺鏇]有元素,默認(rèn)是0,不需要計(jì)算;
- 從[i+1,TSize]遍歷,每個(gè)數(shù)直到找到比它大的數(shù),數(shù)的次數(shù)就是對(duì)應(yīng)的值;
int *dailyTemperatures_1(int* T, int TSize, int* returnSize){
int *result = (int *)malloc(sizeof(int) * TSize);
*returnSize = TSize;
result[TSize-1] = 0;
for(int i = 0;i < TSize-1;i++)
if(i>0 && T[i] == T[i-1])
result[i] = result[i-1] == 0?0:result[i-1]-1;
else{
for (int j = i+1; j < TSize; j++) {
if(T[j] > T[i]){
result[i] = j-i;
break;
}
if (j == TSize-1) {
result[i] = 0;
}
}
}
return result;
}
跳躍對(duì)比2:
- 從右到左遍歷. 因?yàn)樽詈笠惶斓臍鉁夭粫?huì)再升高,默認(rèn)等于0;
- i 從[TSize-2,0]; 從倒數(shù)第二天開始遍歷比較. 每次減一;
- j 從[i+1,TSize]遍歷, j+=result[j],可以利用已經(jīng)有結(jié)果的位置進(jìn)行跳躍,從而減少遍歷次數(shù)
-若T[i]<T[j],那么Result = j - i;
-若reuslt[j] == 0,則表示后面不會(huì)有更大的值,那么當(dāng)前值就應(yīng)該也是0;
int *dailyTemperatures_2(int* T, int TSize, int* returnSize){
int *result = (int *)malloc(sizeof(int) * TSize);
*returnSize = TSize;
result[TSize-1] = 0;
for (int i=TSize-2; i >= 0; i--) {
for (int j = i+1; j < TSize; j+=result[j]) {
if (T[i] < T[j]) {
result[i] = j-i;
break;
}else
{
if (result[j] == 0) {
result[i] = 0;
break;
}
}
}
}
return result;
}
棧的思路3:
- 初始化一個(gè)棧(用來存儲(chǔ)索引),value數(shù)組
- 棧中存儲(chǔ)的是元素的索引值index;
2.將當(dāng)前元素和棧頂元素比較;
如果棧為空,那么直接將當(dāng)前元素索引index 存儲(chǔ)到棧中;
如果棧頂元素>當(dāng)前元素,則將當(dāng)前元素索引index 存儲(chǔ)到棧中;
如果棧頂元素<當(dāng)前元素,則將當(dāng)前元素索引index-棧頂元素index,計(jì)算完畢則將當(dāng)前棧頂元素移除,將當(dāng)前元素索引index 存儲(chǔ)到棧中
int* dailyTemperatures_3(int* T, int TSize, int* returnSize) {
int* result = (int*)malloc(sizeof(int)*TSize);
// 用棧記錄T的下標(biāo)。
int* stack_index = malloc(sizeof(int)*TSize);
*returnSize = TSize;
// 棧頂指針。
int top = 0;
int tIndex;
for (int i = 0; i < TSize; i++)
result[i] = 0;
for (int i = 0; i < TSize; i++) {
printf("\n循環(huán)第%d次,i = %d\n",i,i);
// 若當(dāng)前元素大于棧頂元素，棧頂元素出棧。即溫度升高了，所求天數(shù)為兩者下標(biāo)的差值。
while (top > 0 && T[i] > T[stack_index[top-1]]) {
tIndex = stack_index[top-1];
result[tIndex] = i - tIndex;
top--;
printf("tIndex = %d; result[%d] = %d, top = %d \n",tIndex,tIndex,result[tIndex],top);
}
// 當(dāng)前元素入棧。
stack_index[top] = i;
printf("i= %d; StackIndex[%d] = %d ",i,top,stack_index[top]);
top++;
printf(" top = %d \n",top);
}
return result;
}
第四題
楊輝三角
思路:
- 第一層循環(huán)控制行數(shù)i : 默認(rèn)[i][0] = 1,[i][i] = 1
- 第二層循環(huán)控制列數(shù)j : triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
int** generate(int numRows, int* returnSize){
*returnSize = numRows;
int **res = (int **)malloc(sizeof(int*)*numRows);
for (int i = 0; i < numRows; i++) {
res[i] = (int *)malloc(sizeof(int)*(i+1));
res[i][0] = 1;
res[i][i] = 1;
for (int j = 1; j < i; j++) {
res[i][j] = res[i-1][j] + res[i-1][j-1];
}
}
return res;
}
第五題
爬樓梯問題
方法一:遞歸求解法
f(n) = f(n-1) + f(n-2);
f(1)=1;
f(2)=1;
int ClimbStairs_1(int n){
if (n<1) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
return ClimbStairs_1(n-1) + ClimbStairs_1(n-2);
}
方法二:動(dòng)態(tài)規(guī)劃法
int ClimbStairs(int n){
if(n==1) return 1;
int temp = n+1;
int *sum = (int *)malloc(sizeof(int) * (temp));
sum[0] = 0;
sum[1] = 1;
sum[2] = 2;
for (int i = 3; i <= n; i++) {
sum[i] = sum[i-1] + sum[i-2];
}
return sum[n];
}
第六題
現(xiàn)有一個(gè)整數(shù)序列,你可以交換其中的任意兩個(gè)數(shù)以得到一個(gè)新序列.求共能得到多少種可能結(jié)果(注意:1,1,1,1 無論怎么交換,只能得到一個(gè)序列)
//1 1
//12 21 2(2-1)
//199 919 991 3(2-1)
//123 132 213 231 312 321 3(3-1)
//1122 1212 2211 2121 4(2-1)
//1222 2122 2212 2221 4(2-1)
//1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 4(4-1)
//n n(k-1) k表示一組中不同的數(shù)的個(gè)數(shù)
int getTotal(int arrOrigin[],int n)
{
int i,j = 0;
int k=0;
int temp;
//1、先從小到大排序
for(i=0;i<n;i++){
for(j=0;j<n-1;j++){
if (arrOrigin[j]>arrOrigin[j+1])
{
temp = arrOrigin[j];
arrOrigin[j] = arrOrigin[j+1];
arrOrigin[j+1] = temp;
}
}
}
//2、相鄰倆個(gè)數(shù)比較
for (int i = 0; i <n; i++) {
if(arrOrigin[i]!=arrOrigin[i+1]){
k++;
printf("%d:%d\n",k,arrOrigin[i]);
}
}
if (k == 1) {
return 1;
}
return n*(k-1);
}
第七題
題目: 字符串編碼 LeetCode-中等
編碼規(guī)則為: k[encoded_string]，表示其中方括號(hào)內(nèi)部的 encoded_string 正好重復(fù) k 次。注意 k 保證為正整數(shù)。你可以認(rèn)為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號(hào)總是符合格式要求的。此外，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復(fù)的次數(shù) k ，例如不會(huì)出現(xiàn)像 3a 或 2[4] 的輸入。
例如:
s = "3[a]2[bc]", 返回 "aaabcbc".z
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
思路:
例如:12[a]為例;
1.遍歷字符串 S
2.如果當(dāng)前字符不為方括號(hào)"]" 則入棧stack中;
2.如果當(dāng)前字符遇到了方括號(hào)"]" 則:
① 首先找到要復(fù)制的字符,例如stack="12[a",那么我要首先獲取字符a;將這個(gè)a保存在另外一個(gè)棧去tempStack;
② 接下來,要找到需要備份的數(shù)量,例如stack="12[a",因?yàn)槌鰲＿^字符"a",則當(dāng)前的top指向了"[",也就是等于2;
③ 而12對(duì)于字符串是2個(gè)字符, 我們要通過遍歷找到數(shù)字12的top上限/下限的位置索引, 此時(shí)上限curTop = 2, 下限通過出棧,top = -1;
④ 根據(jù)范圍[-1,2],讀取出12保存到strOfInt 字符串中來, 并且將字符"12\0",轉(zhuǎn)化成數(shù)字12;
⑤ 當(dāng)前top=-1,將tempStack中的字符a,復(fù)制12份入棧到stack中來;
⑥ 為當(dāng)前的stack擴(kuò)容, 在stack字符的末尾添加字符結(jié)束符合'\0';
char * decodeString(char * s){
/*.
1.獲取字符串長(zhǎng)度
2.設(shè)置默認(rèn)棧長(zhǎng)度50
3.開辟字符串棧(空間為50)
4.設(shè)置棧頭指針top = -1;
*/
int len = (int)strlen(s);
int stackSize = 50;
char* stack = (char*)malloc(stackSize * sizeof(char));
int top = -1;
//遍歷字符串,在沒有遇到"]" 之前全部入棧
for (int i = 0; i < len; ++i) {
if (s[i] != ']') {
//優(yōu)化:如果top到達(dá)了棧的上限,則為棧擴(kuò)容;
if (top == stackSize - 1) {
stack = realloc(stack, (stackSize += 50) * sizeof(char));
}
//將字符入棧stack
stack[++top] = s[i];
printf("#① 沒有遇到']'之前# top = %d\n",top);
}
else {
int tempSize = 10;
char* temp = (char*)malloc(tempSize * sizeof(char));
int topOfTemp = -1;
printf("#② 開始獲取要復(fù)制的字符信息之前 # top = %d\n",top);
//從棧頂位置開始遍歷stack,直到"["結(jié)束;
//把[a]這個(gè)字母a 賦值到temp棧中來;
//簡(jiǎn)單說,就是將stack中方括號(hào)里的字符出棧,復(fù)制到temp棧中來;
while (stack[top] != '[') {
//優(yōu)化:如果topOfTemp到達(dá)了棧的上限,則為棧擴(kuò)容;
if (topOfTemp == tempSize - 1) {
temp = realloc(temp, (tempSize += 10) * sizeof(char));
}
//temp棧的棧頂指針自增;
++topOfTemp;
//將stack棧頂字符復(fù)制到temp棧中來;
temp[topOfTemp] = stack[top];
//stack出棧,則top棧頂指針遞減;
top--;
}
printf("#② 開始獲取要復(fù)制的字符信息之后 # top = %d\n",top);
//找到倍數(shù)數(shù)字.strOfInt字符串;
//注意:如果是大于1位的情況就處理
char strOfInt[11];
//p記錄當(dāng)前的top;
int curTop = top;
printf("#③ 開始獲取數(shù)字,數(shù)字位置上限 # curTop = %d\n",curTop);
//top--的目的是把"["剔除,才能找到數(shù)字;
top--;
//遍歷stack得出數(shù)字
//例如39[a] 就要找到這個(gè)數(shù)字39.
//p指向當(dāng)前的top,我就知道上限了; 那么接下來通過循環(huán)來找它的數(shù)字下限;
//結(jié)束條件:棧指針指向?yàn)榭? stack[top] 不等于數(shù)字
while (top != -1 && stack[top] >= '0' && stack[top] <= '9') {
top--;
}
printf("#③ 開始獲取數(shù)字,數(shù)字位置下限 # top = %d\n",top);
//從top-1遍歷到p之間, 把stack[top-1,p]之間的數(shù)字復(fù)制到strOfInt中來;
//39中3和9都是字符. 我們要獲取到這2個(gè)數(shù)字,存儲(chǔ)到strOfInt數(shù)組
for (int j = top + 1; j < curTop; ++j) {
strOfInt[j - (top + 1)] = stack[j];
}
//為字符串strOfInt數(shù)組加一個(gè)字符結(jié)束后綴'\0'
strOfInt[curTop - (top + 1)] = '\0';
//把strOfInt字符串轉(zhuǎn)換成整數(shù) atoi函數(shù);
//把字母復(fù)制strOfInt份到stack中去;
//例如39[a],就需要把復(fù)制39份a進(jìn)去;
int curNum = atoi(strOfInt);
for (int k = 0; k < curNum ; ++k) {
//從-1到topOfTemp 范圍內(nèi),復(fù)制curNum份到stackTop中去;
int kk = topOfTemp;
while (kk != -1) {
//優(yōu)化:如果stack到達(dá)了棧的上限,則為棧擴(kuò)容;
if (top == stackSize - 1) {
stack = realloc(stack, (stackSize += 50) * sizeof(char));
}
//將temp棧的字符復(fù)制到stack中;
//stack[++top] = temp[kk--];
++top;
stack[top] = temp[kk];
kk--;
}
}
free(temp);
temp = NULL;
}
}
//realloc 動(dòng)態(tài)內(nèi)存調(diào)整;
//void *realloc(void *mem_address, unsigned int newsize);
//構(gòu)成字符串stack后, 在stack的空間擴(kuò)容.
char* ans = realloc(stack, (top + 1) * sizeof(char));
ans[++top] = '\0';
//stack 棧不用,則釋放;
free(stack);
return ans;
}
測(cè)試輸入打印...
int main(int argc, const char * argv[]) {
// insert code here...
printf("字符串編碼問題!\n");
char *s ;
s = decodeString("12[a]");
printf("字符編碼后的結(jié)果: %s\n\n\n\n",s);
// s = decodeString("3[a]2[bc]");
// printf("字符編碼后的結(jié)果: %s\n\n\n\n",s);
//
// s = decodeString("3[a2[c]]");
// printf("字符編碼后的結(jié)果: %s\n\n\n\n",s);
//
// s = decodeString("2[abc]3[cd]ef");
// printf("字符編碼后的結(jié)果: %s\n\n\n\n",s);
printf("\n");
return 0;
}
八、去除重復(fù)字母(LeetCode-困難)
給你一個(gè)僅包含小寫字母的字符串，請(qǐng)你去除字符串中重復(fù)的字母，使得每個(gè)字母只出現(xiàn)一次。需保證返回結(jié)果的字典序最?。ㄒ蟛荒艽騺y其他字符的相對(duì)位置）
示例1:
輸入:"bcabc"
輸出:"abc"
示例2:
輸入:"cbacdcbc"
輸出:"acdb"
解題關(guān)鍵:
字典序: 字符串之間比較和數(shù)字比較不一樣; 字符串比較是從頭往后挨個(gè)字符比較,那個(gè)字符串大取決于兩個(gè)字符串中第一個(gè)對(duì)應(yīng)不相等的字符; 例如 任意一個(gè)a開頭的字符串都大于任意一個(gè)b開頭的字符串;例如字典中apple 大于 book;
題目的意思,你去除重復(fù)字母后,需要按最小的字典序返回.并且不能打亂其他字母的相對(duì)位置;
例如 bcabc 你應(yīng)該返回abc, 而不是bca,cab;
例如 cbacdcbc 應(yīng)該返回acdb,而不是cbad,bacd,adcb
例如 zab,應(yīng)該返回zab,而不是abz;
思路:
- 判斷字符串可能出現(xiàn)的特殊情況
- 用一個(gè)record數(shù)組記錄字符串中字母出現(xiàn)的次數(shù);
- 申請(qǐng)一個(gè)字符串棧stack用來存儲(chǔ)去除重復(fù)字母的結(jié)果,并利用它的特性幫助我們找到正確的次序;
- 遍歷字符串s
- 從0~top,遍歷stack 判斷當(dāng)前字符s[i]是否存在于棧stack中
如果當(dāng)前字符是否存在于棧的定義一個(gè)falg 標(biāo)記isExist, 0表示不存在, 1表示存在
6.如果isExist存在,record[s[i]]位置上的出現(xiàn)次數(shù)減一，并繼續(xù)遍歷下一個(gè)字符; 表示當(dāng)前的stack已經(jīng)有這個(gè)字符了沒有必要處理這個(gè)重復(fù)的字母;
7.如果isExist不存在,則
如果不存在,則需要循環(huán)一個(gè)找到一個(gè)正確的位置,然后在存儲(chǔ)起來;
如果不存在，跳過棧中所有比當(dāng)前字符大、且后面還會(huì)出現(xiàn)的元素，然后將當(dāng)前字符入棧
top > -1表示棧非空
stack[top] > s[i]表示棧頂元素比當(dāng)前元素大
record[stack[top]] > 1表示后面還會(huì)出現(xiàn)
通過一個(gè)while循環(huán)找到將棧中位置錯(cuò)誤的數(shù)據(jù),出棧. 找當(dāng)前合適的位置,則結(jié)束while循環(huán);
找到合理的位置后,則將當(dāng)前字符s[i]入棧;
8.直到遍歷完所有字符后,則為字符串棧stack 添加一個(gè)結(jié)束符'\0',并返回當(dāng)前字符串首地址;
char *removeDuplicateLetters(char *s)
{
/*
① 特殊情況處理,s為空,或者字符串長(zhǎng)度為0;
② 特殊情況,s的長(zhǎng)度為1,則沒有必要后續(xù)的處理,則直接返回s;
*/
if (s == NULL || strlen(s) == 0) {
return "";
}
if (strlen(s) == 1) {
return s;
}
//record數(shù)組,用來記錄字符串s中每個(gè)字符未來會(huì)出現(xiàn)的次數(shù);
char record[26] = {0};
int len = (int)strlen(s);
//申請(qǐng)一個(gè)字符串stack;(用棧的特性來進(jìn)行stack字符串的數(shù)據(jù)進(jìn)出)
char* stack = (char*)malloc(len * 2 * sizeof(char));
//memset(void *s, int ch, size_t n) 將stack len*2*sizeof(char)長(zhǎng)度范圍的空間填充0;
memset(stack, 0, len * 2 * sizeof(char));
//stack 棧頂賦初值為-1;
int top = -1;
//1.統(tǒng)計(jì)每個(gè)字符的頻次
//例如bcabc recod[26] = {1,2,2};
int i;
for (i = 0; i < len; i++) {
record[s[i] - 'a']++;
}
//2.遍歷s,入棧
for (i = 0; i < len; i++) {
//isExist 標(biāo)記, 判斷當(dāng)前字符是否存在棧中;
int isExist = 0;
//①從0~top,遍歷stack 判斷當(dāng)前字符s[i]是否存在于棧stack中
//如果當(dāng)前字符是否存在于棧的flag, 0表示不存在, 1表示存在
//top指向棧頂(也是執(zhí)行stack字符串最后一個(gè)字符的位置,表示字符串長(zhǎng)度上限)
for (int j = 0; j <= top; j++) {
if (s[i] == stack[j]) {
isExist = 1;
break;
}
}
//② 如果存在,record[s[i]]位置上的出現(xiàn)次數(shù)減一，并繼續(xù)遍歷下一個(gè)字符
//③ 如果不存在,則需要循環(huán)一個(gè)正確位置存儲(chǔ)起來;
//④ 如果不存在，跳過棧中所有比當(dāng)前字符大、且后面還會(huì)出現(xiàn)的元素，然后將當(dāng)前字符入棧
// top > -1表示棧非空
//stack[top] > s[i]表示棧頂元素比當(dāng)前元素大
//record[stack[top]] > 1表示后面還會(huì)出現(xiàn)
//例如b,c因?yàn)椴环弦韵聴l件會(huì)直接入棧.stack[] = "bc",但是當(dāng)當(dāng)前字符是"a"時(shí),由于bcabc,a不應(yīng)該是在stack的順序是"bca",所以要把位置不符合的字符出棧;
//top = 1,stack[top] > s[i], c>a; 并且stack[top] 在之后還會(huì)重復(fù)的出現(xiàn),所以我們可以安心的把stack中的棧頂C出棧,所以stack[]="b",top減一后等于0; 同時(shí)也需要將record[c]出現(xiàn)次數(shù)減一;
//top=0,stack[top]>s[i],b>a,并且stack[top] 在之后還會(huì)出現(xiàn),所以stack把棧頂b出棧,所以此時(shí)棧stack[]="",top減一后等于-1, 此時(shí)棧中位置不正確的字符都已經(jīng)移除;
if (isExist == 1) {
record[s[i] - 'a']--;
} else {
while (top > -1 && stack[top] > s[i] && record[stack[top] - 'a'] > 1) {
// 跳過該元素，頻次要減一
record[stack[top] - 'a']--;
// 出棧
top--;
}
//⑤ 結(jié)束while 循環(huán);
//循環(huán)結(jié)束的3種可能性:(1)移動(dòng)到棧底(top == -1) ; (2)棧頂元素小于當(dāng)前元素(stack[top] <= s[i]) (3)棧頂元素后面不出現(xiàn)(record[stack[top]] == 1)
// 此時(shí)，當(dāng)前元素要插入到top的下一個(gè)位置
// top往上移動(dòng)1位
top++;
// 入棧
stack[top] = s[i];
}
}
//結(jié)束棧頂添加字符結(jié)束符
stack[++top] = '\0';
return stack;
}
