Problem2：实现Singleton模式
题目描述：设计一个类，我们只能生成该类的一个实例
1 package Problem2; 2 3 public class SingletonClass { 4 5 /* 6 * 题目描述：设计一个类，我们只能生成该类的一个实例 7 */ 8 //volatile:防止指令重排序 9 private static volatile SingletonClass instance; 10 11 private SingletonClass() { 12 } 13 14 public static SingletonClass getInstace() { 15 if (instance == null) { 16 synchronized (SingletonClass.class) { 17 if (instance == null) { 18 instance = new SingletonClass(); 19 } 20 } 21 } 22 23 return instance; 24 25 } 26 27 }
Problem3：二维数组中的查找
题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下的顺序排序。 完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否包含该整数;
1 package Problem3; 2 3 public class Find { 4 5 /* 6 * 题目描述：二维数组中的查找 7 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下的顺序排序。 8 * 完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否包含该整数 9 * 10 */ 11 public static boolean find(int arr[][],int keyNumber){ 12 //从二维数组的右上角开始选取与keyNumber比较的整数 13 //column的变化：arr[0].length-1-->0; 14 //row的变化：0-->arr.length; 15 int column=arr[0].length-1; 16 int row=0; 17 while(column>=0&&row<arr.length){ 18 if(arr[row][column]==keyNumber){ 19 return true; 20 } 21 else if(arr[row][column]>keyNumber){ 22 column--; 23 } 24 else { 25 row++; 26 } 27 } 28 return false; 29 30 } 31 //测试find函数 32 public static void main(String[] args) { 33 /* 34 * 1 2 8 9 35 * 2 4 9 12 36 * 4 7 10 13 37 * 6 8 11 15 38 */ 39 int array[][]=new int[4][4]; 40 array[0][0]=1; 41 array[0][1]=2; 42 array[0][2]=8; 43 array[0][3]=9; 44 array[1][0]=2; 45 array[1][1]=4; 46 array[1][2]=9; 47 array[1][3]=12; 48 array[2][0]=4; 49 array[2][1]=7; 50 array[2][2]=10; 51 array[2][3]=13; 52 array[3][0]=6; 53 array[3][1]=8; 54 array[3][2]=11; 55 array[3][3]=15; 56 System.out.println(find(array, 7)); 57 System.out.println(find(array, 5)); 58 } 59 60 }
同理，比较关键字也可以从二维数组的左下角开始选择，则column和row的增减方式调换一下，但是不能选择左上角和右下角的元素作为与查找元素比较的关键字，因为无论比较结果怎样，都无法进一步缩小查找的范围。
Problem4:替换空格
题目描述：请实现一个函数，将字符串的每个空格替换为"%20"。例如输入"We are happy",则输出"We%20are%20happy."。
1 package Problem4; 2 3 public class ReplaceBank { 4 5 /* 6 * 题目描述： 请实现一个函数，将字符串的每个空格替换为"%20"。 7 * 例如输入"We are happy",则输出"We%20are%20happy."。 8 */ 9 /** 10 * @param args 11 */ 12 13 public String replace(String input) { 14 StringBuilder builder = new StringBuilder(); 15 if (input == null || input.length() == 0) { 16 return null; 17 } 18 for (int i = 0; i < input.length(); i++) { 19 if (input.charAt(i) == ‘ ‘) { 20 builder.append("%"); 21 builder.append("2"); 22 builder.append("0"); 23 } else { 24 builder.append(input.charAt(i)); 25 } 26 } 27 return builder.toString(); 28 } 29 30 // 测试用例 31 public static void main(String[] args) { 32 ReplaceBank test = new ReplaceBank(); 33 // 输入的字符串包含空格：最后面，最前面，中间，连续空格 34 String str1 = "We are happy."; 35 String str2 = " Wearehappy."; 36 String str3 = "Wearehappy. "; 37 String str4 = "We are happy ."; 38 //输入的字符串没有空格 39 String str5="Wearehappy."; 40 //特殊输入测试：字符串只有连续空格、只有一个空格、字符串是一个null指针、字符串是一个空字符串; 41 String str6=" "; 42 String str7=" "; 43 String str8=null; 44 String str9=""; 45 System.out.println(test.replace(str1)); 46 System.out.println(test.replace(str2)); 47 System.out.println(test.replace(str3)); 48 System.out.println(test.replace(str4)); 49 System.out.println(test.replace(str5)); 50 System.out.println(test.replace(str6)); 51 System.out.println(test.replace(str7)); 52 System.out.println(test.replace(str8)); 53 System.out.println(test.replace(str9)); 54 } 55 56 }
Problem5:从尾到头打印链表
题目描述：输入一个链表的头结点，从尾到头反过来打印出每个结点的值.
1 package Problem5; 2 3 import java.util.Stack; 4 5 //首先定义链表结构 6 class LinkNode{ 7 LinkNode next; 8 int node_value; 9 } 10 11 public class PrintListReverse { 12 public void reverse(LinkNode headNode){ 13 //用栈的思想来实现链表的倒序输出 14 Stack<LinkNode> stack=new Stack<LinkNode>(); 15 while(headNode!=null){ 16 stack.push(headNode); 17 headNode=headNode.next; 18 } 19 while(!stack.isEmpty()){ 20 System.out.print(stack.pop().node_value+" "); 21 } 22 System.out.println(); 23 } 24 25 /** 26 * @param args 27 */ 28 public static void main(String[] args) { 29 //输入的链表有多个结点 30 PrintListReverse plr=new PrintListReverse(); 31 LinkNode node1=new LinkNode(); 32 LinkNode node2=new LinkNode(); 33 LinkNode node3=new LinkNode(); 34 node1.node_value=1; 35 node2.node_value=2; 36 node3.node_value=3; 37 node1.next=node2; 38 node2.next=node3; 39 plr.reverse(node1); 40 } 41 42 }
Problem5:重建二叉树
题目描述:输入某二叉树的前序遍历和中序遍历结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。例如输入前序遍历序列:{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6},则重建出图中所示二叉树并且输出它的头结点。
重建的二叉树：
1 package Problem6; 2 3 /* 重建二叉树 4 * 问题描述：输入某二叉树的前序遍历和中序遍历结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中 5 * 都不包含重复的数字。例如输入前序遍历序列:{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6}, 6 * 则重建出图中所示二叉树并且输出它的头结点。 7 */ 8 //定义二叉树节点 9 class BinaryTreeNode { 10 public int value; 11 public BinaryTreeNode leftNode; 12 public BinaryTreeNode rightNode; 13 14 // 无参构造函数 15 public BinaryTreeNode() { 16 17 } 18 19 // 有参构造函数 20 public BinaryTreeNode(int value) { 21 this.value = value; 22 this.leftNode = null; 23 this.rightNode = null; 24 } 25 } 26 27 public class ConstructBinaryTree { 28 29 public static BinaryTreeNode construct(int preOrder[], int inOrder[], 30 int length) throws Exception { 31 if (preOrder == null || inOrder == null || length < 0) { 32 return null; 33 } 34 return constructCore(preOrder, 0, preOrder.length - 1, inOrder, 0, 35 inOrder.length - 1); 36 } 37 38 public static BinaryTreeNode constructCore(int preOrder[], 39 int startPreIndex, int endPreIndex, int inOrder[], 40 int startInIndex, int endInIndex) throws InvalidPutException { 41 // 头结点的值 42 int rootValue = preOrder[startInIndex]; 43 44 // 构建一个只有一个根节点的二叉树 45 BinaryTreeNode root = new BinaryTreeNode(rootValue); 46 // 只有一个元素的情况下： 47 if (startPreIndex == endPreIndex) { 48 if (startInIndex == endInIndex 49 && preOrder[startInIndex] == inOrder[endInIndex]) { 50 System.out.println("只有一个元素"); 51 return root; 52 } else { 53 throw new InvalidPutException(); 54 } 55 56 } 57 // 最重要的一步：在中序遍历中找到根结点的索引 58 int rootInIndex = startInIndex; 59 while (rootInIndex <= endInIndex && inOrder[rootInIndex] != rootValue) { 60 rootInIndex++; 61 } 62 if (rootInIndex == endInIndex && inOrder[rootInIndex] != rootInIndex) { 63 throw new InvalidPutException(); 64 } 65 // 根节点的左子树的长度 66 int leftLength = rootInIndex - startInIndex; 67 // 根节点的左子树的最右端的索引值 68 int leftPreEndIndex = startPreIndex + leftLength; 69 // 构建左子树 70 if (leftLength > 0) { 71 root.leftNode = constructCore(preOrder, startPreIndex + 1, 72 leftPreEndIndex, inOrder, startInIndex, rootInIndex - 1); 73 } 74 // 说明根节点存在右子树 75 if (leftLength < endPreIndex - startPreIndex) { 76 root.rightNode = constructCore(preOrder, leftPreEndIndex + 1, 77 endPreIndex, inOrder, rootInIndex + 1, endInIndex); 78 } 79 return root; 80 } 81 82 // 按照前序遍历打印二叉树的节点 83 public static void printPreBinaryTree(BinaryTreeNode root) { 84 if (root == null) { 85 return; 86 } else { 87 System.out.println(root.value + " "); 88 } 89 if (root.leftNode != null) { 90 printPreBinaryTree(root.leftNode); 91 } 92 if (root.rightNode != null) { 93 printPreBinaryTree(root.rightNode); 94 } 95 } 96 97 public static class InvalidPutException extends Exception { 98 99 private static final long serialVersionUID = 1L; 100 } 101 102 /** 103 * @param args 104 * @throws Exception 105 */ 106 public static void main(String[] args) throws Exception { 107 int preOrder[] = { 1, 2, 4, 7, 3, 5, 6, 8 }; 108 int inOrder[] = { 4, 7, 2, 1, 5, 3, 8, 6 }; 109 ConstructBinaryTree test = new ConstructBinaryTree(); 110 printPreBinaryTree(test.construct(preOrder, inOrder, preOrder.length)); 111 } 112 113 }
Problem7:用两个栈实现队列
题目描述：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能
1 package Problem7; 2 3 import java.util.Stack; 4 5 public class ConStructQueue { 6 /* 7 * 问题描述：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead, 8 * 分别完成在队列尾部插入结点和在队列头部删除结点的功能 9 */ 10 11 /** 12 * @param args 13 */ 14 Stack<String> stack1 = new Stack<String>(); 15 Stack<String> stack2 = new Stack<String>(); 16 17 // 实现appendTail函数 18 public void appendTail(String s) { 19 stack1.push(s); 20 } 21 22 // 实现deleteHead函数 23 public String deleteHead() throws Exception { 24 if (stack2.isEmpty()) { 25 while (!stack1.isEmpty()) { 26 stack2.push(stack1.pop()); 27 } 28 } 29 if (stack2.isEmpty()) { 30 throw new Exception("队列为空，不能进行删除操作"); 31 } 32 return stack2.pop(); 33 } 34 35 public static void main(String[] args) throws Exception { 36 ConStructQueue test = new ConStructQueue(); 37 // 向空的队列中添加元素、删除元素 38 test.appendTail("1"); 39 System.out.println(test.deleteHead()); 40 // 向非空的队列添加删除元素 41 test.appendTail("2"); 42 test.appendTail("3"); 43 System.out.println(test.deleteHead()); 44 45 } 46 47 }
Problem8：旋转数组的最小数字
题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1;
1 package Problem8; 2 3 public class MinInReversingList { 4 /* 5 * 题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 6 * 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1; 7 */ 8 9 /** 10 * @param args 11 * @throws Exception 12 */ 13 public static int minElement(int array[]) throws Exception { 14 // 条件判断 15 if (array == null || array.length <= 0) { 16 throw new Exception("Invalid parameters"); 17 } 18 int left = 0; 19 int right = array.length - 1; 20 int mid = left; 21 while (array[left] >= array[right]) { 22 // 跳出循环的条件 23 if (right - left == 1) { 24 mid = right; 25 break; 26 } 27 mid = (left + right) / 2; 28 if (array[left] == array[mid] && array[mid] == array[right]) { 29 return minFromSortSearch(array); 30 // 算法的核心思想 31 } else { 32 if (array[mid] >= array[left]) { 33 left = mid; 34 } 35 if (array[mid] <= array[right]) { 36 right = mid; 37 } 38 } 39 } 40 return array[right]; 41 } 42 43 public static int minFromSortSearch(int[] array) { 44 int minEle = array[0]; 45 for (int i = 1; i < array.length; i++) { 46 if (array[i] < minEle) { 47 minEle = array[i]; 48 } 49 } 50 return minEle; 51 } 52 53 // 测试 54 public static void main(String[] args) throws Exception { 55 // 功能测试：输入的数组是升序排序数组的一个旋转，数组中有重复数字或者没有重复数字 56 int array1[] = { 3, 4, 5, 1, 2 }; 57 System.out.println(minElement(array1)); 58 int array2[] = { 3, 4, 5, 3, 3 }; 59 System.out.println(minElement(array2)); 60 // 边界测试:输入的数组是一个升序排序数组、只包含一个数字的数组 61 int array3[] = { 3 }; 62 System.out.println(minElement(array3)); 63 // 特殊输入测试：输入null指针 64 int array4[] = null; 65 System.out.println(minElement(array4)); 66 } 67 68 }
Problem9：斐波那契数列
题目描述：写一个函数，输入n，求斐波那契数列的第n项，斐波那契数列的定义如下： n=0,f(n)=0 ;n=1,f(n)=1 n>1;f(n)=f(n-1)+f(n-2).
1 package Problem9; 2 3 public class Fibonacci { 4 /* 5 * 题目描述： 写一个函数，输入n，求斐波那契数列的第n项，斐波那契数列的定义如下： n=0,f(n)=0 n=1,f(n)=1 6 * n>1;f(n)=f(n-1)+f(n-2) 7 */ 8 9 /** 10 * @param args 11 */ 12 // 解法1：用递归解决,但是存在很严重的效率问题，做了很多次的重复计算 13 public static int Fib1(int n) { 14 if (n == 0) { 15 return 0; 16 } else if (n == 1) { 17 return 1; 18 } else { 19 return Fib1(n - 1) + Fib1(n - 2); 20 } 21 22 } 23 24 // 解法2:时间复杂度为O(n),从下向上计算，保存已经计算过的数值，避免重复计算 25 public static long Fib2(int n) { 26 long FibOne = 0; 27 long FibTwo = 1; 28 long FibN = 0; 29 int result[] = { 1, 2 }; 30 if (n < 2) { 31 return result[n]; 32 } else { 33 for (int i = 2; i <= n; i++) { 34 FibN = FibTwo + FibOne; 35 FibOne = FibTwo; 36 FibTwo = FibN; 37 } 38 } 39 return FibN; 40 } 41 42 public static void main(String[] args) { 43 // 用解法1求序列的第100项,直接不动了 44 // System.out.println(Fib1(100)); 45 System.out.println(Fib2(100)); 46 } 47 }
相关题目：一只青蛙一次可以跳上一级台阶，也可以跳上2级。求该青蛙跳上一个n级台阶共有多少种跳法;
原文：http://www.cnblogs.com/ysw-go/p/6272551.html