数据结构与算法面试题

Author：孟超
发布时间：November 10, 2019
176 views
No comments
百度收录：百度已收录
17803 字数
Categories：面试

十六进制转十进制

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main()
{
    string str;
    unordered_map<char,int> mmap;
    
    mmap['0']=0;
    mmap['1']=1;
    mmap['2']=2;
    mmap['3']=3;
    mmap['4']=4;
    mmap['5']=5;
    mmap['6']=6;
    mmap['7']=7;
    mmap['8']=8;
    mmap['9']=9;
    mmap['a']=10;
    mmap['A']=10;
    mmap['b']=11;
    mmap['B']=11;
    mmap['c']=12;
    mmap['C']=12;
    mmap['d']=13;
    mmap['D']=13;
    mmap['e']=14;
    mmap['E']=14;
    mmap['F']=15;
    mmap['f']=15;
    while(cin>>str)
    {
        int sum=0;
        str=str.substr(2);
        for(int i=0;i<str.size();i++)
        {
            sum=sum*16;
            sum=sum+mmap[str[i]];
        }
        cout << sum << endl;
    }
    return 0;
}

十进制转二进制


int transfer(int x)
{
    int p=1,y=0,yushu;
    while(1)
    {
        yushu=x%2;
        x/=2;
        y+=yushu*p;
        p*=10;
        if(x<2)
        {
            y+=x*p;
            break;
        }
    }
    return y;
}

自实现strcmp、自实现strcpy等
https://blog.csdn.net/z_ryan/article/details/79250265

一、双指针

两个变量，数组字符串链表中常用

**leetcode第15题：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]**
双指针解法，首先对数组中的元素进行排序，由小到大。然后定义三个指针使用三个指针（k<i<j)。固定最小的k在左边i=k+1,j=nums.size()-1。移动两个指针包夹求解。保存使得nums[i]+nums[j]+nums[k]=0的解。偏大时j左移，偏小时i右移。i和j相遇时，表示以当前k为最小值的解已经全部求得。k++ 进入下一次循环。解决重复解：上面的思路中可能存在重复解，原因是在i,j,k指针在移动时可能会出现重复数字的情况，比如：nums[i]==nums[i+1],这样的移动不考虑进去的话就会产生重复解。

参考代码:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int> >res;   
        int _size=nums.size();    
        if(_size<3||nums.front()>0||nums.back()<0)
        return res;
        int i,j,k;
        for(k=0;k<=_size-3;k++){
            if(nums[k]>0)
                break;                        //如果第一个元素都大于0，肯定越加越大，不可能为0了
            if(k>0&&nums[k]==nums[k-1])
                continue;                               //跳过无意义移动
            i=k+1;j=_size-1;
            while(i<j){
                if(nums[i]+nums[j]+nums[k]>0)
                    j--;
                else if(nums[i]+nums[j]+nums[k]<0)
                    i++;
                else{
                    res.push_back({nums[i],nums[j],nums[k]});
                    while(i<j&&nums[i]==nums[i+1])      //跳过无意义移动
                        i++;
                    while(i<j&&nums[j]==nums[j-1])      //同上
                        j--;
                    i++;
                    j--;           
                }
            }
        }
        return res;
    }
};

二、排序算法

快速排序，冒泡排序，选择排序，插入排序，希尔排序，归并排序

冒泡

void popSort(int *p, int n)
{
    int tmp;
    for(int i= n-1; i>0; i--)
    {
        for(int j=0; j<i; j++)
        {
            if(p[j] > p[j+1])
            {
                tmp = p[j];
                p[j] = p[j+1];
                p[j+1] = tmp;
            }
        }
    }
}

优点	稳定
缺点	慢，每次只能移动两个数据
平均时间复杂度	O(n2)

插入

void insertSort(int *a,int n)
{
    int i,j,key;
    for(i=1;i<n;i++)//控制需要插入的元素
    {
        key = a[i]; //key 为要插入的元素
            //查找要插入的位置,循环结束,则找到插入位置
        for(j=i; j-1>=0 && a[j-1]>key; j--)
        {
            a[j] = a[j-1]; //移动元素的位置.供要插入元素使用
        } 
        a[j] = key; //插入需要插入的元素
    }
}

