Самый длинный палиндром в массиве целых чисел

Question

Я хочу найти самый большой палиндром в целочисленном массиве. Я попытался сделать свой собственный алгоритм и не смотреть на онлайн. Но это не работает. Я попытался выполнить отладку, но не смог заставить его работать.

Пример ввода:

"1367611342142412431113424823782"

Вывод: 113421424124311

void palindrome()
{
    int max = 0;
    int len;
    int start;
    int end;
    int st=0,en=0;
    bool palin = false;
    for(int i=0;i<size;i++)
    {
        for(int j=size-1; j>=0;j--)
        {
            if(array[i] == array[j])
            {
                start = i;
                end = j;
                while(j==i+1 || j+1 == i || j == i )
                {
                    if(array[i] == array[j])
                    {
                        i++; 
                        j--;
                        palin = true;
                    }
                    else
                    {
                        palin = false;
                        break;  
                    }
                }
                i= start;
                j= end;
            }
            if(palin == true)
                {
                    len = end - start;
                    if(len>max)
                    {
                        cout<<" "<<st<<" "<<en<<endl;
                        st=i;
                        en =j;
                        max = len;
                    }
                }
        }
    }
    cout<<endl;
    cout<<st<<" "<<en<<endl;
    ofstream file("output.txt");
    for(int i=st;i<=en;i++)
    {
        file<<array[i];
    }
}

Answer 1

Есть решение

#include <iostream>
#include <string>

struct Result
{   
    int fromIndex, toIndex;
    Result(int fromIndex, int toIndex){
        this->fromIndex = fromIndex;
        this->toIndex = toIndex;
    }

    int length(){
        return toIndex - fromIndex;
    }
};

bool isPalindrome(std::string &s, int left, int right){
    while(left <= right){
        if(s[left] != s[right]){
            return false;
        }
        left ++;
        right --;
    }
    return true;
}

std::string solve(std::string &s){
    int startIndex = 0;
    int toIndex = s.size() - 1;
    Result result(0,0);
    while(true){
        if(isPalindrome(s, startIndex, toIndex)){
            if(result.length() < (toIndex - startIndex)){
                result.fromIndex = startIndex;
                result.toIndex = toIndex;
            }
        }
        toIndex --;
        if(toIndex <= startIndex){
            toIndex = s.size() - 1;
            startIndex++;
        }
        if(startIndex == s.size() - 1){
            break;
        }
    }

    std::string str = "";
    for (int i = result.fromIndex; i <= result.toIndex; ++i)
    {
        str += s[i];
    }

    return str;

}

int main()
{
    std::string s = "1367611342142412431113424823782";
    std::string result = solve(s);
    std::cout << "Longest palindrome is: "<< result;
    return 0;
}

Answer 2

Вы должны думать более структурно. Сначала разделите вашу задачу на подзадачи. В этом случае существуют подзадачи: 1. просмотреть все возможные комбинации 2. проверить, является ли эта комбинация палиндромом. Каждая задача - это другая функция - так легче думать, читать код и отлаживать. (Если вы хотите записать его в файл - это третье задание!)

Вот код для «прохождения всех возможных комбинаций». Я думаю, вы найдете, как проверить один массив, если это палиндром.

#include <iostream>
using namespace std;

bool isPalindrome(int* arr, int size);
bool findLargestPalindrome(int* arr, int size);

int main()
{
    int arr[] = { 1,3,6,7,6,1,1,3,4,2,1,4,2,4,1,2,4,3,1,1,1,3,4,2,4,8,2,3,7,8,2 };
    int arrSize = 31;

    findLargestPalindrome(arr, arrSize);
}

bool findLargestPalindrome(int* arr, int size)
{
    for (int testSize = size; testSize > 0; testSize--)
    {
        int startIndex = 0;
        while (testSize + startIndex <= size)
        {
            int* arrayToTest = &(arr[startIndex]);
            if (isPalindrome(arr, testSize))
            {
                //TODO: you found it - do with it whatever you want
                return true;
            }
            startIndex++;
        }
    }
    return false;
}

bool isPalindrome(int* arr, int size)
{
    //TODO: your code for single palindrome
    return false;
}

Answer 3

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

#include <iostream>
// using std;
using std::string;

bool isPalindrome(string input)
{
    return (input == string(input.rbegin(), input.rend()));
}

string palindrome(string input)
{
    int size = input.length();

    int longestLength = 0;
    string largedPalindrome;
    string subStr;
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            int subLength = j - 1;
            // First, check the substring's length with current result's length
            if(subLength <= longestLength) continue;
            subStr = input.substr(i, j);

            if(isPalindrome(subStr) && longestLength < subLength){
                longestLength = subLength;
                largedPalindrome = subStr;
            }
        }
    }
    return largedPalindrome;
}

int main()
{
    string largedPalindrome = palindrome("1367611342142412431113424823782");
    std::cout<<largedPalindrome<<std::endl;
}

Выход:

113421424124311

Answer 4

Вопрос похож на самую длинную палиндромную подстроку ... https://leetcode.com/problems/longest-palindromic-substring/

Вот хороший урок по этому заданию с использованием динамического программирования. https://www.youtube.com/watch?v=0xeBqanD5GQ