1.语言:C/OC
2.环境:Leetcode/Xcode
#1.数组
1.连续存储空间,对内存友好;
2.随机访问第K个元素,时间复杂度O(1);
3.删除,插入操作时间复杂度取决于移动元素,O(n);
小栗子:
#### [905. 按奇偶排序数组](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. 按奇偶排序数组 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.非连续存储空间,链式结构,对内存不友好;
2.访问第K个元素,时间复杂度O(n);
3.删除某个节点后的后继节点时间复杂度O(1),在某个节点后插入节点时间复杂度O(1);
4.双向链表,环形链表;
小栗子:
#### [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;
}
//删除节点p的后继节点
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.函数方法调用栈)
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冒泡排序(相邻元素交换,优化:1.当没有交换发生提前退出2.注意排序区间,减少遍历次数);
```
/*
注意值得比较 比较方式:相邻元素比较
优化:1.比较次数 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选择排序(基于比较,交换,每次遍历找到未排序区间最大/最小值);
```
/*
比较方式:每个位置依次找到最大最小值,依次比较
优化:记录最小值位置,交换次数优化
*/
- (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选择排序(基于比较,移动元素);
```
/*
元素比较,元素移动
已排序区间
*/
- (void)insertSort:(NSMutableArray*)array {
if (array == nil) {
return;
}
if (array.count <= 1) {
return;
}
for (NSInteger i = 1;i < array.count;i++) {
//要插入的数据
NSInteger temp = [array[i] integerValue];
NSInteger j = i-1;
//已排序区间
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函数,两个有序数组合并2.每次需要临时数组存储空间,不是原地排序算法3.稳定排序算法:顺序不变);
```
//归并排序
- (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;
}
//分割数组
- (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;
}
//合并数组
- (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.基于分治思想,递归思想关注点在分区函数,每次排序划分后的区间2.原地排序算法3.不稳定排序算法4.极端情况退化O(n*n),选择合适的分区函数)
```
//快速排序(这是分区函数拆分前)
- (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];
}
}
//最终将基准数归位, 因为i == j, 需要将<基数所在位置的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];
//继续左边的排序
[self quickSort:array left:left right:partition - 1 k:k];
//继续右边的排序
[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桶排序/计数排序 :针对数据范围不大的数据,将数据划分成不同的桶来实现排序;
3.2基数排序:要求数据可以划分成高低位,位之间有递进关系。
小栗子:
#### [242. 有效的字母异位词](https://leetcode-cn.com/problems/valid-anagram/)
```
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的一个字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?
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 *枚硬币。
给定一个数字 n,找出可形成完整阶梯行的总行数。
*n *是一个非负整数,并且在32位有符号整型的范围内。
示例 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;
}
```
数据结构与算法总结一(基于C/OC)
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...