СТРУКТУРИ НА ДАННИ И АЛГОРИТМИ

Техника с два указателя

Техниката на две точки е основен алгоритмичен подход, който играе основна роля в оптимизирането на решенията на специфични видове проблеми в компютърните науки. Тази стратегия включва използването на два указателя, често представени като индекси или препратки, които преминават през структура от данни, като масив, списък или низ, едновременно. Чрез манипулиране на позициите на тези два указателя, техниката има за цел ефективно да адресира широк кръг от проблеми, което я прави ценен инструмент в инструментариума на програмиста.

Има няколко начина за прилагане на две точки. За начало нека разгледаме следния метод:

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

Превръщане на тази идея в инструкции:

1. Стартирайте единия указател при първия индекс 0, а другия указател при последния индекс input.length - 1.
2. Използвайте цикъл while, докато указателите станат равни един на друг.
3. При всяка итерация на цикъла премествайте указателите един към друг. Това означава или увеличаване на указателя, който е започнал от първия индекс, намаляване на указателя, който е започнал от последния индекс, или и двете. Решението кои указатели да се преместят ще зависи от проблема, който се опитваме да решим.

Ето малко псевдокод, илюстриращ концепцията:

function fn(arr):
    left = 0
    right = arr.length - 1

    while left < right:
        Do some logic here depending on the problem
        Do some more logic here to decide on one of the following:
            1. left++
            2. right--
            3. Both left++ and right--

Силата на тази техника е, че никога няма да имаме повече от O(n) итерации за цикъла while, защото указателите започват n далеч от един към друг и се приближавайте поне с една крачка във всяка итерация. Следователно, ако можем да запазим работата във всяка итерация при O(1), тази техника ще доведе до линейно време на изпълнение, което обикновено е най-доброто възможно време на изпълнение.

Нека да разгледаме някои от случаите на използване на тази техника:

Пример 1: Даден е низ s, върнете true, ако е палиндром, false в противен случай.

Низът е палиндром, ако се чете еднакво напред и назад. Това означава, че след като го обърнете, той все още е същият низ. Например: “abcdcba” или “racecar”.

Метод 1:Наивен подход

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

Псевдокод:

function isPalindrome(s):
    reversedS = reverse(s)
    if s == reversedS:
        return true
    else:
        return false

Обяснение:

1. Започваме с обръщане на входния низ s с помощта на функция reverse(s).
2. След това сравняваме оригиналния низ s с обърнатия низ reversedS.
3. Ако са идентични, връщаме true, което показва, че s е палиндром. В противен случай връщаме false.

Код на JavaScript:

function isPalindrome(s) {
    // convert to lowercase
    s = s.toLowerCase();

    // Reverse the input string
    const reversedS = s.split('').reverse().join('');
    
    // Compare the original string with the reversed string
    return s === reversedS;
}

// Test cases
const string1 = "racecar";
const string2 = "Radar";

console.log(isPalindrome(string1)); // Output: true
console.log(isPalindrome(string2)); // Output: true

Анализ на сложността:

• Времева сложност: Обръщането на низ отнема O(n) време, където n е дължината на низа. Сравнението също отнема O(n) време. Следователно общата времева сложност е O(n).
• Сложност на пространството: Нуждаем се от допълнително място за съхранение на обърнатия низ, който заема O(n) място. И така, пространствената сложност е O(n).

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

Метод 2: Техника с два указателя

Техниката с два указателя е умна стратегия, която използва факта, че за палиндромен низ първият знак е същият като последния знак, вторият знак е същият като предпоследния знак и т.н. Използвайки два указателя, единият започващ от началото на низа, а другият от края, можем ефективно да проверим дали всички съответни символи са равни. Ако открием несъответствие в която и да е точка, можем веднага да заключим, че низът не е палиндром.

Код на JavaScript:

function isPalindrome(s) {
    let left = 0;             // Pointer starting from the beginning
    let right = s.length - 1; // Pointer starting from the end
    
    while (left < right) {
        // Compare the characters at the left and right pointers, ignoring case
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false; // Mismatch found, not a palindrome
        }
        
        // Move the pointers towards each other
        left++;
        right--;
    }
    
    return true; // No mismatch found, it's a palindrome
}

// Test cases
const string1 = "racecar";
const string2 = "Radar";

console.log(isPalindrome(string1)); // Output: true
console.log(isPalindrome(string2)); // Output: true

Забележете, че ако входът е масив от символи вместо низ, алгоритъмът няма да се промени. Техниката с две точки работи, докато индексните променливи се движат по някаква абстрактна итерируема.

Този алгоритъм е много ефективен, тъй като не само работи в O(n), но също така използва само O (1)интервал. Без значение колко голям е входът, винаги използваме само две цели числа. Времевата сложност е O(n), защото итерациите на цикъла while струват O(1) всяка и никога не може да има повече от O(n) итерации на цикъла while — указателите започват на разстояние n един от друг и се приближават с една стъпка на всяка итерация.

Пример 2: При даден сортиран масив от уникални цели числа и целево цяло число, върнете true, ако съществува двойка числа, които сумират за насочване, false в противен случай. Тази задача е подобна на „Две суми“. (В Two Sum входът не се сортира).

Например, дадени nums = [1, 2, 4, 6, 8, 9, 14, 15] и target = 13, върнете true, защото 4 + 9 = 13.

Метод 1:Подход с груба сила

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

Псевдокод:

function hasPairWithSum(nums, target):
    n = length of nums
    for i from 0 to n-2:
        for j from i+1 to n-1:
            if nums[i] + nums[j] == target:
                return true
    return false

Обяснение:

