1.語言:C/OC
2.環(huán)境:Leetcode/Xcode
#1.數(shù)組
1.連續(xù)存儲空間,對內(nèi)存友好扁凛;
2.隨機訪問第K個元素背伴,時間復雜度O(1)病附;
3.刪除问窃,插入操作時間復雜度取決于移動元素,O(n)完沪;
小栗子:
#### [905. 按奇偶排序數(shù)組](https://leetcode-cn.com/problems/sort-array-by-parity/)
```
/**
?* Return an array of size *returnSize.
?* Note: The returned array must be malloced, assume caller calls free().
?*/
#include <stdio.h>
int* sortArrayByParity(int* A, int ASize, int* returnSize) {
??? *returnSize=ASize;
??? int* temp=(int*)malloc(ASize*sizeof(int));
??? for (int i = 0,j = 0,k = ASize-1;i < ASize;i++) {
??????? if (A[i] % 2 == 0) {
??????????? temp[j] = A[i];
??????????? j++;
??????? }
??????? else {
??????????? temp[k] = A[i];
??????????? k--;
??????? }
??? }
??? return temp;
}
```
#### [922. 按奇偶排序數(shù)組 II](https://leetcode-cn.com/problems/sort-array-by-parity-ii/)
```
/**
?* Return an array of size *returnSize.
?* Note: The returned array must be malloced, assume caller calls free().
?*/
int* sortArrayByParityII(int* A, int ASize, int* returnSize) {
??? *returnSize=ASize;
??? int* temp=(int*)malloc(ASize*sizeof(int));
??? for (int i = 0,j = 0,k = 1;i < ASize;i++) {
??????? if (A[i]%2 == 0) {
??????????? temp[j] = A[i];
??????????? j +=2;
??????? }
??????? else {
??????????? temp[k] = A[i];
??????????? k += 2;
??????? }
??? }
??? return temp;
}
```
# 2.鏈表
1.非連續(xù)存儲空間域庇,鏈式結(jié)構(gòu),對內(nèi)存不友好;
2.訪問第K個元素覆积,時間復雜度O(n);
3.刪除某個節(jié)點后的后繼節(jié)點時間復雜度O(1)听皿,在某個節(jié)點后插入節(jié)點時間復雜度O(1);
4.雙向鏈表,環(huán)形鏈表;
小栗子:
#### [83. 刪除排序鏈表中的重復元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/)
```
/**
?* Definition for singly-linked list.
?* struct ListNode {
?*???? int val;
?*???? struct ListNode *next;
?* };
?*/
struct ListNode* deleteDuplicates(struct ListNode* head) {
??? if (head == NULL ||head->next == NULL) {
??????? return head;
??? }
??? struct ListNode* p = head;
??? int value = p->val;
??? while(p->next != NULL) {
??????? if(p->next->val == value) {
??????????? deleteNode(p);
??????? }
??????? //邊界條件
??????? if (p->next != NULL) {
??????????? if (p->next->val > value) {
??????????? p = p->next;
??????????? value = p->val;
????????? }
??????? }
??? }
??? return head;
}
//刪除節(jié)點p的后繼節(jié)點
void deleteNode(struct ListNode* p) {
??? struct ListNode* q;
??? if (p->next != NULL) {
??????? q = p->next;
??????? p->next = q->next; ?
??????? q = NULL;
??? }
}
```
#### [21. 合并兩個有序鏈表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
```
/**
?* Definition for singly-linked list.
?* struct ListNode {
?*???? int val;
?*???? struct ListNode *next;
?* };
?*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
??? //向第一個比較小的鏈表插入,注意鏈表長度可能不等
??? struct ListNode* w ,*head;
??? if (l1 == NULL) {
??????? return l2;
??? }
??? if (l2 == NULL) {
??????? return l1;
??? }
??? if (l1->val < l2->val) {
??????? head = l1;
??????? l1 = l1->next;
??? }
??? else {
??????? head = l2;
??????? l2 = l2->next;
??? }
??? w = head;
??? while(l1 != NULL && l2 != NULL) {
??????? if (l1->val < l2->val) {
??????????? w->next = l1;
??????????? l1 = l1->next;
??????? }
??????? else {
??????????? w->next = l2;
??????????? l2 = l2->next;
??????? }
??????? w = w->next;
??? }
??? if (l1 != NULL) {
??????? w->next = l1;
??? }
??? if (l2 != NULL) {
??????? w->next = l2;
??? }
??? return head;
}
```
# 3.棧與隊列
1.棧:先進后出FILO宽档,應用場景(1.iOS中頁面導航尉姨,前進與后退;2.函數(shù)方法調(diào)用棧)
2.隊列:先進先出吗冤,應用場景(1.線程隊列)
小栗子:
[20. 有效的括號](https://leetcode-cn.com/problems/valid-parentheses/)
```
bool isValid(char* s) {
? int length = strlen(s);
? char* temp = (char*)malloc(length);
? int tail = 0;
? for (int i = 0;i < length;i++) {
??? char value = s[i];
??? if (value == '(' || value == '{' || value == '[' ) {
??????? temp[tail] = value;
??????? tail++;
??? }
??? else {
??????? if (tail == 0) {
??????????? return false;
??????? }
??????? char now = temp[tail - 1];
??????? if ((now == '(' && value == ')') || (now == '{' && value == '}') || (now == '[' && value == ']')) {
??????? }
??????? else {
??????????? return false;
??????? }
??????? tail--;
??? }
? }
? if (tail != 0) {
??? return false;
? }
? return true;
}
```
# 4.遞歸思想
1.如何寫遞歸代碼又厉?
1.1 遞歸終止條件;
1.2 遞推公式欣孤;
小栗子:見下面歸并排序馋没,快速排序昔逗。
# 5.排序
1.時間復雜度為O(n*n):
1.1冒泡排序(相鄰元素交換降传,優(yōu)化:1.當沒有交換發(fā)生提前退出2.注意排序區(qū)間,減少遍歷次數(shù))勾怒;
```
/*
?注意值得比較 比較方式:相鄰元素比較
?優(yōu)化:1.比較次數(shù) 2.提前退出標志
?*/
- (void)bubbleSort:(NSMutableArray*)array {
??? if (array == nil) {
??????? return;
??? }
??? if (array.count <= 1) {
??????? return;
??? }
??? for (NSInteger i = 0;i < array.count;i++) {
??????? NSInteger flag = 0;
??????? for (NSInteger j = 0;j < array.count-1-i;j++) {
??????????? if ([array[j] integerValue] > [array[j+1] integerValue]) {
??????????????? NSInteger temp = [array[j] integerValue];
??????????????? array[j] = array[j+1];
??????????????? array[j+1] = [NSNumber numberWithInteger:temp];
??????????????? flag = 1;
??????????? }
??????? }
??????? if (!flag) {
??????????? return;
??????? }
??? }
}
```
1.2選擇排序(基于比較婆排,交換声旺,每次遍歷找到未排序區(qū)間最大/最小值);
```
/*
?比較方式:每個位置依次找到最大最小值段只,依次比較
?優(yōu)化:記錄最小值位置腮猖,交換次數(shù)優(yōu)化
?*/
- (void)selectSort:(NSMutableArray*)array {
??? if (array == nil) {
??????? return;
??? }
??? if (array.count <= 1) {
??????? return;
??? }
??? for (NSInteger i = 0;i < array.count;i++) {
??????? NSInteger minPos = i;
??????? for (NSInteger j = i+1; j < array.count;j++) {
??????????? if ( [array[minPos] integerValue] > [array[j] integerValue]) {
??????????????? minPos = j;
??????????? }
??????????? if (j == array.count - 1) {
??????????????? NSInteger temp = [array[minPos] integerValue];
??????????????? array[minPos] = array[i];
??????????????? array[i] = [NSNumber numberWithInteger:temp];
??????????? }
??????? }
?????? ?
??? }
?? ?
}
```
1.3選擇排序(基于比較,移動元素)赞枕;
```
/*
?元素比較澈缺,元素移動
?已排序區(qū)間
?*/
- (void)insertSort:(NSMutableArray*)array {
??? if (array == nil) {
??????? return;
??? }
??? if (array.count <= 1) {
??????? return;
??? }
??? for (NSInteger i = 1;i < array.count;i++) {
??????? //要插入的數(shù)據(jù)
??????? NSInteger temp = [array[i] integerValue];
??????? NSInteger j = i-1;
??????? //已排序區(qū)間
??????? for (;j >= 0;--j) {
??????????? //查找插入位置
??????????? if ([array[j] integerValue] > temp) {
??????????????? //依次向后移動
??????????????? array[j+1] = array[j];
??????????? }
??????????? else {
??????????????? break;
??????????? }
?????????? ?
??????? }
??????? array[j+1] = [NSNumber numberWithInteger:temp];
??? }
}
```
2.時間復雜度O(nlogn):
2.1歸并排序(1.基于分治思想,遞歸思想主要關注點在merge函數(shù)炕婶,兩個有序數(shù)組合并2.每次需要臨時數(shù)組存儲空間姐赡,不是原地排序算法3.穩(wěn)定排序算法:順序不變);
```
//歸并排序
- (void)mergeSort:(NSMutableArray*)array {
?? NSMutableArray * res =? [self mergeSort:array begin:0 end:array.count-1];
??? NSLog(@"res--%@",res);
}
- (NSMutableArray*)mergeSort:(NSMutableArray*)array begin:(NSInteger)begin end:(NSInteger)end {
??? if (begin >= end) {
??????? return [NSMutableArray arrayWithObjects:array[begin], nil];
??? }
??? NSInteger middle = (begin+end)/2;
??? NSMutableArray * leftArray = [self devidArray:array begin:begin end:middle];
??? NSMutableArray * rightArray = [self devidArray:array begin:middle+1 end:end];
??? [self mergeSort:leftArray begin:0 end:leftArray.count-1];
??? [self mergeSort:rightArray begin:0 end:rightArray.count-1];
??? NSMutableArray * res = [self mergeArray:leftArray right:rightArray ];
??? return? res;
}
//分割數(shù)組
- (NSMutableArray*)devidArray:(NSMutableArray*)array begin:(NSInteger)begin end:(NSInteger)end {
??? NSMutableArray * reslutArray = [NSMutableArray arrayWithCapacity:0];
??? for (NSInteger i = begin;i <= end;i++) {
??????? [reslutArray addObject:array[i]];
??? }
??? return reslutArray;
}
//合并數(shù)組
- (NSMutableArray*)mergeArray:(NSMutableArray*)left right:(NSMutableArray*)right {
??? NSMutableArray * resultArray = [NSMutableArray arrayWithCapacity:0];
??? NSInteger i = 0;
??? NSInteger j = 0;
??? while (i < left.count && j < right.count) {
??????? NSInteger valueL = [left[i] integerValue];
??????? NSInteger valueR = [right[j] integerValue];
??????? if (valueL < valueR) {
??????????? [resultArray addObject:[NSNumber numberWithInteger:valueL]];
??????????? i++;
??????? }
??????? else {
??????????? [resultArray addObject:[NSNumber numberWithInteger:valueR]];
??????????? j++;
??????? }
??? }
??? if (i < left.count) {
??????? for (;i<left.count;i++) {
??????????? [resultArray addObject:left[i]];
??????? }
??? }
??? if (j < right.count) {
??????? for (;j < right.count;j++) {
??????????? [resultArray addObject:right[j]];
??????? }
??? }
??? return resultArray;
}
```
2.2快速排序(1.基于分治思想柠掂,遞歸思想關注點在分區(qū)函數(shù)项滑,每次排序劃分后的區(qū)間2.原地排序算法3.不穩(wěn)定排序算法4.極端情況退化O(n*n),選擇合適的分區(qū)函數(shù))
```
//快速排序(這是分區(qū)函數(shù)拆分前)
- (void)quickSort:(NSMutableArray*)array begin:(NSInteger)begin end:(NSInteger)end {
??? if (begin >= end) {
??????? return;
??? }
?? // NSInteger partition = [self partition:array left:begin right:end];
?? ?
??? NSInteger i = begin;
??? NSInteger j = end;
??? NSInteger key = end;
??? while (i != j) {
??????? //注意前后順序 下面順序反了,所以錯了, 如果key改為end涯贞,則能正確輸出
??????? //key從頭枪狂,先遍歷尾;key從尾,先遍歷頭
??????? while (i<j && [array[i] integerValue] <= [array[key] integerValue]) {
??????????? i++;
??????? }
??????? while (i<j && [array[j] integerValue] >= [array[key] integerValue]) {
??????????? j--;
??????? }
?????? ?
??????? if (i < j) {
??????????? [array exchangeObjectAtIndex:i withObjectAtIndex:j];
??????? }
?????? ?
??? }
??? [array exchangeObjectAtIndex:i withObjectAtIndex:end];
?? ?
??? [self quickSort:array begin:begin end:i - 1];
??? [self quickSort:array begin:i + 1 end:end];
}
```
快速排序:
```
- (NSInteger)partition:(NSMutableArray*)array left:(NSInteger)left right:(NSInteger)right {
??? NSInteger key = left;
??? NSInteger i = left;
??? NSInteger j = right;
??? while (i != j) {
??????? while (i<j && [array[key] integerValue] <= [array[j] integerValue]) {
??????????? j--;
??????? }
??????? while (i<j && [array[key] integerValue] >= [array[i] integerValue]) {
??????????? i++;
??????? }
??????? if (i<j) {
??????????? [array exchangeObjectAtIndex:i withObjectAtIndex:j];
??????? }
??? }
?? ?
??? //最終將基準數(shù)歸位, 因為i == j, 需要將<基數(shù)所在位置的value>與<i/j相等的位置的value>互換位置
??? [array exchangeObjectAtIndex:i withObjectAtIndex:left];
??? return i;
}
- (void)quickSort:(NSMutableArray*)array left:(NSInteger)left right:(NSInteger)right k:(NSInteger)k{
??? if (left >= right) {
??????? return;
??? }
??? NSInteger partition = [self partition:array left:left right:right];
??? //繼續(xù)左邊的排序
??? [self quickSort:array left:left right:partition - 1 k:k];
??? //繼續(xù)右邊的排序
??? [self quickSort:array left:partition + 1 right:right k:k];
}
```
快排思想運用:O(n)時間復雜度求第K兴斡妗(大)
```
//求第K小
- (NSInteger)findK:(NSMutableArray*)array begin:(NSInteger)begin end:(NSInteger)end indexOfK:(NSInteger)k {
??? if (begin >= end) {
??????? return -1;
??? }
??? NSInteger partition = [self partition:array left:begin right:end];
??? if (partition+1 == k) {
??????? return [array[partition] integerValue];
??? }
??? else if (k > partition+1) {
????? return?? [self findK:array begin:partition+1 end:end indexOfK:k];
??? }
??? else {
????? return?? [self findK:array begin:begin end:partition-1 indexOfK:k];
??? }
??? return -1;
?? ?
}
```
3.線性排序/時間復雜度O(n)
3.1桶排序/計數(shù)排序 :針對數(shù)據(jù)范圍不大的數(shù)據(jù)州疾,將數(shù)據(jù)劃分成不同的桶來實現(xiàn)排序;
3.2基數(shù)排序:要求數(shù)據(jù)可以劃分成高低位,位之間有遞進關系傻谁。
小栗子:
#### [242. 有效的字母異位詞](https://leetcode-cn.com/problems/valid-anagram/)
```
給定兩個字符串 s 和 t 孝治,編寫一個函數(shù)來判斷 t 是否是 s 的一個字母異位詞。
示例 1:
??? 輸入: s = "anagram", t = "nagaram"
??? 輸出: true
示例 2:
??? 輸入: s = "rat", t = "car"
??? 輸出: false
說明:
你可以假設字符串只包含小寫字母审磁。
進階:
如果輸入字符串包含 unicode 字符怎么辦谈飒?你能否調(diào)整你的解法來應對這種情況?
bool isAnagram(char* s, char* t) {
??? int sLength = strlen(s);
??? int tLength = strlen(t);
??? if (sLength != tLength) {
??????? return false;
??? }
??? int ts[26] = { 0 };
??? int st[26] = { 0 };
??? for (int i = 0;i < sLength;i++) {
??????? ts[s[i] - 'a'] ++;
??????? st[t[i] - 'a'] ++;
??? }
??? for (int i = 0;i < 26;i++) {
??????? if (ts[i] != st[i]) {
??????????? return false;
??????? }
??? }
??? return true;
}
```
# 6.二分查找
1.適用場景有序集合态蒂,查找某一個元素時間復雜度O(logn)杭措;
2.基于分治思想;
基礎二分查找
```
- (NSInteger)binarySearch:(NSMutableArray*)array value:(NSInteger)value {
??? NSInteger head = 0;
??? NSInteger tail = array.count - 1;
?? ?
??? while (head <= tail) {
??????? NSInteger middle = head+(tail-head)/2;
??????? if ([array[middle] integerValue] > value) {
??????????? tail = middle - 1;
??????? }
??????? else if ([array[middle] integerValue] < value) {
??????????? head = middle + 1;
??????? }
??????? else {
??????????? return middle;
??????? }
??? }
??? return -1;
}
```
查找一個小于等于給定值得元素
```
- (NSInteger)binarySearch:(NSMutableArray*)array lastSmallValue:(NSInteger)value {
??? NSInteger head = 0;
??? NSInteger tail = array.count - 1;
??? while (head <= tail) {
??????? NSInteger middle = head + (tail-head)/2;
??????? if ([array[middle] integerValue] <= value) {
??????????? if (middle == array.count - 1) {
??????????????? return middle;
??????????? }
??????????? else if (middle + 1 <=? array.count - 1) {
??????????????? if ([array[middle+1] integerValue] > value) {
??????????????????? return middle;
??????????????? }
??????????????? else {
?????????????????? head = middle + 1;
??????????????? }
??????????? }
??????????? else {
?????????????? head = middle + 1;
??????????? }
?????????? ?
??????? }
??????? else if ([array[middle] integerValue] > value) {
?????????? ?
???????????? tail = middle - 1;
??????? }
??? }
??? return -1;
}
```
第一個大于等于給定值
```
- (NSInteger)binarySearch:(NSMutableArray*)array firstBigValue:(NSInteger)value {
??? NSInteger head = 0;
??? NSInteger tail = array.count - 1;
??? while (head <= tail) {
??????? NSInteger middle = head + (tail-head)/2;
??????? if ([array[middle] integerValue] >= value) {
??????????? if (middle == 0) {
??????????????? return middle;
??????????? }
??????????? else if (middle - 1 >= 0) {
??????????????? if ([array[middle-1] integerValue] < value) {
??????????????????? return middle;
??????????????? }
??????????????? else {
??????????????????? tail = middle - 1;
??????????????? }
??????????? }
??????????? else {
??????????????? tail = middle - 1;
??????????? }
?????????? ?
??????? }
??????? else if ([array[middle] integerValue] <value) {
??????????? head = middle + 1;
??????? }
??? }
??? return -1;
}
```
查找第一個值等于給定值
```
/*
?1.是不是第一個元素
?2.前一個元素是不是也等于value
?*/
- (NSInteger)binarySearch:(NSMutableArray*)array firstValue:(NSInteger)value {
??? NSInteger head = 0;
??? NSInteger tail = array.count - 1;
??? while (head <= tail) {
??????? NSInteger middle = head + (tail-head)/2;
??????? if ([array[middle] integerValue] > value) {
??????????? tail = middle - 1;
??????? }
??????? else if ([array[middle] integerValue] <value) {
??????????? head = middle + 1;
??????? }
??????? else {
??????????? if (middle == 0) {
??????????????? return middle;
??????????? }
??????????? else if (middle >= 1) {
??????????????? if ([array[middle - 1] integerValue] != value) {
??????????????????? return middle;
??????????????? }
??????????????? else {
??????????????????? //向前找
??????????????????? tail = middle - 1;
??????????????? }
??????????? }
??????????? else {
??????????????? //向前找
??????????????? tail = middle - 1;
??????????? }
??????? }
??? }
??? return -1;
}
```
最后一個值等于給定值
```
/*
?1.是不是最后一個元素
?2.后一個元素是不是也是value
?*/
- (NSInteger)binarySearch:(NSMutableArray*)array lastValue:(NSInteger)value {
??? NSInteger head = 0;
??? NSInteger tail = array.count - 1;
??? while (head <= tail) {
??????? NSInteger middle = head + (tail-head)/2;
??????? if ([array[middle] integerValue] > value) {
??????????? tail = middle - 1;
??????? }
??????? else if ([array[middle] integerValue] <value) {
??????????? head = middle + 1;
??????? }
??????? else {
??????????? if (middle == array.count - 1) {
??????????????? return middle;
??????????? }
??????????? else if (middle+1 <= array.count - 1) {
??????????????? if ([array[middle + 1] integerValue] != value) {
??????????????????? return middle;
??????????????? }
??????????????? else {
??????????????????? //向后找
??????????????????? head = middle + 1;
??????????????? }
??????????? }
??????????? else {
??????????????? //向后找
??????????????? head = middle + 1;
??????????? }
??????? }
??? }
??? return -1;
}
```
小栗子:
#### [441. 排列硬幣](https://leetcode-cn.com/problems/arranging-coins/)
```
你總共有 *n *枚硬幣钾恢,你需要將它們擺成一個階梯形狀手素,第 *k *行就必須正好有 *k *枚硬幣。
給定一個數(shù)字 n瘩蚪,找出可形成完整階梯行的總行數(shù)泉懦。
*n *是一個非負整數(shù),并且在32位有符號整型的范圍內(nèi)疹瘦。
示例 1:
??? n = 5
?? ?
??? 硬幣可排列成以下幾行:
??? ¤
??? ¤ ¤
??? ¤ ¤
?? ?
??? 因為第三行不完整崩哩,所以返回2.
int arrangeCoins(int n) {
??? // int i = 0,sum = 0;
??? // while(sum <= n) {
??? //???? i++;
??? //???? sum += i;
??? // }
??? // if (n - sum < i) {
??? //??? i--;
??? // }
??? return arrangeCoins2(n);
}
int arrangeCoins2(int n) {
??? int low = 0, high = (1 << 16) - 1,mid = 0,sum = 0;
??? while(low <= high) {
??????? mid = low + ((high-low)>>1);
??????? sum = ((mid&1) == 0) ? (mid/2) * (mid + 1) : ((mid + 1)/2) *mid;
??????? if (sum == n) {
??????????? return mid;
??????? }
??????? else if(sum > n) {
??????????? high = mid - 1;
??????? }
??????? else {
??????????? low = mid + 1;
??????? }
??? }
??? return sum > n ? mid-1 : mid;
}
```
數(shù)據(jù)結(jié)構(gòu)與算法總結(jié)一(基于C/OC)
最后編輯于 :
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門窖维,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人妙痹,你說我怎么就攤上這事陈辱。” “怎么了细诸?”我有些...
- 文/不壞的土叔 我叫張陵沛贪,是天一觀的道長。 經(jīng)常有香客問我震贵,道長利赋,這世上最難降的妖魔是什么? 我笑而不...
- 正文 為了忘掉前任猩系,我火速辦了婚禮媚送,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘寇甸。我一直安慰自己塘偎,他們只是感情好,可當我...
- 文/花漫 我一把揭開白布拿霉。 她就那樣靜靜地躺著吟秩,像睡著了一般。 火紅的嫁衣襯著肌膚如雪绽淘。 梳的紋絲不亂的頭發(fā)上涵防,一...
- 文/蒼蘭香墨 我猛地睜開眼赔退,長吁一口氣:“原來是場噩夢啊……” “哼橙依!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起,我...
- 正文 年R本政府宣布,位于F島的核電站纺蛆,受9級特大地震影響吐葵,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜桥氏,卻給世界環(huán)境...
- 文/蒙蒙 一温峭、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧字支,春花似錦凤藏、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至欠雌,卻和暖如春抠艾,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背桨昙。 一陣腳步聲響...