Երեք անընդմեջ գործակիցների Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Jiի
Դասավորություն

Խնդիրի հայտարարություն

«Երեք անընդմեջ հավանականություն» խնդրում մեզ տրված է դասավորություն և մենք պետք է ստուգենք ՝ արդյո՞ք ներկա զանգվածում կան երեք անընդմեջ կենտ թվեր, թե ոչ: Եթե ​​դա առկա է, ապա մենք պետք է վերադառնանք ճշմարիտ, այլապես կվերադառնանք կեղծ:

Օրինակ

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

Բացատրություն.

Չկան երեք անընդմեջ գործակիցներ: Ուստի կեղծ վերադարձեք:

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

Բացատրությունը.

Տրված զանգվածում, եթե ստուգենք տարրերի բոլոր երեք հաջորդական հատվածները: Դա կլինի հետեւյալը.

Երեք անընդմեջ գործակիցների Leetcode լուծում

[5, 7, 23] երեք անընդմեջ գործակիցներ են: Ուստի վերադարձեք ճշմարիտ:

Մոտեցում

Դա պարզ խնդիր է, որը կարող է լուծվել ՝ օգտագործելով տրված զանգվածի մեկ հատում: Անցման ընթացքում մենք պետք է ստուգենք բոլոր երեք հաջորդական տարրերը: Այն կետը, երբ գտնում ենք, որ բոլոր երեք թվերը տարօրինակ են, մենք վերադարձնում ենք իրական:

Դրա համար մենք կարող ենք օգտագործել մի օղակ և կարող ենք կրկնել յուրաքանչյուր խմբի երրորդ տարրի համար (3 անընդմեջ տարր) ինդեքսից = 2 ինդեքս = n-1: Այդ ժամանակ ընթացիկ հաջորդական հատվածը կներկայացվի arr [i-2], arr [i-1] և arr [i] տարրերով:
Մենք կսկսենք կրկնվել երրորդ տարրից առջևից: Եթե ​​զանգվածի չափը երեքից պակաս է, ապա մենք կեղծ ենք վերադարձնում:

Ալգորիթմ

  1. Ստեղծեք i փոփոխական և նախաստորագրեք 2 ինդեքսով:
  2. Run a օղակի համար i- ի համար մինչև վերջին տարրը, (n-1), ինդեքսը:
  3. Ստուգեք ՝ i, (i-1) և (i-2) ցուցանիշների տարրը տարօրինակ է, թե ոչ:
  4. Եթե ​​երեքն էլ տարօրինակ են, վերադարձիր իրական: Ուրիշ էլ շարունակեք անցումը:
  5. Բոլոր ցուցանիշները անցնելուց հետո վերադարձեք կեղծ:

Իրականացման

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 լուծման համար

Timeամանակի բարդություն

ՎՐԱ) : Որտեղ N- ը տրված զանգվածի չափն է: Քանի որ յուրաքանչյուր ինդեքսի համար մենք միայն մեկ անգամ ենք անցնում, ժամանակի բարդությունը կլինի O (N):

Տիեզերական բարդություն 

O (1): Մենք ոչ մի լրացուցիչ հիշողություն չենք օգտագործում: Հետևաբար տիեզերական բարդությունը կլինի անընդհատ: