在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
package ccnu.offer; public class Test00 { public static void main(String[] args){ int[][] array = {{1, 3, 5, 23}, {3, 8, 12, 32}, {7, 13, 17, 56}}; boolean b = find(1, array); boolean b1 = find1(1, array); System.out.println(b); System.out.println(b1); } public static boolean find(int target, int [][] array) { for(int i = 0; i < array.length; i++){ // 以每一行为单位进行查找 if(isFind(array, i, target)){ return true; } } return false; } public static boolean isFind(int[][] array, int row, int target) { int[] tmp = array[row]; int low = 0; int high = tmp.length - 1; int mid = (low + high) / 2; while (low <= high) { // 对行号为row的行进行二分查找 if (target > tmp[mid]) { low = mid + 1; } else if (target == tmp[mid]) { return true; } else { high = mid - 1; } mid = (low + high) / 2; } return false; } public static boolean find1(int target, int[][] array){ // 左下角开始 int row = array.length - 1; int column = 0; while(row >= 0 && column <= array[0].length - 1){ if(target == array[row][column]){ // 相等找到退出 return true; }else if(target > array[row][column]){ // 大于右移 column++; }else{ // 上移 row--; } } return false; } }请实现一个函数，将一个字符串中的空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy
package ccnu.offer; import java.util.regex.Matcher; import java.util.regex.Pattern; public class Test01 { public static void main(String[] args) { System.out.println(replaceSpace(new StringBuffer(" We Are Happy"))); } public static String replaceSpace1(StringBuffer str) { Pattern p = Pattern.compile(" +"); //直接利用正则表达式替换 Matcher m = p.matcher(str); return m.replaceAll(" "); } public static String replaceSpace(StringBuffer str) { if(str == null){ return null; } StringBuffer sb = new StringBuffer(); char tmp; for(int i = 0; i < str.length(); i++){ if((tmp = str.charAt(i)) != ' '){ sb.append(tmp); }else if((i - 1) >= 0 && str.charAt(i - 1) != ' '){ // 连续多个空格只会替换一次 sb.append(" "); } } return sb.toString(); } }输入一个链表，从尾到头打印链表每个节点的值
package ccnu.offer; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.ListIterator; public class Test02 { public static void main(String[] args) { int[] arr = {1, 23, 12, 8, 222}; int i = 0; ListNode listNode = new Test02().new ListNode(arr[i++]); listNode.next = null; ListNode p = listNode; while(i < arr.length){ // 创建单链表 ListNode tmp = new Test02().new ListNode(arr[i++]); tmp.next = null; p.next = tmp; p = tmp; } List<Integer> l = printListFromTailToHead3(listNode); for(Integer t : l){ System.out.println(t); } } public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) { List<Integer> l = new ArrayList<Integer>(); List<Integer> l2 = new ArrayList<Integer>(); ListNode node = listNode; while (node != null) { l.add(node.val); node = node.next; } ListIterator<Integer> iter = l.listIterator(l.size()); while (iter.hasPrevious()) { // 从尾部向前遍历 l2.add(iter.previous()); } return (ArrayList<Integer>) l2; } class ListNode { private int val; private ListNode next = null; ListNode(int val) { this.val = val; } } public static ArrayList<Integer> printListFromTailToHead2(ListNode listNode) { List<Integer> l = new ArrayList<Integer>(); ListNode p = listNode; while(p != null){ l.add(p.val); p = p.next; } Collections.reverse(l); // 将容器中元素利用集合工具类中方法直接反转 return (ArrayList<Integer>)l; } public static ArrayList<Integer> printListFromTailToHead3(ListNode listNode) { ArrayList<Integer> l = new ArrayList<Integer>(); ListNode p = listNode; while (p != null) { l.add(p.val); p = p.next; } int size = l.size(); for(int i = 0; i < size/2; i++){ // 直接遍历反转 int tmp = l.get(size - i -1); l.set(size - i - 1, l.get(i)); l.set(i, tmp); } return l; } }输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回
package ccnu.offer; import java.util.ArrayList; import java.util.List; public class Test03 { public static void main(String[] args) { int[] pre = { 1, 2, 3, 4 }; int[] in = { 2, 1, 4, 3 }; // postOrder:2, 4, 3, 1 List<Integer> l = postOrder(reConstructBinaryTree(pre, in)); for (Integer i : l) { System.out.print(i + " "); } List<Integer> l2 = postOrder(reConstructBinaryTree2(pre, in, 0, 0, pre.length)); System.out.println(); for (Integer i : l2) { System.out.print(i + " "); } } public static List<Integer> postOrder(TreeNode root){ List<Integer> rootL = new ArrayList<Integer>(); List<Integer> leftL = new ArrayList<Integer>(); List<Integer> rightL = new ArrayList<Integer>(); List<Integer> l = new ArrayList<Integer>(); if(root != null){ leftL = postOrder(root.left); rightL = postOrder(root.right); rootL.add(root.val); } l.addAll(leftL); l.addAll(rightL); l.addAll(rootL); return l; } // 构建一个二叉树by前序遍历(NLR)and中序遍历(LNR) public static TreeNode reConstructBinaryTree(int [] pre,int [] in) { int pl = 0; // 先序左边节点 int pr = pre.length - 1; // 先序右边节点 int il = 0; // 中序左边节点 int ir = in.length - 1; // 中序右边节点 return create(pre, in, pl, pr, il, ir); } private static TreeNode create(int[] pre, int[] in, int pl, int pr, int il, int ir){ TreeNode root = new Test03().new TreeNode(pre[pl]); int i; for(i = 0; pre[pl] != in[i]; i++); // 找出中序遍历中的当前子树前序的第一个节点的位置 int lLen = i - il; // 左子树长度 int rLen = ir - i; // 右子树长度 if(lLen > 0){ // 左子树不为空 root.left = create(pre, in, pl + 1, pl + lLen, il, il + lLen - 1); }else{ root.left = null; } if(rLen > 0){ // 右子树不为空 root.right = create(pre, in, pr - rLen + 1, pr, ir - rLen + 1, ir); }else{ root.right = null; } return root; } // preBegin表示当前前序序列的开始索引 // inBegin表示当前中序序列的开始索引 // len表示当前序列的长度 public static TreeNode reConstructBinaryTree2(int[] pre, int[] in, int preBegin, int inBegin, int len){ if(pre == null || in == null || pre.length != in.length || pre.length == 0 || in.length == 0){ return null; } if(len <= 0){ return null; } TreeNode root = new Test03().new TreeNode(pre[preBegin]); int rootIndex; for(rootIndex = 0; in[rootIndex] != pre[preBegin]; rootIndex++); root.left = reConstructBinaryTree2(pre, in, preBegin + 1, inBegin, rootIndex - inBegin); root.right = reConstructBinaryTree2(pre, in, preBegin + (rootIndex - inBegin) + 1, rootIndex + 1, len - (rootIndex - inBegin) - 1); return root; } class TreeNode{ private int val; private TreeNode left; private TreeNode right; public TreeNode(int val){ this.val = val; } }用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型
package ccnu.offer; import java.util.EmptyStackException; import java.util.Stack; public class Test04 { private Stack<Integer> stack1 = new Stack<Integer>(); // 负责元素进 private Stack<Integer> stack2 = new Stack<Integer>(); // 负责元素出 public int pop() { if (stack2.isEmpty()) { // 负责出元素的栈不为空 if (stack1.isEmpty()) { throw new EmptyStackException(); } else { // 负责进元素的栈不为空，那么就将其中所有的元素放入到stack2 while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } } return stack2.pop(); } public void push(int val) { stack1.push(val); } public static void main(String[] args) { Test04 t = new Test04(); t.push(12); t.push(1); t.push(6); System.out.println(t.pop()); t.push(8); System.out.println(t.pop()); System.out.println(t.pop()); System.out.println(t.pop()); // System.out.println(t.pop()); } }把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0
package ccnu.offer; public class Test05 { public static void main(String[] args) { int min = new Test05().minNumberInRotateArray(new int[]{5, 6, 6, 3, 4, 5}); System.out.println(min); } public int minNumberInRotateArray(int [] array) { if(array == null){ return 0; } if(array.length == 0){ return 0; } for(int i = 1; i < array.length; i++){ if(array[i] < array[i - 1]){ // 若出现第一个元素递减就为最小元素 return array[i]; } } return array[0]; } }大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项
package ccnu.offer; import java.util.ArrayList; import java.util.List; // 1 1 2 3 5 8 13 21 34 55 89 144 // 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 // 377，610，987，1597，2584，4181，6765，10946，17711，28657，46368 ... public class Test06 { public static void main(String[] args) { System.out.println(fibonacci(7)); System.out.println(fibonacci1(7)); } public static long fibonacci(int n) { if (n == 0) { return 0L; } if (n == 1 || n == 2) { return 1L; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } public static long fibonacci1(int n) { List<Long> l = new ArrayList<Long>(); l.add(1L); // 第一项 l.add(1L); // 第二项 int size; while (n > (size = l.size())) { // 当指定的项数不在容器中，则使用迭代得到这个项 l.add(l.get(size - 1) + l.get(size - 2)); } return l.get(n - 1); } }一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
package ccnu.offer; // 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法 // 分析：如果当前有n级台阶，跳法f(n),此时可以选择跳1级或者2级.如果选择跳1级，剩下的n-1级跳法f(n-1);如果选择跳2级，剩下的n-2级跳法f(n-2) // 因此n级台阶f(n) = f(n-1) + f(n-2) public class Test07 { public static void main(String[] args) { int c = jumpFloor(3); System.out.println("cases: " + c); int c2 = jumpFloor2(3); System.out.println("cases: " + c2); } public static int jumpFloor(int target) { int one = 1; int two = 2; if(target == 1){ // 只有一级 return one; // 一种可能 } if(target == 2){ // 只有两级 return two; // 两种可能 } for(int i = 3; i <= target; i++){ two = one + two; one = two - one; } return two; } public static int jumpFloor2(int target) { if (target < 0) { return 0; } if (target == 0) { return 1; } else { return jumpFloor2(target - 1) + jumpFloor2(target - 2); } } }一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法
package ccnu.offer; // 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法 // 分析：如果当前有n级台阶，跳法f(n),此时可以选择跳1级或者2级.如果选择跳1级，剩下的n-1级跳法f(n-1);如果选择跳2级，剩下的n-2级跳法f(n-2),...,如果跳n-1级，剩下的n-(n-1)级跳法f(1) // f(n) = f(n-1) + f(n-2) + ... +f(1) + f(0) .....①式，其中f(0)=1 // f(n-1) = f(n-2) + ... +f(1) + f(0) .....②式 // ①式减去②式得：f(n) - f(n-1) = f(n-1) ⇨ f(n) = 2 * f(n-1) public class Test08 { public static void main(String[] args) { int c = jumpFloor(3); System.out.println("cases: " + c); } public static int jumpFloor(int target) { if (target < 0) { return 0; } else if (target == 1) { return 1; } else { return jumpFloor(target - 1) * 2; } } }输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示
package ccnu.offer; public class Test08 { public static void main(String[] args) { // System.out.println(Integer.bitCount(811)); int one_bits = oneBits(811);// 2^9+2^8+32+8+2+1=512+256+43=768+43=811 System.out.println(one_bits); } public static int oneBits(int i) { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; } // 如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 // 举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。 // 这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。 public static int oneBits1(int i) { int count = 0; while (i != 0) { count++; i = i & (i - 1); } return count; } }