Три послідовних шанси Рішення 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] - це три послідовні шанси. Звідси повернення true.

Підхід

Це проста задача, яку можна вирішити за допомогою одного обходу даного масиву. Під час обходу ми повинні перевірити наявність усіх трьох послідовних елементів. Точка, в якій ми вважаємо всі три числа непарними, ми повертаємо істинною.

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

Алгоритм

  1. Створіть змінну i та ініціюйте індексом 2.
  2. Запустіть a для петлі для i до останнього елемента, (n-1) -го індексу.
  3. Перевірте, чи елемент в індексах i, (i-1) та (i-2) непарний чи ні.
  4. Якщо всі троє непарні, поверніть true. В іншому випадку продовжуйте обхід.
  5. Після обходу всіх індексів поверніть false.

Реалізація

Програма С ++ для трьох послідовних шансів Рішення 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

Аналіз складності для трьох послідовних шансів рішення Леткод

Складність часу

O (N): Де N - розмір даного масиву. Оскільки ми обходимо лише один раз для кожного індексу, складність часу буде O (N).

Складність простору 

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