新国产少妇一区二区,香蕉视频黄色97

0. 棧思想

利用棧的特性(先進后出)來解決問題，適合的題目類型：

數(shù)據(jù)是線性的
問題中常常設(shè)計到數(shù)據(jù)的來回比較、匹配問題，如括號匹配、每日溫度、字符串解碼、去掉重復(fù)字母等問題。
問題中涉及到數(shù)據(jù)的轉(zhuǎn)置，如進制問題、鏈表倒序打印等。

1. 括號匹配檢驗

假設(shè)表達式中允許包含兩種括號：圓括號和方括號,其嵌套的順序隨意,即([]())?或?[([][])]等為正確的格式，[(]或([())或(()])均為不正確的格式。輸入一個包含上述括號的表達式，檢驗括號是否配對。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef char SElemType;

/* 鏈棧結(jié)構(gòu) */
typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, *StackNodePtr;

typedef struct {
    StackNodePtr top;
} LinkStack;

Status Push(LinkStack *S, SElemType e) {
    if (!S) return ERROR;
    StackNodePtr node = (StackNodePtr)malloc(sizeof(StackNode));
    node->data = e;
    node->next = S->top; // 頭插法
    S->top = node; // 更換頭結(jié)點
    return OK;
}

Status Pop(LinkStack *S, SElemType *e) {
    if (!S || !S->top) return ERROR;
    *e = S->top->data;
    StackNodePtr node = S->top;
    S->top = S->top->next; // 更換頭結(jié)點
    free(node);
    return OK;
}

Status BracketsCheck(char *string) {
    LinkStack stack;
    stack.top = NULL;
    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;
}

int main(int argc, const char * argv[]) {
    if (BracketsCheck("[]()")) {
        printf("括號格式正確\n");
    } else {
        printf("括號格式錯誤\n");
    }
    return 0;
}

2. 每日氣溫

根據(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

棧里面的值，是從大到小排列的，棧底溫度最高，棧頂溫度最低
如果棧里面有值，當(dāng)前溫度比比棧頂溫度更高，依次彈出溫度更低的節(jié)點，并和當(dāng)前索引進行計算獲取像個天數(shù)
新的溫度入棧，原棧頂?shù)囊幌盗袦囟雀偷墓?jié)點都被彈出了，現(xiàn)在新的溫度就是最低的溫度

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 = -1;
    for (int i = 0; i < TSize; i++) {
        if (top > -1 && T[i] > stack[top].temp) { // 棧中有值，且當(dāng)前溫度比棧頂溫度更高
            for (; top > -1 && T[i] > stack[top].temp; top--) { // 遍歷比棧頂溫度低的溫度
                ans[stack[top].index] = i - stack[top].index; // 計算相隔天數(shù)
            }
        }
        // 入棧當(dāng)前溫度
        top++;
        stack[top].index = i;
        stack[top].temp = T[i];
    }
    return ans;
}

int main(int argc, const char * argv[]) {
    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");
    return 0;
}

思路2

從后往前進行計算，緩存第 $j$ 天再過 $x$ 天溫度更高
當(dāng)前溫度還是從前往后遍歷
- 比如第 $j-1$ 天比第 $j$ 天溫度更高，那么我們直接跳過 $x$ 天就可以拿到更高的溫度，而不需要依次比較
如果第 $j$ 天后沒有哪一天溫度更高，則結(jié)束查找

int  *dailyTemperatures_2(int* T, int TSize, int* returnSize){
    int *result = (int *)malloc(sizeof(int) * TSize);
    *returnSize = TSize;
    result[TSize-1] = 0; // 最后一個后面沒有了
    // 倒著計算溫度間隔，倒數(shù)第一個已經(jīng)有了，從倒數(shù)第二個開始
    for (int i = TSize-2; i >= 0; i--) {
        // 從當(dāng)前位置后一個位置開始向后遍歷，T[i]為當(dāng)前溫度，T[j]為索引溫度
        // 通過result[j]可以知道需要前進的天數(shù)，來獲取更高的溫度
        for (int j = i+1; j < TSize; j+=result[j]) {
            if (T[i] < T[j]) { // 當(dāng)前溫度比索引溫度低，則找到了
                result[i] = j-i;
                break;
            } else if (result[j] == 0) { // 當(dāng)前溫度比索引溫度高，但是后面沒有比這個溫度更高的了
                result[i] = 0;
                break;
            }
        }
    }
    return result;
}

3. 爬樓梯問題

假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數(shù)。

3.1 暴力遞歸

