面试题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<N;row++){
for(col = 1;col<N;col++){
if(board[row][col] != board[row][col-1])
break;
}
if(col == N && board[row][col-1] == 1)
return true;
}
//检查列
for(col = 0;col<N;col++){
for(row = 1;row<N;row++){
if(board[row][col] != board[row-1][col])
break;
}
if(row == N && board[row-1][col] == 1)
return true;
}
//检查对角线，从左上角开始
if(board[0][0] != 0){
for(row = 1;row<N;row++){
if(board[row][row] != board[row-1][row-1])
break;
}
if(row == N && board[row-1][row-1] == 1)
return true;
}
//检查对角线，左下角开始
if(board[N-1][0] != 0){
for(row = 1;row<N;row++){
if(board[N-row-1][row] != board[N-row][row-1])
break;
}
if(row == N && board[N-row][row-1] == 1)
return true;
}
return false;
}
}
面试题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<b,若b>>31为0 则a>b
a -= b&(b>>31); //若a<b a=a-(a-b),若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<nums.length;i++){
if(curSum < 0)//如果前n个相加小于0，那么最大的和只能从n+1个开始算
curSum = nums[i];
else
curSum += nums[i];
if(curSum > 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<String,Integer> setupDictionary(String[] book){
Hashtable<String,Integer> table = new Hashtable<String,Integer>();
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<String,Integer> 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<A.length;i++)
System.out.println(A[i]);
int first = 0;
int end = n-1;
int count=0;
int countLeft = 1;
int countRight = 1;
while(first<end){
int s = A[first]+A[end];
if(s == sum){ //如果相等
if(A[first] == A[end]){ //情况1，一串连续的，且这些相加等于sum
count += ((end-first)*(end-first+1)/2);
return count; //注意要在这里结束，否则会继续计数
}else{ //情况2，两串连续的，两个串中各取一个相加等于sum
while(A[first] == A[first+1]){
countLeft++;
first++;
}
while(A[end] == A[end-1]){
countRight++;
end--;
}
count += (countLeft*countRight);
}
first++;
end--;
countLeft=1; //注意开始计数是1
countRight=1;
}else{
if(s>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;
}
}
}