括號(hào)匹配
題目：
假設(shè)表達(dá)式中允許包含兩種括號(hào):圓括號(hào)與?括號(hào),其嵌套順序隨意,即() 或者[([][])]都是正 確的.?這[(]或者(()])或者([()) 都是不正確的格式. 檢驗(yàn)括號(hào)是否匹配的?法可?”期待的急迫 程度"這個(gè)概念來描述.例如,考慮以下括號(hào)的判斷: [ ( [ ] [ ] ) ]
解題思路：
對(duì)于上述問題我們可以考慮使用棧來解決刀诬，每當(dāng)遇到左括號(hào)時(shí)郎任，將符號(hào)入棧巫击，當(dāng)遇到右括號(hào)時(shí)丰榴，取棧頂?shù)姆?hào)與之匹配，如果能夠匹配，將括號(hào)出棧。如果不能匹配，結(jié)束循環(huán)惫搏，說明格式不正確。遍歷結(jié)束蚕涤，如果棧中的元素不為0筐赔，則說明還有沒有匹配成功的元素，返回匹配失敗揖铜。
代碼：
int checkMatchingBrackets(char * S){
// 獲取字符串長度
unsigned long length = strlen(S);
// 初始化棧
Stack stack;
InitStack(&stack);
PushStack(&stack, S[0]);
// 1.如果是左括號(hào) 入棧
// 2.如果是右括號(hào), 取棧頂元素, 如果括號(hào)可以匹配, 將棧頂元素出棧, 繼續(xù)循環(huán). 如果不配直接return.
for (int i = 1; i < length; i++) {
char c = S[i];
switch (c) {
case ']':
{
char top;
GetTop(stack, &top);
if (top == '[') {
PopStack(&stack, &top);
break;
} else {
return -1;
}
}
case '}':
{
char top;
GetTop(stack, &top);
if (top == '{') {
PopStack(&stack, &top);
break;
} else {
return -1;
}
}
case ')':
{
char top;
GetTop(stack, &top);
if (top == '(') {
PopStack(&stack, &top);
break;
} else {
return -1;
}
}
default:
PushStack(&stack, c);
break;
}
}
if (StackLength(stack) == 0) {
DestoryStack(&stack);
return 0;
} else {
DestoryStack(&stack);
return -1;
}
}
返回0說明匹配成功茴丰，-1表示匹配失敗。棧的實(shí)現(xiàn)可以參考之前的文章：
時(shí)間復(fù)雜度： O(n)
空間復(fù)雜度： O(n)
每日氣溫
題目：
根據(jù)每日 氣溫 列表，請(qǐng)重新生成一個(gè)列表贿肩，對(duì)應(yīng)位置的輸出是需要再等待多久溫度才會(huì)升高超過該日的天數(shù)峦椰。如果之后都不會(huì)升高，請(qǐng)?jiān)谠撐恢糜?0 來代替汰规。
例如汤功，給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]
解法一: 暴力法
思路： 如果數(shù)組的長度為n, 當(dāng)遍歷到第i個(gè)元素（0 <= i < n）時(shí), 從[j, n-1] （i + 1 <= j < n）開始遍歷溜哮，如果遇到比第i個(gè)元素大的值滔金，那么result[i] = j - i。
代碼：
int* dailyTemperatures(int* T, int TSize, int* returnSize){
int *res = (int *)malloc(sizeof(int) * TSize);
*returnSize = TSize;
for (int i = 0; i < TSize; i++) {
int x = T[i];
int diff = 0;
for (int j = i + 1; j < TSize; j++) {
int y = T[j];
if (y > x) {
diff = j - i;
break;
}
}
res[i] = diff;
}
return res;
}
時(shí)間復(fù)雜度： O(n^2)
空間復(fù)雜度： O(1)
解法二： 跳躍對(duì)比
思路：
這個(gè)思路和解法一的思路類似都是使用兩次嵌套循環(huán)進(jìn)行查找茂嗓，不同的是餐茵，此解法是外層遍歷是從后往前開始遍歷的。這樣能夠利用已知的信息減少第二次循環(huán)的次數(shù)述吸。
- 最后一天的值一定是
0忿族，因?yàn)樽詈笠惶旌竺嬉欢ú粫?huì)有比他溫度更高的。 - 外層循環(huán)從
[TSize - 2, 0]遍歷數(shù)組刚梭， 元素索引為i肠阱。 - 內(nèi)存循環(huán)從
[i + 1, TSize - 1]票唆， 元素索引為j朴读。- 如果
T[j] > T[i],那么res[i] = j - i - 如果
T[j] <= T[i]- 如果
res[j] == 0則res[i] = 0. 第j天之后沒有比它溫度更高的，那么一定不會(huì)楚天比第i天更高的走趋。 - 如果
res[j] != 0,則j+=res[j]衅金。第j天之后還有比它更高的，直接跳躍到這一天進(jìn)行對(duì)比簿煌。
- 如果
- 如果
代碼：
int* dailyTemperatures2(int* T, int TSize, int* returnSize){
int *res = (int *)malloc(sizeof(int) * TSize);
*returnSize = TSize;
// 最后一個(gè)元素,一定沒有比他溫度跟高的,所以等于0
res[TSize - 1] = 0;
// 從 TSize - 1 開始往前遍歷
for (int i = TSize - 2; i >= 0; i--) {
int x = T[i];
int diff = 0;
for (int j = i + 1; j < TSize; ) {
int y = T[j];
if (y > x) {
diff = j - i;
break;
} else {
// 利用已知信息進(jìn)行跳躍對(duì)比
if (res[j] == 0) {
// 第j天的溫度, 比第i天更低, 第j天后面沒有比他溫度更高的,那么一定不會(huì)出現(xiàn)比第i天更高的,
diff = 0;
break;
} else {
// 第j天后面還有比他更高的,那么直接跳到這天進(jìn)行對(duì)比
j+=res[j];
}
}
}
res[i] = diff;
}
return res;
}
解法三：棧
思路：
- 初始化一個(gè)棧
indexStack用來存放索引氮唯，和結(jié)果數(shù)組result - 遍歷數(shù)組
- 如果當(dāng)前溫度大于棧頂?shù)臏囟龋敲礂ｍ斣匾涛埃瑧?yīng)該在當(dāng)前溫度的索引和棧頂溫度索引的差天后遇到比它溫度高的惩琉。將棧頂元素出棧。
- 將當(dāng)前索引入棧
- 遍歷結(jié)束夺荒，將棧中剩余的元素瞒渠，在結(jié)果數(shù)組
result對(duì)應(yīng)的索引位置的值設(shè)置為0。
代碼：
int* dailyTemperatures(int* T, int TSize, int* returnSize){
int *stack = (int *)malloc(sizeof(int) * TSize);
int top = -1;
int *result = malloc(sizeof(int) * TSize);
*returnSize = TSize;
top++;
stack[top] = 0;
for (int i = 1; i < TSize; i++) {
int temp = T[i];
int topIndex = stack[top];
int topTemp = T[topIndex];
while (topTemp < temp) {
result[topIndex] = i - topIndex;
top--;
if (top == -1) break;
topIndex = stack[top];
topTemp = T[topIndex];
}
top++;
stack[top] = i;
}
while (top != -1) {
result[stack[top]] = 0;
top--;
}
return result;
}
時(shí)間復(fù)雜度：O(n)
爬樓梯
題目：
爬樓梯問題:(LeetCode-中等) 假設(shè)你正在爬樓梯技扼。需要 n 階你才能到達(dá)樓頂伍玖。每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不 同的?法可以爬到樓頂呢剿吻？注意：給定 n 是?個(gè)正整數(shù)窍箍。
解法一：遞歸法
思路：： 如果要爬n階樓梯，是爬n-1階樓梯的方法與爬n-2階樓梯的和。f(n) = f(n-1) + f(n-2).
代碼：
int climbStairs1(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs1(n - 1) + climbStairs1(n - 2);
}
時(shí)間復(fù)雜度： O(2^n).這種時(shí)間復(fù)雜度椰棘，執(zhí)行效率太低纺棺。
解法二：動(dòng)態(tài)規(guī)劃
不難發(fā)現(xiàn)，這個(gè)問題可以被分解為一些包含最優(yōu)子結(jié)構(gòu)的子問題邪狞，即它的最優(yōu)解可以從其子問題的最優(yōu)解來有效地構(gòu)建五辽，我們可以使用動(dòng)態(tài)規(guī)劃來解決這一問題。
在第i階可以又以下兩種方法達(dá)到：
- 在第i-1階后爬一階
- 在第i-2階后爬兩階
到達(dá)第i階的方法總數(shù)外恕，就是(i - i)階和（i - 2）的方法數(shù)之和杆逗。
代碼：
int climbStairs2(int n) {
if (n < 3) {
return n;
}
int arr[n];
arr[0] = 1;
arr[1] = 2;
for (int i = 2; i < n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n - 1];
}
時(shí)間復(fù)雜度： O(n).
字符串編碼
問題：
字符串編碼(LeetCode-中等) 給定?個(gè)經(jīng)過編碼的字符串，返回它解碼后的字符串鳞疲。 編碼規(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 = "12[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
思路： 編碼的字符串存在層級(jí)關(guān)系，所以需要進(jìn)行一層一層的解碼急黎，聯(lián)想到之前的括號(hào)匹配問題扎狱，可以使用棧結(jié)構(gòu)解決問題。一次將字符串進(jìn)行解碼勃教。根據(jù)題目可以得到三個(gè)關(guān)鍵點(diǎn)：
- 遍歷時(shí)第一次出現(xiàn)數(shù)字字符淤击，到
[符號(hào)之間，表示此層字符重復(fù)的次數(shù)故源。 - 遇到
[符號(hào)是污抬，創(chuàng)建一個(gè)棧元素入棧，棧元素保存了此層[]之間的字符绳军，和重復(fù)的次數(shù)印机。 - 每當(dāng)遇到
]時(shí)，需要將此層字符進(jìn)行展開删铃，然后出棧元素耳贬，將展開的字符，添加到此時(shí)棧頂元素的內(nèi)容后面猎唁。
代碼：
Swift實(shí)現(xiàn)版本
public struct Stack<T> {
/// Datastructure consisting of a generic item.
fileprivate var array = [T]()
/// The number of items in the stack.
public var count: Int {
return array.count
}
/// Verifies if the stack is empty.
public var isEmpty: Bool {
return array.isEmpty
}
/**
Pushes an item to the top of the stack.
- Parameter element: The item being pushed.
*/
public mutating func push(_ element: T) {
array.append(element)
}
/**
Removes and returns the item at the top of the sack.
- Returns: The item at the top of the stack.
*/
public mutating func pop() -> T? {
return array.popLast()
}
/// Returns the item at the top of the stack.
public var top: T? {
return array.last
}
}
class StackElem {
var repeatCount: Int = 1
var content: String = ""
var result: String {
return String(repeating: content, count: repeatCount)
}
}
func stringDecode(_ str: String) -> String {
var repeatCountStr: String = ""
var stack = Stack<StackElem>()
stack.push(StackElem())
for c in str {
switch c {
case "a"..."z":
let top = stack.top!
top.content.append(c)
break
case "0"..."9":
repeatCountStr.append(c)
break
case "[" :
// 創(chuàng)建一個(gè)棧元素 入棧
let elem = StackElem()
elem.repeatCount = Int(repeatCountStr)!
repeatCountStr = ""
stack.push(elem)
break
case "]":
// 將棧頂元素出棧
let elem = stack.pop()!
if let top = stack.top {
// 棧中還有元素
top.content.append(elem.result)
}
break
default:
break
}
}
return stack.top?.content ?? ""
}
時(shí)間復(fù)雜度：O(n)
字符串去重
題目：
給你一個(gè)僅包含小寫字母的字符串咒劲，請(qǐng)你去除字符串中重復(fù)的字母顷蟆，使得每個(gè)字母只出現(xiàn)一次。需保證返回結(jié)果的字典序最懈辍（要求不能打亂其他字符的相對(duì)位置）帐偎。
思路： 使用兩次遍歷的方式，第一次遍歷記錄每個(gè)字符出現(xiàn)的次數(shù)蛔屹。第二次遍歷將每個(gè)字符和棧頂字符進(jìn)行比較削樊，如果棧頂字符較小，且后面出現(xiàn)的次數(shù)大于0兔毒，將棧元素出棧漫贞，此棧頂元素出現(xiàn)次數(shù)-1.繼續(xù)對(duì)比下個(gè)棧頂元素，如果棧頂元素在后面不會(huì)出現(xiàn)育叁，將當(dāng)前元素入棧迅脐。
- 創(chuàng)建數(shù)組
letterAppearCount來儲(chǔ)存字符出現(xiàn)的個(gè)數(shù)，將他的每個(gè)元素設(shè)置為0豪嗽。用字符當(dāng)索引時(shí)要字符的索引應(yīng)該為letters - ’a‘,這時(shí)索引值才是從0開始的 - 創(chuàng)建
seen數(shù)組儲(chǔ)存字符是否在棧中0不在谴蔑，1在棧中。 - 第一次遍歷龟梦，如果當(dāng)前的字符為
c隐锭， 那么letterAppearCount[c - 'a'] = letterAppearCount[c - 'a'] + 1. - 第二次遍歷， 創(chuàng)建一個(gè)棧
stack计贰，用來進(jìn)行字典序排序钦睡。- 如果字符在棧中，更新
letterAppearCount數(shù)量 - 如果當(dāng)前字符
c字典序大于棧頂字符蹦玫，將字符c入棧赎婚。 - 如果當(dāng)前字符
c字典序小于棧頂字符，有兩種情況：- 如果棧頂字符在
letterAppearCount數(shù)組中的值大于0時(shí)樱溉，將此元素出棧。同時(shí)更新letterAppearCount數(shù)組中的值-1,seen數(shù)組中置為0,繼續(xù)和棧頂元素進(jìn)行比較 - 如果棧頂字符在
letterAppearCount數(shù)組中的值為0纬凤，說明后面不會(huì)出現(xiàn)了福贞，就不能將這個(gè)字符出棧了。
- 如果棧頂字符在
- 將當(dāng)前字符
c入棧, 更新seen數(shù)組中置為1
- 如果字符在棧中，更新
- 最后得到棧中的從棧底到棧頂組成的字符串就是字典序最小的字符串了停士。
代碼：
char * removeDuplicateLetters(char * s){
// 記錄字符出現(xiàn)次數(shù)的數(shù)組
int *letterAppearCount = (int *)malloc(sizeof(int) * 26);
memset(letterAppearCount, 0, sizeof(int) * 26);
// 記錄字符是否在棧中的數(shù)組
int *seen = (int *)malloc(sizeof(int) * 26);
memset(seen, 0, 26 * sizeof(char));
unsigned long length = strlen(s);
for (int i = 0; i < length; i++) {
letterAppearCount[s[i] - 'a']++;
// printf("字符%c出現(xiàn)次數(shù): %d\n", s[i], letterAppearCount[s[i] - 'a']);
}
char *stack = malloc(sizeof(char) * 27);
int top = -1;
for (int i = 0; i < length; i++) {
char c = s[i];
// 字符已經(jīng)在棧中
if (seen[c - 'a'] == 1) {
// 當(dāng)初字符的出現(xiàn)次數(shù)-1
letterAppearCount[c - 'a']--;
continue;
}
while (top != -1 &&
stack[top] > c &&
letterAppearCount[stack[top] - 'a'] > 1) {
seen[stack[top] - 'a'] = 0;
letterAppearCount[stack[top] - 'a']--;
//printf("out %c, 剩余次數(shù): %d\n", stack[top], letterAppearCount[stack[top] - 'a']);
top--;
}
top++;
stack[top] = c;
seen[c - 'a'] = 1;
//printf("in %c\n", c);
}
top++;
stack[top] = '\0';
//printf("result: %s\n", stack);
return stack;
}
楊輝三角
代碼
int** generate(int numRows, int* returnSize, int** returnColumnSizes){
int **res = malloc(sizeof(int *) * numRows);
*returnSize = numRows;
*returnColumnSizes = malloc(sizeof(int) * numRows);
for (int i = 0; i < numRows; i++) {
int *row = (int *)malloc(sizeof(int) * (i + 1));
res[i] = row;
// 填入行首
res[i][0] = 1;
// 填入行尾
res[i][i] = 1;
(*returnColumnSizes)[i] = i + 1;
if (i < 2) continue;
for (int j = 1; j < i; j++) {
res[i][j] = res[i - 1][j] + res[i - 1][j - 1];
}
}
return res;
}