优点	稳定，快
缺点	比较次数不一定，比较次数越少，插入点后的数据移动越多。
平均时间复杂度	O(n2)

希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法
的一种更高效的改进版本。

void shellSort(int *p, int n)
{
    int gap =n/ 2;
    while (gap >= 1)
    {
        // 把距离为 gap 的元素编为一个组， 扫描所有组
        int i,j,key;
        for ( i = gap; i < n; i++)
        {
            key = p[i];
            // 对距离为 gap 的元素组进行排序
            for (j = i; j-gap >=0 && p[j-gap] > key ; j = j - gap)
            {
                p[j] = p[j-gap];
            } 
            p[j] = key;
        }
        gap = gap / 2; // 减小增量
    }
}

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

优点	快，移动数据少。插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
缺点	不稳定， d 的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。
平均时间复杂度	O(n1.3)

选择排序

int selectSort(int *p, int n)
{
    for(int i=0; i<n-1; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(p[i]>p[j])
            {
                p[i] ^= p[j];
                p[j] ^= p[i];
                p[i] ^= p[j];
            }
        }
    }
}

优点	移动数据的次数已知（n-1 次）
缺点	比较次数多
平均时间复杂度	O(n2)

快速排序

void quickSort(int *p, int left, int right)
{
    if(left < right)
    {
        int pivot = p[left];
        int low = left; int high = right;
        while(low<high)
        {
            while(p[high]>=pivot && low<high)
                high--;
            p[low] = p[high];
            while(p[low] <=pivot && low<high)
                low++;
            p[high] = p[low];
        } 
        p[low] = pivot;
        quickSort(p,left,low-1);
        quickSort(p,low+1,right);
    }
}

优点	极快，移动数据少。
缺点	不稳定，和递归。
平均时间复杂度	O(nlogn)

归并排序

void mergeArr(int *srcArr,int *mergeArr,
int start,int idx,int end)
{
    int i=start; int j= idx +1; int k= start;
    while(i != idx+1 && j!=end +1)
    {
        if(srcArr[i] > srcArr[j])
            mergeArr[k++] = srcArr[j++];
        else
            mergeArr[k++] = srcArr[i++];
    } 
    if(i == idx+1)
        while(j !=end +1)
            mergeArr[k++] = srcArr[j++];
    if(j ==end +1)
        while(i != idx+1)
            mergeArr[k++] = srcArr[i++];
    while(start != end+1)
    {
        srcArr[start] = mergeArr[start];
        start++;
    }
} 
void mergeSort(int *src, int *t,int start,int end)
{
    int mid;
    if(start < end)
    {
        mid = (start + end)/2;
        mergeSort(src,t,start,mid);
        mergeSort(src,t,mid+1,end);
        mergeArr(src,t,start,mid,end);
    }
}

需要额外空间，故称为外排序，前面讲的都是内排序，比如冒泡等。

优点	稳定，效率高
缺点	外排序
平均时间复杂度	O(nlogn)

三、查找算法

线性查找，二分查找

二分查找 :二分查找时间复杂度O(log2n)

int find(vector<int>& nums, int target) 
{
    int left = 0, right = nums.size()-1;
    while (left <= right) 
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) 
            return mid;
        else if (nums[mid] < target) 
            left = mid + 1;
        else 
            right = mid - 1;
    }
    return -1;
}

四、回溯法

矩阵迷宫等问题，用递归

五、动态规划

最优解

六、贪心算法

数学运算相关

七、分治法

八、数组

注意二维数组中，用vector的时候，可以确定数组的行数和列数

行数为：vi.size()

列数为: vi[0].size()

九、字符串

**leetcode第28题：实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。**

这道题让我们在一个字符串中找另一个字符串第一次出现的位置，那首先要做一些判断，如果子字符串为空，则返回0，如果子字符串长度大于母字符串长度，则返回 -1。然后开始遍历母字符串，这里并不需要遍历整个母字符串，而是遍历到剩下的长度和子字符串相等的位置即可，这样可以提高运算效率。从母字符串的第一个位置开始，往后判断是否后面的字母和子字符串相等，相等则继续，反之则break。进行第二次循环，母字符串的第二个字母，往后判断，以此类推

参考代码

