အဆက်မပြတ် Leetcode ဖြေရှင်းချက်မှဂဏန်းသင်္ချာတိုးတက်မှုစေနိုင်သည်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ
အခင်းအကျင်း sorting

ပြstatementနာကြေညာချက်

“ ဂဏန်းသင်္ချာတိုးတက်မှုမှအဆက်မပြတ်လုပ်ဆောင်မှုကိုလုပ်နိုင်သလား” ပြtheနာတွင်ကျွန်ုပ်တို့အား array တစ်ခုပေးထားသည်။ ဂဏန်းသင်္ချာတိုးတက်မှု အဆိုပါ sequence ကိုပြန်လည်စီစဉ်ခြင်းအားဖြင့်။

နမူနာ

arr = [3,1,5]
true

ရှင်းလင်းချက်: array ကို {1,3,5} အဖြစ်ပြန်စီနိုင်သည်။ ၎င်းသည်ဂဏန်းကွဲပြားမှုကိုဂဏန်းနှစ်လုံးနှင့်ဂဏန်းသင်္ချာတိုးတက်မှုအဖြစ်ပုံဖော်သည်။ ထို့ကြောင့် output သည်မှန်သည်။

Sequence Leetcode Solution မှဂဏန်းသင်္ချာတိုးတက်မှုကိုပြုလုပ်နိုင်သည်

ဂဏန်းသင်္ချာစီးရီးဆိုသည်မှာကပ်လျက်နံပါတ်များအကြားကွာခြားမှုသည်ဆက်တိုက်ဖြစ်သည်။ အခြေခံကျသောချဉ်းကပ်နည်းသည် array ကို ကပ်၍ ကပ်လျက်ရှိသော element များအကြားခြားနားချက်ကိုစစ်ဆေးရန်ဖြစ်သည်။ ခြားနားချက်သည်ဆက်တိုက်အားလုံးအတွက်အားလုံးအတွက်အတူတူဖြစ်လျှင်၎င်းသည်ဂဏန်းသင်္ချာတိုးတက်မှုဖြစ်သည်။

အဆက်မပြတ် Leetcode ဖြေရှင်းချက်မှဂဏန်းသင်္ချာတိုးတက်မှုစေနိုင်သည်

sorting များအတွက်အချိန်ရှုပ်ထွေး nlogn ဖြစ်ပါတယ်။ ကျွန်ုပ်တို့သည်ခင်းကျင်းရန်ရှာဖွေမှုဇယားတစ်ခု ဖန်တီး၍ အချိန်ရှုပ်ထွေးမှုကိုတိုးတက်စေနိုင်သည်။

AP ၏ nth term သည် a = (n-1) * d ဖြစ်သည်။ ၎င်းသည်ကိန်းဂဏန်း၏ပထမ ဦး ဆုံးဒြပ်စင်ဖြစ်သည်။ n သည်ဒြပ်စင်အရေအတွက်နှင့် d သည်ခြားနားချက်ဖြစ်သည်။

တစ် ဦး AP ၏နိမ့်ဆုံးဒြပ်စင် = တစ် ဦး ဖြစ်ပါတယ်

AP တစ်ခု၏အများဆုံးဒြပ်စင်သည် = = a + (n-1) * d ဖြစ်သည်

= = (အများဆုံး - နိမ့်ဆုံး) / (n-1) ။

  1. ကျွန်ုပ်တို့သည် array ၏အနိမ့်ဆုံးနှင့်အမြင့်ဆုံး element များကိုတွေ့ရှိလိမ့်မည်။ ၎င်းကိုအသုံးပြုခြင်းအားဖြင့် d (ဘုံခြားနားချက်) ကိုကျွန်ုပ်တို့တွက်ချက်နိုင်သည်။
  2. Array ကိုရှာဖွေမယ့်ဇယားကိုလုပ်ပါ။
  3. ယခုကျွန်ုပ်တို့သည်ပထမ ဦး ဆုံးဒြပ်စင်နှင့်ဘုံခြားနားချက်ကိုသိပြီ။
  4. a နှင့် d မှဖွဲ့စည်းထားသောဂဏန်းသင်္ချာစီးရီးအားလုံး၏ n element များသည် lookup table တွင်ရှိမရှိကျွန်ုပ်တို့စစ်ဆေးပါမည်။
  5. element တွေအားလုံးကို lookup table ထဲမှာရောက်နေတယ်ဆိုရင်တော့ကျနော်တို့က sequence ကနေဂဏန်းသင်္ချာတိုးတက်မှုကိုလုပ်နိုင်ပါတယ်။

အကောင်အထည်ဖော်ရေး

Can Arithmetic Progression From Sequence အတွက် C ++ ကုဒ်

#include <bits/stdc++.h> 
using namespace std; 
  bool canMakeArithmeticProgression(vector<int>& arr) {
  unordered_set<int> seen;
  int mi = INT_MAX, mx = INT_MIN, n = arr.size();
        for (int a : arr) {
            mi = min(mi, a);
            mx = max(mx, a);
            seen.insert(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (seen.find(mi)==seen.end()) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
int main() 
{ 
 vector<int> arr = {3,5,1}; 
 cout <<boolalpha;   
 cout<<canMakeArithmeticProgression(arr)<<endl; 
 return 0;
}
true

Can Arithmetic Progression မှ Sequence မှလုပ်ရန်အတွက် Java ကုဒ်

import java.util.*; 
public class Tutorialcup {
 public static boolean canMakeArithmeticProgression(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        int mi = Integer.MAX_VALUE, mx = Integer.MIN_VALUE, n = arr.length;
        for (int a : arr) {
            mi = Math.min(mi, a);
            mx = Math.max(mx, a);
            seen.add(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (!seen.contains(mi)) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
  public static void main(String[] args) {
    int [] arr = {3,5,1}; 
    System.out.println( canMakeArithmeticProgression(arr));
  }
}
true

ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်းသည်ဂဏန်းသင်္ချာတိုးတက်မှုကို Sequence Leetcode Solution မှပြုလုပ်နိုင်သည်

အချိန်ရှုပ်ထွေး

အထက်ပါကုဒ်၏အချိန်ရှုပ်ထွေးသည် အို (ဎ) ဘာဖြစ်လို့လဲဆိုတော့ငါတို့က lookup table တစ်ခုဖန်တီးဖို့ array ကိုဖြတ်သန်းနေတယ်။ ဂဏန်းသင်္ချာစီးရီးအားလုံးရဲ့ element တွေက Lookup table ထဲမှာရှိနေလားဆိုတာကိုစစ်ဆေးနေတာ။ ဒီမှာ n ဟာ input array ရဲ့အရွယ်အစား။

အာကာသရှုပ်ထွေးမှု

အပေါ်ကကုဒ်ရဲ့ရှုပ်ထွေးမှုက အို (ဎ) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့က array အတွက် lookup table ကိုဖန်တီးနေတာပါ။ ဒီမှာ n ဟာ input array ရဲ့အရွယ်အစား။

ကိုးကား