1.输入一个链表,从尾到头打印链表每个节点的值。
package test3; import java.util.ArrayList; class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } public class printFromTailtoHead { public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> a = new ArrayList<Integer>(); ListNode temp = listNode; while(temp != null){ a.add(new Integer(temp.val)); temp = temp.next; } Integer b ; for(int i=0; i<a.size()/2;i++){ b = a.get(i); a.set(i, a.get(a.size()-i-1)); a.set(a.size()-i-1,b); } return a; } public static void main(String args[]){ ListNode a = new ListNode(1); a.next = new ListNode(2); ArrayList<Integer> b = printListFromTailToHead(a); System.out.println(b.get(0)+"----"+b.get(1)); } } 2. 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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) { return reConstructBinaryTree0(pre, 0, pre.length, in, 0, in.length); } public TreeNode reConstructBinaryTree0(int [] pre, int preStart, int preEnd, int [] in, int inStart, int inEnd) { if (preStart >= preEnd) { // way out return null; } int rootIndex = indexOf(in, inStart, inEnd, pre[preStart]); TreeNode root = new TreeNode(pre[preStart]); int leftPreStart = preStart + 1; int leftPreEnd = leftPreStart + (rootIndex - inStart); int leftInStart = inStart; int leftInEnd = rootIndex; // 构建左子树 root.left = reConstructBinaryTree0(pre, leftPreStart, leftPreEnd, in, leftInStart, leftInEnd); int rightPreStart = leftPreEnd; int rightPreEnd = preEnd; int rightInStart = rootIndex + 1; int rightInEnd = inEnd; // 构建右子树 root.right = reConstructBinaryTree0(pre, rightPreStart, rightPreEnd, in, rightInStart, rightInEnd); return root; } // 找下标 public int indexOf(int[] array, int start, int end, int value) { for (int i = start; i < end; i++) { if (array[i] == value) { return i; } } return -1; } } 3. 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解法：有两个栈，栈1和栈2.当入栈的时候，我们将它全放进栈1中，当需要出栈的时候，我们将栈1出栈到栈2中，然后再将栈2依次出栈。出完栈之后，再把stack2中的数pop出push到stack1，接受下次的操作。所以入栈的时候，思路很简单，注意到要将int类型转为Integer类型，我们使用了new Integer(int);当需要出栈的时候，我们用API提供的方法while(stack1.isEmpty())来将所有栈1的元素压入栈2中，然后将栈2弹出就可以。这里又涉及到将Integer的类型转为int类型的方法Integer.intValue();
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(new Integer(node)); } public int pop() { int pop; while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } pop=stack2.pop().intValue(); while(!stack2.isEmpty()){ stack1.push(stack2.pop()); } return pop; } } 4. 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
public static int minOfShiftedArray(int[] x){ if(x==null||x.length==0){ return -1; } int len=x.length; int low=0; int high=len-1; if(x[low]<x[high]){//if the array is not shifted actually,e.g. {1,2,3,4,5} return x[low]; } int mid=0; while(low<high){ mid=(low&high)+(low^high)/2; if(mid==low){//if there are only two elements left return x[low]<=x[high]?x[low]:x[high]; } if(x[mid]>=x[low]){ low=mid; }else{ high=mid; } } return x[mid]; }
