数据结构与算法总结一(基于C/OC)


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;

}



```





最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,937评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,503评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,712评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,668评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,677评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,601评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,975评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,637评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,881评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,387评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,971评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2 342