class Solution {
public:
    int strStr(string haystack, string needle)
    {
        int i,j;
        if(haystack.size()<needle.size())
        {
            return -1;
        }
        if(needle == "")
        {
            return 0;
        }
        for(i=0;i<=haystack.size()-needle.size();++i)
        {
            for(j = 0;j<needle.size();++j)
            {
                if(haystack[i+j]!=needle[j])
                {
                    break;
                }
            }
            if(j==needle.size())
            {
                return i;
            }
        }
        return  -1;
    }
};

十、链表

自己写的链表

#include<stdio.h>
#include<malloc.h>

typedef struct _Node
{
    int data;
    struct _Node * next;
}Node;

//创建空链表,带有头结点,head是头指针，生成的是头结点
Node *createList()
{
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    return head;
    
}

//插入操作
void insertList(Node* head , int data)
{
    Node *cur = (Node*)malloc(sizeof(Node));
    cur->data = data;
    cur->next = head->next;
    head->next = cur;
}

//遍历
void travereList(Node *head)
{
    head = head ->next;
    while(head)    
    {
        printf("%d\n",head->data);
        head = head ->next;
    }
}    

int lenList(Node* head)
{
    int count = 0;        
    head = head ->next;
    while(head)    
    {
        count++;
        head = head ->next;
    }
    return count;
}

Node *searchList(Node*head,int find)
{
    head = head -> next;
    while(head)
    {
        if(head->data == find)
        {
                break;
        }
        head = head -> next;
    }
    return head;
}

//删除节点
void deleteList(Node *head , Node *pfind)
{
    while(head -> next != pfind)    
    {
        head = head -> next;    
    }
    head -> next = pfind -> next;
    free(pfind);
}

//排序
void popSortList(Node *head)
{
    Node *p,*q;
    int len = lenList(head);
    for(int i = 0;i< len-1;i++)
    {
        p = head -> next;
        q = p -> next; 
        for(int j = 0;j<len-1-i;j++)
        {
            if(p->data > q->data)
            {
                p->data ^= q->data;        
                q->data ^= p->data;        
                p->data ^= q->data;        
            }
            p = p->next;
            q = p->next;
        }
    }

}

//逆转链表，思想就是将链表拆分
void reverseList(Node *head)
{
    Node *h = head -> next;
    head->next = NULL;
    Node *t;
    while(h)    
    {
            t = h->next;
            h->next = head ->next;
            head->next = h;
            h = t;
    }
}

//销毁链表
void destoryList(Node *head)
{
    Node *t;
    while(head)
    {
        t = head->next;
        free(head);
        head = t;
    }

}

int main()
{
    Node *head = createList();    
    insertList(head,4);
    insertList(head,1);
    insertList(head,9);
    insertList(head,7);
    insertList(head,11);
    popSortList(head);
    reverseList(head);
    travereList(head);
    int count = lenList(head); 
    printf("%d\n",count);
    destoryList(head);
    return 0;
}

头指针指向第一个节点，head->next就是第一个节点的next，指向第二个节点

**leetcode第92题：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:
1 ≤ m ≤ n ≤ 链表长度。示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL**

我们可以看出来，总共需要n-m步即可，第一步是将结点3放到结点1的后面，第二步将结点4放到结点1的后面。这是很有规律的操作，那么我们就说一个就行了，比如刚开始，pre指向结点1，cur指向结点2，然后我们建立一个临时的结点t，指向结点3（注意我们用临时变量保存某个结点就是为了首先断开该结点和前面结点之间的联系，这可以当作一个规律记下来），然后我们断开结点2和结点3，将结点2的next连到结点4上，也就是 cur->next = t->next，再把结点3连到结点1的后面结点（即结点2）的前面，即 t->next = pre->next，最后再将原来的结点1和结点2的连接断开，将结点1连到结点3，即 pre->next = t。这样我们就完成了将结点3取出，加入结点1的后方。第二步将结点4取出，加入结点1的后方，也是同样的操作，这里就不多说了，请大家自己尝试下吧，参见代码如下：

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        for (int i = 0; i < m - 1; ++i) pre = pre->next;
        ListNode *cur = pre->next;
        for (int i = m; i < n; ++i) {
            ListNode *t = cur->next;
            cur->next = t->next;
            t->next = pre->next;
            pre->next = t;
        }
        return dummy->next;
    }
};

