剑指offer

1.在一个二维数组中（每个一维数组的长度相同）， 每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 public class Solution { public boolean Find(int target, int [][] array) { boolean found = false; int lie = array[0].length; int hang = array.length; int column = lie - 1; int row = 0; while(column >= 0 && row < hang){ int value = array[row][column]; if(value > target){ column--; }else if(value < target){ row++; }else{ found = true; break; } } return found; } } 2.请实现一个函数，将一个字符串中的每个空格替换成“%20”。 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 public class Solution { public String replaceSpace(StringBuffer str) { if(str == null){ return null; } for(int i=0;i<str.length();i++){ char c = str.charAt(i); if(c == ' '){ str.replace(i,i+1,"%20"); /*StringBuffer的替换功能 ： public StringBuffer replace(int start,int end,String str): 从start开始到end用str替换*/ } } return str.toString(); } } public class Solution { public String replaceSpace(StringBuffer str) { return str.toString().replaceAll(" ","%20"); } } 3.输入一个链表，按链表从尾到头的顺序返回一个ArrayList。 import java.util.Stack; import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { Stack<Integer> stack = new Stack<>(); while(listNode != null){ stack.push(listNode.val); listNode = listNode.next; } ArrayList<Integer> list = new ArrayList<>(); while (!stack.isEmpty()) { list.add(stack.pop()); } return list; } }

