面试题目——《CC150》高等难题

面试题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<cards.length;i++){
			int k = rand(0,i);
			int temp = cards[k];
			cards[k] = cards[i];
			cards[i] = temp;
		}
	}

	public int rand(int lower,int higher){	//生成一个lower和higher（含）之间的随机数
		return lower+(int)(Math.random()*(higher-lower+1));
	}

	public int[] shuffleArrayRecursively(int[] cards,int i){	//打乱前i个部分的次序
		if(i==0)
			return cards;
		shuffleArrayRecursively(cards,i-1);	//打乱先前部分的次序
		int k=rand(0,i);			//在前i中随机选一个数和第i个数交换
		//交换
		int temp = cards[k];
		cards[k] = cards[i];
		cards[i] = temp;
		//返回元素次序被打乱的数组
		return cards;
	}

}

面试题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<article.length;i++){
			String currentWord = article[i];
			if(currentWord.equals(x)){		//等于x
				lastWord1 = i;
				//如果x和y有顺序要求，注释下面三句
				int distance =  lastWord1-lastWord2;	//不用求绝对值，因为lastWord1肯定在lastWord2后面
				if(lastWord2>=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<String,Boolean> map = new HashMap<String,Boolean>();
		for(String s:str)					//把所有的字符串放进哈希表中，并标为true
			map.put(s, true);
		Arrays.sort(str,new Comparator<String>(){		//排序

            @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<String,Boolean> map){
		if(map.containsKey(str) && !isOriginalWord)	//如果已经包含这个字符串，且不是原始字符
			return map.get(str);						//返回true
		for(int i=1;i<str.length();i++){
			String left = str.substring(0,i);
			String right = str.substring(i);
			//使用递归，单词可以由任意数量的其他单词组成，即right也可能由其他单词组成
			if(map.containsKey(left) && map.get(left) == true && canBuildWord(right, false, map))
				return true;
		}
		map.put(str,false);		//把这个检查过的str标记成false，避免以后遇到再重复检查
		return false;
	}

}

面试题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<b.length;i++)
			System.out.println(b[i]);
	}

	public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
		int len = p.length;
		boolean[] result = new boolean[len];
		for(int i=0;i<len;i++){
			if(s.contains(p[i]))
				result[i] = true;
			else
				result[i] = false;
		}
		return result;
    }

}

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

package cc150.high;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Middle {		//实时中位数

	private Comparator<Integer> minHeapComparator;	//小堆存放大于中位数的值
	private Comparator<Integer> maxHeapComparator =  new Comparator<Integer>(){  //大堆存放小于中位数的值，队头是中位数
		@Override
		public int compare(Integer o1, Integer o2) {
			// TODO 自动生成的方法存根
			  if(o1 > o2)  {
	                return -1;
	            }
	            else if(o1<o2){
	                return 1;
	            }
	            else{
	                return 0;
	            }
		}
    };

	private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(maxHeapComparator);	//编写Comparator，最大的数据项在队头
	private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();	//优先队列中，关键字最小的数据项总是在队头

	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<re.length;i++)
			System.out.println(re[i]);

//		md.addNewNumber(6);
//		md.addNewNumber(8);
//		md.addNewNumber(3);
//		md.addNewNumber(5);
//		md.addNewNumber(1);
//		md.addNewNumber(2);
//		System.out.println(md.maxHeap.poll());
//		System.out.println(md.maxHeap.poll());
//		System.out.println(md.maxHeap.poll());
//		System.out.println();
//		System.out.println(md.minHeap.poll());
//		System.out.println(md.minHeap.poll());
//		System.out.println(md.minHeap.poll());

	}

	public int[] getMiddle(int[] A, int n) {
        // write code here
		int[] result = new int[n];
		for(int i=0;i<n;i++){
			addNewNumber(A[i]);
			result[i] = getMedian();
		}
		return result;
    }

	public int getMedian(){
		if(maxHeap.isEmpty())
			return 0;
		if(maxHeap.size() == minHeap.size())
			//return (maxHeap.peek()+minHeap.peek())>>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<String> s = new HashSet<String>();
		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<String> l = c.countChanges(s,4,"abc","bdc");
//		Iterator i = l.iterator();
//		while(i.hasNext())
//			System.out.println(i.next());
	}

	//public int countChanges(Set<String> dic, int n, String s, String t) {
	public int countChanges(String[] dictionary, int n, String s, String t) {
        // write code here
		Set<String> dic = new HashSet<String>();
		for(int i=0;i<n;i++){
			dic.add(dictionary[i].toUpperCase());
		}
		s = s.toUpperCase();
		t = t.toUpperCase();
		Queue<String> actionQueue = new LinkedList<String>();
		Set<String> visitedSet = new HashSet<String>();
		Map<String,String> backtraceMap = new TreeMap<String,String>();

		actionQueue.add(s);
		visitedSet.add(s);

		while(!actionQueue.isEmpty()){		//非空的时候循环
			String w = actionQueue.poll();
			for(String v : getOneEditWords(w)){
				if(v.equals(t)){					//如果改变一次等于t的话
					LinkedList<String> list = new LinkedList<String>();
					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<String> getOneEditWords(String word){	//把s的所有字符换成其他的字符（只替换一个）的所有可能性，放到TreeSet中
		Set<String> words = new TreeSet<String>();
		for(int i=0;i<word.length();i++){
			char[] wordArray = word.toCharArray();
			for(char c='A';c<='Z';c++){			//把第i个字符替换成和原来不一样的字符，并放入TreeSet中
				if(c != word.charAt(i)){
					wordArray[i] = c;
					//System.out.println(new String(wordArray));
					words.add(new String(wordArray));
				}
			}
		}
		return words;
	}

}