链表逆转LeetCode第206题：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *newHead = NULL;
        while (head) {
            ListNode *t = head->next;
            head->next = newHead;
            newHead = head;
            head = t;
        }
        return newHead;
    }
};

十一、栈

自己实现的栈

#include <stdio.h>
#include <stdlib.h>

typedef struct  stack
{
    int len;
    int top;
    char *_space;
}stack;

void initStack(stack *s , int size)
{
    s->len = size;
    s->top = 0;
    s->_space = (char *)malloc(s->len);
}

int isEmpty(stack *s)
{
    return s->top == 0;
}

int isFull(stack *s)
{
    return s->top == s->len;
}

void push(stack *s,char ch)
{
    s->_space[s->top++] = ch;
}

char pop(stack *s)
{
    return s->_space[--s->top];
}

void resetStack(stack *s)
{
    s->top = 0;
}

void clearStack(stack *s)
{
    free(s->_space);
}


int main()
{
    stack s;
    initStack(&s,27);
    for(char i = 'A'; i != 'Z'+1; ++i)
    {
        push(&s,i);
    }
    while(!isEmpty(&s))
    {
            char c = pop(&s);
            printf("%c\n",c);
    }
    return 0;
}

先进后出

十二、队列

自己实现环形队列

#include <stdio.h>
#include<stdlib.h>
//front最开始指向空白待插入位置，rear指向有内容的待出队的位置
typedef struct _Queue
{
    char *_space;
    int _len;
    int _rear;
    int _front;
}Queue;

void initQueue(Queue *q,int size)
{
    q->_len = size;
    q->_space = (char *)malloc(sizeof(q->_len));
    q->_rear = q->_front = 0;
}

int isEmpty(Queue *q)
{
    return q->_front ==  q->_rear;
}

int isFull(Queue *q)
{
    return (q->_rear +1)%q->_len == q->_front;
}

void enQueue(Queue *q,char ch)
{
    q->_space[q->_rear] =ch;
    q->_rear = ++q->_rear %q->_len;
}

char deQueue(Queue *q)
{
    char ch = q->_space[q->_front];
    q->_front = ++q->_front %q->_len;
    return ch;
}

int main()
{
    Queue q;
    initQueue(&q,27);
    for(char i = 'A'; i < 'Z'+1; ++i)
    {
        enQueue(&q,i);
    }
    while(!isEmpty(&q))
    {
            char c = deQueue(&q);
            printf("%c\n",c);
    }
    return 0;
}

先进先出

十三、堆

树，最大堆，最小堆

十四、深度优先

栈

十五、广度优先

堆

十六、树

红黑树、平衡搜索二叉树

二叉树的遍历

先序遍历

void PreOrder(TreeNode *b)
{
    if (b!=NULL)
    {
        printf("%c ",b->_data);
        PreOrder(b->_left);
        PreOrder(b->_right);
    }
}

迭代版：
要用到stack来辅助运算。由于先序遍历的顺序是"根-左-右", 算法为：

把根节点push到栈中
循环检测栈是否为空，若不空，则取出栈顶元素，保存其值，然后看其右子节点是否存在，若存在则push到栈中。再看其左子节点，若存在，则push到栈中。

代码如下：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        while (!s.empty()) {
            TreeNode *t = s.top(); s.pop();
            res.push_back(t->val);
            if (t->right) s.push(t->right);
            if (t->left) s.push(t->left);
        }
        return res;
    }
};

需要用栈来做，思路是从根节点开始，先将根节点压入栈，然后再将其所有左子结点压入栈，然后取出栈顶节点，保存节点值，再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右，代码如下：

//中序遍历
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            res.push_back(p->val);
            p = p->right;
        }
        return res;
    }
};

二叉树层次遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*> q{{root}};
        vector<vector<int>> res;
        while(!q.empty())
        {
            vector<int> orderLine;
            for (int i = q.size(); i >0 ; --i)//注意这里只能把q.size()放在初始化，因为循环中改变了q
            {
                TreeNode* t=q.front();
                q.pop();
                orderLine.push_back(t->val);
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            res.push_back(orderLine);
        }      
        return res;
    }
};

