《剑指offer》算法题第十天

今日题目：

数组中的逆序对
两个链表的第一个公共节点
数字在排序数组中出现的次数
二叉搜索树的第k大节点
字符流中第一个不重复的字符

1. 数组中的逆序对

题目描述：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。

思路：
这道题运用归并排序的思想来求解，归并排序是面试中经常问到的知识点，得经常翻出来熟悉熟悉。

代码如下：

 public class Solution {

     int cnt;

     public int InversePairs(int[] array) {

         cnt = 0;

         if (array != null)

             mergeSortUp2Down(array, 0, array.length - 1);

         return cnt;

     }

     /*

      * 归并排序(从上往下)

      */

     public void mergeSortUp2Down(int[] a, int start, int end) {

         if (start >= end)

             return;

         int mid = (start + end) >> 1;

         mergeSortUp2Down(a, start, mid);

         mergeSortUp2Down(a, mid + 1, end);

         merge(a, start, mid, end);

     }

     /*

      * 将一个数组中的两个相邻有序区间合并成一个

      */

     public void merge(int[] a, int start, int mid, int end) {

         int[] tmp = new int[end - start + 1];

         int i = start, j = mid + 1, k = 0;

         while (i <= mid && j <= end) {

             if (a[i] <= a[j])

                 tmp[k++] = a[i++];

             else {

                 tmp[k++] = a[j++];

                 cnt += mid - i + 1;  // core code, calculate InversePairs............

                 cnt %= 1000000007;

             }

         }

         while (i <= mid)

             tmp[k++] = a[i++];

         while (j <= end)

             tmp[k++] = a[j++];

         for (k = 0; k < tmp.length; k++)

             a[start + k] = tmp[k];

     }

 }

2.两个链表中的第一个公共节点

题目描述：

输入两个链表，找出它们的第一个公共结点。

思路：
《剑指offer》中的参考答案利用了两个栈来分别存储两个链表，然后从链尾到链头遍历两个链表，寻找公共的节点。但是博主觉得没必要那么麻烦，运用一个hashset就能够处理这道题。
另外，在这道题的讨论区中，有一个特别精妙的方法，利用两个指针遍历数组，第一趟得到链表长度的差值，第二趟寻找公共节点，下面也会贴出来。

代码如下：

//利用hashset

import java.util.HashSet;

public class Solution {

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        if(pHead1 == null || pHead2 == null) return null;

        HashSet<ListNode> set = new HashSet();

        while(pHead1 != null){

            set.add(pHead1);

            pHead1 = pHead1.next;

        }

        while(pHead2 != null){

            if(set.contains(pHead2))

                return pHead2;

            pHead2 = pHead2.next;

        }

        return null;

    }

}

//两个指针的方法

public class Solution {

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        ListNode p1 = pHead1;

        ListNode p2 = pHead2;

        while(p1 != p2){

            p1 = (p1==null ? pHead2 : p1.next);

            p2 = (p2==null ? pHead1 : p2.next);

        }

        return p1;

    }

}

3.数字在排序数组中出现的次数

题目描述：

统计一个数字在排序数组中出现的次数。

思路：
比较直接的方法是直接遍历数组，统计目标数字出现的次数，时间复杂度为O(n)。
比较快的方法是利用二分查找的思想，时间复杂度可达到O(logn)。

代码如下：

 public class Solution {

     int count = 0;

     public int GetNumberOfK(int [] array , int k) {

         binSearch(array,k,0,array.length-1);

         return count;

     }

     public void binSearch(int[] nums,int k,int start,int end){

         if(start == end){

             if(nums[start] == k) count++;

             return;

         }else if(start < end){

             int mid = (start+end)/2;

             if(nums[mid] == k){

                 count++;

                 binSearch(nums,k,start,mid-1);

                 binSearch(nums,k,mid+1,end);

             }else if(nums[mid] < k){

                 binSearch(nums,k,mid+1,end);

             }else{

                 binSearch(nums,k,start,mid-1);

             }

         }

     }

 }

4.二叉搜索树的第k大节点

题目描述：

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

思路：
比较直接，二叉树的中序遍历。不过需要提一下的是，二叉树三种遍历顺序的递归和迭代实现方式都得非常熟悉。

代码如下：

 import java.util.Stack;

 public class Solution {

     TreeNode KthNode(TreeNode pRoot, int k){

         if(pRoot == null || k == 0) return null;

         Stack<TreeNode> stack = new Stack();

         int count = 0;

         while(pRoot != null || !stack.isEmpty()){

             if(pRoot != null){

                 stack.push(pRoot);

                 pRoot = pRoot.left;

             }else{

                 pRoot = stack.pop();

                 count++;

                 if(count == k)

                     return pRoot;

                 pRoot = pRoot.right;

             }

         }

         return null;

     }

 }

5.字符流中第一个不重复的字符

题目描述：

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

思路：
这道题和之前的求一个数据流中的中位数的题相似，重点是如何选择一个合适的数据结构来存储数据，是的插入和查询的效率都比较高。
在这道题中，《剑指offer》给的参考答案是声明一个int型的数组来存储各个字符的状态。这种思想非常地重要，应多做练习来熟悉。

代码如下：

 public class Solution {

     //Insert one char from stringstream

     int[] map = new int[256];

     int index = 1;

     public void Insert(char ch)

     {//0代表还未出现相应的字符，-1代表出现一次以上，其他数字代表什么时候出现

         if(map[ch] == 0)

             map[ch] = index;

         else if(map[ch] > 0)

             map[ch] = -1;

         index ++;

     }

   //return the first appearence once char in current stringstream

     public char FirstAppearingOnce()

     {

         int min = Integer.MAX_VALUE;

         int ind = -1;

         for(int i = 0; i < 256; i++){//找出大于0的最小值及其坐标

             if(map[i] > 0 && map[i] < min){

                 min = map[i];

                 ind = i;

             }

         }

         if(ind == -1)//不存在大于0的数，则没有字符出现一次

             return '#';

         else

             return (char)ind;

     }

 }

巴特西

《剑指offer》算法题第十天

最新文章

热门文章