Ошибка сегментации в решении LIS для взлома интервью 11.7

Возникла проблема с взломом интервью по кодированию — часть V Вопрос 11.7
и решение, которое я пытаюсь реализовать здесь, это их решение в Java, преобразованное в C ++. Но я сталкиваюсь с проблемой ошибки сегментации.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
class HtWt
{
public:
int ht;
int wt;
HtWt(int ht,int wt):ht(ht),wt(wt){}
HtWt(const HtWt &other)
{
this->ht=other.ht;
this->wt=other.wt;
}
bool operator<(const HtWt& obj) const
{
cout << __func__ << std::endl;
return (this->ht<obj.ht && this->wt<obj.wt);
}
};

typedef vector<HtWt> vHtWt;
typedef vector<vHtWt > vvHtWt;

vHtWt& getSeqWithMaxLen(vHtWt& seq1,vHtWt& seq2)
{
cout << __func__ << std::endl;
if(seq1.empty())
return seq2;
if(seq2.empty())
return seq1;
return (seq1.size() > seq2.size() ? seq1 : seq2);
}

void  LIS(vHtWt& arr,vvHtWt& solutions,int current_index)
{
cout << __func__ << std::endl;
if(current_index>arr.size()-1 || current_index<0)
return;
cout<<"arr.size()="<<arr.size()<<"current_index = "<<current_index<<endl;
HtWt cur_element = arr[current_index];
/* Find longest sequence we can append current_element to */
vHtWt best_sequence;
for(int i=0;i<current_index;i++)
{
cout<<"inside for loop"<<endl;
if (arr[i]<cur_element)
best_sequence = getSeqWithMaxLen(best_sequence,solutions[i]);
//cout<<"{"<<best_sequence[best_sequence.size()-1].ht<<","<<best_sequence[best_sequence.size()-1].wt<<"}"<<" ";
}
/* Append current_element */
vHtWt new_solution;
if(!best_sequence.empty())
new_solution.insert(new_solution.end(),best_sequence.begin(),best_sequence.end());
new_solution.push_back(cur_element);
/* Add to list and recurse */
solutions[current_index] = new_solution;
LIS(arr,solutions,current_index+1);
}

vHtWt LIS(vHtWt& arr)
{
cout << __func__ << std::endl;
vvHtWt solutions;
LIS(arr,solutions,0);
vHtWt best_sequence;
for(int i=0;i<arr.size();i++)
best_sequence = getSeqWithMaxLen(best_sequence,solutions[i]);
return best_sequence;
}

vHtWt getLIS(vHtWt& arr)
{
cout << __func__ << std::endl;
// sort the array for either height or weight
sort(arr.begin(),arr.end());
return LIS(arr);
}

int main()
{
HtWt arr[] = {HtWt(12, 13), HtWt(11, 15), HtWt(9, 20), HtWt(20, 20), HtWt(40, 21), HtWt(8, 42)};
vHtWt vArr(arr,arr+(sizeof(arr)/sizeof(arr[0])));
vHtWt result = getLIS(vArr);
for(int i=0;i<result.size();i++)
cout<<"{"<<result[i].ht<<","<<result[i].wt<<"}"<<" ";
cout<<endl;
return 0;
}

Может кто-нибудь, пожалуйста, помогите мне сказать, почему код сбоя в строке

HtWt cur_element = arr[current_index];

Размер arr равен 6, а index равен 0, поэтому, я думаю, не должно быть ошибки сегментации.

$ ./a.out
getLIS
operator<
operator<
operator<
operator<
operator<
LIS
LIS
arr.size()=6current_index = 0
Segmentation fault: 11

0

Решение

Вы не получаете ошибку сегментации на линии

HtWt cur_element = arr[current_index]; но в

solutions[current_index] = new_solution;

так как solutions не был инициализирован. Изменить строку

vvHtWt solutions; в

vvHtWt solutions(arr.size());

0

Другие решения


По вопросам рекламы [email protected]