面试题18.1：编写一个函数，将两个数字相加。不得使用+或其他算数运算符。

package cc150.high;public class Add {	public static void main(String[] args) {		// TODO 自动生成的方法存根			}		public int add(int a,int b){	//将两个数字相加，不得使用+或者其他算数运算符		if(b == 0)			return a;		int sum = a^b;					//相加，但不进位		int carry = (a&b)<<1;		//进位，但是不相加		return add(sum,carry);	}}

 

面试题18.2：编写一个方法，洗一副牌。要求做到完美洗牌，换言之，这副牌52！中排列组合出现的概率相同。假设给定一个完美的随机数发生器。

package cc150.high;public class ShuffleArrayInteratively {	public static void main(String[] args) {		// TODO 自动生成的方法存根			}		public void shuffleArrayInteratively(int[] cards){	//使用递归算法洗牌		for(int i=0;i

 

面试题18.3：编写一个方法，从大小为n的数组中随机选出m个整数。要求每个元素被选中的概率相同。

 

面试题18.4：编写一个方法，数出0到n（含）中数字2出现了几次。

package cc150.high;public class Count2 {	public static void main(String[] args) {		// TODO 自动生成的方法存根		Count2 c2 = new Count2();		System.out.println(c2.countNumberOf2s(21));	}		public int countNumberOf2s(int n) {	//对比Leetcode中数1的题目		if (n <= 1) return 0;		 	    int res = 0, m;	    for (m = 1;m <= n;m *= 10) {				//m为10/100/1000...	        int tmp1 = n/m, tmp2 = n%m;	//tmp1是较高位，tmp2是较低位	        if(tmp1 % 10 == 2){				//m=1，tmp1为倒数第一位，tmp2为0；m=10，倒二倒一	        	res += (tmp1 + 7) / 10 * m + (tmp2 + 1);	//如果十位是2，加上个位加一，求十位是2的个数	        	System.out.println("res1="+res);	        }	        else{											//如果个位不是2，求小于这个数的个数是2的个数	        	res += (tmp1 + 7) / 10 * m;	        	System.out.println("res2="+res);	        }	    }	    return res;	}	//	public int countNumberOf2s(int n) {		//复杂度过高，耗时过多//        // write code here//		int count = 0;//		for(int i=2;i<=n;i++)//			count += countNumberOf2(i);//		return count;//    }//	//	public int countNumberOf2(int n) {//        // write code here//		int count = 0;//		while(n>0){//			if(n%10 == 2)//				count++;//			n /= 10;//		}//		return count;//    }}

 

面试题18.5：有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离（也即相隔几个单词）。有办法在O(1)时间里完成搜索操作吗？解法的空间复杂度如何？

package cc150.high;public class Distance {	public static void main(String[] args) {		// TODO 自动生成的方法存根	}		public int getDistance(String[] article, int n, String x, String y) {        // write code here		int min = Integer.MAX_VALUE;		int lastWord1 = -1;		int lastWord2 = -1;		for(int i=0;i
     
      =0 && min>distance)					min = distance;			}else if(currentWord.equals(y)){				lastWord2 = i;				int distance =  lastWord2-lastWord1;				if(lastWord1>=0 && min>distance)					min = distance;			}		}		return min;    }	}
     

 

面试题18.7：给定一组单词，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。

package cc150.high;import java.util.Arrays;import java.util.Comparator;import java.util.HashMap;public class LongestString {	public static void main(String[] args) {		// TODO 自动生成的方法存根		String[] a = {"abcd","bcd","abc","ab","bc","d"};		LongestString ls = new LongestString();		String b = ls.getLongest(a,6);		System.out.println(b);	}		public String  getLongest(String[] str, int n) {        // write code here		HashMap
     
       map = new HashMap
      
       ();		for(String s:str)					//把所有的字符串放进哈希表中，并标为true			map.put(s, true);		Arrays.sort(str,new Comparator
       
        (){		//排序	                      @Override            public int compare(String str1, String str2) {                // TODO Auto-generated method stub                            int l1 = str1.length();                    int l2 = str2.length();                    return l2-l1;			//按字符串的长度从长到短排序            }        });		for(String s:str){			if(canBuildWord(s, true, map)){				//System.out.println(s);				return s;			}		}		return "";    }		public boolean canBuildWord(String str,boolean isOriginalWord,HashMap
        
          map){		if(map.containsKey(str) && !isOriginalWord)	//如果已经包含这个字符串，且不是原始字符			return map.get(str);						//返回true		for(int i=1;i
        
       
      
     

 

面试题18.8：给定一个字符串s和一个包含较短字符串的数组T，设计一个方法，根据T中的每一个较短字符串，对s进行搜索。

package cc150.high;public class Substr {	public static void main(String[] args) {		// TODO 自动生成的方法存根		String[] str = {"a","b","c","d"};		String s = "abc";		Substr sb = new Substr();		boolean[] b  = sb.chkSubStr(str,4,s);		for(int i=0;i

 

面试题18.9：随机生成一些数字并传入某个方法。编写一个程序，每当收到新数字时，找出并记录中位数。

package cc150.high;import java.util.Comparator;import java.util.PriorityQueue;public class Middle {		//实时中位数	private Comparator
     
       minHeapComparator;	//小堆存放大于中位数的值	private Comparator
      
        maxHeapComparator =  new Comparator
       
        (){  //大堆存放小于中位数的值，队头是中位数		@Override		public int compare(Integer o1, Integer o2) {			// TODO 自动生成的方法存根			  if(o1 > o2)  {  	                return -1;  	            }  	            else if(o1
        
          maxHeap = new PriorityQueue
         
          (maxHeapComparator);	//编写Comparator，最大的数据项在队头	private PriorityQueue
          
            minHeap = new PriorityQueue
           
            (); //优先队列中，关键字最小的数据项总是在队头 public static void main(String[] args) { // TODO 自动生成的方法存根 Middle md = new Middle(); int[] a = {236312,116289,257841,40359,21993,121674,68768,288444,98015,118071,130963,221777,71589,233048,89053,20048,264772,141943,170253,299901,193849,211453,198250,280383,126656,4775,229057,119532}; int[] re = md.getMiddle(a,28); for(int i=0;i
            
             >1; return maxHeap.peek(); else return maxHeap.peek(); } public void addNewNumber(int randomNumber){ if(maxHeap.size() == minHeap.size()){ //两个队列相等的情况 if((minHeap.peek() != null) && randomNumber > minHeap.peek()){ //新的数大于小堆的队头 maxHeap.offer(minHeap.poll()); minHeap.offer(randomNumber); }else{ //新的数小于等于小堆的队头，为空默认放进大堆 maxHeap.offer(randomNumber); } }else{ //两个队列不相等的情况 if(randomNumber < maxHeap.peek()){ //新的数小于大堆的队头 minHeap.offer(maxHeap.poll()); maxHeap.offer(randomNumber); }else{ //新的数大于等于大堆的队头 minHeap.offer(randomNumber); } } }}
            
           
          
         
        
       
      
     

 

面试题18.10：给定两个字典里的单词，长度相等。编写一个方法，将一个单词变换成另一个单词，一次只改动一个字母。在变换过程中，每一步得到的新单词都必须是字典里存在的。

package cc150.high;import java.util.HashSet;import java.util.Iterator;import java.util.LinkedList;import java.util.Map;import java.util.Queue;import java.util.Set;import java.util.TreeMap;import java.util.TreeSet;public class Change {		//字符串变换，字符串s变换到t所需要的最少步数，且变换过程中每个字符串都是字典中的	public static void main(String[] args) {		// TODO 自动生成的方法存根		Set
     
       s = new HashSet
      
       ();		s.add("ABC");		s.add("ADC");		s.add("BDC");		s.add("AAA");		Change c = new Change();		String[] str = {"abc","adc","bdc","aaa"};		System.out.println(c.countChanges(str,4,"abc","bdc"));//		System.out.println(c.countChanges(s,4,"abc","bdc"));//		LinkedList
       
         l = c.countChanges(s,4,"abc","bdc");//		Iterator i = l.iterator();//		while(i.hasNext())//			System.out.println(i.next());	}		//public int countChanges(Set
        
          dic, int n, String s, String t) {	public int countChanges(String[] dictionary, int n, String s, String t) {        // write code here		Set
         
           dic = new HashSet
          
           (); for(int i=0;i
           
             actionQueue = new LinkedList
            
             (); Set
             
               visitedSet = new HashSet
              
               (); Map
               
                 backtraceMap = new TreeMap
                
                 (); actionQueue.add(s); visitedSet.add(s); while(!actionQueue.isEmpty()){ //非空的时候循环 String w = actionQueue.poll(); for(String v : getOneEditWords(w)){ if(v.equals(t)){ //如果改变一次等于t的话 LinkedList
                 
                   list = new LinkedList
                  
                   (); list.add(v); while(w != null){ list.add(0,w); //把w插入到list的首部 w = backtraceMap.get(w); //到最后的时候，w指向的是null，这个是结束条件，其他时候w的值赋值为v } //return list; return list.size(); } if(dic.contains(v)){ //如果改变一次后不等于t，但是是字典中的值的话 if(!visitedSet.contains(v)){ actionQueue.add(v); //把这个新的值加入队列中，会从头开始检查 visitedSet.add(v); //标记为已经访问 backtraceMap.put(v, w); //把v指向w，BDC指向ADC指向ABC //System.out.println(v+","+w); } } } } //return null; return 0; } Set
                   
                     getOneEditWords(String word){ //把s的所有字符换成其他的字符（只替换一个）的所有可能性，放到TreeSet中 Set
                    
                      words = new TreeSet
                     
                      (); for(int i=0;i