په جاواسکریپټ کې د ګوګل مرکې څخه د ستونزې حل کول: 4 مختلفې لارې

کله چې ما د الګوریتم فعالیت مطالعه کوله، زه پدې کې راغلم دا د ګوګل د جعلي مرکې ویډیو ده.. دا نه یوازې دا نظر ورکوي چې څنګه مرکې په لوی ټیکنالوژۍ شرکتونو کې ترسره کیږي ، بلکه تاسو ته اجازه درکوي پوه شئ چې څنګه د امکان تر حده د الګوریتمیک ستونزې حل کیږي.

دا مقاله د ویډیو سره یو ډول ملګری دی. په دې کې زه د ښودل شوي ټولو حلونو په اړه نظرونه وړاندې کوم، او په جاواسکریپټ کې زما د حل نسخه. د هر الګوریتم باریکي هم بحث کیږي.

موږ یادونه کوو: د ټولو هابر لوستونکو لپاره - د 10 روبل تخفیف کله چې د هابر پرومو کوډ په کارولو سره د مهارت بکس کوم کورس کې نوم لیکنه وکړئ.

Skillbox وړاندیز کوي: عملي کورس "د ګرځنده پرمخ وړونکي PRO".

د ستونزې تشکیل

موږ ته یو ترتیب شوی صف او یو ځانګړی ارزښت راکړل شوی. بیا له دې څخه غوښتنه کیږي چې داسې فنکشن رامینځته کړي چې ریښتیني یا غلط بیرته راګرځي پدې پورې اړه لري چې ایا په صف کې د کوم دوه شمیرو مجموعه د ورکړل شوي ارزښت سره مساوي کیدی شي.

په بل عبارت، ایا په صف کې دوه عددونه شتون لري، x او y، چې کله یوځای اضافه شي د ټاکل شوي ارزښت سره مساوي وي؟

بېلګه A

که موږ ته یو سري راکړل شي [1, 2, 4, 9] او ارزښت یې 8 وي, نو فنکشن به غلط راستون شي ځکه چې په صف کې هیڅ دوه شمیرې تر 8 پورې نشي اضافه کیدی.

بېلګه ب

مګر که دا یو سري وي [1، 2، 4، 4] او ارزښت یې 8 وي، فنکشن باید ریښتیا راشي ځکه چې 4 + 4 = 8.

حل 1: وحشي ځواک

د وخت پیچلتیا: O(N²).
د فضا پیچلتیا: O(1).

تر ټولو څرګند معنی دا ده چې د ځنځیر شوي لوپونو یو جوړه کارول.

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] + arr[j] === val) {
        return true;
      };
    };
  };
  return false;
};

دا حل موثر ندی ځکه چې دا په صف کې د دوه عناصرو هر ممکنه مجموعه ګوري او د شاخصونو هره جوړه دوه ځله پرتله کوي. (د مثال په توګه، کله چې i = 1 او j = 2 په حقیقت کې د i = 2 او j = 1 سره پرتله کولو سره ورته وي، مګر پدې حل کې موږ دواړه اختیارونه هڅه کوو).

ځکه چې زموږ حل د لوپونو لپاره یو جوړه نیسټ کاروي، دا د O (N²) وخت پیچلتیا سره څلور اړخیزه ده.

حل 2: د بائنری لټون

د وخت پیچلتیا: O(Nlog(N)).
د فضا پیچلتیا: O(1).

څرنګه چې صفونه ترتیب شوي، موږ کولی شو د بائنری لټون په کارولو سره د حل لټون وکړو. دا د ترتیب شوي صفونو لپاره خورا مؤثر الګوریتم دی. د بائنری لټون پخپله د O(log(N)) چلولو وخت لري. په هرصورت، تاسو لاهم اړتیا لرئ د لوپ لپاره وکاروئ ترڅو هر عنصر د نورو ټولو ارزښتونو په مقابل کې وګورئ.