二叉树的深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int lh,rh,maxh;
        if(root!=NULL)
        {
            lh=maxDepth(root->left);
            rh=maxDepth(root->right);
            maxh=rh>lh?rh:lh;
            return maxh+1;
        }
        return 0;
    }
};

完全二叉树的判断

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
      if(root == NULL)
      return false;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
       TreeNode *t = q.front();
       q.pop();
       if(t->left && t->right)
       {
         q.push(t->left);
         q.push(t->right);
       }
       else if(t->right && t->left == NULL)
       {
         return false;
       }
       else 
       {
              if(t->left && t->right == NULL)
              {
                  q.push(t->left);
              }
              while(!q.empty())
              {
                  t = q.front();
                 q.pop();
                 if(t->left || t->right)
                 {
                     return false;
                     }
              }
        }
    }
    return true;
  }
};

十七、哈希表

unordered_map

哈希表的时间复杂度 O(1)

版权属于：孟超
本文链接：https://mengchao.xyz/index.php/archives/767/
转载时须注明出处及本声明

Last modification：February 13th, 2020 at 11:56 am

如果觉得我的文章对你有用，请随意赞赏

数据结构与算法面试题

孟超 • 2019 年 11 月 10 日

十六进制转十进制

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main()
{
    string str;
    unordered_map<char,int> mmap;
    
    mmap['0']=0;
    mmap['1']=1;
    mmap['2']=2;
    mmap['3']=3;
    mmap['4']=4;
    mmap['5']=5;
    mmap['6']=6;
    mmap['7']=7;
    mmap['8']=8;
    mmap['9']=9;
    mmap['a']=10;
    mmap['A']=10;
    mmap['b']=11;
    mmap['B']=11;
    mmap['c']=12;
    mmap['C']=12;
    mmap['d']=13;
    mmap['D']=13;
    mmap['e']=14;
    mmap['E']=14;
    mmap['F']=15;
    mmap['f']=15;
    while(cin>>str)
    {
        int sum=0;
        str=str.substr(2);
        for(int i=0;i<str.size();i++)
        {
            sum=sum*16;
            sum=sum+mmap[str[i]];
        }
        cout << sum << endl;
    }
    return 0;
}

十进制转二进制


int transfer(int x)
{
    int p=1,y=0,yushu;
    while(1)
    {
        yushu=x%2;
        x/=2;
        y+=yushu*p;
        p*=10;
        if(x<2)
        {
            y+=x*p;
            break;
        }
    }
    return y;
}

自实现strcmp、自实现strcpy等
https://blog.csdn.net/z_ryan/article/details/79250265

一、双指针

两个变量，数组字符串链表中常用

参考代码:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int> >res;   
        int _size=nums.size();    
        if(_size<3||nums.front()>0||nums.back()<0)
        return res;
        int i,j,k;
        for(k=0;k<=_size-3;k++){
            if(nums[k]>0)
                break;                        //如果第一个元素都大于0，肯定越加越大，不可能为0了
            if(k>0&&nums[k]==nums[k-1])
                continue;                               //跳过无意义移动
            i=k+1;j=_size-1;
            while(i<j){
                if(nums[i]+nums[j]+nums[k]>0)
                    j--;
                else if(nums[i]+nums[j]+nums[k]<0)
                    i++;
                else{
                    res.push_back({nums[i],nums[j],nums[k]});
                    while(i<j&&nums[i]==nums[i+1])      //跳过无意义移动
                        i++;
                    while(i<j&&nums[j]==nums[j-1])      //同上
                        j--;
                    i++;
                    j--;           
                }
            }
        }
        return res;
    }
};

二、排序算法

快速排序，冒泡排序，选择排序，插入排序，希尔排序，归并排序

冒泡

void popSort(int *p, int n)
{
    int tmp;
    for(int i= n-1; i>0; i--)
    {
        for(int j=0; j<i; j++)
        {
            if(p[j] > p[j+1])
            {
                tmp = p[j];
                p[j] = p[j+1];
                p[j+1] = tmp;
            }
        }
    }
}

优点	稳定
缺点	慢，每次只能移动两个数据
平均时间复杂度	O(n2)

插入

