Java经典面试题-算法
时间：2010-10-17 来源：南通SEO
最近几天一直忙于找工作，好多java基础的东西都会，就是因当时在学校的时候，老师讲的java对算法要求不高，所以算法也一直是本人的缺陷，想 不到，在工作中是要求不高，但在面试当中，别人对算法看的还是很重的。唉。。。吃亏ing......no way ...只能临时抱抱佛脚啦！在网上找了各种各样的算法，决定对他总结下：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class InsertSort implements SortUtil.Sort{
public void sort(int[] data) {
int temp;
for(int i=1;i<data.length;i++){
for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
SortUtil.swap(data,j,j-1);
}
}
}
}
冒泡排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class BubbleSort implements SortUtil.Sort{
public void sort(int[] data) {
int temp;
for(int i=0;i<data.length;i++){
for(int j=data.length-1;j>i;j--){
if(data[j]<data[j-1]){
SortUtil.swap(data,j,j-1);
}
}
}
}
}
选择排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class SelectionSort implements SortUtil.Sort {
public void sort(int[] data) {
int temp;
for (int i = 0; i >< data.length; i++) {
int lowIndex = i;
for (int j = data.length - 1; j > i; j--) {
if (data[j] < data[lowIndex]) {
lowIndex = j;
}
}
SortUtil.swap(data,i,lowIndex);
}
}
}
Shell排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class ShellSort implements SortUtil.Sort{
public void sort(int[] data) {
for(int i=data.length/2;i>2;i/=2){
for(int j=0;j<i;j++){
insertSort(data,j,i);
}
}
insertSort(data,0,1);
}
private void insertSort(int[] data, int start, int inc) {
int temp;
for(int i=start+inc;i<data.length;i+=inc){
for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
SortUtil.swap(data,j,j-inc);
}
}
}
}
快速排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class QuickSort implements SortUtil.Sort{
public void sort(int[] data) {
quickSort(data,0,data.length-1);
}
private void quickSort(int[] data,int i,int j){
int pivotIndex=(i+j)/2;
//swap
SortUtil.swap(data,pivotIndex,j);
int k=partition(data,i-1,j,data[j]);
SortUtil.swap(data,k,j);
if((k-i)>1) quickSort(data,i,k-1);
if((j-k)>1) quickSort(data,k+1,j);
}
private int partition(int[] data, int l, int r,int pivot) {
do{
while(data[++l]<pivot);
while((r!=0)&&data[--r]>pivot);
SortUtil.swap(data,l,r);
}
while(l<r);
SortUtil.swap(data,l,r);
return l;
}
}
改进后的快速排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class ImprovedQuickSort implements SortUtil.Sort {
private static int MAX_STACK_SIZE=4096;
private static int THRESHOLD=10;
public void sort(int[] data) {
int[] stack=new int[MAX_STACK_SIZE];
int top=-1;
int pivot;
int pivotIndex,l,r;
stack[++top]=0;
stack[++top]=data.length-1;
while(top>0){
int j=stack[top--];
int i=stack[top--];
pivotIndex=(i+j)/2;
pivot=data[pivotIndex];
SortUtil.swap(data,pivotIndex,j);
//partition
l=i-1;
r=j;
do{
while(data[++l]<pivot);
while((r!=0)&&(data[--r]>pivot));
SortUtil.swap(data,l,r);
}
while(l<r);
SortUtil.swap(data,l,r);
SortUtil.swap(data,l,j);
if((l-i)>THRESHOLD){
stack[++top]=i;
stack[++top]=l-1;
}
if((j-l)>THRESHOLD){
stack[++top]=l+1;
stack[++top]=j;
}
}
//new InsertSort().sort(data);
insertSort(data);
}
/**
* @param data
*/
private void insertSort(int[] data) {
int temp;
for(int i=1;i<data.length;i++){
for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
SortUtil.swap(data,j,j-1);
}
}
}
}
堆排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class HeapSort implements SortUtil.Sort{
public void sort(int[] data) {
MaxHeap h=new MaxHeap();
h.init(data);
for(int i=0;i<data.length;i++)
h.remove();
System.arraycopy(h.queue,1,data,0,data.length);
}
private static class MaxHeap{
void init(int[] data){
this.queue=new int[data.length+1];
for(int i=0;i<data.length;i++){
queue[++size]=data[i];
fixUp(size);
}
}
private int size=0;
private int[] queue;
public int get() {
return queue[1];
}
public void remove() {
SortUtil.swap(queue,1,size--);
fixDown(1);
}
//fixdown
private void fixDown(int k) {
int j;
while ((j = k ><< 1) <= size) {
if (j < size && queue[j]<queue[j+1])
j++;
if (queue[k]>queue[j]) //不用交换
break;
SortUtil.swap(queue,j,k);
k = j;
}
}
private void fixUp(int k) {
while (k > 1) {
int j = k >> 1;
if (queue[j]>queue[k])
break;
SortUtil.swap(queue,j,k);
k = j;
}
}
}
}
SortUtil:
package org.rut.util.algorithm;
import org.rut.util.algorithm.support.BubbleSort;
import org.rut.util.algorithm.support.HeapSort;
import org.rut.util.algorithm.support.ImprovedMergeSort;
import org.rut.util.algorithm.support.ImprovedQuickSort;
import org.rut.util.algorithm.support.InsertSort;
import org.rut.util.algorithm.support.MergeSort;
import org.rut.util.algorithm.support.QuickSort;
import org.rut.util.algorithm.support.SelectionSort;
import org.rut.util.algorithm.support.ShellSort;
public class SortUtil {
public final static int INSERT = 1;
public final static int BUBBLE = 2;
public final static int SELECTION = 3;
public final static int SHELL = 4;
public final static int QUICK = 5;
public final static int IMPROVED_QUICK = 6;
public final static int MERGE = 7;
public final static int IMPROVED_MERGE = 8;
public final static int HEAP = 9;
public static void sort(int[] data) {
sort(data, IMPROVED_QUICK);
}
private static String[] name={
"insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"
};
private static Sort[] impl=new Sort[]{
new InsertSort(),
new BubbleSort(),
new SelectionSort(),
new ShellSort(),
new QuickSort(),
new ImprovedQuickSort(),
new MergeSort(),
new ImprovedMergeSort(),
new HeapSort()
};
public static String toString(int algorithm){
return name[algorithm-1];
}
public static void sort(int[] data, int algorithm) {
impl[algorithm-1].sort(data);
}
public static interface Sort {
public void sort(int[] data);
}
public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
求最大公约数和最小公倍数
- /**
- * 求最大公约数和最小公倍数
- */
- public class Convention {
- /**
- * 求两数的最大公约数
- */
- int divisor(int m,int n){
- if(m%n==0){
- return n;
- }else{
- return divisor(n,m%n);
- }
- }
- /**
- * 求两数的最小公倍数
- */
- int gbs(int a,int b){
- int gbs = 0;
- gbs = a*b/divisor(a,b);
- return gbs;
- }
- }
求一组数组的众数
- public static double mode(double[] array) {
- Arrays.sort(array);
- int count = 1;
- int longest = 0;
- double mode = 0;
- for (int i = 0; i < array.length - 1; i++) {
- if (array[i] == array[i + 1]) {
- count++;
- } else {
- count = 1;//如果不等于，就换到了下一个数，那么计算下一个数的次数时，count的值应该重新符值为一
- continue;
- }
- if (count > longest) {
- mode = array[i];
- longest = count;
- }
- }
- System.out.println(longest);//打印出这个数出现的次数已判断是否正确
- return mode;
- }
公司笔试题就1个，要求在10分钟内作完。
题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
- package test;
/**
* 用1，2，2，3，4，5，这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234，412345等，要求：“4”不能排第3位，“1”与“5”不能相连。
* @author kafka0102
*
*/
public class ATest {
private static boolean is1Or5(char a,char b){
if(a=='1' && b=='5')return true;
if(a=='5' && b=='1')return true;
return false;
}
private static int countOf2(char[] num,int index){
int n=0;
for(int i=0;i<index;i++){
if(num[i]=='2')n++;
}
return n;
}
private static boolean hasSameNumber(int index,char a, char[] num){
for(int i=0;i<index;i++){
;
}
return false;
}
public static int testArrange(char[] number,char[] num,int index){
int size = 0;//组合的个数
int pos1=1,pos2=2;//该变量为重复的2的数组位置，可以提取出来作为参数
int emp = countOf2(num,index);//得到当前的数组中有几个2
for(int i=0;i<num.length;i++){
if(number[i]=='2'){//当前的数字为2
if(emp >= 2){//数组中2的个数多于2个
continue;
}else if(emp == 1){//数组中有一个2时，要求当前的2不能为位置1的2
if(i==pos1)continue;
}else{
if(i==pos2)continue;//数组中没有2时，要求当前的2不能为位置2的2
}
}else{
if(index==2 && number[i]=='4')continue;//去除4
if(index>0 && is1Or5(num[index-1],number[i]))continue;//去除相邻的1和5
if(hasSameNumber(index,number[i], num))continue;//去除重复数字
}
num[index] = number[i];
if(index==5){
System.out.println(num);
size++;
}else{
size = size + testArrange(number,num,index+1);
}
}
return size;
}
public static void aTest(){
char[] number = {'1','2','2','3','4','5'};
char[] num = new char[number.length];
int size =0;
size = testArrange(number,num,0);
System.out.println("size="+size);
}
public static void main(String[] args) {
aTest();
}
}
有一个String s="SDsBEaA"
要求产生这样的结果:s="AaBDESs"
public class MySort {
public static void main(String[] args) {
List<Character> result = new ArrayList<Character>();
String s = "SDsBEAa";
char[] strArray = s.toCharArray();
// strArray = ABDESas
Arrays.sort(strArray);
for (int i = 97; i < 122; i++) {
char tempLowCase = (char) i;
char tempUpperCase = (char) (i - 32);
for (int j = 0; j < strArray.length; j++) {
if (Character.isUpperCase(strArray[j])) {
if (tempUpperCase == strArray[j]) {
result.add(tempUpperCase);
}
}
if (tempLowCase == strArray[j]) {
result.add(strArray[j]);
}
}
}
System.out.println(result);
}
}
假定你有一点算法数据结构知识
如果没有的话,所有提到的内容请自行查找,
不推荐提问.
最后偶会说说为什么写这些东西,
为什么选择这些而没有选择另一些.
1 链表找环(探测环形链表) O(n)
A 拓扑排序,删0入度点
B DFS(经过一个点就标记,标记2次的即可判定为环)
2 半素数
(只要一个数能被分解成两个素数，那么这个数就是半素数)
注意时间空间的平衡.
输入N (2<=N<=1000000),输出Y或者N,每行一个,遇0结束
这里只讨论探查找第一个质因数的问题.
A 从 2 到 ceil(sqrt(N)) 取余数探查
B 筛质数,2-1000中的质数进行筛选 (因为对最大的N,ceil(sqrt(N))=1000)
C 小素数筛选,大素数使用 Miller-Rabin 测试
3 LCA(最近公共祖先,Least Common Ancestors) 和 RMQ(Range Minimum/Maximum Query)
先说 RMQ,再说 LCA.
RMQ有n多种方法.
本部分复杂度记法:O(预处理时间)-O(查询时间)
朴素(或许可以称作暴力)DP:
造表,O(n^2)-O(1)
分块,每块大小sqrt(N),总块数sqrt(N),
O(n)-O(sqrt(N))
第一次查询本块,第2次查询所有块的最小值
稀疏表(ST,Sparse Table),存储(i,i+2^j)中的最小值(1<=logn)
O(nlogn)-O(1)
(但是很多人懒的把它写好,所以查询成了O(logn)
存储的是下标,不是数)
类线段树,O(n)-O(logn)
LCA->RMQ: O(n)
深度优先遍历,记录节点深度D[i] 和节点第一次出现的位置(在数组中,R[i])
LCA(i,j)=RMQ(R[i],R[j]) (i<j )
因为每边来回各一次,所以数列中总共 2n-1 项.
相邻两项中相差1(遍历总不能跳着来吧),这样的RMQ也叫+/-1RMQ
RMQ->LCA: O(n)
笛卡尔树(Cartesian Tree),构造时间O(n),具体略
+/-1 RMQ有O(n)-O(1)的算法
将数列分成(2log2n)段,每段长(log2n/2).
用上面提到的稀疏表(ST)方法,
可以在O(N)的时间内完成所有小块的预处理
为什么是O(N)? O(n/(log2n/2) * log2(N/log2n*2) )=O(n)
后面对RMQ的预处理仍然是O(n),具体内容自己查找.
查询是O(1)的,相当的快.
回到正题.
对一般的RMQ进行如下处理
RMQ->LCA->(+/-1)RMQ
都可以达到O(n)-O(1)
另外,LCA还有利用并查集的Tarjan算法,
代码简单,但可惜的是它是离线算法.
====
ps: 没事的同学,看不明白的同学欢迎跳走…
ps2:算法导论第二版偶已经看完了,
如果不考虑证明问题的话,
掌握85%应该是可以达到的
ps3:看了好多关于C函数的面试问题,
这些东西只不过是让你注意一下边界处理问题
(当然偶并不否认它不重要)
很多情况下重做这些东西确实等于重造轮子
ps4:看算法导论不一定就等于会了,欢迎找个Online judge做做题
ps5:写这些东西或许就是来充技术文章的数的?
ps6:这里不是CSDN,写了好文章不会有人推你上首页.
废话了这么多,赶紧结束.
相关阅读 更多 +
