leetcode/src/missingRanges/missingRanges.cpp at master · cobain/leetcode · GitHub

History

118 lines (91 loc) · 2.5 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

// Source : https://oj.leetcode.com/problems/missing-ranges/

// Author : Hao Chen

// Date : 2014-12-11

/**********************************************************************************

* Given a sorted integer array where the range of elements are [lower, upper] inclusive,

* return its missing ranges.

* For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99,

* return ["2", "4->49", "51->74", "76->99"].

**********************************************************************************/

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <string>

#include <vector>

#include <algorithm>

#include <iterator>

using namespace std;

string& makeRange(int lo, int hi){

static string result;

result="";

stringstream ss;

if (lo != hi){

ss << lo << "->" << hi;

}else{

ss << lo;

}

ss >> result;

return result;

}

vector<string> findMissingRanges(int A[], int n, int lower, int upper) {

vector<string> result;

if ( n<=0 ) {

result.push_back(makeRange(lower, upper));

return result;

}

if (lower < A[0]){

result.push_back(makeRange(lower, A[0]-1 < upper ? A[0]-1 : upper));

}

for(int i=0; i<n-1; i++){

if ( A[i] + 1 == A[i+1] ) {

continue;

}

result.push_back(makeRange(A[i]+1, A[i+1]-1));

}

if (upper > A[n-1]){

result.push_back(makeRange(A[n-1]+1, upper));

}

return result;

}

void printVector(vector<string> v){

cout << "[";

int i=0;

for(; i<v.size(); i++){

cout << "\"" << v[i] << "\"" << (i==v.size()-1 ? "":", " );

}

cout << "]" <<endl;

}

vector<int> string2Array(string s){

vector<string> strarr;

istringstream iss(s);

copy(istream_iterator<string>(iss),

istream_iterator<string>(),

back_inserter(strarr));

vector<int> result;

for (int i=0; i<strarr.size(); i++){

result.push_back(atoi(strarr[i].c_str()));

}

return result;

}

int main(int argc, char**argv)

{

int A[] = {0, 1, 3, 50, 75};

int lo = 0;

int hi = 99;

vector<string> result = findMissingRanges(A, sizeof(A)/sizeof(A[0]), lo ,hi);

printVector(result);

//usage: ./missingRanges 0 9 "3 5 7"

if (argc>3){

lo = atoi(argv[1]);

hi = atoi(argv[2]);

vector<int> a;

a = string2Array(argv[3]);

int *pA = &a[0];

result = findMissingRanges(pA, a.size(), lo, hi);

printVector(result);

}

return 0;

}

leetcode/src/missingRanges/missingRanges.cpp at master · cobain/leetcode · GitHub

Expand file tree

Breadcrumbs

missingRanges.cpp

Latest commit

History

Breadcrumbs

missingRanges.cpp

File metadata and controls