根據(jù)之前的步數(shù)，嘗試走1步或者2步，看會不會到達階梯總數(shù)。

結(jié)束條件：

階梯總數(shù)比走過的步數(shù)小 $n < setp$ ，則這不是一種可行的方法，返回0。
階梯總數(shù)等于走過的步數(shù) $n == setp$ ，則這是一種方法，返回1。

通過畫圖，我們可以發(fā)現(xiàn)這是一個樹形結(jié)構(gòu)。

時間復(fù)雜度： $O(2^n)$

空間復(fù)雜度： $O(n)$

static int climb_stairs(int step, int n) {
        if (step > n) {
            return 0;
        } else if (step == n) {
            return 1;
        }
        return climb_stairs(step + 1, n) + climb_stairs(step + 2, n);
    }

int climbStairs(int n) {
    return climb_stairs(0, n);
}

3.2 動態(tài)規(guī)劃

第 $i$ 階可以由以下兩種方法得到：

在第 $(i-1)$ 階后向上爬1階。
在第 $(i-2)$ 階后向上爬 2 階。

令 $a[i]$ 表示能到達第 $i$ 階的方法總數(shù)：
$a[i] = a[i-1] + a[i-2]$
這里我們使用一個數(shù)組來進行結(jié)果的統(tǒng)計。

時間復(fù)雜度： $O(n)$

空間復(fù)雜度： $O(n)$

int climbStairs (int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int *a = (int *)malloc(sizeof(int) * (n + 1));
    a[1] = 1;
    a[2] = 2;
    for (int i = 3; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2];
    }
    n = a[n];
    free(a);
    return n;
}

3.3 進一步優(yōu)化

我們發(fā)現(xiàn)，這就是一個斐波那契數(shù)列，且下一個參數(shù)只和前兩個項有關(guān)，那么這兩項之前的空間是沒有必要的。

我們只是有2個參數(shù)來保留前兩項的結(jié)果就行了。

時間復(fù)雜度： $O(n)$

空間復(fù)雜度： $O(1)$

int climbStairs (int n) {
    if (n == 1) return 1;
    int first = 1, second = 2;
    for (int i = 3, third = 0; i <= n; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return second;
}

4. 去除重復(fù)字符

給你一個僅包含小寫字母的字符串，請你去除字符串中重復(fù)的字母，使得每個字母只出現(xiàn)一次。需保證返回結(jié)果的字典序最小（要求不能打亂其他字符的相對位置）。

示例 1:

輸入: "bcabc"
輸出: "abc"

示例 2:

輸入: "cbacdcbc"
輸出: "acdb"

思路：

字符a-z一共26個，加上結(jié)束符\0有27個，所以我們申請一個大小為27的char類型的棧。
先遍歷一遍，看每個字符出現(xiàn)的次數(shù)。
- 后期遍歷的時候可以知道，是否還可以刪除。(使得每個字母只出現(xiàn)一次)
再加入一個標(biāo)記，數(shù)組里面是否已經(jīng)存在某個字符了。
- 存在、后面還有，就可以刪除，后面會添加回來。
要求字典序，那么數(shù)組中的字符基本是由小到大排列的。(不是一定是，因為還要滿足每個字母只出現(xiàn)一次)

核心的處理：

當(dāng)前字符沒有入棧
- 棧不是空棧、當(dāng)前字符比棧頂字符小、棧頂?shù)脑睾竺孢€有時，我們可以把滿足這些條件的棧頂元素彈出。（后面還有機會再加回來）
- 再入棧當(dāng)前字符。(此時如果前面沒有再也不出現(xiàn)的字符，這個就是最小的字符)
結(jié)束遍歷時，棧頂加上結(jié)束符\0，就是我們的目標(biāo)字符串了。

char * removeDuplicateLetters(char *s) {
    if (!s || strlen(s) < 2) return s;
    int top = -1; // 棧頂
    char *stack = malloc(sizeof(char) * 27); // 給后面配置\0多加1
    char inStack[26] = {0}; // 是否入棧
    int charCount[26] = {0}; // 字符剩余總數(shù)
    // 統(tǒng)計單個字符總數(shù)
    char *p = s;
    while (*p) {
        charCount[*p - 'a']++;
        p++;
    }
    p = s;
    int idx = 0; //字符索引
    while (*p) {
        idx = *p - 'a'; // 當(dāng)前字符在數(shù)組中的索引值
        charCount[idx]--; // 更新元素的剩余次數(shù)
        if (!inStack[idx]) { // 當(dāng)前字符沒有入棧
            // 是否需要出棧棧頂字符
            while (top != -1 // 空棧不處理
                   && *p < stack[top] // 當(dāng)前字符比棧頂字符小
                   && charCount[stack[top] - 'a'] > 0) { // 棧頂字符在后面還有，就可以出棧
                inStack[stack[top] - 'a'] = 0; // 棧頂彈出，就沒有入棧了
                --top; // 出棧
            }
            // 當(dāng)前字符沒有入棧，就可以入棧
            stack[++top] = *p;
            inStack[idx] = 1;
        }
        p++; // 繼續(xù)遍歷
    }
    stack[++top] = '\0'; // 循環(huán)已保證棧底到棧頂是排好序的了，加上結(jié)束符
    return stack;
}

