day30

1.剑指 Offer 17. 打印从 1 到最大的 n 位数

 1）直接列举（执行用时比分治短）

 1 class Solution {
 2 public:
 3     vector<int> printNumbers(int n) {
 4       vector<int> res;
 5       int num = 0;
 6       for(int i = 0;i < n;i ++)
 7           num = num * 10 + 9;
 8       for(int i = 1;i <= num;i ++)
 9          res.push_back(i);
10       return res;
11     }
12 };

  2）分治

 1 class Solution {
 2 public:
 3     vector<int> printNumbers(int n) {
 4        int l = 1,r = 0;
 5        for(int i = 0;i < n;i ++)
 6          r = r * 10 + 9;
 7        fun(l,r);
 8        return res;
 9     }
10 
11 private:
12     vector<int> res;
13     void fun(int l,int r){
14         if(l == r){
15             res.push_back(l);
16             return;
17         }
18         fun(l,l + ((r - l) >> 1));
19         fun(l + ((r - l) >> 1) + 1,r);
20     }
21 };

2.剑指 Offer 51. 数组中的逆序对

 分治 + 归并排序

 1 class Solution {
 2 public:
 3     int reversePairs(vector<int>& nums) {
 4        int n = nums.size();
 5        vector<int> tmp(n);
 6        return mergeSort(nums,tmp,0,n - 1);
 7     }
 8 
 9 private:
10     int res;
11     int mergeSort(vector<int>& nums,vector<int>& tmp,int l,int r){
12         if(l >= r)  return 0;
13         int mid = (l + r) >> 1;
14         res = mergeSort(nums,tmp,l,mid) + mergeSort(nums,tmp,mid + 1,r);
15         int i = l,j = mid + 1;
16         for(int k = l;k <= r;k ++)
17           tmp[k] = nums[k];
18         for(int k = l;k <= r;k ++){
19             if(i == mid + 1)  nums[k] = tmp[j ++];
20             else if(j == r + 1 || tmp[i] <= tmp[j])  nums[k] = tmp[i ++];
21             else{  //tmp[i] > tmp[j] (逆序对)
22                nums[k] = tmp[j ++];
23                res += mid - i + 1;
24             }
25         }
26         return res;
27     }
28 };