void insertSort(int *a,int n)
{
    int i,j,key;
    for(i=1;i<n;i++)//控制需要插入的元素
    {
        key = a[i]; //key 为要插入的元素
            //查找要插入的位置,循环结束,则找到插入位置
        for(j=i; j-1>=0 && a[j-1]>key; j--)
        {
            a[j] = a[j-1]; //移动元素的位置.供要插入元素使用
        } 
        a[j] = key; //插入需要插入的元素
    }
}

优点	稳定，快
缺点	比较次数不一定，比较次数越少，插入点后的数据移动越多。
平均时间复杂度	O(n2)

希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法
的一种更高效的改进版本。

void shellSort(int *p, int n)
{
    int gap =n/ 2;
    while (gap >= 1)
    {
        // 把距离为 gap 的元素编为一个组， 扫描所有组
        int i,j,key;
        for ( i = gap; i < n; i++)
        {
            key = p[i];
            // 对距离为 gap 的元素组进行排序
            for (j = i; j-gap >=0 && p[j-gap] > key ; j = j - gap)
            {
                p[j] = p[j-gap];
            } 
            p[j] = key;
        }
        gap = gap / 2; // 减小增量
    }
}

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

优点	快，移动数据少。插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
缺点	不稳定， d 的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。
平均时间复杂度	O(n1.3)

选择排序

int selectSort(int *p, int n)
{
    for(int i=0; i<n-1; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(p[i]>p[j])
            {
                p[i] ^= p[j];
                p[j] ^= p[i];
                p[i] ^= p[j];
            }
        }
    }
}

优点	移动数据的次数已知（n-1 次）
缺点	比较次数多
平均时间复杂度	O(n2)

快速排序

void quickSort(int *p, int left, int right)
{
    if(left < right)
    {
        int pivot = p[left];
        int low = left; int high = right;
        while(low<high)
        {
            while(p[high]>=pivot && low<high)
                high--;
            p[low] = p[high];
            while(p[low] <=pivot && low<high)
                low++;
            p[high] = p[low];
        } 
        p[low] = pivot;
        quickSort(p,left,low-1);
        quickSort(p,low+1,right);
    }
}

优点	极快，移动数据少。
缺点	不稳定，和递归。
平均时间复杂度	O(nlogn)

归并排序

void mergeArr(int *srcArr,int *mergeArr,
int start,int idx,int end)
{
    int i=start; int j= idx +1; int k= start;
    while(i != idx+1 && j!=end +1)
    {
        if(srcArr[i] > srcArr[j])
            mergeArr[k++] = srcArr[j++];
        else
            mergeArr[k++] = srcArr[i++];
    } 
    if(i == idx+1)
        while(j !=end +1)
            mergeArr[k++] = srcArr[j++];
    if(j ==end +1)
        while(i != idx+1)
            mergeArr[k++] = srcArr[i++];
    while(start != end+1)
    {
        srcArr[start] = mergeArr[start];
        start++;
    }
} 
void mergeSort(int *src, int *t,int start,int end)
{
    int mid;
    if(start < end)
    {
        mid = (start + end)/2;
        mergeSort(src,t,start,mid);
        mergeSort(src,t,mid+1,end);
        mergeArr(src,t,start,mid,end);
    }
}

需要额外空间，故称为外排序，前面讲的都是内排序，比如冒泡等。

优点	稳定，效率高
缺点	外排序
平均时间复杂度	O(nlogn)

三、查找算法

线性查找，二分查找

二分查找 :二分查找时间复杂度O(log2n)

int find(vector<int>& nums, int target) 
{
    int left = 0, right = nums.size()-1;
    while (left <= right) 
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) 
            return mid;
        else if (nums[mid] < target) 
            left = mid + 1;
        else 
            right = mid - 1;
    }
    return -1;
}

四、回溯法

矩阵迷宫等问题，用递归

五、动态规划

最优解

六、贪心算法

数学运算相关

七、分治法

八、数组

注意二维数组中，用vector的时候，可以确定数组的行数和列数

行数为：vi.size()

列数为: vi[0].size()

九、字符串

参考代码

