算法题摘录二

转载请注明原文地址:http://www.cnblogs.com/ygj0930/p/6428533.html

心得：编码之前先设计测试用例，这样在编码时就会容易兼顾各种细节错漏。用例可以用边界值法来设计。

1:删除链表中的某结点

传统解法：从头遍历到被删除结点，同时记录被删结点的前结点，然后用前结点->next指向被删结点->next来跳过这个结点，再把结点删除。如果结点是尾结点的话，这中解法是O（n）的。

优化解法：用被删结点的->next结点的值复制给被删结点，把被删结点“变”成了其下结点，于是问题变成了删除其下结点即可。而此时被删结点就是其下结点的前结点，直接令被删结点->next等于其下结点的->next即可。特殊情况为：链表只有一个结点，则把head->next=null即可；删除的是链表的尾结点，则遍历整个链表直到倒数第二个结点，令其next为空即可。

2：调整数组中数的位置，把奇数全部移动到数组前面

这种按照某规则改变数组中元素位置的题目，传统解法都是用“双指针迫近法”，一个指针从前面往后找，一个从后面往前找，找到符合交换条件的就互换两指针所指元素。

这里，我们写出一个通用的方法来做这类数组交换题，交换规则用一个函数来指定。这样，以后改用不同规则时直接在交换的判断条件处调用规则函数即可。

public void Exchange(int[] nums)
   {
       if(nums==null){
           return;
       }
       int begin=0;
       int end=nums.length-1;
       while(begin<end){
           //在判断处调用函数，以后用不同规则，比如偶数移到前时，修改规则函数即可
           while(begin<end && isOdd(nums[begin])){
               ++begin;
           }
           while(begin<end && !isOdd(nums[end])){
               --end;
           }
           if(begin<end){
               int temp=nums[begin];
               nums[begin]=nums[end];
               nums[end]=temp;
           }
       }
   }
   public boolean isOdd(int n){
       return (n&1)==1;
   }

3：找到链表中倒数第K个结点

传统解法：从头到尾遍历一次链表得链表总共有n个结点，那么倒数第K个结点就是从头数起第n-k+1那个结点。第二次遍历到第n-k+1个结点输出即可。

优化解法：遍历一次即可。首先从头到尾遍历整个链表，把每个结点以 index——value 的映射形式保存到一个map中。一次遍历完成后可知共n个结点，此时直接map.get(n-k+1)即可。

双指针（下标）解法：由n-(n-k+1)=k-1可知，链表尾结点比倒数第K个结点多了k-1步。那么我们可以定义一个下标p1，令其先行k-1步。然后定义一个下标p2从链表头开始走。每次p1,p2都递增一步，直到p1到达尾结点，那么此时p2指向的正好是倒数第k个结点。此法需要考虑的特殊情况有：链表为空时，p1不能行k步；链表长<k时，不能找到倒数第K个结点；K=0时，没有-1这个结点供查找。

4：反转链表：输入一个链表头，反正链表并把反转后链表头输出。

要反转链表，只需把头结点的next设为null，而后面各个结点的为其next设为当前结点即可。注意：在修改下个结点的next指针为当前结点时，需要先保存当前结点的next，以访问下个结点。然后再把当前结点的next指向其前面的结点。否则，如果先改方向，则会出现断裂，此时的next是指向原前置结点了，那么后面的结点就访问不到，也就改不了方向了。

5：合并两个有序链表

两个有序链表的合并其实就是跟归并排序差不多，每次比较两个链表头，取小的插入新链表，更新指针位置执行下一个“链表头”，递归使用这个函数就可以了。易错点在于，如果合并双方有一个是空链表时，那么合并结果显然就是非空的那一个，直接返回那个非空的链表即可。

6：判断二叉树B是不是二叉树A的子结构（即二叉树A中是否包含二叉树B）

对于二叉树的问题，我们第一时间想到用递归去解决。