4.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}， 则重建二叉树并返回。 public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { //由于重建二叉树的过程会用到很多边界值，所以题目所给的方法的参数是不够用的 //所以，在下面重载了这个方法，每次传入前序和中序序列以及起始位置 TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1); return root; } private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) { //这里是判断结束的标志，由于是递归算法，我们不可能一直执行下去，所以需要结束标志 //下面这两种情况发生一个就会结束 if(startPre>endPre||startIn>endIn) { return null; } //首先找到根节点 TreeNode root = new TreeNode(pre[startPre]); //对中序遍历进行查找根节点 for(int i=startIn;i<=endIn;i++) { //找到之后，分别对左子树和右子树进行递归算法，重复此步骤 if(in[i]==pre[startPre]) { //重建二叉树的关键就是找到其中的边界值，边界值在图中已经做了描述 root.left=reConstructBinaryTree(pre,startPre+1,startPre+istartIn,in,startIn,i-1); root.right=reConstructBinaryTree(pre,startPre+istartIn+1,endPre,in,i+1,endIn); break; } } return root; } } 5.用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } } 6.把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 import java.util.*; public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length == 0){ return 0; }else{ Arrays.sort(array); return array[0]; } } } 7.斐波那契数列指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 这个数列从第三项开始，每一项都等于前两项之和。现在要求输入一个整数n， 请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 public class Solution { public int Fibonacci(int n) { int a=1,b=1,c=0; if(n<0){ return 0; }else if(n==1 || n==2){ return 1; } for(int i=3;i<=n;i++){ c = a+b; a = b; b = c; } return c; } } 8.一只青蛙一次可以跳上1级台阶，也可以跳上2级。 求该青蛙跳上一个n级的台阶总共有多少种跳法 public class Solution { /*定义一个函数 int JumpFloor(int target) f（n）功能是求青蛙跳上一个n级的台阶总共有多少种跳法*/ public int JumpFloor(int target) { if(target <= 2){ return target; } /*第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。 第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。 所以，小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)*/ return JumpFloor(target - 1) + JumpFloor(target - 2); } } 9.输入一个整数数组，实现一个函数来调整该数组中数字的顺序， 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分， 并保证奇数和奇数，偶数和偶数之间的相对位置不变。 public class Solution { public void reOrderArray(int [] array) { //类似冒泡算法，前偶后奇就交换 for(int i=0;i<array.length-1;i++){ for(int j=0;j<array.length-1-i;j++){ if(array[j]%2==0&&array[j+1]%2==1){ int temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; } } } } } 10.输入一个链表，输出该链表中倒数第k个结点。 //尺子取值 public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(k<=0){ return null; } //先让两个指针都指向头节点 ListNode p1 = head; ListNode p2 = head; //快指针先走 k-1 步，到达第 k 个节点。 for(int i=0;i<k-1;i++){ if(p2 == null){ return null; }else{ //p=p.next是表示修改指针p的位置，把p指向原来的下一个节点。 //每个结点不仅包含值，还包含链接到下一个结点的引用字段。 p2 = p2.next; } } if(p2==null){return null;} //然后两指针同时齐步走，当快指针到达末尾时，慢指针在倒数第 k 个节点上。 while(p2.next!=null){ p1 = p1.next; p2 = p2.next; } return p1; } } 11.输入一个链表，反转链表后，输出新链表的表头。 public class Solution { public ListNode ReverseList(ListNode head) { //head为当前节点 if(head == null) return null; //pre为当前节点的前一个节点,next为当前节点的下一个节点 ListNode pre = null; ListNode next = null; //循环的目的就是让当前节点从指向next到指向pre while(head!=null){ /*next = head.next 可以认为next指针指向了head.next 即是把head.next的值赋给了next， 也就是把head下一个节点的地址赋给pre。 head.next = pre 就是head.next的指针指向了pre，就是 */ /*先用next保存head的下一个节点的信息 保证单链表不会因为失去head节点的原next节点而就此断裂*/ next = head.next; //保存完next，就可以让head从指向next变成指向pre了，代码如下 head.next = pre; //head指向pre后，就继续依次反转下一个节点 //让pre，head，next依次向后移动一个节点，继续下一次的指针反转 pre = head; head = next; } /*如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕 pre就是反转后链表的第一个节点*/ //直接输出pre就是我们想要得到的反转后的链表 return pre; } } 12.输入两个单调递增的链表，输出两个链表合成后的链表 当然我们需要合成后的链表满足单调不减规则。 /*个指针分别指向链表元素，一开始指向量表头部 比较两指针所指向链表元素的大小，将小的元素添加的list3链表中 同时指针指向链表下一个元素，listnode传入的时候也是一个值一个值的传入 而不是一次性的传入了一链值，listnode类中包含了指向当前值的val 以及指向下一个值的next;*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null) return list2; if(list2==null) return list1; ListNode list3 =null; if(list1.val < list2.val){ list3 = list1; list3.next = Merge(list1.next,list2); }else{ list3 = list2; list3.next = Merge(list1,list2.next); } return list3; } } 13. 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 子树：是只要包含了一个结点，就得包含这个结点下的所有节点。 子结构：包含了一个结点，可以只取左子树或者右子树，或者都不取。 public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { boolean flag = false; //判断B为空时，不是子结构 if(root2==null) return false; if(root1==null && root2 != null) return false; //如果找到了root对应的根节点的话 if(root1.val == root2.val){ //以这个根节点为起点判断是否包含root2 flag = isHasSubtree(root1,root2); } //如果找不到，那么就再去root1的左儿子当做起点，去判断是否包含root2 if(!flag){ flag = isHasSubtree(root1.left,root2); //如果还找不到，那么就再去root1的右儿子当做起点，去判断是否包含root2 if(!flag){ flag = isHasSubtree(root1.right,root2); } } return flag; } public static boolean isHasSubtree(TreeNode node1,TreeNode node2){ //如果root2已经遍历完了并且节点能对上，则返回true if(node2 == null) return true; //如果root2还没遍历完，root1遍历完了，那么返回false if(node1==null && node2!=null) return false; //如果跟节点对应得上，那么就分别去子节点匹配 if(node1.val == node2.val){ return isHasSubtree(node1.left, node2.left) && isHasSubtree(node1.right, node2.right); } return false; } } 14.操作给定的二叉树，将其变换为源二叉树的镜像。 二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5 public class Solution { public void Mirror(TreeNode root) { if(root == null) return; TreeNode tmp = null; tmp = root.right; root.right = root.left; root.left = tmp; Mirror(root.left); Mirror(root.right); } }

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字 （当我们顺时针打印该矩阵时，每一圈的起始位置是左上角的元素，并且每一圈左上角元素都有一个共同点：它的行和列所对应的的下标都是相同的。）