容易实现的算不上梦想,轻易放弃的算不上诺言。

要想成功得敢于挑战,有了梦想才有美好的明天！

---

前言：面试的时候我们经常遇到难题，画图、举例子和分解能够很好的帮助我们解决问题和细化问题。

---

一、画图使得抽象问题形象化

1. 二叉树镜像

操作给定的二叉树，将其变换为源二叉树的镜像。 

二叉树的镜像定义：源二叉树 

8    	   /  \    	  6   10    	 / \  / \    	5  7 9 11    	镜像二叉树    	    8    	   /  \    	  10   6    	 / \  / \    	11 9 7  5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/** public class TreeNode {      int val = 0;      TreeNode left = null;      TreeNode right = null;        public TreeNode(int val) {          this.val = val;        }   } */ public  class  Solution { public  void  Mirror(TreeNode root) {          //当树为空或者只有根节点的时候是不需要操作的          if (root== null ||(root.left== null &&root.right== null )){              return ;          }                    TreeNode temp=root.left;          root.left=root.right;          root.right=temp;                    if (root.left!= null ){              Mirror(root.left);          }          if (root.right!= null ){              Mirror(root.right);          }        } }

2. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

import  java.util.ArrayList; public  class  Solution {     /**       * print a matrix       * @param matrix       * @return       */      public  ArrayList<Integer> printMatrix( int [][] matrix) {            if (matrix== null ){              return  null ;          }                    ArrayList<Integer> aList =  new  ArrayList<Integer>();          int  rows=matrix.length;          int  columns=matrix[ 0 ].length;          int  start= 0 ;          while (columns>start* 2 &&rows>start* 2 ){              printMatrixCircle(matrix,rows,columns,start,aList);              ++start;          }                    return  aList;      }        /**       * print the out circle of the matrix       * @param matrix       * @param rows       * @param columns       * @param start       * @param aList       */      private  void  printMatrixCircle( int [][] matrix,  int  rows,  int  columns,              int  start, ArrayList<Integer> aList) {          int  endX=columns- 1 -start;          int  endY=rows- 1 -start;                    //print from left to right          for ( int  i=start;i<=endX;i++){              int  num=matrix[start][i];              System.out.print(num);              aList.add(num);          }                    //print from top to bottom          if (start<endY){              for ( int  j=start+ 1 ;j<=endY;j++){                  int  num=matrix[j][endX];                  System.out.print(num);                  aList.add(num);              }          }                    //print from right to left          if (start<endX&&start<endY){              for ( int  i=endX- 1 ;i>=start;i--){                  int  num=matrix[endY][i];                  System.out.print(num);                  aList.add(num);              }          }                    //from bottom to top                 if (start<endX&&start<endY- 1 ){              for ( int  i=endY- 1 ;i>=start+ 1 ;i--){                  int  num=matrix[i][start];                  System.out.print(num);                  aList.add(num);              }          }                } }

二、举例让抽象具体化

1. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

import  java.util.Stack;   public  class  Solution {              Stack<Integer> data =  new  Stack<Integer>();      Stack<Integer> min =  new  Stack<Integer>();      Integer temp= null ;        public  void  push( int  node) {          if (min.size()== 0 ){              data.push(node);              min.push(node);          } else {              int  t = min.peek();              if (t<node){                   data.push(node);                   min.push(t);              } else {                   data.push(node);                   min.push(node);              }          }                              }        public  void  pop() {          int  num = data.pop();          int  num2 = min.pop();      }        public  int  top() {          return  data.peek();      }        public  int  min() {                return  min.peek();      } }

2. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

import  java.util.ArrayList; import  java.util.Stack; public  class  Solution {     /**       * 栈的压入和弹出序列的判断       *       * @param pushA       * @param popA       * @return       */      public  boolean  IsPopOrder( int [] pushA,  int [] popA) {          if (pushA.length== 0 ||popA.length== 0 ){              return  false ;          }                              boolean  flag =  true ;          Stack<Integer> s =  new  Stack<Integer>();          s.push(- 1 ); //标记开始                    for  ( int  i =  0 ; i < popA.length; i++) {              int  num = popA[i];              int  index= 0 ;                            while  (num != s.peek()) {                  if  (pushA[index] != - 1 ) {                      s.push(index +  1 );                      pushA[index] = - 1 ;                  }                  index++;                  if (index>=pushA.length){                      break ;                  }              }              int  pop = s.pop();              if (num!=pop){                  flag= false ;                  break ;              }            }            return  flag;      } }

3. 从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

import  java.util.ArrayList; import  java.util.LinkedList; import  java.util.Queue;   /** public class TreeNode {      int val = 0;      TreeNode left = null;      TreeNode right = null;        public TreeNode(int val) {          this.val = val;        }   } */ public  class  Solution {      /**       * 按照层遍历二叉树算法的设计       * @param root       * @return       */      public  ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {          ArrayList<Integer> aList =  new  ArrayList<Integer>();          if (root== null ){              return  aList;          }                    Queue<TreeNode> qt =  new  LinkedList<TreeNode>();          qt.offer(root);          while (qt.size()> 0 ){              root=qt.poll();              aList.add(root.val);              if (root.left!= null ){                  qt.offer(root.left);              }              if (root.right!= null ){                  qt.offer(root.right);              }                    }                    return  aList;      } }

4. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

public  class  Solution {      public  boolean  VerifySquenceOfBST( int [] sequence) {          boolean  flag =  true ;          if  (sequence ==  null  || sequence.length <=  0 ) {              return  false ;          }          return  VerifySquenceOfBSTRe(sequence, 0 ,sequence.length);      }        private  boolean  VerifySquenceOfBSTRe( int [] sequence,  int  begin,  int  length) {          int  root=sequence[begin+length- 1 ];          int  i=begin;          for  (; i < length- 1 ; ++i) {              if  (sequence[i] > root) {                  break ;              }          }            // In BST right subtree is smaller than root            int  j = i;          for  (; j < length- 1 ; ++j) {              if  (sequence[j] < root) { //大于等于才是右子树                  return  false ;              }          }            boolean  left =  true ;          if (i> 0 ){              left=VerifySquenceOfBSTRe(sequence, 0 ,i);          }                      boolean  right =  true ;          if (i<length- 1 ){              right=VerifySquenceOfBSTRe(sequence,i+ 1 ,length-i- 1 );          }            return  left&&right;      } }

5. 二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

import  java.util.ArrayList; import  java.util.Stack; /** public class TreeNode {      int val = 0;      TreeNode left = null;      TreeNode right = null;        public TreeNode(int val) {          this.val = val;        }   } */ public  class  Solution {      public  ArrayList<ArrayList<Integer>> FindPath(TreeNode root,  int  target) {          ArrayList<ArrayList<Integer>> pathList =  new  ArrayList<ArrayList<Integer>>();          if  (root ==  null )              return  pathList;          Stack<Integer> stack =  new  Stack<Integer>();                    FindPath(root, target, stack, pathList);                    return  pathList;        }        private  void  FindPath(TreeNode root,  int  target, Stack<Integer> path,              ArrayList<ArrayList<Integer>> pathList) {                    if  (root ==  null )              return ;          //如果左右子树都为空 也就是到达叶子结点          if  (root.left ==  null  && root.right ==  null ) {              if  (root.val == target) {                  ArrayList<Integer> list =  new  ArrayList<Integer>();                  for  ( int  i : path) { //stack有iterator接口实现                      list.add( new  Integer(i));                  }                  list.add( new  Integer(root.val));                  pathList.add(list);              }          }  else  {              //如果不到叶子结点 递归的调用求的              path.push( new  Integer(root.val));              FindPath(root.left, target - root.val, path, pathList);              FindPath(root.right, target - root.val, path, pathList);              path.pop();          }        }   }

三、分解让复杂问题简单

1. 复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

/* public class RandomListNode {      int label;      RandomListNode next = null;      RandomListNode random = null;        RandomListNode(int label) {          this.label = label;      } } */ public class Solution {      /**       * 复杂链表的复制       * @param pHead       * @return       */      public RandomListNode Clone(RandomListNode pHead)    {                    //每一个传入的结点都是pHead          cloneNodes(pHead);          connectRandomNodes(pHead);          return reConnectNode(pHead);                }        /**       * 分离重建两个链表       * @param pHead       * @return       */      private RandomListNode reConnectNode(RandomListNode pHead) {          RandomListNode pNode=pHead;          RandomListNode pClonedHead=null;//复制链表的头结点的设置          RandomListNode pClonedNode=null;                    //          if(pNode!=null){              pClonedHead=pClonedNode=pNode.next;              pNode.next=pClonedNode.next;              pNode=pNode.next;//向后遍历          }          //后续链表的分离复制          while(pNode!=null){              pClonedNode.next=pNode.next;              pClonedNode=pClonedNode.next;              pNode. next=pClonedNode.next;              pNode=pNode.next;                        }                    return pClonedHead;      }        /**       * 链接Random       * @param pHead       */      private void connectRandomNodes(RandomListNode pHead) {          RandomListNode pNode = pHead;          while(pNode!=null){              RandomListNode pCloned = pNode.next;              if(pNode.random!=null){                  pCloned.random=pNode.random.next;//比着葫芦画瓢              }                            pNode=pCloned.next;          }                }        /**       * 结点复制 在同一个链表中       * @param pHead       */      private  void  cloneNodes(RandomListNode pHead) {                    RandomListNode pNode=pHead;          while (pNode!= null ){              RandomListNode pCloned =  new  RandomListNode(pNode.label);              pCloned.next=pNode.next;              pCloned.random= null ;                            pNode.next=pCloned; //复制结点                            pNode=pCloned.next;          }                } }

2. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

/** public class TreeNode {      int val = 0;      TreeNode left = null;      TreeNode right = null;        public TreeNode(int val) {          this.val = val;        }   } */ public  class  Solution {     /**       * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向       *       * 思路：中序遍历可以输出有序       * @param pRootOfTree       * @return       */            public  TreeNode Convert(TreeNode pRootOfTree) {          TreeNode  tnLastNodeInList= null ;          //转换          tnLastNodeInList=convertNode(pRootOfTree,tnLastNodeInList);                    TreeNode tnFirstNodeInList=tnLastNodeInList;                    while (tnFirstNodeInList!= null &&tnFirstNodeInList.left!= null ){              tnFirstNodeInList=tnFirstNodeInList.left;          }                    return  tnFirstNodeInList;      }        private  TreeNode convertNode(TreeNode pRootOfTree, TreeNode tnLastNodeInList) {                    if (pRootOfTree== null ){              return  tnLastNodeInList;          }                    TreeNode tnCur = pRootOfTree;                    //左侧          if (tnCur.left!= null ){              tnLastNodeInList=convertNode(tnCur.left, tnLastNodeInList);          }          //中间  当前的根结点的前一个（PRE）结点就是链表尾          tnCur.left=tnLastNodeInList;                    if (tnLastNodeInList!= null ){ //只要是当前的链表尾不是空的那么就可以设置当前链表的下一个（POST）结点              tnLastNodeInList.right=tnCur;          }          //链表尾部结点向后移动          tnLastNodeInList=tnCur;          //右边重复上边的操作          if (tnCur.right!= null ){              tnLastNodeInList=convertNode(tnCur.right, tnLastNodeInList);          }          return  tnLastNodeInList;      }   }

3. 字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。 

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

import  java.util.*; public  class  Solution {      public  ArrayList<String> Permutation(String str) {          ArrayList<String> strList =  new  ArrayList<String>();          if  (str ==  null  || str.equals( "" )) {              return  strList;          }          strList = arrangeStr(str.toCharArray(),  0 , strList);          Collections.sort(strList);            return  strList;      }        /**       * 采用递归策略实现字符串的全排列: 我们将字符序列看作是两部分，一部分是第一个字符，第二部分是后面的所有字符。       * Step1:首先求出所有可能出现在第一个位置的字符，也就是将第一个字符同后面所有的字符进行交换       * Step2：固定第一个字符，求后面所有字符的排列序列。 后面的字符我们仍然分为两个部分，第一个字符和第一个字符后面的字符。       *       * @param strCharArray       * @param begin       * @param strList       * @return       */      private  ArrayList<String> arrangeStr( char [] strCharArray,  int  begin,              ArrayList<String> strList) {          // 一直安排到最后一个字符就终止          if  (begin == strCharArray.length -  1 ) {              strList.add(String.valueOf(strCharArray));          }  else  {              // 对第一个字符进行设置交换 从不交换开始              for  ( int  i = begin; i < strCharArray.length; ++i) {                  if  (strNothas(strCharArray, i, begin)) {                      char  temp = strCharArray[begin];                      strCharArray[begin] = strCharArray[i];                      strCharArray[i] = temp;                        arrangeStr(strCharArray, begin +  1 , strList);                        temp = strCharArray[begin];                      strCharArray[begin] = strCharArray[i];                      strCharArray[i] = temp;                  }                }          }            return  strList;      }        private  boolean  strNothas( char [] strCharArray,  int  i,  int  begin) {          if  (i == begin) {              return  true ;          }  else  {              for  ( int  j = begin; j < i; j++) {                  if  (strCharArray[i] == strCharArray[j]) {                      // 如果在begin到i之间存在一个重复的就不要进行交换                      return  false ;                  }              }          }          return  true ;      }   }