Решение Leetcode с тремя последовательными шансами


Сложный уровень Легко
Часто спрашивают в Джи
массив

Постановка задачи

В задаче «Три шанса подряд» нам дали массив и мы должны проверить, присутствуют ли в массиве три последовательных нечетных числа. Если он присутствует, мы должны вернуть true, иначе мы вернем false.

Пример

arr = [2,6,4,1]
false

Объяснение :

Нет трех последовательных шансов. Следовательно, верните false.

arr = [1,2,34,3,4,5,7,23,12]
true

Объяснение:

В данном массиве, если мы проверим все три последовательных сегмента элемента. Это было бы так:

Решение Leetcode с тремя последовательными шансами

[5, 7, 23] - три последовательных коэффициента. Следовательно, верните истину.

Подход

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

Для этого мы можем использовать цикл for и выполнять итерацию для третьего элемента каждой группы (3 последовательных элемента) от index = 2 до index = n-1. Тогда текущий последовательный сегмент будет представлен элементами arr [i-2], arr [i-1] и arr [i].
Мы начнем итерацию с третьего элемента спереди. Если размер массива меньше трех, мы возвращаем false.

Алгоритм

  1. Создайте переменную i и инициализируйте ее индексом 2.
  2. Запустите для цикла для i до последнего элемента, (n-1) -й индекс.
  3. Проверьте, является ли элемент с индексами i, (i-1) и (i-2) нечетным или нет.
  4. Если все три нечетные, верните true. Иначе продолжить обход.
  5. После обхода всех индексов верните false.

Реализация

Программа C ++ для решения Leetcode с тремя последовательными шансами

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

bool threeConsecutiveOdds(vector<int>& arr) 
{
    int n=arr.size();

    for(int i = 2; i < n; i++) 
    {
        if(arr[i] % 2 == 1 && arr[i-1] % 2 == 1 && arr[i-2] % 2 == 1 )
        return true;
    }

    return false;

}

int main() 
{
    vector<int> arr={1,2,34,3,4,5,7,23,12};
    
    if(threeConsecutiveOdds(arr) )
        cout<<"true"<<endl;
    else
        cout<<"no"<<endl;

  return 0; 
}
true

Программа на Java для решения Leetcode с тремя последовательными шансами

import java.lang.*;

class Rextester
{  
    public static boolean threeConsecutiveOdds(int[] arr) {

        int n=arr.length;

        for(int i = 2; i < n; i++) 
        {
            if(arr[i] % 2 == 1 && arr[i-1] % 2 == 1 && arr[i-2] % 2 == 1 )
            return true;
        }

        return false;

    }
    
    public static void main(String args[])
    {
       int[] arr={1,2,34,3,4,5,7,23,12};
    
       System.out.println(threeConsecutiveOdds(arr));
   
    }
}
true

Анализ сложности решения Leetcode для трех последовательных шансов

Сложность времени

НА) : Где N - размер данного массива. Поскольку мы проходим только один раз для каждого индекса, временная сложность будет O (N).

Космическая сложность 

О (1): Мы не используем дополнительную память. Следовательно, сложность пространства будет постоянной.