Если вы читали мой предыдущий блог о нотации Big O, вы, возможно, помните, что алгоритм определяется как конечная последовательность четко определенных, реализуемых компьютером инструкций, обычно для решения класса проблем или для выполнения вычислений ( Википедия). Все инженеры-программисты должны изучать алгоритмы, поскольку они могут помочь нам решить проблемы, с которыми мы можем столкнуться на рабочем месте.

Возможно, вы читаете это сообщение в блоге, потому что в настоящее время ищете работу. Если это так, то у LeetCode и HackerRank есть сотни практических проблем алгоритмов, которые соискатели могут использовать. Цель этого блога - вооружить вас несколькими стратегиями, которые помогут решить эти типы проблем, а также те, с которыми вы можете столкнуться на собеседовании и на работе.

В этом блоге мы обсудим следующие три стратегии:

  1. Счетчик частоты
  2. Несколько указателей
  3. Скользящее окно

Эти стратегии взяты из курса Кольта Стила по алгоритмам JavaScript и структурам данных Masterclass Udemy, который я настоятельно рекомендую. Примеры в основном взяты из LeetCode.

Частотомер

Подход с использованием частотомера может быть применен к алгоритмам, в которых вам нужно собирать значения или проверять количество вхождений значения. Эта стратегия использует объекты или наборы и позволяет избежать вложенных циклов (Стил). Более того, частотомеры улучшают временную сложность наших решений с O (n²) при использовании вложенных циклов до O (n).

Теперь, чтобы продемонстрировать на практике стратегию частотомера, давайте рассмотрим пример из Leetcode.

Source: https://leetcode.com/problems/valid-anagram/
Problem:
Given two strings s and t , write a function to determine if t is an anagram of s.
  Test Case #1
     Input: s = "tennis", t = "entsno"
     Output: false
  Test Case #2
     Input: s = "tan", t = "nat"
     Output: true

В этом примере мы будем использовать метод частотомера, чтобы проверить, все ли буквы в каждой строке совпадают и эти буквы встречаются одинаковое количество раз. Если обе эти проверки верны, мы знаем, что s и t являются анаграммами.

Solution:
var isAnagram = function(s, t) {
  // if string lengths are different, it's impossible for string t 
    // to be an anagram
  if (s.length !== t.length) {
    return false;
  }
  const lookup = {};
  for (let i = 0; i < s.length; i++) {
    let letter = s[i];
    // if letter exists, increment by 1, otherwise set to 1
    lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }
  
  console.log(lookup)
   for (let i = 0; i < t.length; i++) {
    let letter = t[i];
    // if letter not found or letter value is zero then string t is
      // not an anagram of string s
    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
    console.log(lookup)
   }
   return true;
};
isAnagram("tennis", "entsno")
isAnagram("tan", "nat")
Test Case #1 Output: 
// lookup object after looping over s string
{ t: 1, e: 1, n: 2, i: 1, s: 1 }
// lookup object decrementing by matching letters in t string 
  //  after each loop
{ t: 1, e: 0, n: 2, i: 1, s: 1 }
{ t: 1, e: 0, n: 1, i: 1, s: 1 }
{ t: 0, e: 0, n: 1, i: 1, s: 1 }
{ t: 0, e: 0, n: 1, i: 1, s: 0 }
{ t: 0, e: 0, n: 0, i: 1, s: 0 }
false
Test Case #2 Output:
// lookup object after looping over s string
{ t: 1, a: 1, n: 1 }
// lookup object decrementing by matching letters in t string 
  //  after each loop
{ t: 1, a: 1, n: 0 }
{ t: 1, a: 0, n: 0 }
{ t: 0, a: 0, n: 0 }
true

В приведенном выше решении мы сначала проверяем, что строки имеют одинаковую длину. У нас есть эта проверка, потому что, если строки имеют разную длину, мы знаем, что они не могут быть анаграммой, и поэтому нам не нужно обрабатывать какой-либо дополнительный код. Первый цикл решения создает сводку всех букв и их частот в строке s в объект, называемый поиском. Второй цикл проверяет, присутствует ли буква в строке t в поиске и значение больше 0. Если оба эти условия истинны, то частота буквы в поиске уменьшается на 1; в противном случае мы знаем, что строка t не является анаграммой строки s. Если второй цикл повторяет последнюю букву в строке t, тогда мы возвращаем истину в качестве частот, и все буквы в поиске будут равны 0.

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

