面完滴滴，小米，百度之后的算法总结

今年本科生找个工作确实非常难，更何况还是非 985/211 院校，虽然面了好几个公司，但都没有结果，求职路漫漫长，不知何时才能找到工作。。。

本人正在找运维，运维开发相关工作，以下是面试过程中被问到的相关算法，在此整理一下，希望能够顺利找到工作。

本人在找工作期间会一直更新此文，希望关注！

1，反转二叉树

BiTree ReversedBiTree(BiTree root)
{
        if (root == null) {
            return null;
        }
        root->left = ReversedTree(root->left);
        root->right = ReversedTree(root->right);

        BiTree tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
}

2，N个数里面找出最大的 k 个数

• 1，使用快速排序，输出最大的 K 个数，算法时间复杂度为 O（n*logn）

• 2，不使用排序则为 O（n*k），遍历 n 个数，把最先遍历到的 k 个数存入到大小为 k 的数组中，假设它们即是最小的 k 个数； 对这 k 个数，利用选择或交换排序找到这 k 个元素中的最大值 kmax（找最大值需要遍历这 k 个数，时间复杂度为 O（k）； 继续遍历剩余 n-k 个数。假设每一次遍历到的新的元素的值为 x，把 x 与 kmax 比较：如果 x<kmax，用 x 替换 kmax，并回到第二步重新找出 k 个元素的数组中最大元素 kmax；如果 x>=kmax，则继续遍历不更新数组。

• 3，使用堆排序的算法复杂度为 O(nlogk)

3，从一个字符串中找出出现频率最高的字符

int[] x = new int[26];
char[] ca = str.toCharArray();
for(int i=0;i <ca.length;i++){
    x[ca[i]-'a']++;
}
for(int i=0;i <ca.length;i++){
    System.out.println("字符"+(char)('a'+i)+"出现了"+ca[i]+"次");
}    

4，快速排序

快速排序选择基准的三种方法：

• 1，选第一个；
• 2，随机选
• 3，选择1，n 和 n/2 的平均数

四种优化方法：

• 优化1：当待排序序列的长度分割到一定大小后，使用插入排序（对于小规模部分有序的数组，快排不如插排好）

• 优化2：在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割

• 优化3：优化递归操作，使用为递归进行优化

• 优化4：使用并行或多线程处理子序列

void quicksort(int arr[],int left,int right)
{
    int i,j,t,temp;
    if(left>=right)
       return;                                 
    temp=a[left]; //temp中存的就是基准数
    i=left;
    j=right;
    while(i!=j)
    {
                   while(a[j]>=temp && i<j)   //顺序很重要，要先从右边开始找
                            j--;
                   while(a[i]<=temp && i<j)   //再找右边的
                            i++;
                   if(i<j)                   //交换两个数在数组中的位置
                   {
                            t=a[i];
                            a[i]=a[j];
                            a[j]=t;
                   }
    }
    a[left]=a[i];   //最终将基准数归位
    a[i]=temp;                       
    quicksort(arr,left,i-1);//继续处理左边的，这里是一个递归的过程
    quicksort(arr,i+1,right);//继续处理右边的 ，这里是一个递归的过程
}

5，二分查找

int BinSearch(int arr[],int low,int high,int num)
{
    while(low<=high)
    {
        int mid=(low+high)/2;
        if(num==arr[mid])       return mid;
        else if(num < arr[mid]) high=mid-1;
        else                    low=mid+1；
    }
    return -1；
}

6，希尔排序

void shellsort2(int a[], int n)  
{  
    int j, gap;  
      
    for (gap = n / 2; gap > 0; gap /= 2)  
        for (j = gap; j < n; j++)//从数组第gap个元素开始  
            if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序  
            {  
                int temp = a[j];  
                int k = j - gap;  
                while (k >= 0 && a[k] > temp)  
                {  
                    a[k + gap] = a[k];  
                    k -= gap;  
                }  
                a[k + gap] = temp;  
            }  
}  

7，冒泡排序(在某趟冒泡排序过程中，若没有发现一个逆序对，就可以直接结束整个排序过程)

void bubble_sort(int arr[],int n)
{
    int flag=1;
    for(int i=0;i<n && flag;i++)
    {
        flag=0;
        for(int j=0;j<n-i;j++)
            if(a[j]>a[j+1])
            {
                int tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
                flag=1;
            }
    }
}

8,选择排序

void select_sort(int arr[],int n)
{
    for(int i=0;i<n;i++)
    {
        int k=i;
        for(int j=i+1;j<n;j++)
            if(a[j]<a[k])
                k=j;
        if(k!=i)
        {
            int tmp=a[i];
            a[i]=a[k];
            a[k]=tmp;
        }
    }
}

9，插入排序

void insert_sort(int arr[],int n)
{
    for(int i=2;i<n;i++)
    {
        if(a[i]<a[i-1])
        {
            a[0]=a[i];
            for(int j=i;a[0]<a[j];j--)
                a[j+1]=a[j];   //记录后移
            a[j+1]=a[0];       //插入到正确的位置
        }
    }
}

10，木桶排序

#include <stdio.h> 
int main()  
{  
    int a[11],i,j,t;  
    for(i=0;i<=10;i++)  
        a[i]=0;  //初始化为0  
      
    for(i=1;i<=5;i++)  //循环读入5个数  
    {  
        scanf("%d",&t);  //把每一个数读到变量t中  
        a[t]++;  //进行计数  
    }  
 
    for(i=0;i<=10;i++)  //依次判断a[0]~a[10]  
        for(j=1;j<=a[i];j++)  //出现了几次就打印几次  
            printf("%d ",i);  
}    

11，实现一个逆转函数

#!/usr/bin/env python
# coding=utf-8


string_reversed = lambda x:x[::-1]

if __name__ == '__main__':
    s = 'abcde'
    print string_reversed(s)

12，计算列表中出现最多次的字符

对于不区分字母大小写时可以使用以下代码：

import string

def get_max_value(text):
    text = text.lower()
    return max(string.ascii_lowercase, key=text.count)

字母区分大小写时相应的代码：

#!/usr/bin/env python
# coding=utf-8


str_count = {}

def get_max_count(text):
    for i in text:
        try:
            str_count.get(i)
            str_count[i] += 1
        except Exception as e:
            str_count[i] = 1

if __name__ == '__main__':
    s = 'asdsaADSADSA'
    get_max_count(s)
    str_count = sorted(str_count.items(),key=lambda x:x[1])
    print str_count[len(str_count)-1]