1 面试题 2 ：实现单例模式 2 3 1. 饿汉式单例类 4 public class SingletonClass { 5 private static final SingletonClass instance=new SingletonClass(); 6 //私有构造函数 7 private SingletonClass() {} 8 public static SingletonClass getInstance() { 9 return instance; 10 } 11 } 12 2. 懒汉式单例模式 13 public class SingletonClass { 14 private static SingletonClass instance=null; 15 //私有构造函数 16 private SingletonClass() {} 17 public synchronized static SingletonClass getInstance() { 18 if(instance==null) { 19 instance=new SingletonClass(); 20 } 21 return instance; 22 } 23 } 24 题 面试题 3 ：二维数组中的查找 25 题目描述：一个二维数组，每一行从左到右递增，每一列从上到下递增．输 26 入一个二维数组和一个整数，判断数组中是否含有整数。 27 public class Find { 28 public static boolean find(int[][] array,int number) { 29 if(array==null) { 30 return false; 31 } 32 int column=array[0].length-1; 33 int row=0; 34 while (row =0) { 35 if(array[row][column]==number) { 36 return true; 37 } 38 if(array[row][column]>number) { 39 column--; 40 } else { 41 row++; 42 } 43 } 44 return false; 45 } 46 public static void main(String args[]) { 47 int[][] testarray=new int[4][4]; 48 testarray[0][0]=1; 49 testarray[0][1]=2; 50 testarray[0][2]=8; 51 testarray[0][3]=9; 52 testarray[1][0]=2; 53 testarray[1][1]=4; 54 testarray[1][2]=9; 55 testarray[1][3]=12; 56 testarray[2][0]=4; 57 testarray[2][1]=7; 58 testarray[2][2]=10; 59 testarray[2][3]=13; 60 testarray[3][0]=6; 61 testarray[3][1]=8; 62 testarray[3][2]=11; 63 testarray[3][3]=15; 64 System.out.println(find(testarray, 1)); 65 } 66 } 67 题 面试题 4 ：替换空格 68 题目：请实现一个函数，把字符串中的每个空格替换成“%20”。 69 public class ReplaceBlank { 70 public static void main(String args[]) { 71 String s="We are happy."; 72 System.out.println(replaceBlank(s)); 73 } 74 public String replaceBlank(String input) { 75 if(input==null) 76 return null; 77 StringBuffer outputBuffer=new StringBuffer(); 78 for(int i=0; i stack=new Stack (); 108 while(headNode!=null) { 109 stack.push(headNode); 110 headNode=headNode.next; 111 } 112 while(!stack.isEmpty()) { 113 System.out.println(stack.pop().data); 114 } 115 } 116 } 117 方法二: : 118 递归方式实现 119 public class PrintListReverse { 120 public static void main (String args[]) { 121 ListNode node1=new ListNode(); 122 ListNode node2=new ListNode(); 123 ListNode node3=new ListNode(); 124 node1.data=1; 125 node2.data=2; 126 node3.data=3; 127 node1.next=node2; 128 node2.next=node3; 129 printListReversversingly test=new printListReversversingly(); 130 test.printListReverse(node1); 131 } 132 public static void printListReverse(ListNode headNode) { 133 if(headNode!=null) { 134 if(headNode.next!=null) { 135 printListReverse(headNode.next); 136 } 137 } 138 System.out.println(headNode.data); 139 } 140 } 141 题 面试题 6 ：重建二叉树 142 题目描述：输入二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设前 143 序遍历和中序遍历结果中都不包含重复的数字，例如输入的前序遍历序列 144 {1,2,4,7,3,5,6,8}和中序遍历序列 {4,7,2,1,5,3,8,6}重建出如图所示的二叉 145 树。 146 public class BinaryTreeNode { 147 public static int value; 148 public BinaryTreeNode leftNode; 149 public BinaryTreeNode rightNode; 150 } 151 import java.util.Arrays; 152 public class Problem6 { 153 public static void main(String[] args) throws Exception { 154 int[] preSort={1,2,4,7,3,5,6,8}; 155 int[] inSort={4,7,2,1,5,3,8,6}; 156 BinaryTreeNode root=constructCore(preSort,inSort); 157 } 158 public static BinaryTreeNode constructCore(int[] 159 preorder,int[] inorder) throws Exception { 160 if(preorder==null||inorder==null) { 161 return null; 162 } 163 if(preorder.length!=inorder.length) { 164 throw new Exception("长度不一样，非法的输入"); 165 } 166 BinaryTreeNode root=new BinaryTreeNode(); 167 for(int i=0; i { 185 private Stack stack1=new Stack (); 186 private Stack stack2=new Stack (); 187 public void appendTail(T t) { 188 stack1.push(t); 189 } 190 public T deleteHead() throws Exception { 191 if(stack2.isEmpty()) { 192 while(!stack1.isEmpty()) { 193 stack2.push(stack1.pop()); 194 } 195 } 196 if(stack2.isEmpty()) { 197 throw new Exception("队列为空，不能删除"); 198 } 199 return stack2.pop(); 200 } 201 public static void main(String args[]) throws Exception { 202 Problem7 p7=new Problem7<>(); 203 p7.appendTail("1"); 204 p7.appendTail("2"); 205 p7.appendTail("3"); 206 p7.deleteHead(); 207 } 208 } 209 题 面试题 8 ：旋转数组的最小数字 210 题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的 211 旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数 212 组 {3,4,5,1,2}为 {1,2,3,4,5}的一个旋转，该数组的最小值为 1. 213 public class Problem8 { 214 public static void main(String[] args) { 215 Problem8 p8=new Problem8(); 216 //int[] array={1,1,1,2,0}; 217 // int[] array={3,4,5,1,2}; 218 int[] array= {1,0,1,1,1}; 219 System.out.println(p8.findMinNum(array)); 220 } 221 public Integer findMinNum(int[] array) { 222 if(array==null) { 223 return null; 224 } 225 int leftIndex=0; 226 int rightIndex=array.length-1; 227 int mid=0; 228 while(array[leftIndex]>=array[rightIndex]) { 229 if(rightIndex-leftIndex<=1) { 230 mid=rightIndex; 231 break; 232 } 233 mid=(leftIndex+rightIndex)/2; 234 if(array[leftIndex]==array[rightIndex]&&array[leftIndex]==a 235 rray[mid]) { 236 if(array[leftIndex+1]!=array[rightIndex-1]) { 237 mid=array[leftIndex+1] =array[leftIndex]) 246 leftIndex=mid; 247 else { 248 if(array[mid]<=array[rightIndex]) 249 rightIndex=mid; 250 } 251 } 252 } 253 return array[mid]; 254 } 255 } 256 题 面试题 9 ：斐波那契数列 257 题目一：写一个函数，输入 n，求斐波那契数列的第 n 项。 258 public class Fibonacci { 259 public long fibonacci(int n) { 260 long result=0; 261 long preOne=0; 262 long preTwo=1; 263 if(n==0) { 264 return preOne; 265 } 266 if(n==1) { 267 return preTwo; 268 } 269 for(int i=2; i<=n; i++) { 270 result=preOne+preTwo; 271 preOne=preTwo; 272 preTwo=result; 273 } 274 return result; 275 } 276 } 277 题 面试题 10 ：二进制中 1 的个数 278 题目：请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如 279 把 9 表示成二进制是 1001；有 2 位是 1，因此如果输入 9，函数输出 2. 280 public class Problem10 { 281 public static void main(String args[]) { 282 Problem10 test=new Problem10(); 283 System.out.println(test.numberOf1(3)); 284 } 285 public int numberOf1(int n) { 286 int count=0; 287 while(n!=0) { 288 count++; 289 n=(n-1) & n; 290 } 291 return count; 292 } 293 } 294 题 面试题 11 ：数值的整数次方 295 题目：实现函数 double Power （double base，int exponent），求 base 的 exponent 296 次方。不得使用库函数，同时不需要考虑大数问题。import 297 java.rmi.server.ExportException; 298 public class Problem11 { 299 public static void main(String[] args) throws Exception { 300 Problem11 p11=new Problem11(); 301 System.out.println(p11.power(2.0, 3)); 302 } 303 public double power(double base,int exponent) throws Exception { 304 double result=0.0; 305 if(equal(base,0.0)&&exponent<0) { 306 throw new Exception("0的负数次幂没有意义"); 307 } 308 if(exponent<0) { 309 result=1.0/powerWithExpoment(base,-exponent); 310 } else{ 311 result=powerWithExpoment(base, exponent); 312 } 313 return result; 314 } 315 private double powerWithExpoment(double base, int exponent) { 316 if(exponent==0) { 317 return 1; 318 } 319 if(exponent==1) { 320 return base; 321 } 322 double result=1.0; 323 for(int i=1; i<=exponent; i++) { 324 result=result*base; 325 } 326 return result; 327 } 328 private boolean equal(double num1, double num2) { 329 if((num1-num2>-0.0000001)&&num1-num2<0.0000001) { 330 return true; 331 } else { 332 return false; 333 } 334 } 335 } 336 题 面试题 12 ：打印 1 到最大的 n 位数 337 题目：输入数字 n，按顺序打印出从 1 到最大的 n 位进制数。比如输入 3，则打 338 印出 1、2、3 一直到 999. 339 public class Problem12 { 340 public static void main(String[] args) { 341 Problem12 p12=new Problem12(); 342 p12.printToMaxOfNDigits(2); 343 } 344 public void printToMaxOfNDigits(int n) { 345 int[] array=new int[n]; 346 if(n<=0) 347 return; 348 printArray(array,0); 349 } 350 private void printArray(int[] array,int n) { 351 for(int i=0; i<10; i++) { 352 if(n!=array.length) { 353 array[n]=i; 354 printArray(array, n+1); 355 } else { 356 boolean isFirstNo0=false; 357 for(int j=0; j stack=new Stack (); 673 while(root!=null||!stack.isEmpty()) { 674 while(root!=null) { 675 BinaryTreeNode temp=root.leftNode; 676 root.leftNode=root.rightNode; 677 root.rightNode=temp; 678 stack.push(root); 679 root=root.leftNode; 680 } 681 root=stack.pop(); 682 root=root.rightNode; 683 } 684 return root; 685 } 686 } 687 题 面试题 20 ：顺时针打印矩阵 688 题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 689 public class Problem20 { 690 public static void main(String[] args) { 691 int[][] array= { 692 {1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16} 693 }; 694 Problem20 testCircle=new Problem20(); 695 testCircle.printMatixClockwisely(array); 696 } 697 public void printMatixClockwisely(int[][] array) { 698 if(array==null) 699 return; 700 int start=0; 701 while(array[0].length>start*2&&array.length>start*2) { 702 printOneCircle(array,start); 703 start++; 704 } 705 } 706 private void printOneCircle(int[][] array, int start) { 707 for(int i=start; i start) { 711 for(int i=start+1; i start && 716 array.length-start-1>start) { 717 for(int i=array.length-start-1; i>start; i--) { 718 System.out.print(array[array.length-start-1][i]+" "); 719 } 720 } 721 if(array.length-1-start>start && 722 array[0].length-1-start>start) { 723 for(int i=array.length-start-1; i>start; i--) { 724 System.out.print(array[i][start]+" "); 725 } 726 } 727 } 728 } 729 题 面试题 21 ：包含 min 函数的栈 730 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min 731 函数。在该栈中，调用min、push及pop德尔时间复杂度都是O(1) 732 public class Problem21 extends MyStack { 733 public static void main(String[] args) { 734 Problem21 test=new Problem21(); 735 test.push(3); 736 test.push(2); 737 test.push(1); 738 test.push(4); 739 test.push(5); 740 System.out.println(test.min()); 741 } 742 private MyStack minStack=new MyStack (); 743 private MyStack dataStack=new MyStack (); 744 public void push(Integer item) { 745 dataStack.push(item); 746 if(minStack.length==0||item<=minStack.head.data) { 747 minStack.push(item); 748 } else { 749 minStack.push(minStack.head.data); 750 } 751 } 752 public Integer pop() { 753 if(dataStack.length==0||minStack.length==0) { 754 return null; 755 } 756 minStack.pop(); 757 return dataStack.pop(); 758 } 759 public Integer min() { 760 if(minStack.length==0) 761 return null; 762 return minStack.head.data; 763 } 764 } 765 题 面试题 22 ：栈的压入、弹出序列 766 题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是 767 否为该栈的弹出序列。假设压入栈的所有数字均不相等。例如压栈序列为 1、2、 768 3、4、5.序列 4、5、3、2、1 是压栈序列对应的一个弹出序列，但 4、3、5、1、 769 2 却不是。 770 public class Problem22 { 771 public static void main(String[] args) { 772 int[] array1= {1,2,3,4,5}; 773 int[] array2= {4,3,5,2,1}; 774 Problem22 test=new Problem22(); 775 System.out.println(test.isPopOrder(array1, array2)); 776 } 777 public boolean isPopOrder(int[] line1,int[] line2) { 778 if(line1==null||line2==null) { 779 return false; 780 } 781 int point1=0; 782 Stack stack=new Stack (); 783 for(int i=0; i queue=new 837 LinkedList (); 838 queue.add(root); 839 while(!queue.isEmpty()) { 840 BinaryTreeNode node=queue.poll(); 841 System.out.print(node.value); 842 if(node.leftNode!=null) { 843 queue.add(node.leftNode); 844 } 845 if(node.rightNode!=null) { 846 queue.add(node.rightNode); 847 } 848 } 849 } 850 } 851 题 面试题 24 ：二叉搜索树的后序遍历序列 852 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。 853 是则返回true，否则返回false。 854 public class Problem24 { 855 public static void main(String[] args) { 856 int[] array= {5,7,6,9,11,10,8}; 857 //int[] array={7,4,6,5}; 858 //int[] array={6,7,8,5}; 859 Problem24 p24=new Problem24(); 860 System.out.println(p24.verfiySequenceOfBST(array)); 861 } 862 public boolean verfiySequenceOfBST(int[] sequence) { 863 if(sequence==null||sequence.length==0) 864 return false; 865 int length=sequence.length; 866 int root=sequence[length-1]; 867 int cut=0; 868 for(int i=0; i root) 870 cut=i+1; 871 break; 872 } 873 if(cut==0) { 874 verfiySequenceOfBST(Arrays.copyOfRange(sequence, 0, 875 length-1)); 876 } else { 877 for(int j=cut; j 0) 884 left= verfiySequenceOfBST(Arrays.copyOfRange(sequence, 885 0, cut)); 886 boolean right=true; 887 if(cut stack=new Stack (); 920 int currentSum=0; 921 findPath(root,sum,stack,currentSum); 922 } 923 } 924 private void findPath(BinaryTreeNode root, int sum, Stack 925 stack,int currentSum) { 926 currentSum+=root.value; 927 stack.push(root.value); 928 if(root.leftNode==null&&root.rightNode==null) { 929 if(currentSum==sum) { 930 System.out.println(" 找到一个路径 "); 931 for(int path:st ack) { 932 System.out.print(path+" "); 933 } 934 } 935 System.out.println(); 936 } 937 } 938 } 939 } 940 if(root.leftNode!=null) { 941 findPath(root.leftNode, sum, stack, currentSum); 942 } 943 } 944 if(root.rightNode!=null) { 945 findPath(root.rightNode, sum, stack, currentSum); 946 } 947 } 948 stack. pop(); 949 } 950 } 951 } 952 } 953 题 面试题 26 ：复杂链表的复制 954 题目：实现函数复制一个复杂链表。在复杂链表中，每个结点除了有一个 next 955 指针指向下一个结点外，还有一个指向链表中任意结点或 null。 956 package com.example.offer26_40; 957 public class Problem26 { 958 public static void main(String[] args) { 959 Problem26 testClone=new Problem26(); 960 ComplexListNode root=new ComplexListNode(); 961 ComplexListNode node1=new ComplexListNode(); 962 ComplexListNode node2=new ComplexListNode(); 963 ComplexListNode node3=new ComplexListNode(); 964 ComplexListNode node4=new ComplexListNode(); 965 root.data=1; 966 node1.next=node2; 967 node2.next=node3; 968 node3.next=node4; 969 root.data=1; 970 node1.data=2; 971 node2.data=3; 972 node3.data=4; 973 node4.data=5; 974 root.sibling=node1; 975 node1.sibling=root; 976 node3.sibling=node1 ; 977 ComplexListNode result=testClone.clone(root); 978 System.out.println(result.data); 979 } 980 public ComplexListNode clone(ComplexListNode head) { 981 cloneNodes(head); 982 connectSiblingNodes(head); 983 return reconnectNodes(head); 984 } 985 public void cloneNodes(ComplexListNode head) { 986 ComplexListNode node=head; 987 while(node!=null) { 988 ComplexListNode cloneNode=new ComplexListNode(); 989 cloneNode.data=node.data; 990 cloneNode.next=node.next; 991 cloneNode.sibling=null; 992 node.next=cloneNode; 993 node=cloneNode.next; 994 } 995 } 996 public void connectSiblingNodes(ComplexListNode head) { 997 ComplexListNode node=head; 998 while(node!=null) { 999 ComplexListNode clonedNode=node.next;1000 if(node.sibling!=null) {1001 clonedNode.sibling=node.sibling.next;1002 }1003 node=clonedNode.next;1004 }1005 }1006 public ComplexListNode reconnectNodes(ComplexListNode head) {1007 ComplexListNode node=head;1008 ComplexListNode clonedHead=null;1009 ComplexListNode clonedNode=null;1010 if(node!=null) {1011 clonedNode=node.next;1012 clonedHead=clonedNode;1013 node.next=clonedNode.next;1014 node=node.next;1015 }1016 while(node!=null) {1017 clonedNode.next=node.next;1018 clonedNode=clonedHead.next;1019 node.next=clonedNode.next;1020 node=node.next;1021 }1022 return clonedHead;1023 }1024 }1025 class ComplexListNode {1026 int data;1027 ComplexListNode next;1028 ComplexListNode sibling;1029 }1030 题 面试题 27 ：二叉搜索树与双向链表1031 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求1032 不能创建任何新的结点，只能调整树中结点指针的指向。1033 public class Problem27 {1034 public BinaryTreeNode convert(BinaryTreeNode root) {1035 BinaryTreeNode lastNodeList=null;1036 convertNode(root,lastNodeList);1037 while(lastNodeList!=null&&lastNodeList.leftNode!=null) {1038 lastNodeList=lastNodeList.leftNode;1039 }1040 return lastNodeList;1041 }1042 private void convertNode(BinaryTreeNode root, BinaryTreeNode1043 lastNodeList) {1044 if(root==null)1045 return;1046 BinaryTreeNode cuurent=root;1047 if(cuurent.leftNode!=null) {1048 convertNode(cuurent.leftNode, lastNodeList);1049 }1050 cuurent.leftNode=lastNodeList;1051 if(lastNodeList!=null)1052 lastNodeList.rightNode=cuurent;1053 lastNodeList=cuurent;1054 if(cuurent.rightNode!=null) {1055 convertNode(cuurent.rightNode, lastNodeList);1056 }1057 }1058 }1059 题 面试题 28 ：字符串的排列1060 题目：输入一个字符串，打印出该字符串中字符的所有排列。1061 public class Problem28 {1062 public static void main(String args[]) {1063 Problem28 testPermutation=new Problem28();1064 testPermutation.permutation("abcd");1065 }1066 public void permutation(String str) {1067 int count=0;1068 if(str==null)1069 return;1070 char[] chs=str.toCharArray();1071 int point=0;1072 System.out.print(chs);1073 System.out.print(" ");1074 count++;1075 char temp1=chs[point];1076 chs[point]=chs[++point];1077 chs[point]=temp1;1078 while(!String.valueOf(chs).equals(str)) {1079 System.out.print(chs);1080 System.out.print(" ");1081 count++;1082 if(point==chs.length-1) {1083 char temp=chs[point];1084 chs[point]=chs[0];1085 chs[0]=temp;1086 point=0;1087 } else {1088 char temp=chs[point];1089 chs[point]=chs[++point];1090 chs[point]=temp;1091 }1092 }1093 System.out.println(count);1094 }1095 }1096 题 面试题 29 ：数组中出现次数超过一半的数组1097 题目：数组中有一个数字出现次数超过数组长度的一半，请找出这个数字。例如1098 输入一个长度为9的数组 {1,2,3,2,2,2,5,4,2}。2出现的次数超过数组长度的1099 一半，因此输出2.1100 public class Problem29 {1101 public static void main(String[] args) {1102 int[] array= {1,2,3,2,2,2,5,4,2};1103 Problem29 p=new Problem29();1104 System.out.println(p.moreThanHalfNum(array));1105 }1106 public Integer moreThanHalfNum(int[] array) {1107 if(array==null)1108 return null;1109 int count=0;1110 Integer resultInteger=null;1111 for(int i=0; i array.length)1148 return;1149 int[] kArray=Arrays.copyOfRange(array, 0, k);1150 buildMaxHeap(kArray);1151 for(int i=k; i kArray[i])1165 largest=left;1166 else1167 largest=i;1168 if(right kArray[largest])1169 largest=right;1170 if(largest!=i) {1171 int temp=kArray[i];1172 kArray[i]=kArray[largest];1173 kArray[largest]=temp;1174 maxHeap(kArray, largest);1175 }1176 }1177 private void buildMaxHeap(int[] kArray) {1178 for(int i=kArray.length/2; i>=0; i--)1179 maxHeap(kArray, i);1180 }1181 }1182 题 面试题 31 ：连续子数组的最大和1183 题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整1184 数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。例1185 如输入的数组为 {1，-2,3,10，-4,7,2，-5}，和最大的子数组为 {3,10，-4,7,2}。1186 public class Problem31 {1187 public static void main(String[] args) {1188 Problem31 p=new Problem31();1189 int[] array= {1,-2,3,10,-4,7,2,-5};1190 System.out.println(p.findGreatestSubArray(array));1191 }1192 public int findGreatestSubArray(int[] array) {1193 if(array==null)1194 return 0;1195 int currentSum=0;1196 int greatestSum=0;1197 for(int i=0; i greatestSum)1204 greatestSum=currentSum;1205 }1206 return greatestSum;1207 }1208 }1209 题 面试题 32 ：从 1 到 到 n 整数中 1 出现的次数1210 题目：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次1211 数。例如输入 12，这些整数中包含 1 的数字有 1,10,11,12，1 一共出现了 5 次。1212 解题思路：解法二告诉我们 1~ N 中"1"的个数跟最高位有关，那我们换个角1213 度思考，给定一个 N，我们分析 1~N 中的数在每一位上出现 1 的次数的和，看看1214 每一位上"1"出现的个数的和由什么决定。1215 1 位数的情况：在解法二中已经分析过，大于等于 1 的时候，有 1 个，小于 1 就1216 没有。1217 2 位数的情况：N=13,个位数出现的 1 的次数为 2，分别为 1 和 11，十位数出现 11218 的次数为 4，分别为 10,11,12,13，所以 f(N) = 2+4。N=23,个位数出现的 1 的1219 次数为3，分别为1，11，21，十位数出现1的次数为10，分别为10~19，f(N)=3+10。1220 由此我们发现，个位数出现 1 的次数不仅和个位数有关，和十位数也有关，如果1221 个位数大于等于 1，则个位数出现 1 的次数为十位数的数字加 1；如果个位数为1222 0，个位数出现 1 的次数等于十位数数字。而十位数上出现 1 的次数也不仅和十1223 位数相关，也和个位数相关：如果十位数字等于 1，则十位数上出现 1 的次数为1224 个位数的数字加 1，假如十位数大于 1，则十位数上出现 1 的次数为 10。1225 3 位数的情况：1226 N=123，个位出现 1 的个数为 13:1,11,21，…，91,101,111,121。十位出现 1 的1227 个数为 20:10~19,110~119。百位出现 1 的个数为 24:100~123。1228 我们可以继续分析 4 位数，5 位数，推导出下面一般情况： 假设 N，我们要计算1229 百位上出现 1 的次数，将由三部分决定：百位上的数字，百位以上的数字，百位1230 一下的数字。1231 如果百位上的数字为 0，则百位上出现 1 的次数仅由更高位决定，比如 12013，1232 百位出现 1 的情况为 100~199,1100~1199,2100~2199，…，11100~11199，共 12001233 个。等于更高位数字乘以当前位数，即 12 * 100。1234 如果百位上的数字大于 1，则百位上出现 1 的次数仅由更高位决定，比如 12213，1235 百位出现 1 的情况为 100~199,1100~1199,2100~2199，…，11100~11199，1236 12100~12199 共 1300 个。等于更高位数字加 1 乘以当前位数，即（12 + 1）*100。1237 如果百位上的数字为 1，则百位上出现 1 的次数不仅受更高位影响，还受低位影1238 响。例如 12113，受高位影响出现 1 的情况：100~199,1100~1199,2100~2199，…，1239 11100~11199，共 1200 个，但它还受低位影响，出现 1 的情况是 12100~12113，1240 共 114 个，等于低位数字 113+1。1241 public class Problem32 {1242 public static void main(String[] args) {1243 Problem32 p=new Problem32();1244 System.out.println(p.countOne(123));1245 }1246 public long countOne(long n) {1247 long count = 0;1248 long i = 1;1249 long current = 0,after = 0,before = 0;1250 while((n / i) != 0) {1251 current = (n / i) % 10; //当前位数字1252 before = n / (i * 10); //高位数字1253 after = n - (n / i) * i; //低位数字1254 if (current > 1)1255 count = count + (before + 1) * i;1256 else if (current == 0)1257 count = count + before * i;1258 else if(current == 1)1259 count = count + before * i + after + 1;1260 i = i * 10;1261 }1262 return count;1263 }1264 }1265 题 面试题 33 ：把数组排成最小的数1266 题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼1267 接出的所有数字的最小的一个。例如输入 {3,32,321}，则打印最小的数字是1268 321323.1269 public class Problem33 {1270 public static void main(String[] args) {1271 Problem33 test=new Problem33();1272 int[] array= {3,32,321};1273 test.printMin(array);1274 }1275 public void printMin(int[] array) {1276 int[] clone=array.clone();1277 printMinNumber(clone,0,clone.length-1);1278 for(int i:clone)1279 System.out.print(i);1280 }1281 private void printMinNumber(int[] array, int start, int end) {1282 if(start right.charAt(i))1308 return false;1309 }1310 return result;1311 }1312 }1313 题 面试题 34 ：丑数1314 题目：我们把只包含因子 2,3,和 5 的称为丑数。求按从小到大的顺序的第 15001315 个丑数。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7.习惯上我们把 11316 当做第一个丑数。1317 public class Problem34 {1318 public static void main(String[] args) {1319 Problem34 p=new Problem34();1320 System.out.println(p.getUglyNumber(1500));1321 }1322 public int getUglyNumber(int n) {1323 if(n<0)1324 return 0;1325 int[] uglyArray=new int[n];1326 uglyArray[0]=1;1327 int multiply2=1;1328 int multiply3=1;1329 int multiply5=1;1330 for(int i=1; i hash=new1360 LinkedHashMap ();1361 for(char item:strChar) {1362 if(hash.containsKey(item))1363 hash.put(item, hash.get(item)+1);1364 else1365 hash.put(item, 1);1366 }1367 for(char key:hash.keySet()) {1368 if(hash.get(key)==1)1369 return key;1370 }1371 return null;1372 }1373 }1374 题 面试题 36 ：数组中的逆序对1375 题目：在数组中的两个数字如果前一个数字大于后一个数字，则这两个数字组成1376 一个逆序对。输入一个数组，求出这个数组的逆序对的总数。例如在数组 {7,5,6,4}1377 中，一共存在 5 个逆序对，分别是（7,6）、（7、5），（7、4），（6、4），1378 （5、4）。1379 public class Problem36 {1380 public static void main(String[] args) {1381 Problem36 p=new Problem36();1382 int[] array= {7,5,6,4};1383 System.out.println(p.inversePairs(array));1384 }1385 public int inversePairs(int[] array) {1386 if(array==null)1387 return 0;1388 int[] copy=array.clone();1389 return mergeSort(array,copy,0,array.length-1);1390 }1391 private int mergeSort(int[] array, int[] result, int start, int1392 end) {1393 if(start==end) {1394 result[start]=array[start];1395 return 0;1396 }1397 int length=(end-start)/2;1398 int left=mergeSort(result, array, start, start+length);1399 int right=mergeSort(result, array, start+length+1, end);1400 int leftIndex=start+length;1401 int rightIndex=end;1402 int count=0;1403 int point=rightIndex;1404 while(leftIndex>=start&&rightIndex>=start+length+1) {1405 if(array[leftIndex]>array[rightIndex]) {1406 result[point--]=array[leftIndex--];1407 count+=rightIndex-start-length;1408 } else {1409 result[point--]=array[rightIndex--];1410 }1411 }1412 for(int i=leftIndex; i>=start; i--)1413 result[point--]=array[i];1414 for(int j=rightIndex; j>=start+length+1; j--)1415 result[point--]=array[j];1416 return left+right+count;1417 }1418 }1419 题 面试题 37 ：两个链表的第一个公共结点1420 题目：输入两个链表，找出它们的第一个公共结点。1421 import com.utils.ListNode;1422 public class Problem37 {1423 public static void main(String[] args) {1424 ListNode head1=new ListNode();1425 ListNode second1=new ListNode();1426 ListNode third1=new ListNode();1427 ListNode forth1=new ListNode();1428 ListNode fifth1=new ListNode();1429 ListNode head2=new ListNode();1430 ListNode second2=new ListNode();1431 ListNode third2=new ListNode();1432 ListNode forth2=new ListNode();1433 head1.nextNode=second1;1434 second1.nextNode=third1;1435 third1.nextNode=forth1;1436 forth1.nextNode=fifth1;1437 head2.nextNode=second2;1438 second2.nextNode=forth1;1439 third2.nextNode=fifth1;1440 head1.data=1;1441 second1.data=2;1442 third1.data=3;1443 forth1.data=6;1444 fifth1.data=7;1445 head2.data=4;1446 second2.data=5;1447 third2.data=6;1448 forth2.data=7;1449 Problem37 test=new Problem37();1450 System.out.println(test.findFirstCommonNode(head1,1451 head2).data);1452 }1453 public ListNode findFirstCommonNode(ListNode head1,ListNode1454 head2) {1455 int len1=getListLength(head1);1456 int len2=getListLength(head2);1457 ListNode longListNode=null;1458 ListNode shortListNode=null;1459 int dif=0;1460 if(len1>len2) {1461 longListNode=head1;1462 shortListNode=head2;1463 dif=len1-len2;1464 } else {1465 longListNode=head2;1466 shortListNode=head1;1467 dif=len2-len1;1468 }1469 for(int i=0; i -1&&last>-1)1507 number=last-first+1;1508 }1509 return number;1510 }1511 private int getFirstK(int[] array, int k,int start, int end) {1512 if(start>end)1513 return -1;1514 int middleIndex=(start+end)/2;1515 int middleData=array[middleIndex];1516 if(middleData==k) {1517 if((middleIndex>0&&array[middleIndex-1]!=k)||middleIndex==0)1518 return middleIndex;1519 else1520 end=middleIndex-1;1521 } else if(middleData>k)1522 end=middleIndex-1;1523 else1524 start=middleIndex+1;1525 return getFirstK(array, k, start, end);1526 }1527 private int getLastK(int[] array,int k, int start, int end) {1528 if(start>end)1529 return -1;1530 int middleIndex=(start+end)/2;1531 int middleData=array[middleIndex];1532 if(middleData==k) {1533 if((middleIndex right)?left+1:right+1;1579 }1580 }1581 题目二：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树1582 中任意结点的左右子树的深度相差不超过1，那么他就是一棵平衡二叉树。1583 public boolean isBalanced(BinaryTreeNode root) {1584 int depth=0;1585 return isBalanced(root,depth);1586 }1587 private boolean isBalanced(BinaryTreeNode root, int depth) {1588 if(root==null) {1589 depth=0;1590 return true;1591 }1592 int left=0,right=0;1593 if(isBalanced(root.leftNode,left)&&isBalanced(root.rightNod1594 e, right)) {1595 int diff=left-right;1596 if(diff<=1&&diff>=-1) {1597 depth=1+(left>right?left:right);1598 return true;1599 }1600 }1601 return false;1602 }1603 测试用例跟题目 1 相同。1604 题 面试题 40 ：数组中只出现一次的数字。1605 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序1606 找出这两个只出现一次的数字。要求时间复杂度是 O（n），空间复杂度为 O（1）；1607 public class Problem40 {1608 public static void main(String[] args) {1609 int[] array= {2,4,3,6,3,2,5,5};1610 Problem40 p=new Problem40();1611 p.findNumsAppearOnce(array);1612 }1613 public void findNumsAppearOnce(int[] array) {1614 if(array==null)1615 return;1616 int number=0;1617 for(int i:array)1618 number^=i;1619 int index=findFirstBitIs1(number);1620 int number1=0;1621 int number2=0;1622 for(int i:array) {1623 if(isBit1(i,index))1624 number1^=i;1625 else1626 number2^=i;1627 }1628 System.out.println(number1);1629 System.out.println(number2);1630 }1631 private int findFirstBitIs1(int number) {1632 int indexBit=0;1633 while((number&1)==0) {1634 number=number>>1;1635 ++indexBit;1636 }1637 return indexBit;1638 }1639 private boolean isBit1(int number, int index) {1640 number=number>>index;1641 return (number&1)==0;1642 }1643 }1644 题 面试题 41 ：和为 s 的两个数字 VS 和为 s 的连续正数序列1645 题目一：输一个递增排序的数组和一个数字 s,在数组中查找两个数使得它们的1646 和正好是 s。如果有多对数字的和等于 s，输出任意一对即可。例如：输入数组1647 {1,2,4,7,11,15}和数字为 15.输出 4 和 11.1648 public class Problem41 {1649 public static void main(String[] args) {1650 Problem41 p=new Problem41();1651 int[] data= {1,2,4,7,11,15};1652 int sum=15;1653 System.out.println(p.findNumberWithSum(data, sum));1654 }1655 public boolean findNumberWithSum(int[] data,int sum) {1656 boolean found=false;1657 if(data==null)1658 return found;1659 int num1=0;1660 int num2=0;1661 int start=0;1662 int end=data.length-1;1663 while(start sum)1671 end--;1672 else1673 start++;1674 }1675 System.out.println(num1);1676 System.out.println(num2);1677 return found;1678 }1679 }1680 题目二：输入一个正数 s，打印出所有和为 s 的连续正数序列（至少含两个数）。1681 例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以结果打印出 3 个连续序列 1-5、1682 4-6、和 7-8.1683 public void findContinuesSequence(int sum) {1684 if(sum<3)1685 return;1686 int small=1;1687 int big=2;1688 int middle=(1+sum)/2;1689 int curSum=small+big;1690 while(small sum&&small =0; i--) {1726 sb.append(str[i]+" ");1727 }1728 System.out.println(sb);1729 }1730 }1731 题目二：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。1732 请定义一个函数实现字符串左旋转操作的功能。比如输入字符串“abcdefg”和1733 数字 2.该函数左旋转 2 位得到的结果“cdefgab".1734 public void leftRotateString(String sentence,int index){1735 if(sentence==null||index>sentence.length()||index<0){1736 return;1737 }1738 String[] splitString={sentence.substring(0,index),1739 sentence.substring(index,sentence.length())};1740 StringBuffer resultbBuffer=new StringBuffer();1741 for(String s:splitString){1742 resultbBuffer.append(reverse(s));1743 }1744 System.out.println(reverse(resultbBuffer.toString()));1745 }1746 public String reverse(String str) {1747 char[] array=str.toCharArray();1748 for(int i=0;i<(array.length+1)/2;i++)1749 {1750 char temp=array[i];1751 array[i]=array[array.length-1-i];1752 array[array.length-1-i]=temp;1753 }1754 return String.valueOf(array);1755 }1756 题 面试题 43 ：n 个骰子的点数1757 题目：把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 s。输入 n，打印1758 出 s 的所有可能的值出现的概率。1759 public class Problem43 {1760 public static void main(String[] args) {1761 Problem43 p=new Problem43();1762 p.printProbability(2);1763 }1764 public void printProbability(int number){1765 if(number<1)1766 return;1767 int gMaxValue=6;1768 int[][] probabilities=new int[2][];1769 probabilities[0]=new int[gMaxValue*number+1];1770 probabilities[1]=new int[gMaxValue*number+1];1771 int flag=0;1772 for(int i=1;i numberZero)?false:true;1824 }1825 }1826 题 面试题 45 ：圆圈中最后剩下的数字1827 题目：0,1，...,n-1 这 n 个数排成一个圆圈，从数字 0 开始每次从这个圆圈里1828 删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。1829 public class Problem45 {1830 public static void main(String[] args) {1831 Problem45 p=new Problem45();1832 System.out.println(p.lastRemaining(6, 3));1833 }1834 public int lastRemaining(int n,int m){1835 if(n<1||m<1)1836 return -1;1837 int last=0;1838 for(int i=2;i<=n;i++){1839 last=(last+m)%i;1840 }1841 return last;1842 }1843 }1844 题 面试题 46 ：求 1+2+...+n1845 题目：求 1+2+...+n,要求不能用除法、for、while、if、else、switch、case1846 等关键字及条件判断语句（A?B:C）。1847 题 面试题 47 ：不用加减乘除做加法1848 题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则1849 运算符号。1850 public class Problem47 {1851 public static void main(String[] args) {1852 Problem47 p=new Problem47();1853 System.out.println(p.add(8, 16));1854 }1855 public int add(int num1,int num2){1856 int sum,carray;1857 do{1858 sum=num1^num2;1859 carray=(num1&num2)<<1;1860 num1=sum;1861 num2=carray;1862 }while(num2!=0);1863 return num1;1864 }1865 }