每日一题之《剑指offer》34,35题

第34题：第一个只出现一次的字符

难易度：⭐

题目描述：
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符
并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

本题是对哈希表这种数据结构应用的考察，将传入的字符串变成char数组后，每一个字母字符对应hashmap的key,它是第几次出现的则作为value,如果出现了两次以上，那么就将value赋值给-1;思路很简单，代码如下：

import java.util.HashMap;
import java.util.Map.Entry;

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str == null || str.length() == 0){
            return -1;
        }
        
        HashMap<Character,Integer> map = new HashMap<>();
        char[] chs = str.toCharArray();
        for(int i = 0;i < chs.length;i++){
            if(map.containsKey(chs[i])){
                map.put(chs[i],-1);
            }else{
                map.put(chs[i],i);
            }
        }
        int res = -1;
        boolean flag = true;
        for(Entry<Character,Integer> entry : map.entrySet()){
            if(entry.getValue() != -1 && flag){
                res = entry.getValue();
                flag = false;
            }else{
                if(res > entry.getValue() && entry.getValue() != -1){
                    res = entry.getValue();
                }
            }
        }
        return res;
    }
}

第35题：数组中的逆序对

难易度：⭐⭐

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数P。
并将P对1000000007取模的结果输出。 即输出P%1000000007

本题考察的内容是对归并排序的理解，可以参考我的文章时间复杂度的认识,递归,归并排序
如果依次遍历计算逆序对那么时间复杂度为O(n ^２)，但是本题的最优解应该是O(n logn),如果理解了归并排序，那么也很容易理解这道题的代码，相似的还有小和问题。
代码如下：

public class Solution {
    public static int result = 0;
    public int InversePairs(int [] array) {
        mergeSort(array);
        return result;
    }
    
    public static void mergeSort(int[] arr){
        sort(arr,0,arr.length - 1);
    }
    public static void sort(int[] arr,int l,int r){
        if(l < r){
            int mid = l + ((r - l) >> 1);
            sort(arr,l,mid);
            sort(arr,mid + 1,r);
            merge(arr,l,mid,r);
        }
    }
    public static void merge(int[] arr,int l,int mid,int r){
        int p1 = l;
        int p2 = mid + 1;
        int[] help = new int[r - l + 1];
        int i = 0;
        while(p1 <= mid && p2 <= r){
            result = arr[p1] > arr[p2] ? (result + (r - p2 + 1))%1000000007 : result;
            help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while(p2 <= r){
            help[i++] = arr[p2++];
        }
        for(i = 0;i < help.length;i++){
            arr[l + i] = help[i];
        }
    }
}