算法，是我們程序員縱向發(fā)展所必須攀登的一座大山一罩，下面我們做一些算法題，難度逐漸遞增撇簿。當(dāng)然我們碰見解不開的題時千萬不要?dú)怵H聂渊，有時候一天做出一道題，都是很不容易的四瘫。
- 充分閱讀題目.了解題目背后的關(guān)鍵意思;
- 分析題目,涉及到哪些數(shù)據(jù)結(jié)構(gòu),對問題進(jìn)行分類. 到底屬于鏈表問題, 棧思想問題, 字符串問題,二叉樹問題,圖相關(guān)問題,排序問題; 與你之前所接觸過的算法題有沒有類似,找到問題的解題思路
- 實(shí)現(xiàn)算法. 在算法的實(shí)現(xiàn)的過程,并不是一蹴而就, 肯定是需要不斷的調(diào)試,修改的;
- 驗(yàn)證算法正確性
- 找到題源, 看其他的開發(fā)者對齊的解決思路.
- 找到題解建議之后, 對于其他優(yōu)秀思路,分析它的優(yōu)勢,并且學(xué)習(xí)它的思路.并且寫成其他解法的代碼
- 算法題的解題能力來自于2點(diǎn): 對于數(shù)據(jù)結(jié)構(gòu)與算法核心問題是否夯實(shí) + 是否有足夠多且足夠耐心的積累;
其中第五步和第六步格外的重要汉嗽，我們在作出算法題之后，不要沉迷于短暫的喜悅之中找蜜，而是要多看看其他大神的解題思路饼暑，取其精華，學(xué)習(xí)思想，算法最重要的還是思想弓叛，只做題的話就有點(diǎn)揀了芝麻丟了西瓜的意思了
我們做算法的時候可以多利用棧的思想（先進(jìn)后出）解決問題彰居，有時候會特別方便，那么什么時候可以利用棧思想呢撰筷？大體分為以下三點(diǎn)：
- 數(shù)據(jù)是線性的
- 問題中常常涉及到數(shù)據(jù)的來回比較,匹配問題;例如,每日溫度,括號匹配,字符串解碼,去掉重復(fù)字母等問題.
- 問題中涉及到數(shù)據(jù)的轉(zhuǎn)置,例如進(jìn)制問題.鏈表倒序打印問題等
Tip：注意并不是說棧思想只是一個解決的的參考思想.并不是萬能的.它適用于以上這樣的情況下去解決問題;
1. 進(jìn)制轉(zhuǎn)化問題（LeetCode-簡單）
給定一個十進(jìn)制的數(shù)字N陈惰，將其轉(zhuǎn)化為M進(jìn)制（以8為例）。
解題思路：
- 初始化一個空棧S
- 當(dāng)十進(jìn)制N非零時,循環(huán)執(zhí)行以下操作
- 把N與8求余得到的八進(jìn)制數(shù)壓入棧S;
- N更新為N與8的商;
- 當(dāng)棧S非空時,循環(huán)執(zhí)行以下操作
- 彈出棧頂元素e;
- 輸出e;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲空間初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType類型根據(jù)實(shí)際情況而定闭专，這里假設(shè)為int */
/* 順序棧結(jié)構(gòu) */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* 用于棧頂指針 */
}SqStack;
//4.1 構(gòu)建一個空棧S
Status InitStack(SqStack *S){
S->top = -1;
return OK;
}
//4.2 將棧置空
Status ClearStack(SqStack *S){
//疑問: 將棧置空,需要將順序棧的元素都清空嗎?
//不需要,只需要修改top標(biāo)簽就可以了.
S->top = -1;
return OK;
}
//4.3 判斷順序棧是否為空;
Status StackEmpty(SqStack S){
if (S.top == -1)
return TRUE;
else
return FALSE;
}
//4.4 返回棧的長度
int StackLength(SqStack S){
return S.top + 1;
}
//4.5 獲取棧頂
Status GetTop(SqStack S,SElemType *e){
if (S.top == -1)
return ERROR;
else
*e = S.data[S.top];
return OK;
}
//4.6 插入元素e為新棧頂元素
Status PushData(SqStack *S, SElemType e){
//棧已滿
if (S->top == MAXSIZE -1) {
return ERROR;
}
//棧頂指針+1;
S->top ++;
//將新插入的元素賦值給棧頂空間
S->data[S->top] = e;
return OK;
}
//4.7 刪除S棧頂元素,并且用e帶回
Status Pop(SqStack *S,SElemType *e){
//空棧,則返回error;
if (S->top == -1) {
return ERROR;
}
//將要刪除的棧頂元素賦值給e
*e = S->data[S->top];
//棧頂指針--;
S->top--;
return OK;
}
//4.8 從棧底到棧頂依次對棧中的每個元素打印
Status StackTraverse(SqStack S){
int i = 0;
printf("此棧中所有元素");
while (i<=S.top) {
printf("%d ",S.data[i++]);
}
printf("\n");
return OK;
}
解題如下：
void conversion(int N){
SqStack S;
SElemType e;
//1.初始化一個空棧S
InitStack(&S);
//2.
while (N) {
PushData(&S, N%8);
N = N/8;
}
//3.
while (!StackEmpty(S)) {
Pop(&S, &e);
printf("%d\n",e);
}
}
2. 爬樓梯問題（LeetCode-中等）
假設(shè)你正在爬樓梯奴潘。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個臺階影钉。你有多少種不同的方法可以爬到樓頂呢画髓？注意：給定 n 是一個正整數(shù)。
示例例1:
輸?入: 2
輸初: 2
解釋: 有2種?方法可以爬到樓頂
①. 1階+1階
②. 2階
示例例2:
輸?入: 3
輸初: 3
解釋: 有3種?方法可以爬到樓頂
①. 1階+1階+1階
②. 1階+2階
③. 2階+1階
我們分為兩種方法解答：①.遞歸法 ②. 動態(tài)規(guī)劃法
方法一:遞歸求解法
/*
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);
}
方法二:動態(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];
}
3. 楊輝三角（LeetCode-中等）
給定一個非負(fù)整數(shù) numRows平委，生成楊輝三角的前 numRows 行奈虾。在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和廉赔。
示例:
輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
我們利用動態(tài)規(guī)劃法解決這個問題肉微。
思路:
- 第一層循環(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;
}
動態(tài)規(guī)劃
動態(tài)規(guī)劃(英語:Dynamic programming，簡稱 DP)是一種在數(shù)學(xué)蜡塌、管理理科學(xué)碉纳、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)和?生物信息 學(xué)中使?用的馏艾，通過把原問題分解為相對簡單的?子問題的?方式求解復(fù)雜問題的方法劳曹。
動態(tài)規(guī)劃常常適?用于有重疊?子問題和最優(yōu)?子結(jié)構(gòu)性質(zhì)的問題，動態(tài)規(guī)劃?方法所耗時間往往遠(yuǎn)少于樸素解法琅摩。
動態(tài)規(guī)劃背后的基本思想非常簡單铁孵。?致上，若要解一個給定問題房资，我們需要解其不不同部分(即?問題)蜕劝，再根據(jù)子問題的解以得出原問題的解。動態(tài)規(guī)劃往往用于優(yōu)化遞歸問題轰异，例如斐波那契數(shù)列岖沛，如果運(yùn)用遞歸的方式來求解會重復(fù)計(jì)算很多相同的子問題，利?用動態(tài)規(guī)劃的思想可以減少計(jì)算量搭独。通常許多子問題?常相似烫止，為此動態(tài)規(guī)劃法試圖僅僅解決每個子問題一次，從?而減少計(jì)算量戳稽。
?旦某個給定?子問題的解已經(jīng)算出，則將其記憶化存儲，以便下次需要同一個?問題解之時直接查表惊奇。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增?時特別有用互躬。
4. 括號匹配檢驗(yàn)（LeetCode-中等）
假設(shè)表達(dá)式中允許包含兩種括號:圓括號與方括號,其嵌套順序隨意,即() 或者[([][])]都是正確的.而這 [(]或者(()])或者([()) 都是不正確的格式. 檢驗(yàn)括號是否匹配的方法可用"期待的急迫程度"這個概念來描述.
第一種解法：鏈?zhǔn)酱鎯?/p>
typedef int Status;
typedef int SElemType; /* SElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
/* 鏈棧結(jié)構(gòu) */
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*StackNodePtr;
typedef struct
{
int count;
StackNodePtr top;
}LinkStack;
Status InitStack(LinkStack *S){
S->top = (StackNodePtr)malloc(sizeof(StackNode));
if (S->top == NULL) {
return ERROR;
}
S->top = NULL;
S->count = 0;
return OK;
}
Status Push(LinkStack *S ,char data){
if (!S) return ERROR;
StackNodePtr temp = (StackNodePtr)malloc(sizeof(StackNode));
temp->data = data;
temp->next = S->top;
S->top = temp;
S->count++;
return OK;
}
Status Pop(LinkStack *S ,char *e){
if (!S || !S->top) return ERROR;
*e = S->top->data;
StackNodePtr node = S->top;
S->top = S->top->next; // 更換頭結(jié)點(diǎn)
S->count--;
free(node);
return OK;
}
Status BracketsCheck(char *string) {
LinkStack stack;
InitStack(&stack);
char *p = string;
while (*p) {
if (*p == '[' || *p == '(') {
if (!Push(&stack, *p)) {
return FALSE;
}
} else if (*p == ']') {
char bracket = 0;
if (!Pop(&stack, &bracket) || bracket != '[') {
return FALSE;
}
} else if (*p == ')') {
char bracket = 0;
if (!Pop(&stack, &bracket) || bracket != '(') {
return FALSE;
}
}
p++;
}
return TRUE;
}
if (BracketsCheck("([]())")) {
printf("括號格式正確\n");
} else {
printf("括號格式錯誤\n");
}
第二種解法：順序存儲
typedef struct {
char * base ;//棧底指針
char * top ; //棧頂指針
int stacksize; //棧MaxSize
}SqStack;
//初始化棧
/*
思路:
1. 如果棧底為空
2. 分配一個最大容量Stack_Init_Size的數(shù)組,棧底/棧頂都指向與它.[參考圖空棧情況]
3. 初始化棧的最大容易Stack_Init_Size
*/
int Init(SqStack *stack){
stack->base = (char *)malloc(sizeof(char)*Stack_Init_Size);
stack->top = stack->base;
if (stack->base == NULL) {
return -1;
}
stack->stacksize = Stack_Init_Size;
printf("初始化成功\n");
return 0;
}
//獲取棧頂數(shù)據(jù)
/*
思路:
1.判斷棧是否為空
2.非空,則棧定指針-1,返回棧頂元素;
*/
char GetTop(SqStack stack){
if (stack.base == stack.top) {
printf("沒有數(shù)據(jù)\n");
return '#';
}
return *(stack.top-1);
}
//往棧中插入元素
/*
思路:
1.判斷棧是否已滿,若滿則返回ERROR #問題:如何判斷棧是否已滿?
2.棧滿,則續(xù)容空間 #問題:如何給已滿棧續(xù)容空間?
3.將元素element壓棧
4.棧頂指針加"1"
*/
Status PushData(SqStack *stack,char element){
if (stack->top - stack->base == Stack_Init_Size) {
//棧滿擴(kuò)容
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 OK;
}
//刪除棧頂元素
/*
思路:
1.判斷棧是否已空
2.非空,則獲取棧頂元素,并將棧頂減"1";
*/
char PopData(SqStack *stack){
if(stack->top==stack->base){
printf("棧為空\n");
return '#';
}
//printf("刪除數(shù)據(jù)成功");
return *--stack->top;
}
//釋放椝汤桑空間
int Destroy(SqStack *stack){
free(stack->base);
stack->stacksize=0;
return 0;
}
//處理數(shù)據(jù)吼渡，借助棧判斷
/*
思路:
1. 將第0個元素壓棧
2. 遍歷[1,strlen(data)]
(3). 取棧頂字符
(4). 檢查該字符是左括號("(","[")
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){
PushData(&stack,data[0]);
for(int i=1;i<strlen(data);i++){
char top = GetTop(stack);
switch(top){
case '(':
if(data[i]==')')PopData(&stack);
else PushData(&stack,data[i]);
break;
case '[':
if(data[i]==']')PopData(&stack);
else PushData(&stack,data[i]);
break;
case '#':
if(data[i]=='('||data[i]=='['){
PushData(&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;
}
}
SqStack stack;
Init(&stack);
char data[180];
printf("請輸入要校驗(yàn)的符號:\n");
scanf("%s",data);
int result = ExecuteData(stack,data);
if(result==0)printf("括號是正確匹配的\n");
else printf("括號匹配不正確\n");
5. 每日氣溫
根據(jù)每日 氣溫 列表，請重新生成一個列表乓序，對應(yīng)位置的輸入是你需要再等待多久溫度才會升高的天數(shù)寺酪。如果之后都不會升高，請輸入 0 來代替替劈。
例如寄雀，給定一個列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]陨献。
提示：氣溫 列表長度的范圍是 [1, 30000]盒犹。每個氣溫的值的都是 [30, 100] 范圍內(nèi)的整數(shù)。
提示：氣溫 列表長度的范圍是 [1, 30000]眨业。每個氣溫的值的均為華氏度急膀，都是在 [30, 100] 范圍內(nèi)的整數(shù)。
解題關(guān)鍵: 實(shí)際上就是找當(dāng)前元素 從[i,TSize] 找到大于該元素時. 數(shù)了幾次. 首先最后一個元素默認(rèn)是0,因?yàn)樗竺嬉呀?jīng)沒有元素了.
typedef struct Temp {
int index;/* 用于棧頂指針 */
int temp;
} Temp;
int* dailyTemperatures(int* T, int TSize, int* returnSize) {
int *ans = (int *)calloc(TSize, sizeof(int ));
Temp *stack = (Temp *)malloc(sizeof(Temp) * TSize);
*returnSize = TSize;
int top = 0;
for (int i = 0; i < TSize; i++) {
printf("%d %d\n",top,stack[top].temp);
if (top > 0 && T[i] > stack[top].temp) { // 棧中有值龄捡，且當(dāng)前溫度比棧頂溫度更高
for (; top > 0 && T[i] > stack[top].temp; top--) { // 遍歷比棧頂溫度低的溫度
ans[stack[top].index] = i - stack[top].index; // 計(jì)算相隔天數(shù)
}
}
// 入棧當(dāng)前溫度卓嫂。每次都是入棧新的溫度
top++;
stack[top].index = i;
stack[top].temp = T[i];
}
return ans;
}
int temperatures[8] = {73, 74, 75, 71, 69, 72, 76, 73};
int returnSize;
int *result = dailyTemperatures(temperatures, 8, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
typedef struct Temp {
int index;/* 用于棧頂指針 */
int temp;
} Temp;
int* dailyTemperatures(int* T, int TSize, int* returnSize) {
/* 存儲結(jié)果 */
// int *ans = (int *)malloc(sizeof(int) * TSize);
int *ans = (int *)calloc(TSize, sizeof(int ));
/* 存儲原始的氣溫?cái)?shù)據(jù) */
Temp *stack = (Temp*)malloc(sizeof(Temp) * TSize);
*returnSize = TSize;
int top = 0;
/* 73, 74, 75, 71, 69, 72, 76, 73 */
for (int i = 0; i < TSize; i++) {
printf("%d %d\n",top,stack[top].temp);
if (top > 0 && T[i] > stack[top].temp) { // 棧中有值，且當(dāng)前溫度比棧頂溫度更高
for (; top > 0 && T[i] > stack[top].temp; top--) { // 遍歷棧內(nèi)的溫度有沒有比當(dāng)前溫度低的溫度
ans[stack[top].index] = i - stack[top].index; // 計(jì)算相隔天數(shù)
printf("內(nèi)層循環(huán)%d\n",top);
}
}
// 入棧當(dāng)前溫度聘殖。每次都是入棧新的溫度
top++;
stack[top].index = i;
stack[top].temp = T[i];
}
return ans;;
}
/*
暴力法1:
1. 從左到右開始遍歷,從第一個數(shù)到最后一個數(shù)開始遍歷. 最后一個數(shù)因?yàn)楹竺鏇]有元素,默認(rèn)是0,不需要計(jì)算;
2. 從[i+1,TSize]遍歷,每個數(shù)直到找到比它大的數(shù),數(shù)的次數(shù)就是對應(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;
}
/*
跳躍對比:
1. 從右到左遍歷. 因?yàn)樽詈笠惶斓臍鉁夭粫偕?默認(rèn)等于0;
2. i 從[TSize-2,0]; 從倒數(shù)第二天開始遍歷比較. 每次減一;
3. j 從[i+1,TSize]遍歷, j+=result[j],可以利用已經(jīng)有結(jié)果的位置進(jìn)行跳躍,從而減少遍歷次數(shù)
-若T[i]<T[j],那么Result = j - i;
-若reuslt[j] == 0,則表示后面不會有更大的值,那么當(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;
}
/*
思路:
1. 初始化一個棧(用來存儲索引),value數(shù)組
1. 棧中存儲的是元素的索引值index;
2.將當(dāng)前元素和棧頂元素比較;
如果棧為空,那么直接將當(dāng)前元素索引index 存儲到棧中;
如果棧頂元素>當(dāng)前元素,則將當(dāng)前元素索引index 存儲到棧中;
如果棧頂元素<當(dāng)前元素,則將當(dāng)前元素索引index-棧頂元素index,計(jì)算完畢則將當(dāng)前棧頂元素移除,將當(dāng)前元素索引index 存儲到棧中
*/
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;
}
6.一只青蛙一次可以跳上1級臺階，也可以跳上2級绷旗。喜鼓。。衔肢。庄岖。它也可以跳上n級，此時該青蛙跳上一個n級的臺階總共有多少種跳法角骤？
用數(shù)學(xué)歸納法可以證明：f(n)=2n?1f(n)=2n?1.
遞歸式證明：
當(dāng)n = 1 時隅忿， 只有一種跳法心剥，即1階跳：Fib(1) = 1;
當(dāng)n = 2 時， 有兩種跳的方式背桐，一階跳和二階跳：Fib(2) = Fib(1) + Fib(0) = 2;
當(dāng)n = 3 時优烧，有三種跳的方式，
第一次跳出一階后链峭，后面還有Fib(3-1)中跳法畦娄；
第一次跳出二階后，后面還有Fib(3-2)中跳法弊仪；
第一次跳出三階后熙卡，后面還有Fib(3-3)中跳法
Fib(3) = Fib(2) + Fib(1)+Fib(0)=4;
當(dāng)n = n 時，共有n種跳的方式励饵，
第一次跳出一階后驳癌，后面還有Fib(n-1)中跳法；
第一次跳出二階后曲横，后面還有Fib(n-2)中跳法……………………..
第一次跳出n階后, 后面還有 Fib(n-n)中跳法.
Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+……….+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+…….+Fib(n-1)
又因?yàn)镕ib(n-1)=Fib(0)+Fib(1)+Fib(2)+…….+Fib(n-2)
兩式相減得：Fib(n)-Fib(n-1)=Fib(n-1)
=====》 Fib(n) = 2*Fib(n-1) n >= 2
遞歸等式如下：
n = 1 f(n) = 1;
n = 2 f(n) = 2;
n > 2 f(n) = 2 * f(n-1);
所以：f(n)=2?f(n?1)=2?2(n?2)....=2n?1?f(0)=2n?1f(n)=2?f(n?1)=2?2(n?2)....=2n?1?f(0)=2n?1
int FrogJump12nStepRecursive(int n)
{
if (n == 1){
return 1;
}else if (n == 2){
return 2;
}else{
return 2 * FrogJump12nStepRecursive(n - 1);
}
}
7. 取出重復(fù)字符
給你一個僅包含小寫字母的字符串喂柒，請你去除字符串中重復(fù)的字母，使得每個字母只出現(xiàn)一次禾嫉。需保證返回結(jié)果的字典序最性纸堋（要求不能打亂其他字符的相對位置）
字符串解碼
給定一個經(jīng)過編碼的字符串，返回它解碼后的字符串熙参。
編碼規(guī)則為:k[encoded_string]艳吠，表示其中方括號內(nèi)部的encoded_string正好重復(fù)k次，k為正整數(shù)孽椰。
你可以認(rèn)為輸入字符串總是有效的昭娩；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的黍匾。
此外栏渺，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復(fù)的次數(shù) k 锐涯，例如不會出現(xiàn)像3a或2[4]的輸入磕诊。
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef"
解題關(guān)鍵:
字典序: 字符串之間比較和數(shù)字比較不一樣; 字符串比較是從頭往后挨個字符比較,那個字符串大取決于兩個字符串中第一個對應(yīng)不相等的字符; 例如 任意一個a開頭的字符串都大于任意一個b開頭的字符串;例如字典中apple 大于 book;
題目的意思,你去除重復(fù)字母后,需要按最小的字典序返回.并且不能打亂其他字母的相對位置;
例如 bcabc 你應(yīng)該返回abc, 而不是bca,cab;
例如 cbacdcbc 應(yīng)該返回acdb,而不是cbad,bacd,adcb
例如 zab,應(yīng)該返回zab,而不是abz;
char *removeDuplicateLetters(char *s)
{
/*
① 特殊情況處理,s為空,或者字符串長度為0;
② 特殊情況,s的長度為1,則沒有必要后續(xù)的處理,則直接返回s;
*/
if (s == NULL || strlen(s) == 0) {
return "";
}
if (strlen(s) == 1) {
return s;
}
char record[26] = {0};
int len = (int)strlen(s);
char* stack = (char*)malloc(len * 2 * sizeof(char));
//memset(void *s, int ch, size_t n) 將stack len*2*sizeof(char)長度范圍的空間填充0;
memset(stack, 0, len * 2 * sizeof(char));
//stack 棧頂賦初值為-1;
int top = -1;
//1.統(tǒng)計(jì)每個字符的頻次
int i;
for (i = 0; i < len; i++) {
record[s[i] - 'a']++;
}
//2.遍歷s,入棧
for (i = 0; i < len; i++) {
int isExist = 0;
for (int j = 0; j <= top; j++) {
if (s[i] == stack[j]) {
isExist = 1;
break;
}
}
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--;
}
top++;
// 入棧
stack[top] = s[i];
}
}
//結(jié)束棧頂添加字符結(jié)束符
stack[++top] = '\0';
return stack;
}
printf("去掉重復(fù)字母! LeetCode-困難 \n");
char *s ;
s = removeDuplicateLetters("bcabc");
printf("%s\n",s);
s = removeDuplicateLetters("zab");
printf("%s\n",s);
s = removeDuplicateLetters("cbacdcbc");
printf("%s\n",s);
printf("\n");
8.字符串編碼
給定一個經(jīng)過編碼的字符串纹腌，返回它解碼后的字符串霎终。
編碼規(guī)則為:k[encoded_string]，表示其中方括號內(nèi)部的encoded_string正好重復(fù)k次升薯，k為正整數(shù)莱褒。
你可以認(rèn)為輸入字符串總是有效的；輸入字符串中沒有額外的空格涎劈，且輸入的方括號總是符合格式要求的广凸。
此外阅茶，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復(fù)的次數(shù) k 炮障，例如不會出現(xiàn)像3a或2[4]的輸入目派。
示例：
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef"
char * decodeString(char * s){
/*
題目: 字符串編碼LeetCode-中等
編碼規(guī)則為: k[encoded_string]，表示其中方括號內(nèi)部的 encoded_string 正好重復(fù) k 次胁赢。注意 k 保證為正整數(shù)。你可以認(rèn)為輸入字符串總是有效的白筹；輸入字符串中沒有額外的空格智末，且輸入的方括號總是符合格式要求的。此外徒河，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字系馆，所有的數(shù)字只表示重復(fù)的次數(shù) k ，例如不會出現(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)前字符不為方括號"]" 則入棧stack中;
2.如果當(dāng)前字符遇到了方括號"]" 則:
① 首先找到要復(fù)制的字符,例如stack="12[a",那么我要首先獲取字符a;將這個a保存在另外一個棧去tempStack;
② 接下來,要找到需要備份的數(shù)量,例如stack="12[a",因?yàn)槌鰲＿^字符"a",則當(dāng)前的top指向了"[",也就是等于2;
③ 而12對于字符串是2個字符, 我們要通過遍歷找到數(shù)字12的top上限/下限的位置索引, 此時上限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.獲取字符串長度
2.設(shè)置默認(rèn)棧長度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]這個字母a 賦值到temp棧中來;
//簡單說,就是將stack中方括號里的字符出棧,復(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] 就要找到這個數(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個數(shù)字,存儲到strOfInt數(shù)組
for (int j = top + 1; j < curTop; ++j) {
strOfInt[j - (top + 1)] = stack[j];
}
//為字符串strOfInt數(shù)組加一個字符結(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 動態(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;
}
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;
}
