Блог

Я работаю над проблемой из codesignal, которая просит определить, можно ли переставить символы строки, чтобы создать палиндром. Мой подход к этому заключался в создании a HashMap и размещении в нем каждого символа строки. Если HashMap содержит четную сумму всех значений, мы должны убедиться, что каждое значение само по себе является четным. В противном случае, если сумма нечетная, нам нужно посмотреть, не было ли четным самое большее одно значение. В настоящее время я прохожу тесты 9/10.

Тест, который я проваливаю, имеет входные данные: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbccccaaaaaaaaaaaaa" . Мое решение выводит true , когда оно должно быть false . Я не вижу, где я ошибаюсь.

 boolean palindromeRearranging(String inputString) {
    
    HashMap<Character,Integer> letters=new HashMap<Character,Integer>();
    boolean isPalidrome=false;
    
    //one character strings are palindromes
    if(inputString.length()==1)
    {
        isPalidrome=true;
    }

    //look at the string and count the instances of each character
    for(int i=0;i<inputString.length();i  )
    {
        //add each character not in the hashmap already
        if(!letters.containsKey(inputString.charAt(i)))
        {
            letters.put(inputString.charAt(i), 1);
        }
        //otherwise, increment the count
        else if(letters.containsKey(inputString.charAt(i)))
        {
            letters.put(inputString.charAt(i), letters.get(inputString.charAt(i))   1);
        }
    }
    
    //sum the values in the hashmap
    int sum=0;
    Collection<Integer>val=letters.values();
    //count of values that are not even
    int v=0;
    
    for(int n:val)
    {
        //System.out.println("n:" n);
        sum =n;
        
        //if a value corresponding to a key isn't even, increase the count 
        if(sum%2!=0)
        {
            v  ;
        }
    }
    
    //System.out.println(sum);
    
    //if we have an even sum then we have to make sure each key has an even value
    if(sum%2==0)
    {
        for(int n:val)
        {
            //if a key doesn't have an even value
            if(n%2!=0)
            {
                isPalidrome=false;
            }
            else
                isPalidrome=true;
        }
    }
    
    if(sum%2!=0)
    {
        if(v==1)
        {
            isPalidrome=true;
        }
        else
            isPalidrome=false;
    }
    
    return isPalidrome;

}
 

В этой части вашего кода

 if(sum%2!=0)
    {
        v  ;
    }
 

он должен измениться на

 if(n%2!=0)
    {
        v  ;
    }
 

Вы забыли добавить разрыв в цикл внутри if(sum%2==0)

 boolean palindromeRearranging(String inputString) {

    HashMap<Character,Integer> letters=new HashMap<Character,Integer>();
    boolean isPalidrome=false;
    
    //one character strings are palindromes
    if(inputString.length()==1)
    {
        isPalidrome=true;
    }

    //look at the string and count the instances of each character
    for(int i=0;i<inputString.length();i  )
    {
        //add each character not in the hashmap already
        if(!letters.containsKey(inputString.charAt(i)))
        {
            letters.put(inputString.charAt(i), 1);
        }
        //otherwise, increment the count
        else if(letters.containsKey(inputString.charAt(i)))
        {
            letters.put(inputString.charAt(i), letters.get(inputString.charAt(i))   1);
        }
    }
    
    //sum the values in the hashmap
    int sum=0;
    Collection<Integer>val=letters.values();
    //count of values that are not even
    int v=0;
    
    for(int n:val)
    {
        //System.out.println("n:" n);
        sum =n;
        
        //if a value corresponding to a key isn't even, increase the count 
        if(n%2!=0)
        {
            v  ;
        }
    }
    
    //System.out.println(sum);
    
    //if we have an even sum then we have to make sure each key has an even value
    if(sum%2==0)
    {
        for(int n:val)
        {
            //if a key doesn't have an even value
            if(n%2!=0)
            {
                isPalidrome=false;
                break;
            }
            else
                isPalidrome=true;
        }
    }
    
    if(sum%2!=0)
    {
        if(v==1)
        {
            isPalidrome=true;
        }
        else
            isPalidrome=false;
    }
    
    return isPalidrome;

}
 

Вместо вычисления суммы значений hashmap ниже приведена моя логика. В принципе, палиндром может быть сформирован максимум из одного набора нечетных символов и может иметь любой набор четных символов. Допустим, есть строка aaaabbcccc . Здесь есть два набора четных символов (a amp; b) и один набор нечетных, которые могут быть палиндромом, если они переставлены. Ниже приведена моя программа на c .

 #include <bits/stdc  .h>
using namespace std;

int main()
{
        string input;
        cin>> input;
        
        cout<< input<< endl;
        
        int a[26] = {0};

        for (int i = 0; input[i] != ''; i  )
            a[input[i] - 97]  ;
        
        int odd = 0;
        for (int i = 0; i < 26; i  )
        {
            if (a[i] != 0)
            {
                if (a[i] % 2)
                {
                    odd  ;
                    if (odd > 1)
                    {
                        cout<< "false"<< endl;
                        break;
                    }
                }
                
            }
        }

        if (odd < 2)
            cout<< "true"<< endl;
    return 0;
}
 

Вы можете попробовать эту логику для проверки наличия палиндрома.