【leetcode】228. 汇总区间

题目内容

228. 汇总区间

思路分析

本题的算法感觉就是个自然而然的算法，也没有什么技巧。但是自己写的代码好蠢，还分各种情况讨论。答案的代码又精简，又把所有的情况考虑进去了。向答案学习。

方法一：一次遍历

参考资料

本题目在以下两个情况下会产生新区间：

遍历到最后一个数，必须得输出一个新区间
数字不连续，即nums[i] != nums[i+1]

按照区间长度是否等于1，输出又分为两种情况。因此可以使用指针来追踪区间的两个端点。

代码

#include <vector>
#include <math.h>
#include <limits.h>
#include <string>

using namespace std;

// 一次遍历（自己写的）
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution1 {
public:
    void push_into_result(int start, int stop, vector<string>& result) {
       if (start == stop) {
         result.push_back(to_string(start));
       } else {
         result.push_back(to_string(start) + "->" + to_string(stop));
       }
    }

    vector<string> summaryRanges(vector<int>& nums) {
       int n = nums.size();

       vector<string> result;

       if (n == 0) return result;

       int start{ nums[0] }, stop { nums[0] };
       if (n == 1) {
          push_into_result(start, stop, result);
          return result;
       }

       for (int i = 1; i < n; ++i) {
          if (nums[i] == nums[i - 1] + 1) {
             stop = nums[i];
          } else{
             push_into_result(start, stop, result);
             start = nums[i];
             stop = nums[i];
          }
       }

       push_into_result(start, stop, result);

       return result;
    }
};

// 一次遍历（抄答案的）
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
       vector<string> result;
       int left = 0;

       for (int i = 0; i < nums.size(); ++i) {
          // 当遍历到最后一个数或nums[i]与后一个数不连续时得到一个新区间
          if (i + 1 == nums.size() || nums[i] + 1 != nums[i + 1]) {
             // 令left总是为新区间的左端点
             // 得到新区间时判断left与i的相对位置
             // 若left==i，则为左右端点在同一点的区间
             // 若left!=i，则区间的左右端点为[nums[left], nums[i]]
             // 令left = i + 1来保证left为新区间的左端点
             result.push_back(to_string(nums[left])
                + (left == i ? "" : ("->" + to_string(nums[i]))));
             left = i + 1;
          }
       }

       return result;
    }
};

int main() {
   Solution s;
   vector<int> input{  };
   vector<string> result = s.summaryRanges(input);
   int a = 0;
}

收获

自己写的代码太Low了