1. Инициализираме променлива n, за да съхраним дължината на входния масив nums.
2. Използваме два вложени цикъла, за да преминем през всички възможни двойки числа в масива, представени от индекси i и j.
3. За всяка двойка проверяваме дали сумата от nums[i] и nums[j] е равна на целевото цяло число.
4. Ако бъде намерена двойка, която отговаря на условието, връщаме true, което показва, че съществува двойка с желаната сума.
5. Ако не бъде намерена такава двойка след проверка на всички възможни двойки, връщаме false.

Код на JavaScript:

function hasPairWithSum(nums, target) {
    const n = nums.length;

    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return true;
            }
        }
    }

    return false;
}

// Example usage:
const nums = [1, 2, 4, 6, 8, 9, 14, 15];
const target = 13;
const result = hasPairWithSum(nums, target);
console.log(result); // Output: true (4 + 9 = 13)

Анализ на сложността:

• Времева сложност: Подходът с груба сила проверява всички възможни двойки числа, което води до времева сложност от O(n²), където n е броят на елементите в масива.
• Пространствена сложност: Алгоритъмът използва постоянно количество допълнително пространство, така че пространствената сложност е O(1).

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

Метод 2: Техника с два указателя

Нека използваме примерния вход. С два указателя започваме, като гледаме първото и последното число. Сборът им е 1 + 15 = 16. Тъй като 16 > target, трябва да направим текущата ни сума по-малка. Следователно трябва да преместим показалеца right. Сега имаме 1 + 14 = 15. Отново преместете десния показалец, защото сумата е твърде голяма. Сега, 1 + 9 = 10. Тъй като сумата е твърде малка, трябва да я увеличим, което може да стане чрез преместване на показалеца left. 2 + 9 = 11 < target, така че го преместете отново. И накрая, 4 + 9 = 13 = target.

Причината, поради която този алгоритъм работи: тъй като числата са сортирани, преместването на левия показалец трайно увеличава стойността, към която сочи левият показалец (nums[left] = x). По същия начин преместването на десния показалец постоянно намалява стойността, към която сочи десният показалец (nums[right] = y). Ако имаме x + y > target, тогава никога не можем да имаме решение с y, защото x може само да се увеличава. Така че, ако съществува решение, можем да го намерим само чрез намаляване на y. Същата логика може да се приложи към x, ако x + y < target.

Код на JavaScript:

function hasPairWithSum(nums, target) {
    let left = 0;             // Pointer starting from the beginning
    let right = nums.length - 1; // Pointer starting from the end
    
    while (left < right) {
        const sum = nums[left] + nums[right];
        
        if (sum === target) {
            return true; // Pair found, return true
        } else if (sum < target) {
            left++; // Move the left pointer to increase the sum
        } else {
            right--; // Move the right pointer to decrease the sum
        }
    }
    
    return false; // No pair found, return false
}

const nums = [1, 2, 4, 6, 8, 9, 14, 15];
const target = 13;

const result = hasPairWithSum(nums, target);
console.log(result); // Output: true (4 + 9 = 13)

Този алгоритъм използва O(1) пространство и има времева сложност O(n).

Друг подход с техниката на две точки

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

Следният метод е приложим, когато проблемът има две итерируеми във входа, например два масива.

Пример 3: Дадени са два сортирани масива с цели числа arr1 и arr2, връща нов масив, който комбинира и двата и също е сортиран.

Тривиалният подход би бил първо да комбинирате двата входни масива и след това да извършите сортиране. Ако имаме n = arr1.length + arr2.length, тогава това дава времева сложност от O(n⋅logn) (разходите за сортиране). Това би бил добър подход, ако входните масиви не са сортирани, но тъй като те са сортирани, можем да се възползваме от техниката на два указателя, за да подобрим до O(n ).

Решение: Техника с две точки

Можем да изградим масива с отговори ans един по един елемент. Започнете два указателя от първия индекс на всеки масив и сравнете техните елементи. При всяка итерация имаме 2 стойности. Която стойност е по-ниска, трябва да е първа в отговора, така че я добавете към отговора и преместете съответния показалец.

Код на JavaScript:

var combine = function(arr1, arr2) {
    // Initialize an empty array to store the merged result
    let ans = [];
    // Initialize two pointers for arr1 and arr2
    let i = 0, j = 0;
    
    // Loop until we reach the end of either arr1 or arr2
    while (i < arr1.length && j < arr2.length) {
        // Compare the current elements at arr1[i] and arr2[j]
        if (arr1[i] < arr2[j]) {
            // If arr1[i] is smaller, push it to the result and move the arr1 pointer
            ans.push(arr1[i]);
            i++;
        } else {
            // If arr2[j] is smaller or equal, push it to the result and move the arr2 pointer
            ans.push(arr2[j]);
            j++;
        }
    }
    
    // If there are remaining elements in arr1, append them to the result
    while (i < arr1.length) {
        ans.push(arr1[i]);
        i++;
    }
    
    // If there are remaining elements in arr2, append them to the result
    while (j < arr2.length) {
        ans.push(arr2[j]);
        j++;
    }
    
    // Return the merged and sorted array
    return ans;
}

Както в предишните два примера, този алгоритъм има времева сложност O(n) и използва O(1) пространство (ако не не броим изхода като допълнително пространство, което обикновено не го правим).

Заключителни бележки:

От решаващо значение е да се признае, че обсъдените тук техники служат по-скоро като ценни насоки, отколкото като строги правила. Конкретният проблем, който срещате, може да изисква персонализиран подход. Например, в първия метод инициирахме указателите при първия и последния индекс, но някои ситуации може да изискват различна начална точка за указателите. По същия начин, вторият метод включва преместване на два указателя напред по отделни входове, но има сценарии, при които можете да се справите с един вход, но въпреки това да започнете и двата указателя от първия индекс и да ги придвижите напред в тандем.

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