剑指offer 50与51


剑指offer 50与51

1.面试题50. 第一个只出现一次的字符

method1:使用map存储每个字符对应出现的次数,再遍历一次s,若当前字符出现次数是1次,就返回。

class Solution {
public:
    char firstUniqChar(string s) {
        map<char,int> m;
        for(auto c : s) {
            m[c]++;
        }
        char res=' ';
        for(auto c : s) {
            if(m[c]==1) {
                res = c;
                break;
            }
        }
        return res;
    }
};

method2:哈希思想,数组模拟

class Solution {
public:
    char firstUniqChar(string s) {
        int cs[26]={0};
        for(auto c : s) {
            cs[c -'a']++;
        }
        char res = ' ';
        for(auto c : s) {
            if(cs[c - 'a']==1) {
                res = c;
                break;
            }
        }
        return res;
    }
};

2.面试题51. 数组中的逆序对

method1:归并排序

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        return reversePairs(nums,0,nums.size()-1);
    }
    // 对于一个大小为N的数组,其最大的逆序数对个数为:n*(n-1)/2,非常容易产生整形溢出,而题目中给定的最大n为50000,满足在int范围。
    // merge函数求出在nums[l...mid]和arr[mid+1...r]有序基础上,arr[l...r]的逆序对个数
    int __merge(vector<int>& nums,int left,int mid,int right) {
        vector<int> newNums(right-left+1);
        for(int i=left;i<=right;i++) {
            newNums[i-left] = nums[i];
        }
        int ret = 0;
        int i=left;
        int j=mid+1;
        int k=left;
        while(i<=mid || j<=right) {
            if(i>mid) {
                while(j<=right) {
                    nums[k++] = newNums[j-left];
                    j++;
                }
            } else if(j>right) {
                while(i<=mid) {
                    nums[k++] = newNums[i-left];
                    i++;
                }
            } else if(newNums[i-left]<=newNums[j-left]) {
                nums[k++] = newNums[i-left];
                i++;
            } else { // 右半部分 <= 左半部分
                nums[k++] = newNums[j-left];
                j++;
                // 此时, 因为右半部分k所指的元素小
                // 这个元素和左半部分的所有未处理的元素都构成了逆序数对
                // 左半部分此时未处理的元素个数为 mid - i + 1
                ret += mid- i + 1;
            }
        }
        return ret;
    }
    int reversePairs(vector<int>& nums,int left,int right) {
        if(left>=right) {
            return 0;
        }
        int mid = left + (right-left)/2;
        int res1 = reversePairs(nums,left,mid);
        int res2 = reversePairs(nums,mid+1,right);
        return res1+res2+__merge(nums,left,mid,right);
    }
}

更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录