class Solution {
public:
    int strStr(string haystack, string needle)
    {
        int i,j;
        if(haystack.size()<needle.size())
        {
            return -1;
        }
        if(needle == "")
        {
            return 0;
        }
        for(i=0;i<=haystack.size()-needle.size();++i)
        {
            for(j = 0;j<needle.size();++j)
            {
                if(haystack[i+j]!=needle[j])
                {
                    break;
                }
            }
            if(j==needle.size())
            {
                return i;
            }
        }
        return  -1;
    }
};

十、链表

自己写的链表

#include<stdio.h>
#include<malloc.h>

typedef struct _Node
{
    int data;
    struct _Node * next;
}Node;

//创建空链表,带有头结点,head是头指针，生成的是头结点
Node *createList()
{
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    return head;
    
}

//插入操作
void insertList(Node* head , int data)
{
    Node *cur = (Node*)malloc(sizeof(Node));
    cur->data = data;
    cur->next = head->next;
    head->next = cur;
}

//遍历
void travereList(Node *head)
{
    head = head ->next;
    while(head)    
    {
        printf("%d\n",head->data);
        head = head ->next;
    }
}    

int lenList(Node* head)
{
    int count = 0;        
    head = head ->next;
    while(head)    
    {
        count++;
        head = head ->next;
    }
    return count;
}

Node *searchList(Node*head,int find)
{
    head = head -> next;
    while(head)
    {
        if(head->data == find)
        {
                break;
        }
        head = head -> next;
    }
    return head;
}

//删除节点
void deleteList(Node *head , Node *pfind)
{
    while(head -> next != pfind)    
    {
        head = head -> next;    
    }
    head -> next = pfind -> next;
    free(pfind);
}

//排序
void popSortList(Node *head)
{
    Node *p,*q;
    int len = lenList(head);
    for(int i = 0;i< len-1;i++)
    {
        p = head -> next;
        q = p -> next; 
        for(int j = 0;j<len-1-i;j++)
        {
            if(p->data > q->data)
            {
                p->data ^= q->data;        
                q->data ^= p->data;        
                p->data ^= q->data;        
            }
            p = p->next;
            q = p->next;
        }
    }

}

//逆转链表，思想就是将链表拆分
void reverseList(Node *head)
{
    Node *h = head -> next;
    head->next = NULL;
    Node *t;
    while(h)    
    {
            t = h->next;
            h->next = head ->next;
            head->next = h;
            h = t;
    }
}

//销毁链表
void destoryList(Node *head)
{
    Node *t;
    while(head)
    {
        t = head->next;
        free(head);
        head = t;
    }

}

int main()
{
    Node *head = createList();    
    insertList(head,4);
    insertList(head,1);
    insertList(head,9);
    insertList(head,7);
    insertList(head,11);
    popSortList(head);
    reverseList(head);
    travereList(head);
    int count = lenList(head); 
    printf("%d\n",count);
    destoryList(head);
    return 0;
}

头指针指向第一个节点，head->next就是第一个节点的next，指向第二个节点

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        for (int i = 0; i < m - 1; ++i) pre = pre->next;
        ListNode *cur = pre->next;
        for (int i = m; i < n; ++i) {
            ListNode *t = cur->next;
            cur->next = t->next;
            t->next = pre->next;
            pre->next = t;
        }
        return dummy->next;
    }
};

链表逆转LeetCode第206题：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *newHead = NULL;
        while (head) {
            ListNode *t = head->next;
            head->next = newHead;
            newHead = head;
            head = t;
        }
        return newHead;
    }
};

十一、栈

自己实现的栈

#include <stdio.h>
#include <stdlib.h>

typedef struct  stack
{
    int len;
    int top;
    char *_space;
}stack;

void initStack(stack *s , int size)
{
    s->len = size;
    s->top = 0;
    s->_space = (char *)malloc(s->len);
}

int isEmpty(stack *s)
{
    return s->top == 0;
}

int isFull(stack *s)
{
    return s->top == s->len;
}

void push(stack *s,char ch)
{
    s->_space[s->top++] = ch;
}

char pop(stack *s)
{
    return s->_space[--s->top];
}

void resetStack(stack *s)
{
    s->top = 0;
}

void clearStack(stack *s)
{
    free(s->_space);
}


