java面试笔记(数据结构)


java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 我将我在面试中遇到的各种算法题总结如下,希望对找工作的同学有帮助!我将我在面试中遇到的各种算法题总结如下,希望对找工作的同学有帮助!我将我在面试中遇到的各种算法题总结如下,希望对找工作的同学有帮助!我将我在面试中遇到的各种算法题总结如下,希望对找工作的同学有帮助!****表示遇到的次表示遇到的次表示遇到的次表示遇到的次 数数数数 ****1,用递归的方式判断某个字符串是不是回文字符串(正反读都一样),比如(“abcdcba”) publicpublicpublicpublic staticstaticstaticstatic booleanbooleanbooleanboolean is回文(String s) { ifififif (s.length() == 0 || s.length() == 1) { returnreturnreturnreturn truetruetruetrue; } ifififif (s.charAt(0) == s.charAt(s.length()-1)) { returnreturnreturnreturn is回文(s.substring(1, s.length()-1)); } returnreturnreturnreturn falsefalsefalsefalse; } 2, 加法运算得到一个整型数字比如说是 10 有如下几种情况: 1+9=10 2+8=10 1+2+7=10 1+2+3+4=10 1+1+1+1+1+5=10 。。。。。。。。 。。。。。。。。 很多种情况(4+6与6+4 相同) publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid split(intintintint num, intintintint result, intintintint begin, StringBuffer sbf) { ifififif(result==num){//如果结果为指定的结果,则直接打印并退出 System.out.println(num+"="+sbf.toString()); returnreturnreturnreturn; } forforforfor(intintintint i=begin;i<=num-result;i++){ String str=""; ifififif(sbf.length()==0){ str=""+i; }elseelseelseelse{ str="+"+i; } sbf.append(str); split(num,result+i,i,sbf); sbf.delete(sbf.length()-str.length(), sbf.length()); } java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 } publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid main(String[] args) { intintintint num = 10; intintintint begin = 1; intintintint result = 0; StringBuffer sbf = newnewnewnew StringBuffer(); split(num, result, begin, sbf); } ****3,递归几个题 //求阶乘,如4!=24 publicpublicpublicpublic staticstaticstaticstatic longlonglonglong factorial(intintintint i) { ifififif (i < 0) returnreturnreturnreturn -1; elseelseelseelse ifififif (i == 0 || i == 1) returnreturnreturnreturn 1; elseelseelseelse returnreturnreturnreturn i * factorial(i - 1); } //求和运算,如1 + 2 + 3 +... = ? publicpublicpublicpublic staticstaticstaticstatic intintintint sum(intintintint i) { ifififif (i == 0) returnreturnreturnreturn 0; elseelseelseelse returnreturnreturnreturn i + sum(i - 1); } //求斐波那契数列,如1,1,2,3,5,8,13.... publicpublicpublicpublic staticstaticstaticstatic intintintint fibonacci(intintintint i) { ifififif (i == 0 || i == 1) returnreturnreturnreturn 1; elseelseelseelse returnreturnreturnreturn fibonacci(i - 1) + fibonacci(i - 2); } //非递归求斐波那契数列 publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid fibonacci(intintintint m) { longlonglonglong x = 1, y = 1; forforforfor (intintintint i = 1; i <= m; i++) { java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 y = x + y; x = y - x; } } ****4,一个农夫养了一头牛,三年后,这头牛每年会生出 1头牛,生出来的牛三年后,又可以 每年生出一头牛……问农夫 10年后有多少头牛?n年呢?(用 JAVA实现) 方法 1: publicpublicpublicpublic classclassclassclass Cow { privateprivateprivateprivate staticstaticstaticstatic intintintint count = 1; publicpublicpublicpublic voidvoidvoidvoid feedCow(intintintint year, intintintint age) { year++; age++; ifififif (year <= 10) { ifififif (age >= 3) { count++; feedCow(year, 0); } feedCow(year, age); } } publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid main(String[] args) { newnewnewnew Cow().feedCow(0, 0); System.out.println(count); } } 方法二: publicpublicpublicpublic classclassclassclass Cow { publicpublicpublicpublic staticstaticstaticstatic intintintint count = 0; publicpublicpublicpublic Cow(intintintint year) { count++; forforforfor (intintintint i = 3 + year; i <= 10; i++) { newnewnewnew Cow(i); } } publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid main(String[] args) { newnewnewnew Cow(0); System.out.println(count); } } java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 方法三: publicpublicpublicpublic classclassclassclass Cow { privateprivateprivateprivate intintintint age; publicpublicpublicpublic Cow() { age = 0; } publicpublicpublicpublic Cow play() { age++; returnreturnreturnreturn age > 3 ? newnewnewnew Cow() : nullnullnullnull; } publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid main(String[] args) { List list = newnewnewnew ArrayList(); list.add(newnewnewnew Cow()); forforforfor (intintintint i = 0; i <= 10; i++) { forforforfor (intintintint j = 0; j < list.size(); j++) { Cow cow = list.get(j).play(); ifififif (cow != nullnullnullnull) list.add(cow); } } System.out.println("10年后,共有:" + list.size()); } } ********5,一个整数数组,包含正数和负数,从该数组中找一个子数组,该子数组所有元素的和 最大。例如数组:6, -1, 9, 3, -2, 0, -8, 4, 7, 1 它和最大为 19,就是这个数组本身。 写出代码。 publicpublicpublicpublic classclassclassclass Test { privateprivateprivateprivate staticstaticstaticstatic intintintint calculate(intintintint[] array) { intintintint start = 0; //起始索引 intintintint end = 0; //结束索引 intintintint max = array[0]; // 子数组的和 intintintint remax = array[0]; // 子数组和的最大值 forforforfor (intintintint i = 1; i < array.length; i++) { ifififif (max > 0) {//若子数组的和的值大于0,则继续加 max += array[i]; } elseelseelseelse {//否则舍去 max = array[i]; start = i; } java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 ifififif (max > remax) { remax = max; end = i; } } /*当输入数组中所有整数都是负数时,子数组和的最大值就是数组中的最大元素。*/ ifififif (remax < 0) { remax = array[0]; start = end = 0; forforforfor (intintintint i = 1; i < array.length; i++) { ifififif (remax < array[i]) { remax = array[i]; start = i; end = i; } } } System.out.println("从" + start + "到" + end + "最大,最大为:" + remax); returnreturnreturnreturn remax; } publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid main(String[] args) { intintintint[] array = {6, -1, 9, 3, -2, 0, -8, 4, 7, 1}; calculate(array); } } ****6,实现一个二叉排序树 classclassclassclass Node { intintintint data; Node left; Node right; publicpublicpublicpublic Node(intintintint data) { thisthisthisthis.data = data; } voidvoidvoidvoid add(Node node) { //添加的节点数据大于当前节点的数据时,放在右子树这边 ifififif (node.data < data){ ifififif (left == nullnullnullnull) left = node; elseelseelseelse java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 left.add(node); } elseelseelseelse { ifififif (right == nullnullnullnull) right = node; elseelseelseelse right.add(node); } } voidvoidvoidvoid printBiTree() { ifififif (left != nullnullnullnull){ left.printBiTree(); } System.out.print(data + ""); ifififif (right != nullnullnullnull){ right.printBiTree(); } } } classclassclassclass BiTree { Node root;//根结点 BiTree addNode(Node node) { ifififif (root == nullnullnullnull) root = node; elseelseelseelse root.add(node); returnreturnreturnreturn thisthisthisthis; } BiTree addNode(intintintint... datas) { forforforfor (intintintint data : datas) { Node node = newnewnewnew Node(data); ifififif (root == nullnullnullnull) root = node; elseelseelseelse root.add(node); } returnreturnreturnreturn thisthisthisthis; } voidvoidvoidvoid printBiTree() { root.printBiTree(); } java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 } publicpublicpublicpublic classclassclassclass TreeTest { publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid main(String[] args) { BiTree tree = newnewnewnew BiTree(); tree.addNode(8, 9, 12, 6, 3, 7); tree.printBiTree(); } } ****7,折半查找的非递归算法 classclassclassclass BinarySearch { staticstaticstaticstatic intintintint search(intintintint key, intintintint... datas) { intintintint start = 0; intintintint end = datas.length - 1; intintintint pos; whilewhilewhilewhile (start <= end) { pos = (start + end) / 2; ifififif (datas[pos] == key) returnreturnreturnreturn pos; elseelseelseelse ifififif (datas[pos] > key) end = pos - 1; elseelseelseelse start = pos + 1; } returnreturnreturnreturn -start; } } publicpublicpublicpublic classclassclassclass BinarySearchTest { publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid main(String[] args) { intintintint [] datas = {3, 7, 8, 9, 12}; System.out.println(BinarySearch.search(10, datas)); } } 8, 折半查找的递归算法 classclassclassclass BinarySearch { staticstaticstaticstatic intintintint search(intintintint key, intintintint start , intintintint end, intintintint... datas) { ifififif (start > end) returnreturnreturnreturn -start; intintintint pos = (start + end) / 2; java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 ifififif (datas[pos] == key) returnreturnreturnreturn pos; elseelseelseelse ifififif (datas[pos] > key) returnreturnreturnreturn search(key, start, pos - 1, datas); elseelseelseelse returnreturnreturnreturn search(key, pos + 1, end, datas); } } publicpublicpublicpublic classclassclassclass BinarySearchTest { publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid main(String[] args) { intintintint [] datas = {3, 7, 8, 9, 12}; System.out.println(BinarySearch.search(9, 0, datas.length - 1, datas)); } } ****8,快速排序 classclassclassclass QuickSort { /*调用此方法将确定start所指的值的最后排好序的位置*/ privateprivateprivateprivate staticstaticstaticstatic intintintint sort(intintintint start, intintintint end, intintintint... datas) { intintintint key = datas[start]; whilewhilewhilewhile (start < end) { whilewhilewhilewhile (start < end && key <= datas[end]) { end--; } datas[start] = datas[end]; whilewhilewhilewhile (start < end && key >= datas[start]) { start++; } datas[end] = datas[start]; } datas[start] = key; returnreturnreturnreturn start; } staticstaticstaticstatic voidvoidvoidvoid qSort(intintintint start, intintintint end, intintintint... datas) { ifififif (start < end) { intintintint pos = sort(start, end, datas); qSort(start, pos - 1, datas); //递归调用 qSort(pos + 1, end, datas); } java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 } } 冒泡排序 classclassclassclass BubbleSort { /* 从大到小*/ publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid sort(intintintint... datas) { booleanbooleanbooleanboolean flag = truetruetruetrue; forforforfor (intintintint i = datas.length - 1; i > 0 && flag; i--) { flag = falsefalsefalsefalse; forforforfor (intintintint j = 0; j < i; j++) { ifififif (datas[j] < datas[j+1]) {//改成>则从小到大排序 intintintint temp = datas[j]; datas[j] = datas[j+1]; datas[j+1] = temp; flag = truetruetruetrue; } } } } } 9,简单选择排序 classclassclassclass SelectSort { publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid sort(intintintint... datas) { forforforfor (intintintint i = 0; i则表示从小到大排序 k = j; } ifififif (k != i) { intintintint temp = datas[k]; datas[k] = datas[i]; datas[i] = temp; } } } } java 数据结构面试资料(不断更新中......) zcl 所有,翻版必究 10,插入排序 classclassclassclass InsertSort { publicpublicpublicpublic staticstaticstaticstatic voidvoidvoidvoid sort(intintintint... datas) { forforforfor (intintintint i = 1; i < datas.length; i++) { intintintint temp = datas[i]; intintintint j; forforforfor (j = i; j > 0; j--) { ifififif (datas[j-1] > temp) {//改成<则表示从大到小排序 datas[j] = datas[j-1]; } elseelseelseelse breakbreakbreakbreak; } datas[j] = temp; } } }
还剩9页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 15 金币 [ 分享pdf获得金币 ] 9 人已下载

下载pdf

pdf贡献者

zjixuanlv

贡献于2011-07-16

下载需要 15 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf