剑指面试题java版算法.docx
- 文档编号:18219440
- 上传时间:2023-08-14
- 格式:DOCX
- 页数:75
- 大小:42.74KB
剑指面试题java版算法.docx
《剑指面试题java版算法.docx》由会员分享,可在线阅读,更多相关《剑指面试题java版算法.docx(75页珍藏版)》请在冰点文库上搜索。
剑指面试题java版算法
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
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 79. if(input.charAt(i)==' ') { 80. outputBuffer.append("%"); 81. outputBuffer.append("2"); 82. outputBuffer.append("0"); 83. } else { 84. outputBuffer.append(String.valueOf(input.charAt(i))); 85. } 86. } 87. return new String(outputBuffer); 88. } 89.} 90.题 面试题 5 : 从尾到头打印链表 91.题目: 输入一个链表的头结点,从尾到头反过来打印出每个结点的值。 92.方法一: 非递归的方式 93.public class PrintListReverse { 94. public static void main (String args[]) { 95. ListNode node1=new ListNode(); 96. ListNode node2=new ListNode(); 97. ListNode node3=new ListNode(); 98. node1.data=1; 99. node2.data=2; 100. node3.data=3; 101. node1.next=node2; 102. node2.next=node3; 103. printListReversversingly test=new printListReversversingly(); 104. test.printListReverse(node1); 105. } 106. public static void printListReverse(ListNode headNode) { 107. 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 168. if(inorder[i]==preorder[0]) { 169. root.value=inorder[i]; 170. System.out.println(root.value); 171. root.leftNode=constructCore(Arrays.copyOfRange(preorder,1, 172. i+1), Arrays.copyOfRange(inorder, 0, i)); 173. root.rightNode=constructCore(Arrays.copyOfRange(preorder,i+ 174. 1, preorder.length),Arrays.copyOfRange(inorder, i+1, 175. inorder.length)); 176. } 177. } 178. return root; 179. } 180.} 181.题 面试题 7 : 用两个栈实现队列 182.题目描述: 用两个栈实现一个队列,实现对了的两个函数 appendTail 和 183.deleteHead,分别完成在队列尾插入结点和在队列头部删除结点的功能。 184.public class Problem7 185. private Stack 186. private 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 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] (leftIndex+1): (r 238. ightIndex-1); 239. break; 240. } else { 241. leftIndex++; 242. rightIndex--; 243. } 244. } else { 245. if(array[mid]>=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.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 剑指面 试题 java 算法