Блог

Главная - Вопросы по программированию - Я пробежал несколько раз, но не смог найти, в чем ошибка. Я предоставляю свой код, может кто-нибудь, пожалуйста, выяснить ошибку?

Я пробежал несколько раз, но не смог найти, в чем ошибка. Я предоставляю свой код, может кто-нибудь, пожалуйста, выяснить ошибку?

#c

Вопрос:

Ссылка : https://www.codechef.com/LRNDSA01/problems/LAPIN

Описание программы : Лапиндром определяется как строка, которая при разделении посередине дает две половины, имеющие одинаковые символы и одинаковую частоту каждого символа. Если в строке нечетное количество символов, мы игнорируем средний символ и проверяем наличие лапиндрома. Например, gaga-это лапиндром, так как две половины ga и ga имеют одинаковые символы с одинаковой частотой. Кроме того, abccab, rotor и xyzxy являются несколькими примерами лапиндромов. Обратите внимание, что аббааб НЕ является лапиндромом. Две половины содержат одинаковые символы, но их частоты не совпадают. Ваша задача проста. Учитывая строку, вам нужно определить, является ли она лапиндромом.

Мой код :

  #include <stdio.h>
 #include <string.h>

 int main(){
    
    int i,t,len,j,k,arr_indx,check = 0;
    char s[1000],left[500],right[500];
        
        //s[] = input string
        //left[] = left side of the string after division        
        //right[] = right side of the string after division
        //len = length of the input string
        //arr_index = It is the array index 
  
    scanf("%d",amp;t);
    for(i = 1;i <= t;i  )
    {
        

        scanf("%s",amp;s);
        len = strlen(s);
        
        
        //if even length

        if(len % 2 == 0)
        {
            for(j = 0;j < len/2;j  )
                left[j] = s[j];
            left[j] = '';
            
            for(k = len/2,arr_indx = 0;k < len;k  ,arr_indx  )
                right[arr_indx] = s[k];
            right[arr_indx] = '';
        }
        
        //if odd length

        else
        {
            for(j = 0;j < len/2;j  )
                left[j] = s[j];
            left[j] = '';
            
            for(k = ((len/2) 1),arr_indx = 0;k < len;k  ,arr_indx  )
                right[arr_indx] = s[k];
            right[arr_indx] = '';
        }
        
        //Checking

        for(k = 0;k < strlen(left);k  )
            for(j = 0;j < strlen(right);j  )
                if(left[k] == right[j])
                   check  ;     

        if(check == strlen(left)) //printing
        printf("YESn");
        else
        printf("NOn");
        check = 0;
    }
    return 0;
}

Комментарии:

1. Пожалуйста, укажите входные данные, ожидаемые результаты и фактические результаты. В настоящее время мы не можем догадаться, что не так с вашим кодом, если только мы не потратим больше времени на его чтение и тестирование, чем кто-либо из нас.

2. Давайте представим себе строку aaaaaa , это наверняка лапиндром. Сколько это будет check стоить? Ожидая получить 3(почему ?), фактический результат: 9. Хм, это не совсем правильно. Ваша логика проверки неверна.

3. Размеры массивов для массивов s left , right должны быть 1001 , 501, 501 соответственно, чтобы можно было хранить нулевой символ ( ). И, в целом, логика не верна. Даже если бы это было правильно, алгоритм был бы очень неэффективен (читай медленно).

Ответ №1:

Алгоритм, который вы реализовали, одновременно неверен и очень медленный (даже если он был правильным). Поскольку входные символы ограничены a..z, вы можете реализовать быстрый алгоритм, сравнив частоты букв в левой и правой частях входного текста. Пример реализации приведен ниже. Код предполагает, что коды символов a..z являются смежными, что не гарантируется стандартом C.

 #include <stdio.h>
#include <string.h>

#define NLETTERS ('z' - 'a'   1)

int main(void)
{
    int T;
    
    scanf("%d ", amp;T);
    while (--T >= 0) {
        char buf[1002];
        int lfreq[NLETTERS] = {0}, rfreq[NLETTERS] = {0}, yes = 1;
        fgets(buf, sizeof buf, stdin);
        for (int i = 0, j = strcspn(buf, "n") - 1; i < j;   i, --j) {
              lfreq[buf[i] - 'a'];
              rfreq[buf[j] - 'a'];
        }
        for (int i = 0; i < NLETTERS;   i) {
            if (lfreq[i] != rfreq[i]) {
                yes = 0;
                break;
            }
        }
        puts(yes ? "YES" : "NO");
    }
    return 0;
}
Метки: , , , , ,