这里判断树B是不是树A的子结构，只需遍历树A，找到B的根节点值的结点，然后从这个结点展开递归遍历逐层比较A、B两树的各层子结点值，直到B树到底则返回true，否则（A树先到底，或者有一个结点不同）则返回false。

 public boolean A_find_B(TreeNode rootA,TreeNode rootB){
       boolean res=false;
       if(rootA!=null && rootB!=null){
           if(rootA.value==rootB.value){
               res=A_find_B_Recursively(rootA, rootB);
           }
           //从左子树递归找B的根,一旦找到了，修改res，那么就不用在右子树找了
           if(!res){
               res=A_find_B(rootA.left, rootB);
           }
           //从右子树递归找B的根
           if(!res){
               res=A_find_B(rootA.right, rootB);
           }
       }
       return res;
   }
   //把A中找到的B根结点传进来，递归地比较各层结点值
   public boolean A_find_B_Recursively(TreeNode node_of_A,TreeNode rootB){
       if(node_of_A==null){
           return false;
       }
       if(rootB==null){
           return true;
       }
       if(node_of_A.value!=rootB.value){
           return false;
       }
       return A_find_B_Recursively(node_of_A.left, rootB) &&  A_find_B_Recursively(node_of_A.right, rootB);
   }

7：顺时针/逆时针打印矩阵

这道题单纯考循环以及对边界的掌控：观察打印规律我们可知：每圈的打印都是从矩阵对角线上的点开始的，并且打印 rows/2 圈即可完成全部点的打印。所以我们用矩阵对角线上的点作为每圈开始坐标nums[start][start]。用一个循环来控制打印多少圈以及各圈的开始坐标。再实现一个函数专门负责从开始坐标打印一圈。

public void printMatrix(int[][] nums){
      int rows=nums.length;
      int cols=nums[0].length;
      
      if (nums==null || rows<=0 || cols<=0) {
        return;
    }
      int start=0;
      //用start标记每圈的起点，并控制循环次数
      while(cols>start*2 && rows>start*2){
          Print_one_Circle(nums,cols,rows,start);
          ++start;
      }
  }
  public void  Print_one_Circle(int[][] nums,int cols,int rows,int start) {
    //由start得出该圈的范围
      int endRow=rows-1-start;
      int endCol=cols-1-start;
      //右start和endCol从左往右打印一行
      for(int i=start;i<=endCol;++i){
          System.out.print(nums[start][i]+",");
      }
      //接着上面结束的地方的下面一个点，从上往下打印第endCol列
      for(int i=start+1;i<=endRow;++i){
          System.out.print(nums[i][endCol]+",");
      }
      //接着从右往左打印第endRow行。注意打印的起点是上面打印的终点的左边。上面打印结束于nums[endRow][endCol]，所以这里起点是nums[endRow][endCol-1]
      for(int j=endCol-1;j>=start;--j){
          System.out.print(nums[endRow][j]+",");
      }
      //接着上面结束的地方从下往上打印当前圈第0列,注意终点是在nums[start][start]的下面一个点。
      for(int j=endRow-1;j>start;--j){
          System.out.print(nums[j][start]+",");
      }
   }

8：实现一个栈，使得O（1）时间就可以直接获得栈内最小值。

我们可以定义一个辅助栈专门用来存放最小值。当一个数入数据栈data-stack时，把这个数与辅助栈顶端数比较，取二者间小者作为这个数对应的最小值存入辅助栈。这样每次取min时直接从辅助栈获取top()即是数据栈中最小值。而每次pop()时同时把数据栈和辅助栈顶弹出即可保证数据栈顶元素时刻对应辅助栈顶。

9：由栈的输入序列，判断一个输出序列是否合法

注意，这里不是先全部输入再输出的，有可能在输入的间隙有输出。所以不能单纯用倒序来判断。

我们直到，栈每次弹出栈顶，所以弹出序列每一个数都对应输入序列的当前栈顶。由此我们就可以得到此题解法：

用一个数组pops[]存放弹出序列，index=0指向第一个元素，也就是第一个出栈的元素值。

定义一个栈，每次用栈顶元素与pops[index]比较看栈顶是不是第一个出栈的元素，是则弹出，同时index++，指向下一个出栈的元素；否，则说明当前栈顶不是第一个出栈的，继续输入，把下一个元素入栈；再比较.....重复以上操作：直到所有输入序列已全部入栈而栈顶还没弹出则说明该pop序列非法；如果最后pops[]序列遍历完并且栈内元素全部弹出则说明pop序列合法。

10：从上往下打印二叉树，同层的从左往右打印

二叉树的按层遍历，用队列的“先进先出”实现按层打印：每次取出并打印队首，则把队首的子节点入队。