面试题17.1：编写一个函数，不用临时变量，直接交换两个数。

　　思路：使用差值或者异或

package cc150.middle;public class Exchange {	public static void main(String[] args) {		// TODO 自动生成的方法存根		int[] a= {1,2};		Exchange ec = new Exchange();		int[] b= ec.exchangeAB(a);		System.out.println(b[0]);		System.out.println(b[1]);	}		 public int[] exchangeAB(int[] AB) {	        // write code here//		 	AB[0] = AB[0]-AB[1];//		 	AB[1] = AB[0]+AB[1]; //		 	AB[0] = AB[1]-AB[0]; 		 		 	AB[0] = AB[0]^AB[1];		 	AB[1] = AB[0]^AB[1]; 		 	AB[0] = AB[1]^AB[0]; 		 	return AB;	    }}

 

面试题17.2：设计一个算法，判断玩家是否赢了井字游戏。

package cc150.middle;public class Board {	//井字棋	public static void main(String[] args) {		// TODO 自动生成的方法存根		int[][] a = {
    {1,0,1},{1,-1,-1},{1,-1,0}};		Board b = new Board();		System.out.println(b.checkWon(a));	}		public boolean checkWon(int[][] board) {        // write code here		int N = board.length;		int row = 0;		int col = 0;				//检查行		for(row = 0;row

 

面试题17.3：设计一个算法，算出n阶乘有多少个尾随零。

package cc150.middle;public class Factor {	public static void main(String[] args) {		//n阶乘有多少个尾随零		// TODO 自动生成的方法存根		Factor f = new Factor();		System.out.println(f.getFactorSuffixZero(10));	}		public int getFactorSuffixZero(int n) {//统计所有相乘的数中分解出5的个数，2的个数必定大于5，只要统计5的个数即可        // write code here//		int count = 0;//		for(int i=2;i<=n;i++)//			count += factorOf5(i);//		return count;				int count = 0;		for(int i=5;n/i>0;i*=5)		//如果n=10的话，有2个数在5和25之间			count += n/i;		return count;    }		public int factorOf5(int n) {        // write code here		int count = 0;		while(n%5 == 0){	//求余数			count ++;			n/=5;		}		return count;    }}

 

面试题17.4：编写一个方法，找出两个数字中最大的那一个。不得使用if-else或其他比较运算符。

package cc150.middle;public class Max {	public static void main(String[] args) {		// TODO 自动生成的方法存根			}		public int getMax(int a, int b) {        // write code here		b = a-b;					//此时b>>31为1则b小于0即a
     
      >31为0 则a>b	    a -= b&(b>>31); 	//若a
      b a=a-0 	    return a;    }}
     

 

面试题17.6：给定一个整数数组，编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n-m越小越好，也就是说，找出符合条件的最短序列。

 

面试题17.7：给定一个整数，打印该整数的英文描述（例如“One Thousand,Two Hundred Thirty Four”）。

package cc150.middle;public class ToString {	public static void main(String[] args) {		// TODO 自动生成的方法存根		ToString ts = new ToString();		System.out.println(ts.toString(1000));		//输入1234，输出"One Thousand,Two Hundred Thirty Four"	}		public static String[] digits = {"One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};	public static String[] teens = {"Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};	public static String[] tens = {"Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};	public static String[] bigs = {"","Thousand","Million"};		public String toString(int x) {        // write code here		if(x == 0)			return "Zero";		else if(x < 0)			return "Negative " + toString(-1*x);		int count = 0;		String str = "";		while(x > 0){			if(x % 1000 != 0){						if(count == 0 || str == "")  //One Million后面不能有逗号					str = toString100(x % 1000)+bigs[count]+str; //把count大的million放在前面，原来的str放在后面				else					str = toString100(x % 1000)+bigs[count]+","+str; //把count大的million放在前面，原来的str放在后面			}			x /= 1000;			count ++;		}		return str.trim();    }		public String toString100(int x){		String str = "";		//转换百位数的地方		if(x >= 100){			str+=digits[x/100-1]+" Hundred ";			x%=100;		}		//转换十位数的地方		if(x >= 11 && x <= 19){			return str+teens[x-11]+" ";		}else if(x == 10 || x >= 20){			str+=tens[x/10-1]+" ";			x%=10;		}		//转换个位数的地方		if(x >= 1 && x<=9){			str+=digits[x-1]+" ";				}		return str;	}		}

 

面试题17.8：给定一个整数数组（有正数有负数），找出总和最大的连续数列，并返回总和。（剑指Offer原题）

package jianzhiOffer;public class FindGreatestSumOfSubArray {		//连续子数组的最大和	public static void main(String[] args) {		// TODO 自动生成的方法存根//		int[] Arr = {-1,-2,-3,-10,-4,-7,-2,-5};		int[] Arr = {6,-3,-2,7,-15,1,2,2};		System.out.println(findGreatestSumOfSubArray(Arr));	}		public static boolean InvalidInput = false;		public static int findGreatestSumOfSubArray(int[] nums){		if(nums == null || nums.length<=0){			InvalidInput = true;			return 0;		}		InvalidInput = true;		int curSum = 0;		int curGreatestSum = Integer.MIN_VALUE;//数组内可能全部都是负数		for(int i=0;i
     
       curGreatestSum)//数组内可能全部都是负数				curGreatestSum = curSum;		}		return curGreatestSum;	}}
     

 

面试题17.9：设计一个方法，找出任意指定单词在一本书中的出现频率。

package cc150.middle;import java.util.Hashtable;public class Frequency {	public static void main(String[] args) {		// TODO 自动生成的方法存根			}		public int getFrequency(String[] article, int n, String word) {        // write code here		return wordFrequency(setupDictionary(article),word);    }		public Hashtable
     
       setupDictionary(String[] book){		Hashtable
      
        table = new Hashtable
       
        ();		for(String word:book){			word = word.toLowerCase();			if(word.trim() != ""){		//去掉空格之后，不等于空				if(!table.containsKey(word))					table.put(word, 0);				table.put(word, table.get(word)+1);			}		}		return table;	}		public int wordFrequency(Hashtable
        
          table, String word){		if(table == null || word == null)			return -1;		word = word.toLowerCase();		if(table.containsKey(word))			return table.get(word);		return 0;	}}
        
       
      
     

 

面试题17.12：设计一个算法，找出数组中两数之和为指定值的所有整数对。

package cc150.middle;import java.util.Arrays;public class FindPair {	public static void main(String[] args) {		//有重复的情况		// TODO 自动生成的方法存根		int[] a = {11,7,7,6,14,2,14,15,2,1,2,12,13,9,8,15,13,8,10,11,14,10,2,9,4,9,3,7,6,10,15,4,7,6,15,3,9,13,5,2,6,10,10,1,12,4,3,3,8,8,1,4,7,11,13,5,13,15,4,3,1,11,6,11,9,9,11,15,12,10,13,3,11,4,8,9,7,3,13,9,11,3,2,11,10,1,4,2,3,3,14,11,5,10,1,14,8,1,11,3,1,9,14,6,1,7,15,10,14,6,4,12,11};		FindPair fp = new FindPair();		System.out.println(fp.countPairs(a,113,16));	}		public int countPairs(int[] A, int n, int sum) {        // write code here		Arrays.sort(A);		for(int i=0;i
     
      sum)					end--;				else					first++;			}		}		return count;    }}
     

 

面试题17.13：有个简单的类似结点的数据结构BiNode，包含两个指向其他结点的指针。数据结构BiNode可用来表示二叉树（其中node1为左子节点，node2为右子节点）或双向链表（其中node1为前趋结点，node2为后继结点）。编写一个方法，将二叉查找树（用BiNode实现）转换为双向链表。要求所有数值的排序不变，转换操作不得引入其他数据结构（即直接操作原先的数据结构）。

package cc150.middle;public class Converter {	public static void main(String[] args) {		//二叉查找树转换成双向链表		// TODO 自动生成的方法存根		Converter cv = new Converter();		TreeNode t4 = cv.new TreeNode(4);		TreeNode t2 = cv.new TreeNode(2);		TreeNode t5 = cv.new TreeNode(5);		TreeNode t1 = cv.new TreeNode(1);		TreeNode t3 = cv.new TreeNode(3);		TreeNode t6 = cv.new TreeNode(6);		TreeNode t0 = cv.new TreeNode(0);		t4.left = t2;		t4.right = t5;		t2.left = t1;		t2.right = t3;		t5.right = t6;		t1.left = t0;		cv.treeToList(t4);		while(cv.head.next != null){			System.out.println(cv.head.val);			cv.head = cv.head.next;		}				}		private ListNode head  = new ListNode(-1);	private ListNode q  = head;		public ListNode treeToList(TreeNode root) {		//使用中序遍历        // write code here		if(root != null){			treeToList(root.left);			q.next = new ListNode(root.val);			q = q.next;			treeToList(root.right);		}		return head.next;		    }		public class ListNode {	    int val;	    ListNode next = null;	    ListNode(int val) {	        this.val = val;	    }	}		public class TreeNode {	    int val = 0;	    TreeNode left = null;	    TreeNode right = null;	    public TreeNode(int val) {	        this.val = val;	    }	}		}