ដំណោះស្រាយលេខសេស Leetcode ជាប់គ្នាចំនួនបី


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ឌីជី
អារេ

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុង "បញ្ហាបីសេសជាប់គ្នា" យើងត្រូវបានគេផ្តល់ឱ្យ អារេ ហើយយើងត្រូវពិនិត្យមើលថាតើមានលេខសេសបីជាប់គ្នានៅក្នុងអារេបច្ចុប្បន្នរឺអត់។ ប្រសិនបើវាមានវត្តមាននោះយើងត្រូវតែត្រឡប់ជាការពិតបើមិនដូច្នេះទេយើងនឹងត្រលប់មកវិញមិនពិត។

ឧទាហរណ៍

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

ការពន្យល់៖

មិនមានហាងឆេងបីជាប់គ្នាទេ។ ដូច្នេះត្រឡប់មិនពិត។

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

ការពន្យល់:

នៅក្នុងអារេដែលបានផ្តល់ឱ្យប្រសិនបើយើងពិនិត្យមើលផ្នែកទាំងបីជាប់គ្នា។ វានឹងមានដូចខាងក្រោម៖

ដំណោះស្រាយលេខសេស Leetcode ជាប់គ្នាចំនួនបី

[៥, ៧, ២៣] គឺជាហាងឆេងបីជាប់គ្នា។ ដូច្នេះត្រឡប់ជាការពិត។

វិធីសាស្រ្ត

វាជាបញ្ហាសាមញ្ញមួយដែលអាចត្រូវបានដោះស្រាយដោយប្រើត្រាប់តាមតែមួយនៃអារេដែលបានផ្តល់។ ក្នុងកំឡុងពេលឆ្លងកាត់យើងត្រូវពិនិត្យរកធាតុជាប់គ្នាទាំងបី។ ចំនុចដែលយើងរកឃើញលេខទាំង ៣ នោះគឺសេសយើងត្រលប់មកវិញជាការពិត។

ចំពោះបញ្ហានេះយើងអាចប្រើរង្វិលជុំហើយយើងអាចធ្វើវាបានសម្រាប់ធាតុទីបីនៃក្រុមនីមួយៗ (ធាតុជាប់គ្នា ៣) ពីសន្ទស្សន៍ = ២ ដល់សន្ទស្សន៍ = n-១ ។ បន្ទាប់មកផ្នែកបន្តបន្ទាប់នាពេលបច្ចុប្បន្ននឹងត្រូវបានតំណាងដោយធាតុ arr [i-3], មកដល់ [i-2] និងទៅដល់ [អាយ] ។
យើងនឹងចាប់ផ្តើមនិយាយពីធាតុទីបីពីខាងមុខ។ ប្រសិនបើទំហំនៃអារេតិចជាងបីនោះយើងត្រលប់មកវិញមិនពិត។

ក្បួនដោះស្រាយ

  1. បង្កើតអថេរ I និងអាទិសង្កេតជាមួយសន្ទស្សន៍ ២ ។
  2. រត់មួយ សម្រាប់រង្វិលជុំ សម្រាប់ខ្ញុំរហូតដល់ធាតុចុងក្រោយ (n-1) សន្ទស្សន៍។
  3. ពិនិត្យមើលថាតើធាតុនៅចង្អុលបង្ហាញ i, (i-1) និង (i-2) គឺសេសឬអត់។
  4. បើទាំងបីនាក់មានសេសគឺត្រលប់មកវិញជាការពិត។ ផ្សេងទៀតបន្តការឆ្លងកាត់។
  5. បន្ទាប់ពីឆ្លងកាត់ការចង្អុលបង្ហាញទាំងអស់សូមត្រលប់មកវិញមិនពិត។

ការអនុវត្តន៍

កម្មវិធីស៊ីអេជអាយអាយសម្រាប់ដំណោះស្រាយសេសឡេយលេខកូដ

#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

កម្មវិធីចាវ៉ាសម្រាប់ដំណោះស្រាយសេសឡៃកូដដែលត្រូវគ្នា

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 (១)៖ យើងមិនប្រើការចងចាំបន្ថែមទេ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហនឹងមានថេរ។