剑指offer1-5

文章目录

1数组查找2、StringBuffer、字符串替换3、输入一个链表，按链表从尾到头的顺序返回一个ArrayList4、根据前序遍历和前序遍历还原二叉树5、两个栈构造一个队

1数组查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 package qiuzhike; import java.awt.geom.Ellipse2D; public class Solution { public static boolean Find(int target, int [][] array) { if(array.length!=0){ int row =0; int col = array[0].length-1; while(row<array.length&&col>=0) { if(target>array[row][col]) { row++; } else if(target<array[row][col]) { col--; } else { return true; } } return false; }else{ return false; } }; public static void main(String[] args) { int a[][] = new int[][]{ {2,3,5,9}, {4,7,9,12}, {8,10,11,17} }; boolean aString = Find(1,a); System.out.println(aString); } } //或者 public class Solution{ public boolean Find(int target,int[][] array){ if(array.length==0) return false; for(int i=0;i<array.length;i++){ for(int j=array[i].length-1; j>=0;j--){ //如果不在第i行，则跳出j循环，执行下一个i循环 if(array[i][j]<target){ break; } //如果在第i行则继续j循环 else if(array[i][j]>target){} else{ return true; } } } return false; } }

2、StringBuffer、字符串替换

请实现一个函数，将一个字符串中的每个空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。

注意： StringBuffer没有replaceAll()函数 字符串不能直接Str[i]，要用str.charAt(i) StringBuffer转字符串—>str2.toString(); charAt比较应该是’ '而不是" "

package qiuzhike; public class Solution { public static String replaceSpace(StringBuffer str) { if(str==null) return null; StringBuffer str2=new StringBuffer(); for (int i=0;i<str.length();i++){ if (str.charAt(i)==' '){ str2.append(" "); }else{ str2.append(str.charAt(i)); } } return str2.toString(); } public static void main(String[] args) { String string = " 15 456 789 "; StringBuffer str = new StringBuffer(string); String s = replaceSpace(str); System.out.println(); } } 或者用replace： for (int i=0;i<str.length();i++){ if (str.charAt(i)==' '){ //str2.append(" "); str.replace(i,i+1," "); } //else{ // str2.append(str.charAt(i)); //} }

3、输入一个链表，按链表从尾到头的顺序返回一个ArrayList

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。 非递归： import java.util.ArrayList; public class Solution{ public ArrayList<Integer> printListFromTailToHead(ListNode listNode){ ArrayList<Integer> list = new ArrayList<>(); if(listNode==null) return list; while(listNode!=null){ list.add(0,listNode.val); listNode = listNode.next; } return list; } }

递归： 注：刚开始直接写的hArrayList.add(readListNode(listNode));，但是输出的只有最后一个值，原因在于只有最后一个返回来值，其他都返回的节点，并没有加入到int数组里。

/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */ import java.util.ArrayList; public class Solution { ArrayList<Integer> hArrayList = new ArrayList<>(); public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { if(listNode!=null){ readListNode(listNode); } return hArrayList; } public void readListNode(ListNode l){ if (l==null){ return; } readListNode(l.next); hArrayList.add(l.val); } }

4、根据前序遍历和前序遍历还原二叉树

4.根据前序遍历和前序遍历还原二叉树 前序遍历：{1,2,4,7,3,5,6,8} 前序遍历：{4,7,2,1,5,3,8,6} 根据前序遍历定义，先遍历根节点，然后遍历左子树和右子树，由第一个元素“1”，可以将中序遍历分成左右子树，左子树{4,7,2}，右子树{5,3,8,6}。 然后再根据2把左子树{4,7,2}，分为左子树{4,7},右子树为空； 再跟据7把左子树分为{7}，右子树为空 通过递归的方式可以重建二叉树。

package Jianzhi; public class Solution1 { /** * * @param pre 前序遍历序列 * @param in 中序遍历序列 * @return 重建二叉树 * @auther fan.lee */ public TreeNode reConstructBinaryTree(int [] pre,int [] in){ TreeNode root = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1); return root; } public TreeNode reConstructBinaryTree(int[] pre,int startpre,int endpre,int[] in,int startin,int endin){ if (startpre>endpre || startin>endin) return null; TreeNode treeNode = new TreeNode(pre[startpre]); //为了在每一次递归中找到当前根节点在中序序列in中的坐标 for(int i=0;i<in.length;i++){ if(pre[startpre]==in[i]){ //根节点把中序序列划分为左子树和右子树，左/右子树的值在先序遍历序列中是连续的 //startpre+i-startin时左子树中的值在先序遍历中，左子树值的右临界值 treeNode.left = reConstructBinaryTree(pre, startpre+1,startpre+i-startin,in,startin,i-1); //i+1,endin,每次划分后右子树的范围，i的后面，到endin treeNode.right = reConstructBinaryTree(pre,i-startin+startpre+1,endpre,in,i+1,endin); } } return treeNode; } //中序遍历 public static void inTraverBinaryTree(TreeNode2 tree){ if (tree==null) return; if (tree.left !=null){ inTraverBinaryTree(tree.left); } System.out.print(tree.val); if(tree.right != null){ inTraverBinaryTree(tree.right); } } //先序遍历 public static void preTraverBinaryTree(TreeNode2 tree){ if (tree==null) return; System.out.print(tree.val); if (tree.left !=null){ preTraverBinaryTree(tree.left); } if(tree.right != null){ preTraverBinaryTree(tree.right); } } public static void main(String[] args) { int[] pre = { 1, 2, 4, 7, 3, 5, 6, 8 }; int[] in = { 4, 7, 2, 1, 5, 3, 8, 6 }; TreeNode2 tree = reConstructBinaryTree(pre, in); System.out.print("先序遍历的结果:"); preTraverBinaryTree(tree); System.out.print("\n"); System.out.print("中序遍历的结果"); inTraverBinaryTree(tree); } }

5、两个栈构造一个队

【用到的概念】： 栈：先进后出。 栈方法：出栈：pop()，入栈push(int a),判断栈空isEmpty(). 而队列是先进先出。 【想法】：一个栈当作进栈队列，出栈时候，先把栈1的序列出栈到栈2序列，然后再从栈2出栈，达到先进先出的效果

package day03; import java.util.Stack; public class StackToQueue { private Stack<Integer> stack1 = new Stack<>(); private Stack<Integer> stack2 =new Stack<>(); /* 有一个逻辑： 出栈时候判断栈2是否为空，如果非空，也就是说这个时候栈2中还有一些 从栈1中pop出的元素，这些元素只在栈2，不在栈1 当栈2空的时候，再把栈1中的元素移动过来 如： 1 2 3 4 5进栈 此时stack1: 5 4 3 2 1 出栈 stack1-->stack2 此时【stack2: 1 2 3 4 5】 【stack1: 是空】 1 2 出栈 进栈 6 7 8 【此时stack1: 8 7 6】 【stack2: 3 4 5】 出栈 3 4 5，stack2空。 出栈 判断stack2空。 stack1-->stack2 此时【stack2: 6 7 8】 【stack1: 空】 */ //进栈 public void push(int node){ stack1.push(node); } public int pop(){ //如果栈2中元素为空时，则让栈1中的元素出栈到栈2中 if (stack2.isEmpty()){ //判断栈1是否为空，用isEmpty while (!stack1.isEmpty()){ //这里调用的是栈的pop方法，而不是StackToQueue类中定义的pop方法 //StackToQueue类中定义的pop方法,只能通过实例去访问 stack2.push(stack1.pop()); } } //栈为空，或者为栈1的逆顺序 return stack2.pop(); } public static void main(String[] args) { StackToQueue queue = new StackToQueue(); for (int i= 0;i<10;i++){ queue.push(i); } for (int i= 0;i<10;i++){ System.out.println(queue.pop()); } } }