面试题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;
}
}