Member 13711733 Ответов: 1

Самая длинная повторяющаяся подпоследовательность с использованием только LINQ

Вы не можете использовать какие-либо циклы, if-else, try-catch, рекурсию и т. д.
Вы можете накладываться друг на друга. В последовательности 1111 самое длинное повторение-111. В последовательности 11211 - самое длинное повторение равно 11.

LongestRepetition(Новый [] {1, 2, 1, 2, 1, 2, 3, 2, 1, 2}) должен вернуться Новый [] {1, 2, 1, 2}.

Что я уже пробовал:

Я не знаю, что и попробовать. Я решил ее без Линка.

это мой код.:

static string LongestRepetition(string str)
        {
            var list = new List<string>();
            var counter = 0;
            var rep = "";

            for (int i = 0; i < str.Length; i++)
            {
                rep = "";
                for (int k = i; k < str.Length; k++)
                {
                    counter = 0;
                    rep += str[k];
                    var startIndex = 0;
                    var indexOf = int.MinValue;
                    while ((indexOf = str.IndexOf(rep, startIndex)) >= 0)
                    {
                        counter++;
                        startIndex = indexOf + 1;
                        if (counter > 1) break;
                    }

                    if (counter > 1)
                    {
                        list.Add(rep);
                    }
                }
            }

            return list.OrderByDescending(x => x.Length).FirstOrDefault();
        }

1 Ответов

Рейтинг:
7

Maciej Los

Член 13711733[^] писанное:
LongestRepetition(new [] {1, 2, 1, 2, 1, 2, 3, 2, 1, 2}) должны вернуться new [] {1, 2, 1, 2}.


Почему? Он должен логически вернуться new [] {1, 2, 1, 2, 1, 2}- потому что это самое длинное повторение.

Проверьте это универсальное решение linq:
public static T[] GetLongestRepetition<T>(T[] list)
{
	
	return list.TakeWhile(o => list.GroupBy(x=>x)
				.Where(grp=>grp.Count()>1)
				.Any(grp=>grp.Key.Equals(o)))
		.ToArray();
}

Использование:
int[] nums = new int[]{1, 2, 1, 2, 1, 2, 3, 2, 1, 2};
var result = GetLongestRepetition(nums);
Console.WriteLine("{0}", string.Join("", result)); //prints 121212
	
string s = "aabaa";
var result1 = GetLongestRepetition(s.ToArray());
Console.WriteLine("{0}", string.Join("", result1)); //prints aa

string num = "1123811238479";
var result2 = GetLongestRepetition(num.ToArray());
Console.WriteLine("{0}", string.Join("", result2)); //prints 1123811238


Примечание №1: это решение, к сожалению, использует "скрытый цикл", см.: TakeWhile[^]

Примечание № 2: у меня нет достаточно времени, чтобы проверить мое решение. Таким образом, он может нуждаться в улучшении...

Graeme_Grant

5 б

Maciej Los

Спасибо, Грэм.

Member 13711733

Спасибо! Но я не могу переделать его, чтобы сделать магию без прыжка. Как вы думаете, это можно сделать с помощью ввода 

new [] {1, 2, 1, 2, 1, 2, 3, 2, 1, 2})
возвращаться 
new [] {1, 2, 1, 2}

Maciej Los

Как я уже упоминал в своем ответе - нет. Самое длинное повторение-это: {1, 2, 1, 2, 1, 2}

Member 13711733

В вашем случае, если 1212123212 возвращает 121212, то 11211 должен возвращать 111, а не 11.

Maciej Los

И снова - нет.
Самый длинный повтор [11211] есть [11].
Самый длинный повтор [1212123212] это [121212];
Самый длинный повтор [111211] или [112111] было бы [111].
Что означает повторение? Число элементов, которые происходят последовательно.
Подумай об этом!

Member 13711733

Это не мое определение повторения. Для меня повторение - это подпоследовательность, которая встречается по крайней мере дважды в последовательности.
121212 - 1212
11211 - 11
111211 - 11
и так далее.

Maciej Los

Вы не упомянули об этом в своем вопросе. Это новое требование, и это все меняет.

Maciej Los

КСТАТИ:
Для [121212] - повторение, которое происходит по крайней мере дважды, будет [12] и [21]

Member 13711733

Да. И самое длинное повторение, которое происходит по крайней мере дважды, - это 1212.

Maciej Los

Ну, вы ищете самые длинные последовательные пары ;)