剑指offer时间效率39-48

优化时间效率

• 剑指 Offer 39. 数组中出现次数超过一半的数字
• • 题目
  • 代码
• 剑指 Offer 40. 最小的k个数
• • 题目
  • 代码
• 剑指 Offer 41. 数据流中的中位数
• • 题目
  • 代码
• 剑指 Offer 43. 1～n 整数中 1 出现的次数
• • 题目
  • 代码
• 剑指 Offer 44. 数字序列中某一位的数字
• • 题目
  • 代码
• 剑指 Offer 45. 把数组排成最小的数
• • 题目
  • 代码
• 剑指 Offer 46. 把数字翻译成字符串
• • 题目
  • 代码
• 剑指 Offer 47. 礼物的最大价值
• • 题目
  • 代码
• 剑指 Offer 48. 最长不含重复字符的子字符串
• • 题目
  • 代码

剑指 Offer 39. 数组中出现次数超过一半的数字

题目

代码

摩尔投票法：
核心理念为 票数正负抵消。
假设第一个数为众数，往后遍历，如果当前数等于众数，票数加一，否则票数减一，每当票数为零，重新当前遍历的数为众数，重复操作，最后剩下的数即为众数。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //摩尔投票法
        int votes = 0, x = 0;
        for(auto a: nums) {
            if(votes == 0) {
                //假设当前数为众数
                x = a;
            }
            if(x == a) {
                votes = votes + 1;
            }else {
                votes = votes - 1;
            }
        }
        return x;
    }
};

分治法

class Solution {
public:
    //target出现次数
    int majorityElement_count(vector<int>& nums, int target, int lo, int hi) {
        int count = 0;
        for(int i = lo; i <= hi; i++) {
            if(nums[i] == target) {
                count++;
            }
        }
        return count;
    }
    int majorityElement_rec(vector<int>& nums, int lo, int hi) {
        if(lo == hi) {
            return nums[lo];
        }
        int mid = lo + (hi - lo)/2;
        int leftmajor = majorityElement_rec(nums, lo, mid);
        int rightmajor = majorityElement_rec(nums, mid + 1, hi);
        //判断出现次数是否超过一半
        if(majorityElement_count(nums, leftmajor, lo, hi) > (hi - lo + 1 ) / 2) {
            return leftmajor;
        }
        if(majorityElement_count(nums, rightmajor, lo, hi) > (hi - lo + 1) / 2) {
            return rightmajor;
        }
        return - 1;
    }
    int majorityElement(vector<int>& nums) {
        return majorityElement_rec(nums, 0, nums.size() - 1);
    }
};

剑指 Offer 40. 最小的k个数

题目

代码

方法一：堆
大根堆的根节点为最大值

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        //优先队列为大根堆，使大根堆实时维护数组的前k小值
        vector<int>res;
        priority_queue<int> pq;
        for(int i = 0; i < k; i++) {
            pq.push(arr[i]);
        }
        for(int i = k; i < arr.size(); i++) {
            if(arr[i] < pq.top()) {
            //弹出堆顶元素
                pq.pop();
                pq.push(arr[i]);
            }
        }
        while(!pq.empty()) {
            res.push_back(pq.top());
            pq.pop();
        }
        return res;
    }
};

方法二:
基于快速排序的数组划分

class Solution {
public:
//基于快速排序的数组划分
//根据快速排序原理，如果某次划分后 基准数正好是第 k+1 小的数字 ，那么此时基准数左边的所有数字便是最小的 k 个数。
    vector<int> fastsort(vector<int>& arr, int l, int r, int k) {
        int i = l, j = r, x = arr[l];
        //随机取基准值
        while(i < j) {
            //找到第一个大于x的
            while(i < j && arr[j] > x) {
                j--;
            }
            if(i < j) {
                arr[i++] = arr[j];
            }
            while(i < j && arr[i] < x) {
                i++;
            }
            if(i < j) {
                arr[j--] = arr[i];
            }  
        }
        arr[i] = x;
        if(i > k) {
            return fastsort(arr,l, i - 1, k);
        }
        if(i < k) {
            return fastsort(arr, i+1, r, k);
        }
        //此时返回前K个数字
        vector<int>res;
        res.assign(arr.begin(), arr.begin() + k);
        return res;
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        return fastsort(arr, 0, arr.size() - 1, k);
    }
};

剑指 Offer 41. 数据流中的中位数

题目

代码

class MedianFinder {
public:
    /** initialize your data structure here. */
    //大顶堆
    priority_queue<int,vector<int>,less<int>>maxheap;
    //小顶堆
    priority_queue<int,vector<int>,greater<int>>minheap;

    MedianFinder() {

    }
    
    void addNum(int num) {
        //判断大顶堆与小顶堆元素个数是否相等,相等则先放入minheap中，调整排序后弹出
        //存入maxheap中
        if(maxheap.size() == minheap.size()) {
            minheap.push(num);
            int top = minheap.top();
            minheap.pop();
            maxheap.push(top);
        }else {
            maxheap.push(num);
            int top = maxheap.top();
            maxheap.pop();
            minheap.push(top);
        }
    }
    