Стратегия множественных указателей обычно используется для линейных структур (то есть массивов, строк и связанных списков). Типы проблем, при которых полезно использовать несколько указателей, - это когда вам нужно найти значение или пару значений, которые удовлетворяют определенному условию. Кольт Стил описывает процесс того, как это работает, следующим образом: «Создание указателей или значений, которые соответствуют индексу или позиции и перемещаются к началу, концу или середине в зависимости от определенного условия» (Стил). Стил также отмечает, что решения с несколькими указателями имеют эффективную временную сложность O (n) и минимальную пространственную сложность O (1).

Теперь, чтобы продемонстрировать на практике стратегию использования нескольких указателей, давайте рассмотрим пример.

Source: Colt Steele's JavaScript Algorithms and Data Structures Masterclass Course on Udemy
Problem:
Write a function called sumZero which accepts a sorted array of integers.The function should find the first pair where the sum is 0. Return an array that includes both values that sum to zero or undefined if a pair does not exist.
Test Case #1
     
     Input = [-3, -2, -1, 0, 1, 2, 3]
     Output = [-3, 3]
Test Case #2
     
     Input = [-2, 0, 1, 3]
     Output = undefined
Test Case #3
     
     Input = [1, 2, 3]
     Output = undefined

В этом примере мы будем использовать стратегию множественных указателей, чтобы увидеть, содержит ли массив два значения, которые при сложении равны 0. Поскольку наш массив отсортирован, мы можем разместить один указатель в начале и один в конце массива. Затем верните значения двух указателей, если они в сумме равны 0.

Solution:
var sumZero = function(arr) {
     let pointer1 = 0
     let pointer2 = arr.length - 1;
     // Needs to be less than instead of less than or equal to
        // to prevent a single 0 creating a false positive.
      while(pointer1 < pointer2) {
         let sum = arr[pointer1] + arr[pointer2];
         console.log(sum, arr[pointer1], arr[pointer2])     
         if(sum === 0) {
              return [arr[pointer1], arr[pointer2]];
         } else if(sum > 0) {
              pointer2--;
         } else {
              pointer1++;
         }
      }
};
sumZero([-3, -2, -1, 0, 1, 2, 3])
sumZero([-2, 0, 1, 3])
sumZero([1, 2, 3])
Test Case #1 Output:
// console.log of sum, value at pointer1, and value at pointer2
0 -3 3
// result
[ -3, 3 ]
Test Case #2 Output:
// console.log of sum, value at pointer1, and value at pointer2
1 -2 3
-1 -2 1
1 0 1
// result
undefined
Test Case #3 Output:
// console.log of sum, value at pointer1, and value at pointer2
4 1 3
3 1 2
// result
undefined

В приведенном выше решении мы сначала устанавливаем позицию pointer1 в начало массива и pointer2 в конец массива. Затем мы видим, чему равна сумма значений в указателе1 и указателе2. Если сумма отрицательна, нам нужно переместить указатель1 на одно значение вправо. Если сумма положительная, нам нужно переместить указатель2 на одно значение влево. Если сумма равна 0, значит, мы нашли искомую пару и возвращаем значения. Мы продолжаем этот шаблон до тех пор, пока не найдем пару, сумма которой равна 0, или не дойдем до последней итерации цикла while, где позиция указателя1 меньше позиции указателя2 и не вернем значение undefined.

Дополнительные примеры:

Source: https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/727/
Problem: 
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
     Input: nums = [0,0,1,1,1,2,2,3,3,4]
     Output: 5, nums = [0,1,2,3,4]

Solution:
var removeDuplicates = function(nums) {
    if (nums.length === 0) {
        return 0
    }
    
    let pointer1 = 0
for (let pointer2 = 1; pointer2 < nums.length; pointer2++) {
        if (nums[pointer1] !== nums[pointer2]) {
            pointer1++;
            nums[pointer1] = nums[pointer2]
        }
    }
    
    return pointer1 + 1
    
    
};
Source: https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/567/
Problem: 
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
     Input: [0,1,0,3,12]
     Output: [1,3,12,0,0]