دلته هغه څه دي چې ممکن حل ورته ښکاري. د شیانو روښانه کولو لپاره، موږ د بائنری لټون کنټرول لپاره جلا فعالیت کاروو. او همدارنګه د removeIndex() فنکشن، کوم چې د ورکړل شوي شاخص څخه د سرې نسخه بیرته راګرځوي.

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++){
    if (binarySearch(removeIndex(arr, i), val - arr[i])) {
      return true;
    }
  };
  return false;
};
 
const removeIndex = (arr, i) => {
  return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
 
const binarySearch = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  let pivot = Math.floor(arr.length / 2); 
  while (start < end) {
    if (val < arr[pivot]) {
      end = pivot - 1;
    } else if (val > arr[pivot]) {
      start = pivot + 1;
    };
    pivot = Math.floor((start + end) / 2);
    if (arr[pivot] === val) {
      return true;
    }
  };
  return false;
};

الګوریتم د شاخص څخه پیل کیږي [0]. دا بیا د لومړي شاخص پرته د صف یوه نسخه رامینځته کوي او د بائنری لټون کاروي ترڅو وګوري چې ایا کوم پاتې ارزښتونه د مطلوب مقدار تولید لپاره په صف کې اضافه کیدی شي. دا عمل په صف کې د هر عنصر لپاره یو ځل ترسره کیږي.

د لوپ لپاره پخپله به د O(N) خطي وخت پیچلتیا ولري، مګر د لوپ لپاره دننه موږ د بائنری لټون ترسره کوو، کوم چې د O(Nlog(N)) ټولیز وخت پیچلتیا ورکوي. دا حل د تیر یو په پرتله ښه دی، مګر لاهم د پرمختګ لپاره خونه شتون لري.

3 حل: خطي وخت

د وخت پیچلتیا: O(N).
د فضا پیچلتیا: O(1).

اوس به موږ ستونزه حل کړو، په یاد ولرئ چې صف ترتیب شوی دی. د حل لاره دا ده چې دوه شمیرې واخلئ: یو په پیل کې او بل په پای کې. که پایله د اړتیا سره توپیر ولري، نو د پیل او پای ټکي بدل کړئ.

په نهایت کې به موږ یا د مطلوب ارزښت سره مخ شو او ریښتیني راستون شو ، یا به د پیل او پای ټکي سره یو ځای شي او غلط بیرته راستانه شي.

const findSum = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  while (start < end) {
    let sum = arr[start] + arr[end];
    if (sum > val) {
      end -= 1;
    } else if (sum < val) {
      start += 1;
    } else {
      return true;
    };
  };
  return false;
};

اوس هر څه سم دي، د حل لاره غوره ښکاري. مګر څوک تضمین کولی شي چې صف امر شوی و؟

بیا څه؟

په لومړي نظر کې ، موږ کولی شو په ساده ډول لومړی صف ته امر کړی وای او بیا یې پورته حل کارولی وای. مګر دا به د اعدام وخت څنګه اغیزه وکړي؟

غوره الګوریتم د وخت پیچلتیا O (Nlog (N)) سره Quicksort دی. که موږ دا زموږ په غوره حل کې وکاروو، دا به خپل فعالیت له O (N) څخه O (Nlog (N)) ته بدل کړي. ایا دا ممکنه ده چې د غیر منظم شوي صف سره یو خطي حل ومومئ؟

حل 4

د وخت پیچلتیا: O(N).
د فضا پیچلتیا: O(N).

هو، یو خطي حل شتون لري؛ د دې کولو لپاره، موږ باید یو نوی صف جوړ کړو چې د میچونو لیست لري چې موږ یې په لټه کې یو. دلته تجارت بند د حافظې ډیر کارول دي: دا په کاغذ کې یوازینۍ حل دی چې د O(1) څخه ډیر د ځای پیچلتیا سره.

که د ورکړل شوي سرې لومړی ارزښت 1 وي او د لټون ارزښت 8 وي، موږ کولی شو ارزښت 7 د "لټون ارزښتونو" صف ته اضافه کړو.

بیا، لکه څنګه چې موږ د صف هر عنصر پروسس کوو، موږ کولی شو د "لټون ارزښتونو" لړۍ وګورو او وګورو چې آیا یو یې زموږ د ارزښت سره برابر دی. که هو، ریښتیا بیرته راشئ.

