神刀安全网

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

今年本科生找个工作确实非常难,更何况还是非 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,把 xkmax 比较:如果 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,nn/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(left,i-1);//继续处理左边的,这里是一个递归的过程     quicksort(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;j<n;j++)             if(a[j]<a[i])                 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]

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 面完滴滴,小米,百度之后的算法总结

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址