Самая длинная матрица с переключающими элементами - PullRequest
Новая
       13

Самая длинная матрица с переключающими элементами

2 голосов
/ 12 октября 2019

Массив называется " switch ", если нечетные и четные элементы равны.

Пример:

[2, 4,2,4] - это коммутационный массив, поскольку элементы в четных позициях (индексы 0 и 2) и нечетных позициях (индексы 1 и 3) равны.

Если A =[3,7,3,7, 2, 1, 2] , подмассивы переключения:

==> [3,7,3,7] и [2,1,2]

Следовательно, самая длинная подмассива коммутации составляет [3,7,3,7] с length =4.

В качестве другого примера, если A = [1,5,6,0,1,0] , единственный подмассив переключения - [0, 1,0] .

Другой пример: A = [7, -5, -5, -5,7, -1,7] , переключающий под-Массивы: [7, -1,7] и [- 5, -5, -5] .

Вопрос:

Напишите функцию, которая получает массив и находит его самый длинный переключаемый подмассив.

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

Ответы [ 2 ]

3 голосов
/ 12 октября 2019

Я предполагаю, что массив проиндексирован нулями. 

if arr.size <= 2
    return arr.size
else 
   ans = 2
   temp_ans = 2 // We will update ans when temp_ans > ans;
   for i = 2; i < arr.size ; ++i
       if arr[i] = arr[i-2]
            temp_ans = temp_ans + 1;
       else
            temp_ans = 2;
       ans = max(temp_ans , ans);
   return ans;

Я думаю, что это должно сработать, и я не думаю, что ему нужны какие-либо объяснения.
Пример кода

2 голосов
/ 12 октября 2019 
 private static int solve(int[] arr){
        if(arr.length == 1) return 1;
        int even = arr[0],odd = arr[1];
        int start = 0,max_len = 0;
        for(int i=2;i<arr.length;++i){
            if(i%2 == 0 && arr[i] != even || i%2 == 1 && arr[i] != odd){
                 max_len = Math.max(max_len,i - start);
                 start = i-1;
                 if(i%2 == 0){
                     even = arr[i];
                     odd = arr[i-1];
                 }else{
                     even = arr[i-1];
                     odd = arr[i];
                 }
            }
        }     


        return Math.max(max_len,arr.length - start);
    }
  • Это похоже на проблему со скользящим окном.
  • Мы отслеживаем четное и нечетное равенство с двумя переменными even и odd.
  • Всякий раз, когда мынатолкнуться на неудовлетворенное условие, например, индекс, но не равный переменной even, и то же самое относится к odd, мы сначала
    • Записываем длину до сих пор в max_len.
    • Сбросstart до i-1, поскольку это необходимо, если все элементы равны.
    • Сброс even и odd в соответствии с текущими индексами i до arr[i] и arr[i-1] соответственно.

Демо: https://ideone.com/iUQti7

...