Хашааны алгоритм  


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг CodeNation Facebook-ийн Google-ийн Intuit JP Morgan Morgan Stanley
Array Динамик програмчлал LeetCode

Асуудлын мэдэгдэл  

“Уран зургийн хашааны алгоритм” -д танд хэдэн тулгуур (зарим модон хэсэг эсвэл бусад хэсэг), зарим өнгөөр ​​хашаа өгсөн гэж заасан байдаг. Хамгийн ихдээ ойролцоох 2 хашаа ижил өнгөтэй байхаар хашаа будах хэдэн аргыг олж мэдээрэй. Энэ тоо их байж болох тул хариултыг 1000000007 гэсэн модулаар буцаана уу.

Жишээ нь  

Хашааны алгоритмPin

Number of posts/wooden sticks = 2
Number of colors = 2
4

Тайлбар
Та хоёр бичлэгийг 2 янзаар өнгөөр ​​будаж болно. Танд бичлэгийг ижил өнгөөр ​​будах 2 арга бий. Нийтдээ 4 арга байна.

Хашааны алгоритмыг будах арга  

Гэнэн хандлагаар эхэлье. Бидэнд n бичлэг, k өнгө байгаа гэж өгсөн. Одоо бид ижил өнгөөр ​​хамгийн ихдээ хоёр зэргэлдээ бичлэг байхаар бичлэгийг будах хэдэн аргыг олох хэрэгтэй. Хэрэв бид бол нэг гэнэн хандлага байж болох юм бүх дарааллыг бий болгох бичлэг бүрээс олж авсан өнгийг илэрхийлнэ. Гэхдээ энэ арга нь маш үр ашиггүй бөгөөд цаг хугацааны хязгаарыг давах болно.

Тэгэхээр, илүү сайн арга гэж юу байж болох вэ? Нэг арга барил Хэрэв бид асуудлыг жижиг асуудлуудад хуваах юм бол ийм байж болох юм. Бичлэгийн тоо = n-2 ба n-1-ийн хариуг мэдэж байгаа гэж үзье. Эдгээр утгыг F (n-2) ба F (n-1) -ийг тус тусад нь тэмдэглэе. Тиймээс F (n-1) нь хамгийн ихдээ хоёр зэргэлдээ бичлэгүүд ижил өнгөтэй байж болох F (n-2) -н хувьд ижил байдаг аргуудын тоог илэрхийлдэг гэдгийг бид мэднэ. Одоо бид (n-2) th ба n байрлал дахь бичлэгүүдийг ижил өнгөөр ​​будаж байвал (n-1) th post (n-1) nd бичлэгтэй ижил өнгөтэй байхыг шаарддаггүй гэж үзэж байна. Энэ утгыг F (n-2) ашиглан тэмдэглэнэ. Тиймээс манай nth бичлэг сүүлийн бичлэгийнхтэй ижил өнгөтэй байх тохиолдлыг бид авч үзсэн. Мөн одоогийн нийтлэл, сүүлчийн бичлэг ижил өнгөтэй байж болохгүй арга замыг авч үзэх хэрэгтэй. Энэ утгыг F (n-2) ашиглан тэмдэглэнэ. Одоо бидэнд nth бичлэгийг будах (k-1) аргууд байна. Тиймээс нийт аргуудын тоо нь (F (n-1) + F (n-1)) * (k-2) -тэй тэнцүү байна.

мөн үзнэ үү
Декодлох арга

код  

Хашааны алгоритмыг будах C ++ код

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

int main(){
  // number of posts
  int n;cin>>n;
  // number of available colors
  int k;cin>>k;
  int mod = 1000000007;
  int ways = 0;
  if(n == 1)cout<<k;
  else if(n == 2)cout<<k*k;
  else {
    int last = k*k; int lastTolast = k;
    for(int i=3;i<=n;i++){
      ways = ((last + lastTolast)*(k-1))%mod;
      lastTolast = last;
      last = ways;
    }
    cout<<ways;
  }
}
4 2
10

Хашааны алгоритмыг будах Java код

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// number of posts
    int n = sc.nextInt();
    // number of available colors
    int k = sc.nextInt();
    int mod = 1000000007;
    int ways = 0;
    if(n == 1)System.out.print(k);
    else if(n == 2)System.out.print(k*k);
    else {
      int last = k*k; int lastTolast = k;
      for(int i=3;i<=n;i++){
        ways = ((last + lastTolast)*(k-1))%mod;
        lastTolast = last;
        last = ways;
      }
      System.out.print(ways);
    }
    }
}
4 2
10

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N), алгоритмаас харж болно. Бид n-тэй тэнцэх хүртэл үргэлжлэх нэг давталтыг ашигласан болно. Тиймээс n давталт хийх нь бидэнд цаг хугацааны шугаман нарийн төвөгтэй байдлыг илэрхийлнэ.

Сансрын нарийн төвөгтэй байдал

O (1),  бид DP массив хийхийн оронд тогтмол тооны хувьсагчийг ашигласан тул. Асуудлыг шийдэх арга нь зөвхөн сүүлийн хоёр жижиг асуудлаас хамаарах тул энэ арга нь илүү амьдрах чадвартай болно.