［LeetCode］Summary Ranges-白红宇

［LeetCode］Summary Ranges

阅读量：2236 次

发布时间：2019-05-09

本文共 1714 字，大约阅读时间需要 5 分钟。

解题思路：

1，凡是数组nums中元素elem 减去前一个元素 pre的结果不为1的，都是一个range的开始；

2，通过一次遍历，用一个hash表把这些range的开始index记录下来，最后加上vector.size()作为结束

3，hash表中的没两个元素，都是nums中一个range的起始位，通过一次遍历，很容易得到想要的结果

边界条件：vector为空，或者vector长度为1；找到range的hash表

前条件：startIndex=0, i = 1；hashTable

不变式：求的startNum和EndNum，判断两个是否相等。会生成2种字符串

结束条件：hashTable遍历结束

// 编译错误

Line 9: missing template arguments before ‘.’ token

vector向量用错了！

Line 9: ‘class std::vector<int>’ has no member named ‘length’

Line 30: expected ‘,’ or ‘;’ before ‘for’ //疯掉了。总是忘记语句结束的 ;

// WA

原因，nums的range起始位置忘记用hashTable变换

class Solution {public:    vector
   
     summaryRanges(vector
    
     & nums) {        vector
     
       ret;        stringstream ss;        vector
      
        hashT;        if (nums.size() == 0)            return ret;        if (nums.size() == 1){            ss.str("");            ss << nums[0];            ret.push_back(ss.str());            return ret;        }        hashT.push_back(0);        for (int i = 1; i < nums.size(); ++i){            if (nums[i] - nums[i-1] == 1)                continue;            hashT.push_back(i);        }        hashT.push_back(nums.size()); //2 is the least length of hashTable        int startIndex = hashT[0];        int endIndex = -1;        for (int i = 1; i < hashT.size(); ++i){            endIndex = hashT[i];            int start = nums[startIndex];            int end = nums[endIndex-1];            if (start == end){                ss.str("");                ss << start;                ret.push_back(ss.str());            }else{                ss.str("");                ss << start << "->" << end;                ret.push_back(ss.str());            }            startIndex = endIndex;        }        return ret;    }};