    double findMedian() {
        //个数为偶数，取平均值
        if(maxheap.size() == minheap.size()) {
            return (maxheap.top()+minheap.top())*1.0/2;
        }else {
            return maxheap.top()*1.0;
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

剑指 Offer 43. 1～n 整数中 1 出现的次数

题目

代码

class Solution {
   public:
    int countDigitOne(int n) {
        // "1"出现的次数 = sum ("1"在各个计数位上出现的次数)
        // 从个位开始向最高位统计
        // 以3101592为例
        // 将数字拆分为[a...][cur][b...]
        // cur 为当前位
        long base = 1;
        int res = 0;
        while (base <= n) {
            // 计算 a..., cur, b...
            int a, cur, b;
            a = n / base / 10;
            cur = (n / base) % 10;
            b = n % base;
            // 将当前位设为1，考察其他部分的变化范围
            if (cur > 1) {
                // 一、cur > 1，
                //          [3101 ] 5 [92]
                // 变化范围：[0-3101] 1 [0-99]
                // 总个数：   (a+1)  *  base
                res += (a + 1) * base;
            } else if (cur == 1) {
                // 二、cur == 1，
                //             [310] 1 [592]
                // 1、变化范围 [0-309] 1 [0-999]
                //              a    *  base
                // 2、变化范围 [310]   1 [0-592]
                //               1   *   (b+1)
                // 总个数：a *base + (b + 1)
                res += a*base + b + 1;

            } else {
                // 三、cur < 1，
                //           [31] 0 [1592]
                // 变化范围 [0-30] 1 [0-9999]
                // 总个数    a     *   base
                res += a * base;
            }
            // 统计更高一位
            base *= 10;
        }
        return res;
    }
};

剑指 Offer 44. 数字序列中某一位的数字

题目

代码

class Solution {
public:
    int findNthDigit(int n) {
        long start=1; //每个位数最小值
        long count=9;//各 digit下的数位数量
        int digit=1;
        while(n>count){
            n=n-count;
            digit++;
            start=start*10;
            count=9*start*digit;
        }
        //num是所求数位在从数字 start开始的第 [(n - 1) / digit][(n−1)/digit] 个数字中
        int num=start+(n-1)/digit;  
        //举个例子，9是第9位，10~99共180位，189位就是99中的后一个9，
        //那么按程序走，189-9=180=n，不进入循环，所以start=10，(180-1)/2=89余1，
        //这180位是从start前一位(9)开始算的，所以要-1，否则就是从start(10)中的1开始加了
        count=(n-1)%digit;     //计算是该数字第几位
        string s=to_string(num);
        int ans=s[count]-'0';
        return ans;
    }
};

剑指 Offer 45. 把数组排成最小的数

题目

代码

class Solution {
public:
    void quicksort(vector<string>& strs, int l, int r) {
        if(l > r) {
            return ;
        }
        int i = l, j = r;
        while(i < j) {
            //若拼接字符串 x + y > y + x ，则 x “大于” y ，这一步是因为x和y可能是多位数
            while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j--;
            while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;
            swap(strs[i], strs[j]);
        }
        swap(strs[i], strs[l]);
        quicksort(strs, l, i - 1);
        quicksort(strs, i + 1, r);
    }
    string minNumber(vector<int>& nums) {
        string res;
        vector<string>strs;
        for(auto a:nums) {
            //把每一个数字转换成string
            strs.push_back(to_string(a));
        }
        quicksort(strs, 0, strs.size() - 1);
        for(string b:strs) {
            res.append(b);
        }
        return res;
    }
};

剑指 Offer 46. 把数字翻译成字符串

题目

代码

class Solution {
public:
    int translateNum(int num) {
        //类似青蛙跳台阶，跳1或者跳2
        string str = to_string(num);
        int n = str.size();
        int res = 0;
        vector<int>dp(n+1);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            int n = (str[i - 2] - '0')*10 + (str[i - 1] - '0');
            if(n >= 10 && n <= 25) {
                dp[i] = dp[i-1] + dp[i-2];
            }else {
                dp[i] = dp[i-1];
            }    
        }
        res = dp[n];
        return res;
    }
};

剑指 Offer 47. 礼物的最大价值

题目

代码

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int maxvalue = 0;
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>>dp(m,vector<int>(n));
        dp[0][0] = grid[0][0];
        //初始化第一行
        int i , j ;
        for( i = 0, j = 1; j < n; j++) {
            dp[i][j] = dp[i][j - 1] + grid[i][j];
        }
        //初始化第一列
        for( i = 1, j = 0; i < m; i++) {
            dp[i][j] = dp[i - 1][j] + grid[i][j];
        }
       
        for( i = 1; i < m; i++) {
            for( j = 1; j < n; j++) {
                //每个位置只能从左或者上来
                dp[i][j] = max(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j]);
            }
        }
        maxvalue = dp[m-1][n-1];
        return maxvalue;
    }
};

剑指 Offer 48. 最长不含重复字符的子字符串

题目

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //滑动窗口,字符对应索引
        unordered_map<char, int>m;
        int sz = s.size();
        int left = 0,right = 0, res = 0;
        while(right < sz) {
            //窗口内已经存在该字符
            if(m.find(s[right]) != m.end() && left <= m[s[right]]) {
                //缩小窗口大小，移动到重复字符所在位置的右边
                left = m[s[right]] + 1; 
            }
            if(right - left + 1 > res) {
                res = right - left + 1;
            }
            m[s[right]] = right;
            right++;
        }
        return res;
    }
};