[LeetCode] Summary Ranges
Summary Ranges
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given
Credits: Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
問題解決の考え方:
この問題は、隣接するデータのセットを区間で表すことを意味します.markはeasyですが、スズメは小さいのに五臓がそろっていて、落とし穴の問題がたくさんあります.
1、最初に考えたのは以下のコードです.しかし、いくつかの問題に注意しなければならない.1つはオーバーフロー可能な問題であり,1つは自己作成のデジタル回転文字列のコードであり,もう1つは2つの数が隣接しているかどうかを判断することである.c++についてよく知らないので、数字を文字列に変換する方法が分からず、手で書きました.囧.このバージョンのコードは怠け者の足袋のようだ.ヘッダファイルでは、このような方法to_string.また,隣接しているか否かを判断するには不等号を用いるべきである.したがって,簡略化されたコードは以下の通りである.以上の2つのバージョンは、まず後に哨兵データを追加します.
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given
[0,1,2,4,5,7]
, return ["0->2","4->5","7"].
Credits: Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
問題解決の考え方:
この問題は、隣接するデータのセットを区間で表すことを意味します.markはeasyですが、スズメは小さいのに五臓がそろっていて、落とし穴の問題がたくさんあります.
1、最初に考えたのは以下のコードです.しかし、いくつかの問題に注意しなければならない.1つはオーバーフロー可能な問題であり,1つは自己作成のデジタル回転文字列のコードであり,もう1つは2つの数が隣接しているかどうかを判断することである.c++についてよく知らないので、数字を文字列に変換する方法が分からず、手で書きました.囧.このバージョンのコードは怠け者の足袋のようだ.
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
int len = nums.size();
vector<string> result;
if(len == 0){
return result;
}
int left = nums[0];
nums.push_back(nums[len-1]);
len++;
for(int i=1; i<len; i++){
if(nums[i] == nums[i-1] || ((long long)nums[i] - (long long)nums[i-1] > 1)){
if(left == nums[i-1]){
result.push_back(intToString(left));
}else{
result.push_back(intToString(left) + "->" + intToString(nums[i-1]));
}
left = nums[i];
}
}
return result;
}
string intToString(int n){
if(n==0){
return "0";
}
long long lN = n;
string s = "";
if(lN<0){
s = "-";
lN = -lN;
}
stack<char> stacks;
while(lN!=0){
stacks.push(lN%10 + '0');
lN = lN/10;
}
while(!stacks.empty()){
s += stacks.top();
stacks.pop();
}
return s;
}
};
、実はc++の中で直接数字を文字列に変換することができます.class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
int len = nums.size();
vector<string> result;
if(len == 0){
return result;
}
int left = nums[0];
nums.push_back(nums[len-1]);
len++;
for(int i=1; i<len; i++){
if(nums[i] == nums[i-1] || nums[i] - nums[i-1] != 1){
if(left == nums[i-1]){
result.push_back(to_string(left));
}else{
result.push_back(to_string(left) + "->" + to_string(nums[i-1]));
}
left = nums[i];
}
}
return result;
}
};
3、ネット上で別の解決策を見つけて、とても優雅で、その解答の構想は各区間の左右の2つの端点を見つけて、しかも哨兵を必要としません.class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
int len = nums.size();
int i=0;
vector<string> result;
while(i<len){
int j=1;
while(i+j<len && nums[i+j] - nums[i] == j) j++;
result.push_back(j==1 ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[i + j - 1]));
i += j;
}
return result;
}
};