Овладение искусством решения проблем: понимание и применение общих шаблонов решения проблем

1. Счетчик частоты

Этот шаблон использует объекты или наборы для сбора значений/частот значений. Это часто позволяет избежать необходимости использования вложенных циклов или операций O(N²) с массивами/строками.

// Function that returns true if every value in the array has 
// it's corresponding value squared in the second array. The frequency of 
// values must be the same.

// Naive Solution - Time Complexity - N^2
function sameSquared(arr1, arr2){
    if(arr1.length !== arr2.length){
        return false;
    }
    for(let i = 0; i < arr1.length; i++){
        let correctIndex = arr2.indexOf(arr1[i] ** 2)
        if(correctIndex === -1) {
            return false;
        }
        arr2.splice(correctIndex,1)
    }
    return true
}

// Refactored - Time Complexity - O(n)
function sameSquared(arr1, arr2){
    if(arr1.length !== arr2.length){
        return false;
    }
    let frequencyCounter1 = {}
    let frequencyCounter2 = {}
    for(let val of arr1){
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
    }
    for(let val of arr2){
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1        
    }
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}

2. Несколько указателей

Создание указателей или значений, которые соответствуют индексу или положению и перемещаются к началу, концу или середине на основе определенного условия, очень эффективно для решения задач с минимальной объемной сложностью. также.

// Function that accepts a sorted array of integers. The function should
// find the first pair where the sum is 0. Returns an array that includes
// both values that sum to zero or undefined if a pair does not exist.

// Naive Solution - Time Complexity - O(N^2) - Space Complexity - O(1)
function sum(arr){
    for(let i = 0; i < arr.length; i++){
        for(let j = i+1; j < arr.length; j++){
            if(arr[i] + arr[j] === 0){
                return [arr[i], arr[j]];
            }
        }
    }
}

// Refactored Solution- Time Complexity - O(N) - Space Complexity - O(1) 
function sum(arr){
    let left = 0;
    let right = arr.length - 1;
    while(left < right){
        let sum = arr[left] + arr[right];
        if(sum === 0){
            return [arr[left], arr[right]];
        } else if(sum > 0){
            right--;
        } else {
            left++;
        }
    }
}

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

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

// Function which accepts an array of integers and a number called n. 
// The function calculates the maximum sum of n consecutive elements
// in the array.

// Naive Solution - Time Complexity - O(N^2)
function maxSubarraySum(arr, num) {
  if ( num > arr.length){
    return null;
  }
  var max = -Infinity;
  for (let i = 0; i < arr.length - num + 1; i ++){
    temp = 0;
    for (let j = 0; j < num; j++){
      temp += arr[i + j];
    }
    if (temp > max) {
      max = temp;
    }
  }
  return max;
}

// Refactored Solution - Time Complexity - O(N)
function maxSubarraySum(arr, num){
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

4. Разделяй и властвуй

Этот шаблон включает в себя разделение набора данных на более мелкие фрагменты, а затем повторение процесса с подмножеством данных. Этот шаблон может значительно уменьшить временную сложность.

// Function that accepts a value and returns the index where the value 
// passed to the function is located. If the value is not found, function 
// returns -1

// Naive Solution - Time Complexity O(N) - Linear Search
function search(arr, val){
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === val){
            return i;
        }
    }
    return -1;
}

// Refactored Solution - Time Complexity - Log(N) - Binary Search
function search(array, val) {
 
    let min = 0;
    let max = array.length - 1;
 
    while (min <= max) {
        let middle = Math.floor((min + max) / 2);
        let currentElement = array[middle];
 
        if (array[middle] < val) {
            min = middle + 1;
        }
        else if (array[middle] > val) {
            max = middle - 1;
        }
        else {
            return middle;
        }
    }
 
    return -1;
}

Заключение:

• Разработка подхода к решению проблем невероятно важна.
• Думая о коде перед его написанием, вы всегда быстрее решаете проблемы.
• Помните о шаблонах решения проблем.
• Использование частотомеров, нескольких указателей, скользящих окон и принципа «разделяй и властвуй» поможет сократить время и пространство и решить более сложные задачи.

Не стесняйтесь делиться своими мыслями. Вы можете связаться со мной в Linkedin или Twitter. Вы можете проверить все исходные коды на Github.