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 };
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/277200.html