const findSum = (arr, val) => {
  let searchValues = [val - arr[0]];
  for (let i = 1; i < arr.length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.includes(arr[i])) {
      return true;
    } else {
      searchValues.push(searchVal);
    }
  };
  return false;
};

د حل اساس د لوپ لپاره دی، کوم چې لکه څنګه چې موږ پورته ولیدل، د O(N) د خطي وخت پیچلتیا لري.

زموږ د فعالیت دویمه تکراري برخه Array.prototype.include() ده، د جاوا سکریپټ میتود چې ریښتیا یا غلط بیرته راستنیږي پدې پورې اړه لري چې ایا سرې ورکړل شوی ارزښت لري.

د Array.prototype.includes() د وخت پیچلتیا معلومولو لپاره، موږ کولی شو د MDN لخوا چمتو شوي پولیفیل وګورو (او په جاواسکریپټ کې لیکل شوي) یا د جاواسکریپټ انجن د سرچینې کوډ کې میتود وکاروو لکه ګوګل V8 (C++).

// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
  Object.defineProperty(Array.prototype, 'includes', {
    value: function(valueToFind, fromIndex) {
 
      if (this == null) {
        throw new TypeError('"this" is null or not defined');
      }
 
      // 1. Let O be ? ToObject(this value).
      var o = Object(this);
 
      // 2. Let len be ? ToLength(? Get(O, "length")).
      var len = o.length >>> 0;
 
      // 3. If len is 0, return false.
      if (len === 0) {
        return false;
      }
 
      // 4. Let n be ? ToInteger(fromIndex).
      //    (If fromIndex is undefined, this step produces the value 0.)
      var n = fromIndex | 0;
 
      // 5. If n ≥ 0, then
      //  a. Let k be n.
      // 6. Else n < 0,
      //  a. Let k be len + n.
      //  b. If k < 0, let k be 0.
      var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
 
      function sameValueZero(x, y) {
        return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
      }
 
      // 7. Repeat, while k < len
      while (k < len) {
        // a. Let elementK be the result of ? Get(O, ! ToString(k)).
        // b. If SameValueZero(valueToFind, elementK) is true, return true.
        if (sameValueZero(o[k], valueToFind)) {
          return true;
        }
        // c. Increase k by 1.
        k++;
      }
 
      // 8. Return false
      return false;
    }
  });
}

دلته د Array.prototype.include() تکراري برخه په 7 ګام کې د وخت لوپ دی چې (تقریبا) د ورکړل شوي سرې ټول اوږدوالی تیریږي. دا پدې مانا ده چې د دې وخت پیچلتیا هم خطي ده. ښه، ځکه چې دا تل زموږ د اصلي صف څخه یو ګام شاته وي، د وخت پیچلتیا O (N + (N - 1)) ده. د لوی O نوټیشن په کارولو سره ، موږ دا O (N) ته ساده کوو - ځکه چې دا N دی چې ترټولو لوی تاثیر لري کله چې د ان پټ اندازه زیاتیږي.

د ځایي پیچلتیا په اړه، یو اضافي سرې ته اړتیا ده چې اوږدوالی یې اصلي سري منعکس کوي (منفی یو، هو، مګر دا له پامه غورځول کیدی شي)، د O (N) ځایي پیچلتیا په پایله کې. ښه، د حافظې زیاتوالی د الګوریتم اعظمي موثریت تضمینوي.

زه امید لرم چې تاسو مقاله ستاسو د ویډیو مرکې لپاره د ضمیمه په توګه ګټور ومومئ. دا ښیي چې یوه ساده ستونزه په مختلفو لارو حل کیدی شي د مختلفو سرچینو کارول (وخت، حافظه) سره.

Skillbox وړاندیز کوي:

• آنلاین کورس پلي شوی "د پایتون ډیټا شنونکی".
• آنلاین کورس "د مسلک مخکینۍ پراختیا کونکی".
• یو کلن عملي کورس "د پی ایچ پی جوړونکی له 0 څخه تر پرو".

سرچینه: www.habr.com