int main()
{
    stack s;
    initStack(&s,27);
    for(char i = 'A'; i != 'Z'+1; ++i)
    {
        push(&s,i);
    }
    while(!isEmpty(&s))
    {
            char c = pop(&s);
            printf("%c\n",c);
    }
    return 0;
}

先进后出

十二、队列

自己实现环形队列

#include <stdio.h>
#include<stdlib.h>
//front最开始指向空白待插入位置，rear指向有内容的待出队的位置
typedef struct _Queue
{
    char *_space;
    int _len;
    int _rear;
    int _front;
}Queue;

void initQueue(Queue *q,int size)
{
    q->_len = size;
    q->_space = (char *)malloc(sizeof(q->_len));
    q->_rear = q->_front = 0;
}

int isEmpty(Queue *q)
{
    return q->_front ==  q->_rear;
}

int isFull(Queue *q)
{
    return (q->_rear +1)%q->_len == q->_front;
}

void enQueue(Queue *q,char ch)
{
    q->_space[q->_rear] =ch;
    q->_rear = ++q->_rear %q->_len;
}

char deQueue(Queue *q)
{
    char ch = q->_space[q->_front];
    q->_front = ++q->_front %q->_len;
    return ch;
}

int main()
{
    Queue q;
    initQueue(&q,27);
    for(char i = 'A'; i < 'Z'+1; ++i)
    {
        enQueue(&q,i);
    }
    while(!isEmpty(&q))
    {
            char c = deQueue(&q);
            printf("%c\n",c);
    }
    return 0;
}

先进先出

十三、堆

树，最大堆，最小堆

十四、深度优先

栈

十五、广度优先

堆

十六、树

红黑树、平衡搜索二叉树

二叉树的遍历

先序遍历

void PreOrder(TreeNode *b)
{
    if (b!=NULL)
    {
        printf("%c ",b->_data);
        PreOrder(b->_left);
        PreOrder(b->_right);
    }
}

迭代版：
要用到stack来辅助运算。由于先序遍历的顺序是"根-左-右", 算法为：

把根节点push到栈中
循环检测栈是否为空，若不空，则取出栈顶元素，保存其值，然后看其右子节点是否存在，若存在则push到栈中。再看其左子节点，若存在，则push到栈中。

代码如下：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        while (!s.empty()) {
            TreeNode *t = s.top(); s.pop();
            res.push_back(t->val);
            if (t->right) s.push(t->right);
            if (t->left) s.push(t->left);
        }
        return res;
    }
};

//中序遍历
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            res.push_back(p->val);
            p = p->right;
        }
        return res;
    }
};

二叉树层次遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*> q{{root}};
        vector<vector<int>> res;
        while(!q.empty())
        {
            vector<int> orderLine;
            for (int i = q.size(); i >0 ; --i)//注意这里只能把q.size()放在初始化，因为循环中改变了q
            {
                TreeNode* t=q.front();
                q.pop();
                orderLine.push_back(t->val);
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            res.push_back(orderLine);
        }      
        return res;
    }
};

二叉树的深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int lh,rh,maxh;
        if(root!=NULL)
        {
            lh=maxDepth(root->left);
            rh=maxDepth(root->right);
            maxh=rh>lh?rh:lh;
            return maxh+1;
        }
        return 0;
    }
};

完全二叉树的判断

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
      if(root == NULL)
      return false;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
       TreeNode *t = q.front();
       q.pop();
       if(t->left && t->right)
       {
         q.push(t->left);
         q.push(t->right);
       }
       else if(t->right && t->left == NULL)
       {
         return false;
       }
       else 
       {
              if(t->left && t->right == NULL)
              {
                  q.push(t->left);
              }
              while(!q.empty())
              {
                  t = q.front();
                 q.pop();
                 if(t->left || t->right)
                 {
                     return false;
                     }
              }
        }
    }
    return true;
  }
};

十七、哈希表

unordered_map

哈希表的时间复杂度 O(1)

版权属于：孟超
本文链接：https://mengchao.xyz/index.php/archives/767/
转载时须注明出处及本声明

一、双指针

二、排序算法

三、查找算法

四、回溯法

五、动态规划

六、贪心算法

七、分治法

八、数组

九、字符串

十、链表

十一、栈

十二、队列

十三、堆

十四、深度优先

十五、广度优先

十六、树

十七、哈希表