Solution:
var moveZeroes = function(nums) {
   let pointer1 = 0
    
       for(let pointer2 = 0; pointer2 < nums.length; pointer2++) {
           if(nums[pointer2] !== 0) {
               let temp = nums[pointer1]
               nums[pointer1] = nums[pointer2]
               nums[pointer2] = temp
               pointer1++
           }
       }
       return nums
};
moveZeroes([0,1,0,3,12])
Video Explanation: https://www.youtube.com/watch?v=0rPuILjoVsg

Раздвижное окно

Последняя стратегия, которую мы обсудим в этом блоге, - это скользящее окно. Подобно стратегии с несколькими указателями, скользящее окно обычно используется для линейных структур (то есть массивов и строк). Типы проблем, при которых полезно скользящее окно, - это когда вам нужно найти / отслеживать подмножество ввода, которое следует некоторому шаблону. Кольт Стил описывает процесс того, как это работает, следующим образом: «Этот шаблон включает создание окна, которое может быть либо массивом, либо числом от одной позиции к другой. В зависимости от определенного условия окно либо увеличивается, либо закрывается (и создается новое окно) »(Стил). Кроме того, использование скользящего окна предпочтительно, поскольку оно имеет временную сложность O (n).

Теперь, чтобы продемонстрировать стратегию скользящего окна на практике, давайте рассмотрим пример.

Source: Colt Steele's JavaScript Algorithms and Data Structures Masterclass Course on Udemy
Problem:
Write a function called maxSubarraySum which accepts an array of integers and a number called n. the function should calculate the maximum sum of n consecutive elements in the array.
Test Case #1
     
     Input = [1,2,5,2,8,1,5], n = 2
     Output = 10
Test Case #2
     
     Input = [1,2,5,2,8,1,5], n = 4
     Output = 17

В этом примере мы будем использовать стратегию скользящего окна, чтобы найти наибольшую сумму из подмножества данных. Мы сделаем это, создав окно, размер которого определяется n. Затем мы сдвигаем окно на 1 позицию вправо и определяем, больше ли эта сумма, чем предыдущие суммы. Затем, как только последнее окно будет суммировано, мы вернем наибольшую сумму.

Solution:
function maxSubarraySum(arr, n){
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < n) return null;
  for (let i = 0; i < n; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = n; i < arr.length; i++) {
    tempSum = tempSum - arr[i - n] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}
maxSubarraySum([1,2,5,2,8,1,5],2)
maxSubarraySum([1,2,5,2,8,1,5],4)
Test Case #1 Output:
// the initial maxSum
3
// sliding window, tempSum on left and previous maxSum on right
7 3
7 7
10 7
9 10
6 10
// result
10
Test Case #2 Output:
// the initial maxSum
10
// sliding window, tempSum on left and previous maxSum on right
17 10
16 17
16 17
// result
17

В приведенном выше решении мы сначала объявляем две переменные, maxSum и tempSum, и устанавливаем их равными 0. Затем мы устанавливаем граничный случай для возврата null, если n, размер окна, больше, чем массив. Затем мы находим суммирование первого окна, перебирая только указанное количество из n чисел и добавляя каждое число к переменной maxSum. Затем мы устанавливаем нашу переменную tempSum в значение maxSum; временная сумма будет нашим скользящим окном. Затем во втором цикле мы находим значение следующего окна, вычитая первое значение из нашего начального окна (arr [0]) и добавляя следующее значение в массиве, которого не было в нашем начальном окне (т. Е. Arr [3 ], если первое окно содержало arr [0], arr [1], arr [2]), и установив это значение равным значению tempSum. Затем мы устанавливаем значение maxSum равным большему из tempSum и предыдущего maxSum. Продолжаем этот процесс, пока не дойдем до конца массива и не вернем maxSum

Спасибо, что нашли время, чтобы узнать больше о стратегиях решения алгоритмов. Я надеюсь, что этот блог снабдил вас несколькими стратегиями, которые помогут вам в поиске работы и / или работе.

Ресурсы

Стил, К. (нет данных). Мастер-класс по алгоритмам JavaScript и структурам данных. Онлайн-курс.

Алгоритм. (2020, 07 октября). Получено 10 октября 2020 г. с сайта https://en.wikipedia.org/wiki/Algorithm.