#c #algorithm
Вопрос:
Ссылка на вопрос:https://leetcode.com/проблемы/относительные ранги/;
Это мое решение:Использование двумерного массива nums[2][Оценка]:nums[0][Оценка] для записи оценки[Оценка].nums[1][Оценка] для записи индекса каждого элемента в оценке[Оценка].Затем быстрая сортировка для nums[2][Оценка].Таким образом,вывод:элемент в nums[0][Оценка] упорядочивается от большого к малому порядку, а nums[1][Оценка] записывает соответствующий индекс элемента в score[Оценка].Наконец, используя ret[nums[1][i]] для записи ранга и возврата.Вот код:
void quicksort(int left,int right,int row,int col,int nums[row][col]);
char **findRelativeRanks(int* score, int scoreSize, int* returnSize)
{
char **ret=(char **)malloc(sizeof(char *)*scoreSize);
*returnSize=scoreSize;
int i;
int nums[2][scoreSize]; //to record score[scoreSzie] and index
for(i=0;i<scoreSize;i )
{
nums[0][i]=score[i];
}
for(i=0;i<scoreSize;i )
{
nums[1][i]=i;
}
quicksort(0,scoreSize-1,2,scoreSize,nums); //Quicksort for nums[2][scoreSize]
for(i=0;i<scoreSize;i ) //record rank by ret[scoreSize]
{
if(i<3)
{
switch(i)
{
case 0:ret[nums[1][0]]=(char*)malloc(sizeof(char)*15);
strcpy(ret[nums[1][0]],"Gold Medal");
break;
case 1:ret[nums[1][1]]=(char*)malloc(sizeof(char)*15);
strcpy(ret[nums[1][1]],"Sliver Medal");
break;
case 2:ret[nums[1][2]]=(char*)malloc(sizeof(char)*15);
strcpy(ret[nums[1][2]],"Bronze Medal");
break;
default:break;
}
}else
{
ret[nums[1][i]]=(char*)malloc(sizeof(char)*1);
ret[nums[1][i]][0]='1' i;
}
}
return ret;
}
void quicksort(int left,int right,int row,int col,int nums[row][col])
{
if(left<right)
{
int l=left,r=right;
int pivot=nums[0][left];
int temp=nums[1][left];
while(l<r)
{
while(r>lamp;amp;nums[0][r]<=pivot) r--;
if(r>l)
{
nums[1][l]=nums[1][r];
nums[0][l ]=nums[0][r];
}
while(r>lamp;amp;nums[0][l]>pivot) l ;
if(r>l)
{
nums[1][r]=nums[1][l];
nums[0][r--]=nums[0][l];
}
}
nums[0][l]=pivot;
nums[1][l]=temp;
quicksort(left,l-1,row,col,nums);
quicksort(l 1,right,row,col,nums);
}else
{
return;
}
}
Ошибка в том, что
=================================================================
==42==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000072 at pc 0x564293732f0b bp 0x7fffde673830 sp 0x7fffde673820
READ of size 1 at 0x602000000072 thread T0
#3 0x7fbdea9b60b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6 0x270b2)
0x602000000072 is located 0 bytes to the right of 2-byte region [0x602000000070,0x602000000072)
allocated by thread T0 here:
#0 0x7fbdeb5fbbc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5 0x10dbc8)
#3 0x7fbdea9b60b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6 0x270b2)
Shadow bytes around the buggy address:
0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa 00 07 fa fa 00 07 fa fa 00 07 fa fa[02]fa
0x0c047fff8010: fa fa 02 fa fa fa fd fa fa fa fd fd fa fa fa fa
0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==42==ABORTING
Как новый программист,я изо всех сил стараюсь понять,в чем проблема, но мне это не удалось.Мне действительно нужна помощь.Большое спасибо.
Комментарии:
1. «Как новый программист» я рекомендую вам держаться как можно дальше от таких так называемых сайтов «соревнования» или «онлайн-судьи». Они не являются учебными или обучающими ресурсами. Совсем наоборот, так как большинство примеров, как правило, представляют собой крайне плохой код. Покупайте книги, посещайте занятия, почти все остальное лучше для изучения программирования и вашего языка по выбору.
2. Вы пробовали войти в свой код с помощью отладчика? Вам нужно научиться использовать отладчик, который поставляется вместе с цепочкой инструментов.
3. @Someprogrammerdude,@jwdonahue,большое спасибо,я приму ваш совет.
Ответ №1:
Как указывали люди в комментариях, вы должны попытаться отладить то, что происходит в вашей программе, либо используя gdb , либо добавив некоторые инструкции печати. Кроме того, если вам все еще не так комфортно с C, может быть, сначала стоит прочитать какую-нибудь книгу.
Я рассмотрел проблему и не думаю, что вам нужно внедрять свою собственную версию QuickSort только для этой проблемы. Вы можете просто использовать qsort метод библиотеки C, который хорошо протестирован и более надежен.
- Я заметил, что этот раздел здесь посвящен обработке (
rank > 3) дел:
ret[nums[1][i]]=(char*)malloc(sizeof(char)*1);
ret[nums[1][i]][0]='1' i;
Вы выделяете массив строк размером 1. Даже если мы учтем, что ранги будут состоять только из одной цифры, это неверно, так как даже для строки с одной цифрой вам нужны два символа: один для исходной строки и один для .
Если вы внимательно прочтете ограничения проблемы, вы увидите, что размер массива может достигать 10000. Так что, возможно, использование sprintf было бы лучше здесь:
rankStr = malloc(6 * sizeof(char));
sprintf(rankStr, "%d", rank 1);
- Я нахожу ваш подход к использованию
int nums[2][scoreSize]для хранения как оценки, так и исходного индекса перед сортировкой, а затем сортировкой немного слишком сложным. Я бы предложил создать паруstructfor, подобную этой:
typedef struct ValueToIndexPair {
int value;
int index;
} ValueToIndexPair;
Вы можете легко использовать qsort предоставление пользовательской функции компаратора для сравнения со значением:
int cmpfunc (const void * a, const void * b) {
const ValueToIndexPair* i1 = (ValueToIndexPair*) a;
const ValueToIndexPair* i2 = (ValueToIndexPair*) b;
return (i2->value - i1->value );
}
char **findRelativeRanks(int* score, int scoreSize, int* returnSize) {
// ...
qsort(scoreToIndexList, scoreSize, sizeof(ValueToIndexPair), cmpfunc);
}
С немного очищенной версией вашего кода я смог принять это решение:
typedef struct ValueToIndexPair {
int value;
int index;
} ValueToIndexPair;
int cmpfunc (const void * a, const void * b) {
const ValueToIndexPair* i1 = (ValueToIndexPair*) a;
const ValueToIndexPair* i2 = (ValueToIndexPair*) b;
return (i2->value - i1->value );
}
char **findRelativeRanks(int* score, int scoreSize, int* returnSize) {
char **ranks = malloc(scoreSize * sizeof(char*));
*returnSize = scoreSize;
ValueToIndexPair scoreToIndexList[scoreSize];
for (int i = 0; i < scoreSize; i ) {
scoreToIndexList[i].value = score[i];
scoreToIndexList[i].index = i;
}
qsort(scoreToIndexList, scoreSize, sizeof(ValueToIndexPair), cmpfunc);
for (int i = 0; i < scoreSize; i ) {
char *rankStr = createRankString(i);
int currentScoreOrignalIndex = scoreToIndexList[i].index;
ranks[currentScoreOrignalIndex] = rankStr;
}
return ranks;
}
char *createRankString(int rank) {
char firstRankStr[12] = "Gold Medal";
char secondRankStr[13] = "Silver Medal";
char thirdRankStr[15] = "Bronze Medal";
char *rankStr;
if (rank == 0) {
rankStr = malloc(12 * sizeof(char));
strcpy(rankStr, firstRankStr);
} else if (rank == 1) {
rankStr = malloc(13 * sizeof(char));
strcpy(rankStr, secondRankStr);
} else if (rank == 2) {
rankStr = malloc(15 * sizeof(char));
strcpy(rankStr, thirdRankStr);
} else {
rankStr = malloc(6 * sizeof(char));
sprintf(rankStr, "%d", rank 1);
}
return rankStr;
}
Комментарии:
1. Я прочитал все, что вы написали. Это очень полезно для меня. Большое спасибо. Хорошего дня.