LC 163. Missing Ranges 【lock, hard】

Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

example:

Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]

这题应该是实现的细节处理，最大整数，最小整数比较难，也是调了很久的corner case才调出来的。

好不容易Accept了，自己写的还是有点惨。

还要注意

if(lower++ == something) something;

不管判断对不对，lower都会自增的，要当心。

AC第一版

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 struct TreeNode {
 5     int val;
 6     TreeNode *left;
 7     TreeNode *right;
 8     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 9 };
10 15 
16 
17 vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
18   vector<string> ret;
19   vector<int> processed;
20   for(int i=0; i<nums.size(); i++){
21     if(processed.empty() || processed.back() != nums[i]){
22       processed.push_back(nums[i]);
23     }
24   }
25   nums.clear();
26   //for(auto i : processed) nums.push_back(i);
27   
28   for(auto i : processed) cout << i << " ";
29   cout << endl;
30   nums = processed;
31   if(lower == upper) {
32     if(!nums.empty()) return ret;
33     else ret.push_back(to_string(lower));
34     return ret;
35   }
36   if(nums.empty()){
37     ret.push_back(to_string(lower) + "->" + to_string(upper));
38     return ret;
39   }
40   for(int i=0; i<nums.size(); i++){
41     //cout << lower << "and" << nums[i] << endl;
42     if (lower == nums[i]) {
43       lower++;
44       continue;
45     }
46     
47     if(lower+1 == nums[i]) ret.push_back(to_string(lower));
48     else ret.push_back(to_string(lower) + "->" + to_string(nums[i]-1));
49     if(nums[i] == (1 << 31)-1) return ret;
50     lower = nums[i]+1;
51   }
52   //cout << lower << upper << endl;
53   if(lower > upper) return ret;
54   if(lower == upper) ret.push_back(to_string(lower));
55   else ret.push_back(to_string(lower) + "->" + to_string(upper));
56   return ret;
57 }

AC 第二版

简化了一些代码

vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
  vector<string> ret;
  vector<int> processed;
  // filter duplicate
  for(auto val : nums) {
    if(processed.empty() || processed.back() != val) processed.push_back(val);
  }
  nums.clear();
  nums = processed;
//   for(auto i : processed) cout << i << " ";
//   cout << endl;
  // corner case 1: lower == upper
  if(lower == upper) {
    if(nums.empty()) ret.push_back(to_string(lower));
    return ret;
  }
  for(int i=0; i<nums.size(); i++){
    if (lower != nums[i]) {
      if(lower+1 == nums[i]) ret.push_back(to_string(lower));
      else ret.push_back(to_string(lower) + "->" + to_string(nums[i]-1));
    }
    if(nums[i] == (1 << 31)-1) return ret;
    lower = nums[i]+1;
  }
  //cout << lower << upper << endl;
  if(lower == upper) ret.push_back(to_string(lower));
  else if(lower < upper) ret.push_back(to_string(lower) + "->" + to_string(upper));
  return ret;
}