5. 字符串解碼

給定一個經(jīng)過編碼的字符串，返回它解碼后的字符串。

編碼規(guī)則為:k[encoded_string]，表示其中方括號內(nèi)部的encoded_string正好重復(fù)k次，k為正整數(shù)。

你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。

此外，你可以認為原始數(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".

#define MAXSIZE 2000

typedef char* StrType;
typedef struct StrStackNode
{
    int multi;
    StrType data;
    struct StrStackNode *next;
} StrStackNode, *StrStackNodePtr;

typedef struct
{
    StrStackNodePtr top;
    int count;
} StrLinkStack;

void PushStr(StrLinkStack *S, int multi, StrType e) {
    StrStackNodePtr node = (StrStackNodePtr)malloc(sizeof(StrStackNode));
    node->multi = multi;
    node->data = e;
    node->next = S->top;
    S->top = node;
}

void PopStr(StrLinkStack *S, int *multi, StrType *e) {
    StrStackNodePtr node = S->top;
    *multi = node->multi;
    *e = node->data;
    S->top = S->top->next;
    free(node);
}

char * decodeString(char *s)
{
    int multi = 0;
    StrType res = (StrType)malloc(sizeof(char) * MAXSIZE); // 記錄當(dāng)前的字符串
    *res = '\0';
    StrLinkStack strStack = {NULL, 0};
    StrType p = s;
    while (*p) {
        if(*p >= '0' && *p <= '9') { // 計算出現(xiàn)次數(shù)
            multi = multi * 10 + *p - '0';
        } else if (*p == '[') { // 入棧'['之前的次數(shù)和字符串
            PushStr(&strStack, multi, res);
            multi = 0;
            res = (StrType)malloc(sizeof(char) * MAXSIZE);
            *res = '\0';
        } else if (*p == ']') { // 出棧'['之前的次數(shù)和字符串
            StrType curStr = res; // 當(dāng)前是嵌套最深的字符串，如3[a2[cd]]中的cd
            int curMulti = 0;
            PopStr(&strStack, &curMulti, &res); // 出棧，如3[a2[cd]]中的2和"a"
            StrType tmp = (StrType)malloc(sizeof(char) * MAXSIZE);
            *tmp = '\0';
            for (int i = 0; i < curMulti; i++) { // 拼接，如3[a2[cd]]中的2[cd]
                strcat(tmp, curStr);
            }
            strcat(res, tmp); // 拼接，如3[a2[cd]]中的"a"和2[cd]生成的cdcd
        } else {
            strncat(res, p, 1); // 在字符串中追加一個字符
        }
        p++;
    }
    return res;
}

6. 楊輝三角

在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和。

示例：

輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

思路：

如果要求第n行的顯示可能還會考慮遞歸。這里要求每行都要返回，直接就按題目意思，使用動態(tài)規(guī)劃就好了。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generate(int numRows, int* returnSize, int** returnColumnSizes){
    int size, i;
    int **res = (int **)malloc(sizeof(int *) * numRows);
    int *columnSizes = (int *)malloc(sizeof(int) * numRows);
    for (int j = 0; j < numRows; j++) {
        size = j + 1;
        columnSizes[j] = size;
        res[j] = (int *)malloc(sizeof(int) * size);
        res[j][0] = 1;
        res[j][size-1] = 1;
        if (j > 1)
            for (i = 1; i < size-1; i++)
                res[j][i] = res[j-1][i-1] + res[j-1][i];
    }
    *returnColumnSizes = columnSizes;
    *returnSize = numRows;
    return res;
}

int main(int argc, const char * argv[]) {
    int **res, *returnColumnSizes;
    int returnSize;
    int numRows = 5;
    res = generate(numRows, &returnSize, &returnColumnSizes);
    for (int i = 0; i < returnSize; i++) {
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d ", res[i][j]);
        }
        printf("\n");
    }
    free(res);
    free(returnColumnSizes);
    return 0;
}
// 輸出
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1

