一、数据结构部分
1、数组和链表的区别
C++语言中可以用数组处理一组数据类型相同的数据,但不允许动态定义数组的大小,即在使用数组之前必须确定数组的大小。而在实际应用中用户使用数组之前有时无法准确确定数组的大小,只能将数组定义成足够大,这样数组中有些空间可能不被使用,从而造成内存空间的浪费。链表是一种常见的数据组织形式,它采用动态分配内存的形式实现。需要时可以用new分配内存空间,不需要时用delete将已分配的空间释放,不会造成内存空间的浪费。
从逻辑结构来看:数组必须事先定义固定的长度(元素个数),不能适应数据动态的增减的情况,即数组的大小一旦定义就不能改变。当数据增加时,可能超出原来定义的元素个数,当数据减少时,造成内存浪费;链表动态的进行存储分配,可以适应数据动态的增减的情况,且可以方便的插入、删除数据项(数组中插入、删除数据项时,需要移动其他数据项)。 从内存存储来看:(静态)数组从栈中分配空间(用new创建的堆中),对于程序员快速,但是自由度小,链表从堆中分配空间,自由度大但是申请管理比较麻烦。
从访问方式来看:数组在内存中是连续存储的,因此,可以利用下标索引进行随机访问,链表是链式存储结构,在访问元素的时候只能通过线性的方式由前到后顺序访问,所以访问效率比数组要低。
2、链表的一些操作:
链表的反转:参考博客链表的逆序
链表存在环路的判断:参考博客判断链表是否有环及两链表是否相交
有序链表:保持数据有序的链表叫做有序链表。
定义一个有序链表(Java实现):
class Link{ public long dData; public Link next; public Link(long ){ dData = dd; } } class SortedList{ private Link first; public SortedList(){ first = null; } //插入一个元素 public void insert(long key){ Link newLink = new Link(key); Link previous = null; Link current = first; while(current != null && key > current.dData){ previous = current; current = current.next; } if(previous == null){ first = newLink; }else{ previous.next = newLink; } newLink.next = current; } }有序链表的效率:在有序链表插入和删除某一项最多需要O(N)次比较,(平均N/2),因为必须沿着链表上一步一步才能找到正确的位置。然而,可以在O(1)的时间内找到或者删除最小值,因为它总是在表头。如果一个应用频繁的存取最小项,且不需要快速的插入,那么有序链表是一个有效的方案选择。例如:优先级队列可以用有序链表来实现。
表插入排序:有序链表可以用于一种高效的排序机制,假设一个无序数组,如果从这个数组中取出数据,然后一个一个地插入有序链表,他们自动的按顺序排列,把他们从有序表中删除,重新放入数组,那么数组就会排好序了。
双向链表相关操作:
双向链表既提供了向前遍历,也允许向后遍历。每个链节点有两个指向其他节点的引用,第一个像普通链表一样指向下一个链接点,第二个指向前一个链接点。数据结构如下:
class Link{ public long dData; public Link next; public Link previous; ... }
循环链表相关操作:当循环链表的基本操作,双向循环链表的操作
3、队列(特殊的如优先队列参考博客http://blog.csdn.net/zhang20072844/article/details/10286997),栈的应用。
4、二叉树的基本操作
二叉树的三种遍历方式(前序、中序、后序)及递归和非递归实现,三种方式的主要应用(如后缀表达式)。相关操作的时间复杂度。
先序遍历的递归算法:
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ if(T){ if(Visit(T->data)){ if(PreOrderTraverse(T->lchild, Visit)){ if(PreOrderTraverse(T->rchild, Visit)){ return OK; } } } return ERROR; }else return OK; }
根据递归算法执行过程中的递归工作栈的状态变化状况可以写出相应的非递归算法。
Status InOrderTravers(BiTree T, Status(*visit)(TElemType e)){ //采用二叉链表存储结构,Visit是对数据元素操作的应用函数 //中序遍历二叉树T的非递归算法,对每个数据元素调用函数Visit InitStack(S); Push(S, T);//根指针进栈 while(!StackEmpty(S)){ while(GetTop(S,p) && p) Push(S,p->lchild);//向左走到尽头 Pop(S,p);//空指针出栈 if(!StackEmpty(S)){ Pop(S,p); if(!Visit(p->data)) return error; Push(S,p->rchid); } } } Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ //采用链表结构,Visit是对数据元素操作的应用函数 //中序遍历二叉树T的非递归算法,对每个元素调用函数Visit InitStack(S); p=T; while(p || !StackEmpty){ if(p){ Push(S,p); p = p->lchild;//根指针进栈,遍历左子树 }else{ Pop(S, p); if(!Visit(p->data)) return ERROR; p = p->rchild; } } return OK; }
5、字符串相关
(1)字符串逆序
普通逆序:
char[] chars = new char[a.length()]; for(int i=chars.length-1,j=0;i>=0;i--,j++){ chars[j] = a.toCharArray()[i]; } System.out.println(String.valueOf(chars));原地逆序:不允许额外分配空间,思想是将字符串两边的字符逐个交换。
public String reverse(String s){ //普通逆序 /* char[] chars = new char[s.length()]; for(int i=chars.length-1,j=0;i>=0;i--,j++){ chars[j] = s.toCharArray()[i]; }*/ //原地逆序 char[] chars = s.toCharArray(); for(int i=0,j=chars.length-1;i<=j;i++,j--){ char t = chars[i]; chars[i] = chars[j]; chars[j] = t; } return String.valueOf(chars); }不允许临时变量的原地逆序。上面的原地逆序虽然没有额外的分配空间,但还是使用了临时变量,严格的说也算是额外空间吧,如果再严格一点,连临时变量 也不允许的话,主要有下面两种方法:一是异或操作,因为异或操作可以交换两个变量而无需借助第三个变量,二是使用字符串的结束符'\0'所在的位置作为交换空间,这样有个局限,就是只适合以'\0'结尾的字符串,对于不支持这种字符串格式的语言就不能使用了。
//判断是否是一个中文汉字 public static boolean isChineseChar(char c) throws UnsupportedEncodingException{ return String.valueOf(c).getBytes("GBK").length>1; } //截取字符串 public static String cutString(String orignal, int count) throws UnsupportedEncodingException{ if(orignal != null && !"".equals(orignal)){ orignal = new String(orignal.getBytes(), "GBK"); if(count > 0 && count < orignal.getBytes("GBK").length){ StringBuffer buffer = new StringBuffer(); char c; for(int i=0;i<count;i++){ c = orignal.charAt(i); buffer.append(c); if(isChineseChar(c)){ --count; } } return buffer.toString(); } } return orignal; }(3)字符串匹配算法
二、算法部分
1、排序算法
排序算法是最基本的,最常用的算法,也是笔试面试中最常被考察到的算法。最基本的冒泡排序,选择排序,插入排序要很快的用代码实现,这些主要考察你的实际编码能力。堆排序,归并排序,快排序,这些算法需要熟悉主要的思想和需要注意细节的地方,需要熟悉常用排序算法的时间和空间复杂度。
各种排序算法的使用范围总结:
(1)当数据规模较小的时候,可以使用简单的排序算法如直接插入排序或直接选择排序。
(2)当文件的初态已经基本有序时,可以使用插入排序或冒泡排序。
(3)当数据规模较大时,应用速度快的排序算法。可以考虑快速排序。当记录随机分布的时候,快排的平均时间最短,但可能出现最坏的情况,这时候的时间复杂度是O(n^2),且递归深度为n,所需的栈空间为O(n)。
(4)堆排序不会出现快排那样的最坏情况,且堆排序所需的辅助空间比快排要少。但这两种算法都不是稳定的,若要求排序时稳定,可以考虑用归并排序。
(5)归并排序可以用于内排序,也可以用于外排序。在外排序时,通常采用多路归并,并且通过解决长顺串的合并,产生长的初始串,提高主机与外设并行能力等措施,以减少访问外存次数,提高外排序的效率。
常见排序算法java实现:
插入排序:
public class InsertSort { public static void main(String[] args){ int[] a = {0,2,1,5,4,3}; inserSort(a); for(int i=1;i<a.length;i++){ System.out.println(a[i]); } } public static void inserSort(int[] l){ int j=0; for(int i=2;i<l.length;++i){ if(l[i] < l[i-1]){ l[0] = l[i]; l[i] = l[i-1]; for(j=i-2;l[0] < l[j];--j){ l[j+1] = l[j]; } l[j+1] = l[0]; } } } }
快速排序
public class Qsort { public static void main(String[] args){ int[] a = {3,2,5,4,1}; qSort(a, 0, a.length-1); for(int i=0;i<a.length;i++){ System.out.println(a[i]); } } public static void qSort(int[] a, int low, int high){ if(low < high){ int p = partion(a, low, high); qSort(a, low, p-1); qSort(a, p+1, high); } } public static int partion(int[] a, int low, int high){ int p = a[low]; while(low < high){ while(low<high && a[high] > p) --high; a[low] = a[high]; while(low<high && a[low] < p) ++low; a[high] = a[low]; } a[low] = p; return low; } }
选择排序
public class SelectSort { public static void main(String[] args){ int[] a = {3,2,5,4,1}; selectSort(a); for(int i=0;i<a.length;i++){ System.out.println(a[i]); } } public static void selectSort(int[] a){ for(int i=0;i<a.length;i++){ int j = selectMinKey(a, i); if(i != j){ int t = a[i]; a[i] = a[j]; a[j] = t; } } } public static int selectMinKey(int[] a, int i){ int min = Integer.MAX_VALUE,index=0; for(int j=i;j<a.length;j++){ if(a[j] < min){ min = a[j]; index = j; } } return index; } }
归并排序:
public class MergeSort { public void mergeSort(int[] s){ msort(s, s, 1, s.length); } public void msort(int[] sr, int[] tr, int s, int t){ if(s == t) tr[s] = sr[s]; else{ int m = s+t/2; int[] tr2 = null; msort(sr, tr2, s, m); msort(sr, tr2, m+1, t); merge(sr, tr2, s, m, t); } } public void merge(int[] sr, int[] tr, int i, int m, int n){ int j = 0,k=0; for(j=m+1, k=i;i<m&&j<n;k++){ if(sr[i] < sr[k]) tr[k] = sr[i++]; else tr[k] = sr[j++]; } if(i <= m){ for(int temp1=i;temp1<=m;temp1++){ tr[i] = sr[m]; } } if(j<=n){ } for(int temp2=j;temp2<=n;temp2++){ tr[j] = sr[j]; } } }
2、查找算法
能够熟练写出或者是上机编码出二分查找的程序
int Search_bin(SSTable ST, KeyType key){ //在有序表ST中这般查找其关键字等于key的数据元素, //则函数值为该元素在表中的位置,否则为0 low = 1; high=ST.length; while(low < high){ mid = (low+hign)/2; if(EQ(key, ST.elem[mid].key)) return mid; else if(LT(key, ST.elem[mid].key)) high = mid-1; else low = mid + 1; } return 0; }
3、hash算法
4、一些算法设计思想
相关推荐
java面试常用的数据结构与算法,数组、集合、散列表、栈、队列、链表、二叉树
现代计算机常用数据结构和算法汇总,还有微软100道面试题及详尽的解答。。
微软等数据结构+算法面试100题首次完整亮相[100题V0.1最终完美珍藏版
微软数据结构与算法,看到该文件的网友有福了,哈哈!
有JAVA数据结构和算法的教程 还有算法题 加部分面试题 从别人那下的 在这一次给了 希望能帮到大家
有关数据结构中常用的算法的详细解析,有助于大家面试、笔试与学习
2021年最新整合的数据结构与算法的面试题,一共100多页的文档,需要的小伙伴可以拿走,里面有按编程语言区分需要学习的算法知识点,很详细很全面。
非常好的面试题,经典数据结构和算法题目。
很全面的数据结构和算法面试题及相关考点
网上搜集的一个c++数据结构与算法的文档,包含各类数据结构、算法、大量数据处理等方法,然后我还增加了那些是笔试面试中重点需要看的。希望能帮助到找工作的同学。另外可以从我的资源中下载c++基础知识的文档。
一年之前的10月14日,一个名叫July 的人在一个叫csdn 的论坛上开帖分享微软等公司数据结构+算法面试100题,自此,与上千网友一起做,一起思考,一起解答这些面试题目,最终成就了一个名为:结构之法算法之道的编程...
面试---10. 数据结构与算法.pdf
数据结构和算法名企面试题目,里面的test是其中一道的解答
算法大全-面试题-链表-栈-二叉树-数据结构
java数据结构与算法,面试必备
微软等公司数据结构+算法面试100题.微软等公司数据结构+算法面试100题.微软等公司数据结构+算法面试100题.微软等公司数据结构+算法面试100题.微软等公司数据结构+算法面试100题.
通过本资源,读者不仅能学习到数据结构的基本原理和算法的实现技巧,还能了解如何在技术面试中有效地展示这些知识。内容包括但不限于数组、链表、栈、队列、树、图、排序和搜索算法,以及常见的算法问题解决策略。...
程序员面试精选 主要是数据结构和算法,题很多,60多页 其中有很多是微软面试题
22:数据结构模板:如何让解题变成搭积木?.mp4 23:算法模板:如何让高频算法考点秒变默写题?.mp4 彩蛋 聊聊我的大厂面试经历,谈谈我对算法学习的看法.mp4 结束语 算法的精进之路.mp4 下载地址:
数据结构面试算法集锦数据结构面试算法集锦数据结构面试算法集锦