一些java面试中经常出现的算法题

kaile 贡献于2014-11-23

作者 zengwenbin  创建于2014-04-06 02:20:00   修改者zengwenbin  修改于2014-04-06 02:25:00字数13164

文档摘要:快速排序需要确认有无问题1.现在输入n个数字,以逗号,分开;然后可选择升或者降序排序  本题的splitStringByComma(String)方法纯属多余,可以用String的split方法一句话代替,且可读性也更强,下面的一段话源自JDK1.6API,StringTokenizer类已不再提倡使用,保留仅为旧代码。 StringTokenizer是出于兼容性的原因而被保留的遗留类(虽然在新代码中并不鼓励使用它)。
关键词:

快速排序需要确认有无问题 1.现在输入n个数字,以逗号,分开;然后可选择升或者降序排序   本题的splitStringByComma(String )方法纯属多余,可以用String的split方法一句话代替,且可读性也更强,下面的一段话源自JDK1.6API,StringTokenizer类已不再提倡使用,保留仅为旧代码。  StringTokenizer 是出于兼容性的原因而被保留的遗留类(虽然在新代码中并不鼓励使用它)。建议所有寻求此功能的人使用 String 的 split 方法或 java.util.regex 包。  import java.util.*;  public class bycomma{      public static String[] splitStringByComma(String source){         if(source==null||source.trim().equals(""))                 return null;         StringTokenizer commaToker = new StringTokenizer(source,",");        String[] result = new String[commaToker.countTokens()];          int i=0;          while(commaToker.hasMoreTokens()){               result[i] = commaToker.nextToken();               i++;           }          return result;      }      public static void main(String args[]){          String[] s = splitStringByComma("5,8,7,4,3,9,1");           int[] ii = new int[s.length];           for(int i = 0; i=0;i--){            System.out.println(ii[i]);            }                 }  }  2.编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串。 但是要保证汉字不被截半个,如"我ABC"4,应该截为"我AB",输入"我ABC汉DEF",6,应该输出为"我ABC"而不是"我ABC+汉的半个"。  代码:  public static boolean isLetter(char c) {      int k=0X80;      return c/k==0?true:false;       }          public static int lengths(String strSrc){      if (strSrc==null) {         return 0;      }      int len=0;      char[] strChar=strSrc.toCharArray();      for (int i=0;ilengths(origin)){         return origin;           }      byte[] strByte=new byte[len];      System.arraycopy(origin.getBytes(),0,strByte,0,len);      int count=0;      for (int i=0;i1) partition(data,low,k-1);       if ((high-k)>1) partition(data,k+1,high);  }  public static int partition(int[] data int low,int high, int pivot ){        do {               while (data [++low]pivot);                swap(data,low,high);        }        while (low 0; i--) {      String tmp = o rigin.substring(i - 1, i);      result += tmp;     }     return result;  }  10、给你一组字符如{1,3,4,7,2,1,1,5,2},让你输出里面出现次数最多且数值最大的一个,出现几次   public void fun4() {      int[] a = { 4, 1, 2, 4, 5, 1, 1, 1, 5, 1, 3, 4, 5 };      Arrays.sort(a);      for (int i = 0; i < a.length; i++) {          System.out.print(a[i] + " ");      }     System.out.println();     int maxNumber = a[a.length - 1], maxCount = 1;     int curNumber = a[a.length - 1], curCount = 1;     for (int i = a.length - 1; i > 0; i--) {          curNumber = a[i];          if (a[i] == a[i - 1]) {              curCount++;          } else {               System.out.println("i=" + i + ",curCount=" + curCount+ ",maxCount=" + maxCount + ",maxNumber=" + maxNumber);               if (curCount > maxCount) {                   maxCount = curCount;                   maxNumber = curNumber;               }              curCount = 1;            }  }     if (curCount > maxCount) {        maxCount = curCount;        //maxNumber = curNumber;  }  System.out.println("curCount=" + curCount + ",maxCount=" + maxCount + ",maxNumber=" + maxNumber);  }   11、求两个数的公约数,M,N    int divisor =1;  for (int i = 2; i <= b; i++) {  if(a%i==0 && b%i==0){  divisor = i;  }  }  System.out.println(a+"和"+b+"的最大公约数是:"+divisor);  }   12、实现数组复制    我的理解:这是深复制,数组a,b不再有关联  public void fun8(){  int[] a = {1,2,3,4,56,7,8};  int[] b = (int[])a.clone();  Conica.print(a);  Conica.print(b);  b[0]=100;  Conica.print(a);  Conica.print(b);  }   13、冒泡排序的实现    public void fun9(){  int[] a = {1,5,2,6,8,74,1,25,69,8};  Conica.print(a);  for(int i=0; ia[j+1]){  int temp = a[j];  a[j] = a[j+1];  a[j+1] = temp;  }  }  }  Conica.print(a);  }   14、编程显示某一文件目录下的文件名    public void fun10(){  File file = new File("G:\\03月份");  if(file.exists()){  if(file.isDirectory()){  String[] files = file.list();  Conica.println(files);  }  }  }  15、从键盘输入4个十进制数字字符,将其转换为4位时间之数并显示出来   16、编程实现统计文本文件中某个单词的出现频率,并输出统计结果   用HashMap来解决  假设单词不存在跨行的,每个单词用,. ;分割        public static void countNum() throws IOException {     BufferedReader br = null;     try {      br = new BufferedReader(new FileReader("c://file.txt"));      Map map = new HashMap();      for (String s = br.readLine(); s != null; s = br.readLine()) {       StringTokenizer st = new StringTokenizer(s, ",.   ;");       while (st.hasMoreTokens()) {        String temp = st.nextToken();        if (map.containsKey(temp)) {         map.put(temp, new Integer((Integer)map.get(temp) + 1));        } else {              map.put(temp, new Integer(1));        }       }      }      for (Iterator it = map.entrySet().iterator(); it.hasNext();) {       Map.Entry entry = (Map.Entry) it.next();       System.out.println(entry.getKey() + "-->" + entry.getValue()         + "times");      }     } finally {      br.close();     }  }  17、编程模仿DOS下的dir命令,列出某个目录下的内容  18、编程说明String和StringBuffer字符串的区别   19、编程计算N!的程序,一个使用递归方法,一个不用递归方法    递归 :  long fuction(int n){     if (n==0) return 1;  else            return n* fuction(n-1);    }   不递 :  long s=1;  for(int i=2;i<=n;i++)  {        s*=i;  }  20、编程实现ASCII码和Unicode码之间的转换   21.用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求: "4 "不能在第三位, "3 "与 "5 "不能相连.  此题具体算法及程序可参考:  http://topic.csdn.net/u/20070114/14/1170e023-e8f0-4331-8bd8-516c6f1e40da.html    22。一个字符串中可能包含a~z中的多个字符,如有重复,如String data="aavzcadfdsfsdhshgWasdfasdf",求出现次数最多的那个字母及次数,如有多个重复的则都求出。〔金山公司面试题〕  import java.util.ArrayList;  import java.util.Collections;  import java.util.Iterator;  import java.util.TreeSet;  public class FindRepeatChar {  public static void doString(String strInput) {     char[] chars = strInput.toCharArray();     ArrayList lists = new ArrayList();     TreeSet set = new TreeSet();     for (int i = 0; i < chars.length; i++) {      lists.add(String.valueOf(chars[i]));      set.add(String.valueOf(chars[i]));     }     System.out.println(set);     Collections.sort(lists);     System.out.println(lists);     StringBuffer sb = new StringBuffer();     for (int i = 0; i < lists.size(); i++) {      sb.append(lists.get(i));     }     strInput = sb.toString();     System.out.println(strInput);     int max = 0;     String maxString = "";     ArrayList maxList = new ArrayList();     for (Iterator its = set.iterator(); its.hasNext();) {      String os = (String) its.next();      i nt begin = strInput.indexOf(os);      int end = strInput.lastIndexOf(os);      int value = end - begin + 1;      if (value > max && value > 1) {       max = value;       maxString = os;       maxList.add(os);      } else if (value == max) {       maxList.add(os);      }     }     int index = 0;     for (int i = 0; i < maxList.size(); i++) {      if (maxList.get(i).equals(maxString)) {       index = i;       break;      }     }     System.out.println("出现最多的字符为:");     for (int i = 0; i < maxList.size(); i++) {      System.out.println(maxList.get(i) + "");     }     System.out.println();     System.out.println("出现最多的次数为:" + max);  }  public static void main(String[] args) {     String strInput = new String("aavzcadfdsfsdhshgWasdfasdf");     doString(strInput);  }  }  23.金额转换,阿拉伯数字的金额转换成中国传统的形式如:(¥1011)->(一千零一拾一元整)输出。  public class RenMinBi { private static final char[] data = new char[]{ '零','壹','贰','叁','肆','伍','陆','柒','捌','玖'};  private static final char[] units = new char[]{ '元','拾','佰','仟','万','拾','佰','仟','亿'}; public static void main(String[] args) { // TODO Auto-generated method stub System.out.println( convert(222222222)); } public static String convert(int money) { StringBuffer sbf = new StringBuffer(); int unit = 0; while(money!=0) { sbf.insert(0,units[unit++]); int number = money%10; sbf.insert(0, data[number]); money /= 10; } return sbf.toString(); } } 24.1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?   25.编写一个程序,将a.txt文件中的单词与b.txt文件中的单词交替合并到c.txt文件中,a.txt文件中的单词用回车符分隔,b.txt文件中用回车或空格进行分隔? import java.io.File; import java.io.FileReader; import java.io.FileWriter;   public class MainClass{        public static void main(String[] args) throws Exception{               FileManager a = new FileManager("a.txt",new char[]{'\n'});               FileManager b = new FileManager("b.txt",new char[]{'\n',' '});                        FileWriter c = new FileWriter("c.txt");               String aWord = null;               String bWord = null;               while((aWord = a.nextWord()) !=null ){                      c.write(aWord + "\n");                      bWord = b.nextWord();                      if(bWord != null)                             c.write(bWord + "\n");               }                             while((bWord = b.nextWord()) != null){                      c.write(bWord + "\n");               }                   c.close();        }      }   class FileManager{          String[] words = null;        int pos = 0;        public FileManager(String filename,char[] seperators) throws Exception{               File f = new File(filename);               FileReader reader = new FileReader(f);               char[] buf = new char[(int)f.length()];               int len = reader.read(buf);               String results = new String(buf,0,len);               String regex = null;               if(seperators.length >1 ){                      regex = "" + seperators[0] + "|" + seperators[1];               }else{                      regex = "" + seperators[0];               }               words = results.split(regex);        }               public String nextWord(){               if(pos == words.length)                      return null;               return words[pos++];        } }   26.题目:从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2-10为数字本身,A为1,J为11,Q为12,K为13,而大小王可以看成任意数字。  分析:这题目很有意思,是一个典型的寓教于乐的题目。我们需要把扑克牌的背景抽象成计算机语言。不难想象,我们可以把5张牌看成由5个数字组成的数组。大小王是特殊的数字,不妨把它们都当成0,这样和其他扑克牌代表的数字就不重复了。     接下来我们来分析怎样判断5个数字是不是连续的。最直观的是,我们把数组排序。但值得注意的是,由于0可以当成任意数字,我们可以用0去补满数组中的空缺。也就是排序之后的数组不是连续的,即相邻的两个数字相隔若干个数字,但如果我们有足够的0可以补满这两个数字的空缺,这个数组实际上还是连续的。举个例子,数组排序之后为{0,1,3,4,5}。在1和3之间空缺了一个2,刚好我们有一个0,也就是我们可以它当成2去填补这个空缺。     于是我们需要做三件事情:把数组排序,统计数组中0的个数,统计排序之后的数组相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数,那么这个数组就是连续的;反之则不连续。最后,我们还需要注意的是,如果数组中的非0数字重复出现,则该数组不是连续的。换成扑克牌的描述方式,就是如果一副牌里含有对子,则不可能是顺子。     基于这个思路,我们可以写出如下的代码: 1 import java.util.Arrays; 2 import java.util.Random; 3 4 5 public class ContinuousPoker { 6 7 /**Q67 扑克牌的顺子 8 * 从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。 9 * 2-10为数字本身,A为1,J为11,Q为12,K为13,而大小王可以看成任意数字。 10 */ 11 private static final int[] poker={ 12 0,0 13 ,1,2,3,4,5,6,7,8,9,10,11,12,13 14 ,1,2,3,4,5,6,7,8,9,10,11,12,13 15 ,1,2,3,4,5,6,7,8,9,10,11,12,13 16 ,1,2,3,4,5,6,7,8,9,10,11,12,13}; 17 private static final int MAX=5; 18 private static final int MAX_VAL=13; 19 20 public static void main(String[] args) { 21 //test 1.Specific data for test. 22 int[][] testData={ 23 {7,8,0,10,11}, 24 {7,8,0,0,11}, 25 {8,9,9,10,11}, 26 {7,8,9,10,11}, 27 }; 28 for(int[] pokerSelected:testData){ 29 test(pokerSelected); 30 } 31 //test 2.Imitate the real situation:Select 5 poker randomly. 32 int[] pokerSelected=randomSelect(poker,MAX); 33 test(pokerSelected); 34 35 } 36 37 public static void test(int[] pokerSelected){ 38 System.out.println(Arrays.toString(pokerSelected)); 39 boolean continuous=isContinuous(pokerSelected); 40 System.out.println("continuous is "+continuous); 41 } 42 43 /* 44 1)确认5张牌中除了0,其余数字没有重复的(可以用表统计的方法); 45 2) 满足这样的逻辑:(max,min分别代表5张牌中的除0以外的最大值最小值) 46 如果没有0,则max-min=4,则为顺子,否则不是 47 如果有一个0,则max-min=4或者3,则为顺子,否则不是 48 如果有两个0,则max-min=4或者3或者2,则为顺子,否则不是 49 最大值和最小值在1)中就可以获得 50 */ 51 public static boolean isContinuous(int[] x){ 52 int[] existTimes=new int[MAX_VAL+1]; 53 boolean result=false; 54 int len=x.length; 55 int max=x[0],min=x[0]; 56 int zeroCount=0; 57 for(int i=0;imax)max=x[i]; 63 if(x[i]1){//duplicate non-zero element 68 return false; 69 } 70 } 71 if(zeroCount==0){ 72 if(max-min==MAX-1)result=true; 73 }else if(zeroCount==1){ 74 if(max-min==MAX-1 || max-min==MAX-2)result=true; 75 }else if(zeroCount==2){ 76 if(max-min==MAX-1 || max-min==MAX-2 || max-min==MAX-3)result=true; 77 } 78 79 return result; 80 } 81 82 /* 83 * @param count how many elements you want to pick 84 * @param data the data array 85 */ 86 public static int[] randomSelect(int[] data,int count){ 87 int[] result=new int[count]; 88 int len=data.length; 89 for(int i=0;i

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

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

需要 3 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档