7. 七進制數(shù)

給定一個整數(shù)，將其轉(zhuǎn)化為7進制，并以字符串形式輸出。

示例 1:

輸入: 100
輸出: "202"

示例 2:

輸入: -7
輸出: "-10"

注意: 輸入范圍是 [-1e7, 1e7] 。

思路：

范圍 [-1e7, 1e7] 。

int main(int argc, const char * argv[]) {
    int i = 1;
    int num = 1e7;
    while (num) {
        num = num / 7;
        i++;
    }
    printf("%d\n", i);
    return 0;
}
// 輸出
10

考慮到還有負號-，所以數(shù)組的長度至少為11。

進制轉(zhuǎn)換

$100 = 2*7^2+0*7^1+2*7^0$

$100\ \%\ 7=2$

$(100-2)/7=2*7^1+0*7^0$

我們可以看到通過不斷取余%和求商/操作，就可以拿到 $7^k$ 的系數(shù)，再加上'0'就是我們的字符表示了。
二進制字符表示是從高位到低位的，但我們上面的操作是從低位到高位進行獲取的，所以我們把順序數(shù)組改成棧的表示。最后出棧顯示最終結(jié)果。

char * convertToBase7(int num) {
    if (num == 0) return "0";
    int top = -1;
    char *stack = (char *)malloc(sizeof(char) * 11);
    // 確定正負
    int flag = 0;
    if (num < 0) {
        flag = 1;
        num = -num;
    }
    // 進制轉(zhuǎn)換，入棧
    char rest;
    while (num > 0) {
        rest = num % 7 + '0';
        num = num / 7;
        stack[++top] = rest;
    }
    if (flag) stack[++top] = '-';
    // 出棧輸出結(jié)果
    int count = top + 1;
    char *res = (char *)malloc(sizeof(char) * (count + 1));
    int i = 0;
    for (; i < count; i++) {
        res[i] = stack[top--];
    }
    res[i] = '\0';
    free(stack);
    return res;
}

8. 刪除字符串中的所有相鄰重復(fù)項

個人發(fā)現(xiàn)的一道比較有意思的題，有點像祖瑪游戲，中間消除之后，如果兩個相同元素相遇仍然可以消除。

leetcode 1047

給出由小寫字母組成的字符串 S，重復(fù)項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們。

在 S 上反復(fù)執(zhí)行重復(fù)項刪除操作，直到無法繼續(xù)刪除。

在完成所有重復(fù)項刪除操作后返回最終的字符串。答案保證唯一。

示例：

輸入："abbaca"
輸出："ca"
解釋：
例如，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時唯一可以執(zhí)行刪除操作的重復(fù)項。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執(zhí)行重復(fù)項刪除操作，所以最后的字符串為 "ca"。

提示：

1 <= S.length <= 20000
S 僅由小寫英文字母組成。

思路：

這里為了不適用額外的存儲空間，使用了雙指針?biāo)枷牒蜅Ｋ枷搿?/p>

快指針進行遍歷，慢指針表示棧頂，最后添加結(jié)束符。

char * removeDuplicates(char * S){
    int top = 0;
    for (int i = 0; S[i]; i++, top++) {
         S[top] = S[i];
         if (top > 0 && S[top] == S[top - 1])
             top -= 2;
    }
    S[top] = '\0';
    return S;
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)與算法-棧練習(xí)題

數(shù)據(jù)結(jié)構(gòu)與算法-棧練習(xí)題

0. 棧思想

1. 括號匹配檢驗

2. 每日氣溫

思路1

思路2

3. 爬樓梯問題

3.1 暴力遞歸

3.2 動態(tài)規(guī)劃

3.3 進一步優(yōu)化

4. 去除重復(fù)字符

5. 字符串解碼

6. 楊輝三角

7. 七進制數(shù)

8. 刪除字符串中的所有相鄰重復(fù)項

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)與算法-棧練習(xí)題

0. 棧思想

1. 括號匹配檢驗

2. 每日氣溫

思路1

思路2

3. 爬樓梯問題

3.1 暴力遞歸

3.2 動態(tài)規(guī)劃

3.3 進一步優(yōu)化

4. 去除重復(fù)字符

5. 字符串解碼

6. 楊輝三角

7. 七進制數(shù)

8. 刪除字符串中的所有相鄰重復(fù)項

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av