В процес съм на самообучаване на структури от данни и алгоритми и в момента следвам курса, пуснат на Udemy от Colt Steele. След като завърших Bootcamp, нямах традиционен курс по алгоритми или теория и използване на структури от данни в компютърните науки. Досега това беше впечатляващ курс и аз продължавам с бавно, но стабилно темпо. Колт постоянно предупреждава студентите, че материалът може да е гъст на моменти и да не бързат с курса, но той успява да раздели материала на смилаеми концепции и показва стъпка по стъпка реализации, които наистина навлизат дълбоко в популярните алгоритми и структури от данни.

Открих, че използването на този курс във връзка с уебсайтове за предизвикателства в кодирането като Codewars, HackerRank и LeetCode наистина ми помогна с разбирането. Стилът ми на учене включва практическа работа и изпробване на предизвикателства, така че внедряването на структура от данни или използването на такава в предизвикателство с код беше много полезно в моето обучение.

По-долу ще разгледам 3 модела за решаване на проблеми, които установих, че постоянно се срещат при опити за предизвикателства при кодиране.

  1. Честотомер
  2. Множество указатели
  3. Плъзгащ се прозорец

Честотомер

Примерно предизвикателство за кодиране изглежда по следния начин: „Дадени са 2 низа, определете дали всеки низ е анаграма на другия. Анаграмата е дума или фраза, образувана чрез пренареждане на буквите на различна дума или фраза.“

В условия, които не използват никакви структури от данни и използвайки примера по-горе. Подходът, който ще използваме, е да използваме обект, за да следим появата на всяка буква във входния низ.

В следващите раздели научавате, че „обектът“, който съхраняваме нашите различни двойки ключ:стойност, се нарича хеш карта/таблица. Те могат да се усложнят, тъй като двойките ключ:стойност могат да се състоят от всички типове данни и други структури от данни.

function validAnagram(str1, str2){
   if (str1.length != str2.length ) { return false }
   const FC1 = {}
   const FC2 = {}
   for ( let val of str1){
      FC1[val] = ( FC1[val] || 0 ) + 1
   }
   for ( let val of str2){
      FC2[val] = ( FC2[val] || 0 ) + 1
   }
   for ( let key in FC1 ) {
      if ( !(key in FC2)) { return false }
      if ( FC2[key] !== FC1[key] ) { return false }
   }
   return true;
}

Има множество подходи за решаване на този тип проблем, но ако опишем това решение по отношение на нотацията BigO, можем да опишем времевата сложност като O(3n), което опростява до O(n) и

Множество указатели

За това предизвикателство за кодиране имплементирайте функция, която приема сортиран масив и връща цяло число от уникалните стойности в масива.

Проблем, който има множество указатели, обикновено означава преминаване през масив, указател може да започне в началото, средата, края или където и логично да зададете указателя да бъде. Обичайно е, подобно на проблема по-горе, указателите да се разместват така, че да сравнявате един елемент със следващия елемент. Единият елемент е елемент за „четене“, а другият е елемент за „запис“, като използвате този подход, можете също да редактирате масиви на място.

function countUniqueValues(array){
   let p1 = 0
   let p2 = 1
   if ( array.length === 0) { return 0}
   for (let i = 0; i < array.length; i++ ) {
      if (array[p1]===array[p2]) {
         p2++}
      if ( array[p1] !== array[p2]) {
         p1++;
         array[p1] = array[p2];
      }
   }
   return p1
}

Този подход предотвратява вложени цикли и позволява време на изпълнение O(n), а не време на изпълнение O(n²), което причиняват вложени цикли. Горното решение също има пространствена сложност O(1), тъй като този алгоритъм използва само 2 променливи на указателя.

Имайте предвид, че когато използвате указатели, обичайните проблеми вече изискват 2 или 3 указателя и може да се наложи да преосмислите своя подход. Освен това този подход обикновено изисква сортиран масив, за да работи.

Плъзгащ се прозорец

Намерих този модел за най-малко интуитивен и открих, че проблемите, които използват този модел, не са толкова популярни, колкото 2-те по-горе. Въпреки това наличието на този модел в репертоара е полезно при разбиването на по-сложни проблеми.

Прозорецът може да се счита за подмножество от данни, масив или низ, които трябва да се следят. Прозорецът може да бъде увеличен или намален чрез промяна на индексите или позициите, които желаем да видим. Следващият пример включва максимизиране на подмасив при даден несортиран масив и размер на подмасив.

Създайте функция, която приема масив от несортирани цели числа и цяло число. Връща максималната стойност на последователните елементи в подмасив, равна на въведеното цяло число.

function maxSubarraySum(array, num){
   
   if (array.length < num) { return null}
   
   let maxSum = 0
   let tempSum = 0
   for ( let i=0; i < num; i++) {
      tempSum+=array[i]
   }
   maxSum = tempSum
   for ( let j=num; j < array.length; j++ ){
      tempSum = tempSum - array[j-num] + array[j]
      if (tempSum > maxSum) { maxSum = tempSum }
   }
   
  return maxSum
}

Ако проучите горното решение, основната настройка е, че първият цикъл инициира прозореца, докато вторият цикъл „плъзга“ прозореца надолу по входния масив. Наивното решение на този проблем обикновено включва вложени цикли за тестване на всяка комбинация от елементи, но прост дизайн като този по-горе позволява едно преминаване O(n) и постоянна пространствена сложност O(1), тъй като ние използваме само 2 допълнителни променливи.

Има много модели на проблеми, но това бяха 3-те, с които се сблъсках за първи път в курса на Colt Steele. Не мога да подчертая достатъчно важността на следване на курс или някаква учебна програма, когато изучавате материали като структури от данни и алгоритми. Много се наслаждавам на процеса досега и планирам да продължа обучението си, както и да пиша блогове по теми, които срещам.

Повече съдържание в plainenglish.io