Алгоритм LeetCode ставит под сомнение процесс чистки зубов (JavaScript)

алгоритм JavaScript LeetCode

Потребовалось более десяти дней, чтобы прочитать «Алгоритм», а затем повторно ответить на вопросы LeetCode, и я многому научился. На этот раз хорошо запишите свой опыт.
Я разместил весь код для ответа на вопрос на github для справки.
адрес проекта:GitHub.com/фиолетовый Джек/…
Адрес темы:Ли ТСО's.com/problemset/…

Мне стыдно признаться, что «Обмен вопросами по логике LeetCode», который я написал ранее, на самом деле менее практичен, и все это касается решений. ВажнееЯ не изучал алгоритмы систематически(самоучка по программированию). Таким образом, это приводит к следующим проблемам:

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

После этого я прочитал книгу "Алгоритмы (4-е издание)", сделал это еще раз и попытался решить проблему с АС, и проблемы снова навалились. Так что на этот раз это заняло намного больше времени, чем в первый раз.

Решения различных проблем

Не мудрствуя лукаво, давайте систематически разберем некоторые алгоритмы и варианты решения задачи.

бинарное дерево

Двоичные деревья в основном используют рекурсию слева и справа от двух элементов и рекурсию вниз. Например:

Вычислить максимальную глубину бинарного дерева

var maxDepth = function (root) {
    if (root == null) return 0
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};

Представлять бинарное дерево как двумерный массив

var levelOrder = function(root) {
    let ans = []
    helper(root, ans, 0)
    return ans
};

function helper(node, ans, i){
    if (node == null) return
    if (i == ans.length) ans.push([])
    ans[i].push(node.val)

    helper(node.left, ans, i + 1)
    helper(node.right, ans, i + 1)
}

Все они ищут данные бинарного дерева рекурсивно вниз слой за слоем.

вопрос о возможности

Эти типы вопросов обычно сообщают вам набор данных, а затем определяют вероятность, минимальное или максимальное значение. Например:

Учитывая несколько номиналов монет и общую сумму, используйте наименьшее количество монет, чтобы составить общую сумму.

var coinChange = function (coins, amount) {
    let max = amount + 1
    let dp = new Array(amount + 1)
    dp.fill(max)
    dp[0] = 0

    for (let i = 1; i < max; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount]
};

Используя динамическое программирование (DP), перечисляются от 0 до минимального количества монет, необходимых для целевых линий.

Выясните, сколько существует возможностей от верхнего левого угла матрицы до нижнего правого угла и только вправо и вниз.

var uniquePaths = function (m, n) {
    const pos = new Array(m)
    for (let i = 0; i < m; i++) {
        pos[i] = new Array(n)
    }
    for (let i = 0; i < n; i++) {
        pos[0][i] = 1
    }
    for (let i = 0; i < m; i++) {
        pos[i][0] = 1
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            pos[i][j] = pos[i - 1][j] + pos[i][j - 1]
        }
    }
    return pos[m - 1][n - 1]
};

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

Получить максимальное совокупное значение последовательных элементов данного массива

var maxSubArray = function (nums) {
    let count = nums[0], maxCount = nums[0]
    for (let i = 1; i < nums.length; i++) {
        count = Math.max(count + nums[i], nums[i])
        maxCount = Math.max(maxCount, count)    
    }
    return maxCount
};

Приведенный выше вопрос сохраняет и возвращает максимальное значение путем непрерывного сравнения максимального значения.

На самом деле вопрос о возможности используетдинамическое программированиеЭто проще и понятнее, чем использование алгоритмов DFS и BFS. (Я использую DFS для частого TLE)

найти

Часто встречающиеся проблемы поиска, такие как поиск значения, обычно используют следующие методы:

  • Алгоритм сортировки (сортировку легче найти)
  • бинарный поиск
  • Поиск перемещения по индексу (это имя метода, как я думаю, возможно, это то, что оно означает ~)

Найдите значение в 2D-матрице, которое увеличивается по горизонтали и вертикали

var searchMatrix = function (matrix, target) {
    if (matrix.length == 0) return false
    let row = 0, col = matrix[0].length - 1
    while (true) {
        if (matrix[row][col] > target && col > 0) {
            col--
        } else if (matrix[row][col] < target && row < matrix.length - 1) {
            row++
        } else if (matrix[row][col] == target) {
            return true
        } else {
            break
        }
    }
    return false
};

Сначала найдите положение в правом верхнем углу и найдите целевое значение, изменив координаты положения. Для поиска результатов использовался метод поиска с перемещением по индексу.

Найдите положение самого левого и самого правого числа в массиве

var searchRange = function (nums, target) {
    let targetIndex = binarySearch(nums, target, 0, nums.length - 1)
    if (targetIndex == -1) return [-1, -1]
    let l = targetIndex, r = targetIndex
    while(l > 0 && nums[l - 1] == target){
        l--
    }
    while(r < nums.length - 1 && nums[r + 1] == target){
        r++
    }
    return [l, r]
};

function binarySearch(arr, val, lo, hi) {
    if (hi < lo) return -1
    let mid = lo + parseInt((hi - lo) / 2)

    if (val < arr[mid]) {
        return binarySearch(arr, val, lo, mid - 1)
    } else if (val > arr[mid]) {
        return binarySearch(arr, val, mid + 1, hi)
    } else {
        return mid
    }
}

Используйте этот вопросдихотомиячтобы найти значение индекса целевого числа, затемМетод перемещения индексаНайдите символы слева и справа соответственно. Получить значение индекса левой и правой сторон и вернуться.

палиндром

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

Найти самый длинный палиндром в заданной строке

var longestPalindrome = function (s) {
    let maxLength = 0, left = 0, right = 0
    for (let i = 0; i < s.length; i++) {
        let singleCharLength = getPalLenByCenterChar(s, i, i)
        let doubleCharLength = getPalLenByCenterChar(s, i, i + 1)
        let max = Math.max(singleCharLength, doubleCharLength)
        if (max > maxLength) {
            maxLength = max
            left = i - parseInt((max - 1) / 2)
            right = i + parseInt(max / 2)
        }
    }
    return s.slice(left, right + 1)
};

function getPalLenByCenterChar(s, left, right) {
    // 中间值为两个字符，确保两个字符相等
    if (s[left] != s[right]){
        return right - left
    }
    while (left > 0 && right < s.length - 1) {
        left--
        right++
        if (s[left] != s[right]){
            return right - left - 1
        }
    }
    return right - left + 1
}

дорожные вопросы

Путь вопросов может быть выполнен с использованием алгоритмов поиска в глубину (DFS) и в ширину (BFS). Я обычно использую для этого DFS. Целевой путь постоянно находится путем рекурсивной маркировки пройденного пути. Такие как:

Определяет, можно ли составить слово, используя соседние буквы в двумерном массиве букв данного слова.(212 вопросов)

let hasWord = false

var findWords = function (board, words) {
    var ans = []
    for (let word of words) {
        for (let j = 0; j < board.length; j++) {
            for (let i = 0; i < board[0].length; i++) {
                if (board[j][i] == word[0]) {
                    hasWord = false
                    DFS(word, board, 0, j, i, "")
                    if (hasWord) {
                        if (!ans.includes(word))
                            ans.push(word)
                    }
                }
            }
        }
    }
    return ans
};

function DFS(word, board, index, j, i, subStr) {
    if (word[index] == board[j][i]) {
        subStr += board[j][i]
        board[j][i] = "*"
        if (j < board.length - 1)
            DFS(word, board, index + 1, j + 1, i, subStr)
        if (j > 0)
            DFS(word, board, index + 1, j - 1, i, subStr)
        if (i < board[0].length - 1)
            DFS(word, board, index + 1, j, i + 1, subStr)
        if (i > 0)
            DFS(word, board, index + 1, j, i - 1, subStr)
        board[j][i] = word[index]
    }
    if (index >= word.length || subStr == word) {
        hasWord = true
    }
}

Поскольку DFS — это путь к черному, если каждый элемент использует DFS для его поиска, будет тайм-аут. Если позволяют условия (например, поиск увеличивающегося массива), вы можете передатьустановить кешчтобы оптимизировать проблему тайм-аута поиска DFS.

Получает максимальную длину смежного возрастающего массива в двумерной матрице.

const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]

var longestIncreasingPath = function (matrix) {
    if (matrix.length == 0) return 0
    const m = matrix.length, n = matrix[0].length
    let max = 1

    let cache = new Array(m)
    for (let i = 0; i < m; i++){
        let child = new Array(n)
        child.fill(0)
        cache[i] = child
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let len = dfs(matrix, i, j, m, n, cache)
            max = Math.max(max, len)
        }
    }
    return max
}

function dfs(matrix, i, j, m, n, cache){
    if (cache[i][j] != 0) return cache[i][j]
    let max = 1
    for (let dir of dirs){
        let x = i + dir[0], y = j + dir[1]
        if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;
        let len = 1 + dfs(matrix, x, y, m, n, cache)
        max = Math.max(max, len)
    }
    cache[i][j] = max
    return max
}

Поместите длину, которую искал DFS, в кеш, если есть другие элементы, которые идут к текущему значению через DFS, просто верните максимальное значение кеша.

связанный список

С точки зрения JS связанный список — это структура данных, в которой строка объектов соединена указателем. добросовестное использованиеnextУказатель изменится на точку, чтобы завершить ряд операций со связанным списком. Такие как:

Сортировка связанного списка:

var sortList = function (head) {
    if (head == null || head.next == null) return head

    let prev = null, slow = head, fast = head
    while (fast != null && fast.next != null) {
        prev = slow
        slow = slow.next
        fast = fast.next.next
    }

    prev.next = null;

    let l1 = sortList(head)
    let l2 = sortList(slow)

    return merge(l1, l2)
};

function merge(l1, l2) {
    let l = new ListNode(0), p = l;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }

    if (l1 != null)
        p.next = l1;

    if (l2 != null)
        p.next = l2;

    return l.next;
}

использовалметод сортировки слиянием сверху внизСвязанный список отсортирован. использоватьslow.nextа такжеfast.next.nextОбе скорости получают узлы связанного списка и, таким образом, получают промежуточные значения.

Обратный порядок связанного списка

var reverseList = function(head) {
    let ans = null,cur = head
    while (cur != null) {
        let nextTmp = cur.next
        cur.next = ans
        ans = cur
        cur = nextTmp
    }
    return ans
};

Сортировать

Сортировка и поиск являются одними из самых важных задач в алгоритмах. Общие алгоритмы сортировки:

  • Сортировка вставками
  • сортировка выбором
  • быстрая сортировка
  • Сортировка слиянием
  • сортировка по подсчету

Дополнительные сведения об алгоритмах сортировки см.«Алгоритм домашней сортировки JS», автор статьи объяснял различные алгоритмы сортировки картинками и текстом, что легко понять.
Вот несколько примеров алгоритмов сортировки:

Найдите K-е наибольшее значение в массиве

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    for (let i = 0; i <= k; i++) {
        let max = i
        for (let j = i; j < nums.length; j++) {
            if (nums[j] > nums[max]) max = j
        }
        swap(nums, i, max)
    }
    return nums[k - 1]
};

function swap(arr, a, b) {
    let tmp = arr[a]
    arr[a] = arr[b]
    arr[b] = tmp
}

использовалсортировка выборомРанжируйте верхние значения K, чтобы получить результат.

для массивов с повторяющимися значениями[2,0,2,1,1,0]Сортировать

var sortColors = function (nums) {
    sort(nums, 0, nums.length - 1)
};

function sort(arr, lo, hi) {
    if (hi <= lo) return
    let lt = lo, i = lo + 1, gt = hi;
    let v = arr[lo]
    while (i <= gt) {
        if (arr[i] < v) swap(arr, lt++, i++)
        else if (arr[i] > v) swap(arr, i, gt--)
        else i++
    }
    sort(arr, lo, lt - 1)
    sort(arr, gt + 1, hi)
}

function swap(arr, a, b) {
    let x = arr[a]
    arr[a] = arr[b]
    arr[b] = x
}

Это использование повторяющихся значенийБыстрая сортировка с разделением на три частиэто очень хорошее решение. Конечно,сортировка по подсчетуЗакон - хороший выбор.
Кроме того, сортировка связанного списка, упомянутая ранее, используетСортировка слиянием.

арифметическая задача

Арифметическая задача кажется простой, но самая большая проблема заключается в следующем: если вы используете накопление и накопление такого рода роста на постоянном уровне, вы столкнетесь с TLE (превышением лимита времени), когда столкнетесь с большим числом. Итак, мы используем экспоненциальный рост, чтобы найти результат. Такие как:

Вычислить x в n-й степени

var myPow = function (x, n) {
    if (n == 0) return 1
    if (n < 0) {
        n = -n
        x = 1 / x
    }
    return (n % 2 == 0) ? myPow(x * x, parseInt(n / 2)) : x * myPow(x * x, parseInt(n / 2));
};

Сначала я использовал x*x для умножения n раз, но когда n слишком велико, время истекло. Используя приведенную выше схему: 29 = 2 * 44 = 2 * 82 = 2 * 64 = 128
Необходимо обратить внимание на переход от изменения уровня Чаншу к экспоненциальному изменению уровня непосредственно в математической операции.

найти квадратный корень из х

var mySqrt = function (x) {
    let l = 0, r = x
    while (true) {
        let mid = parseInt(l + (r - l) / 2)
        if (mid * mid > x) {
            r = mid - 1
        } else if (mid * mid < x) {
            if ((mid + 1) * (mid + 1) > x) {
                return mid
            }
            l = mid + 1
        } else {
            return mid
        }
    }
};

В этой задаче используется метод дихотомии для нахождения результата.

бинарная проблема

Двоичные задачи, общее использованиепобитовые операторыи бинарное преобразованиеNumber.parseInt()а такжеNumber.prototype.toString()решать.

Обратный двоичный порядок 32-битного числа

var reverseBits = function(n) {
    var t = n.toString(2).split("");
    while(t.length < 32) t.unshift("0"); // 插入足够的 0
    return parseInt(t.reverse().join(""), 2);
};

Общие алгоритмы

Сказав так много, на самом деле, в дополнение к обычно используемой сортировке и поиску, другими наиболее часто используемыми алгоритмами являются DP, DFS и BFS. Можно сказать, что: освоив сортировку и эти три алгоритма, вы сможете справиться с большинством алгоритмических задач. Понять такой удивительный алгоритм?

Кратко расскажу о нескольких видах сортировки и поиска

  • Пузырьковая сортировка: Обход массива, сравнение элемента с соседними элементами за ним, если текущий элемент больше, чем элемент за ним, поменять местами позицию. Таким образом, он проходится от начала до конца и получается последний отсортированный и воспроизведенный элемент. Затем повторите вышеуказанные шаги еще раз от 1 до n - 1. Пока, наконец, первый и второй элементы не сравнят размер. Это как бы сзади наперед.
  • сортировка выбором: пройтись по массиву, найти наименьшую позицию элемента, поменять местами позицию с первым элементом, а затем сузить диапазон для перехода от второго элемента и так далее до последнего элемента. Его можно сортировать сзади наперед или спереди назад.
function sort(arr) {
    const len = arr.length
    for (let i = 0; i < len; i++) {
        let min = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) min = j
        }
        swap(arr, i, min)
        console.log(arr)
    }
    return arr
}
  • Сортировка вставками: Пройдите массив, выберите элемент, сравните его с предыдущими соседними элементами, если текущий элемент меньше предыдущего элемента, измените положение и продолжайте сравнение до тех пор, пока элемент перед текущим элементом не станет меньше, чем текущий элемент ( или наверх), чтобы все элементы снова отсортировались. Это вид спереди назад.
function sort(arr) {
    const len = arr.length
    for (let i = 1; i < len; i++) {
        for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            swap(arr, j, j - 1)
            console.log(arr)
        }
    }
    return arr
}
  • Сортировка холмов: Аналогично сортировке вставками, выберите элемент и сравните размер и положение первых n элементов элемента. Затем снова уменьшите значение n. Этот метод может уменьшить проблему, заключающуюся в том, что минимальное значение в сортировке вставками находится в конце, и тогда вам нужно поменять местами позиции одну за другой, чтобы узнать первую. Уменьшите количество обменов. Это вид спереди назад.
  • Сортировка слиянием: в «Алгоритме» упоминаются два типа сортировки слиянием: один — сортировка слиянием сверху вниз. Разделите массив на наименьшие единицы (от 1 до 2 элементов) и отсортируйте их, затем сравните первые два элемента с двумя последними элементами и так далее, чтобы завершить сортировку всего массива. Существует также сортировка слиянием снизу вверх, которая напрямую делит массив на несколько подмассивов для сортировки и последующего слияния.
let aux = new Array(arr.length)
function sort(arr, lo, hi) {
    if (hi <= lo) return
    let mid = lo + (parseInt((hi - lo) / 2))

    sort(arr, lo, mid)
    sort(arr, mid + 1, hi)
    merge(arr, lo, mid, hi)
}

function merge(arr, lo, mid, hi) {
    let i = lo, j = mid + 1
    for (let k = lo; k <= hi; k++) {
        aux[k] = arr[k]
    }
    for (let k = lo; k <= hi; k++) {
        if (i > mid) arr[k] = aux[j++]
        else if (j > hi) arr[k] = aux[i++]
        else if (aux[j] < aux[i]) arr[k] = aux[j++]
        else arr[k] = aux[i++]
    }
    console.log(arr)
}
  • быстрая сортировка: выберите первое значение в качестве среднего значения, затем поместите элементы меньше среднего значения слева от среднего значения, а элементы больше среднего значения справа от среднего значения, а затем вырежьте элементы на обоих стороны снова до минимальной единицы.
function sort(arr, lo, hi) {
    if (hi <= lo + 1) return
    let mid = partition(arr, lo, hi) // 切分方法
    sort(arr, lo, mid)
    sort(arr, mid + 1, hi)
}

function partition(arr, lo, hi) {
    let i = lo, j = hi + 1
    let v = arr[lo]
    while(true) {
        while(arr[++i] < v) if (i == hi) break
        while(v < arr[--j]) if (j == lo) break
        if ((i >= j)) break
        swap(arr, i, j)
        console.log(arr)
    }
    swap(arr, lo, j)
    console.log(arr)
    return j
}
  • Быстрая сортировка с разделением на три части: Подобно быстрой сортировке, суть оптимизации заключается в том, что если элемент равен разделяемому элементу, позиция элемента остается неизменной. Наконец, элементы, меньшие, чем сегментированные элементы, помещаются влево, те, которые равны сегментированным элементам, помещаются в середину в соответствии с номером, а те, которые больше, чем сегментированные элементы, размещаются справа.Подходит для массивов с большим количеством элементов одинакового размера. 
function sort(arr, lo, hi) {
    if (hi <= lo) return
    let lt = lo, i = lo + 1, gt = hi;
    let v = arr[lo]
    while (i <= gt) {
        if (arr[i] < v) swap(arr, lt++, i++)
        else if (arr[i] > v) swap(arr, i, gt--)
        else i++
        console.log(arr)
    }
    sort(arr, lo, lt - 1)
    sort(arr, gt + 1, hi)
}
  • сортировка кучей: Можно сказать, что сортировка кучей является сортировкой выбором, которая использует концепцию кучи для сортировки. Используйте функцию return-maximum очереди с приоритетом, чтобы одно за другим возвращать максимальное значение текущей кучи.
  • сортировка по подсчету: состоит в том, чтобы сохранить количество вхождений всех элементов массива в массив, а затем вернуть отсортированный массив от меньшего к большему.
  • сортировка ведра: На самом деле это LSD и MSD сортировка строковой сортировки. LSD перемещается справа налево по строке, используя обозначение индекса, сортируя в соответствии с текущим значением. МНД сортируется слева направо методом подсчета индексов, после первого символа строки строковый массив разбивается на несколько массивов с такой же первой строкой и выполняется вторая и третья сортировка МНД соответственно.
  • бинарный поиск: Сравните промежуточное значение отсортированного массива с целевым значением. Если целевое значение меньше среднего значения, возьмите первую половину массива и продолжите деление пополам. Если целевое значение больше среднего значения, возьмите вторую половину массива и продолжите деление пополам. Если целевое значение равно среднему значению, нажмите!

DP

Для динамического программирования см.Подробное объяснение динамического программирования — Цзоу Бо рассказывает о динамическом программированииОдна статья, в которой рассказывается о путях, монетах и ​​самых длинных подпоследовательностях. Все вопросы в LeetCode.
Мое понимание: динамическое программирование — это процесс вывода, в котором следующее состояние может быть получено на основе предыдущего состояния или нескольких предыдущих состояний.

DFS

Поиск в глубину (DFS) состоит в том, чтобы выбрать возможность из условия 1 в условие 2 для поиска, а затем вернуться к поиску других возможностей и так далее. Например, если есть 5 путей, то алгоритм DFS состоит в том, чтобы отправить только одного разведчика пройти один путь до конца для разведки, а если это не удается, то вернуться к следующему пути.

DFS（顶点v）
{
  标记v为已遍历；
  for（对于每一个邻接v且未标记遍历的点u）
      DFS（u）;
}

DFS использует рекурсивный способ поиска.

Пример:Определяет, можно ли составить целевое слово, используя соседние буквы в двумерной буквенной матрице.

var exist = function (board, word) {
    for (let y = 0; y < board.length; y++) {
        for (let x = 0; x < board[0].length; x++) {
            if (find(board, word, y, x, 0)) return true
        }
    }
    return false
};

function find(board, word, y, x, d) {
    if (d == word.length) return true
    if (y < 0 || x < 0 || y == board.length || x == board[y].length) return false;
    if (board[y][x] != word[d]) return false
    let tmp = board[y][x]
    board[y][x] = "*"
    let exist = find(board, word, y, x + 1, d + 1)
        || find(board, word, y, x - 1, d + 1)
        || find(board, word, y + 1, x, d + 1)
        || find(board, word, y - 1, x, d + 1)
    board[y][x] = tmp
    return exist
}

BFS

Поиск в ширину (BFS) — это процесс синхронного перечисления всех возможностей от условия 1 до условия 2. Хорошо для поиска кратчайшего пути. Например, если есть 5 дорог, то алгоритм BFS состоит в том, чтобы отправить разведчиков для разведки каждой из 5 дорог.

BFS()
{
  输入起始点；
  初始化所有顶点标记为未遍历；
  初始化一个队列queue并将起始点放入队列；

  while（queue不为空）
  {

    从队列中删除一个顶点s并标记为已遍历； 
    将s邻接的所有还没遍历的点加入队列；
  }
}

BFS — это способ использования массива для хранения следующей вершины.

Пример:Замените буквы по одной, от слова A к слову B, через слова в заданном массиве. (127 вопросов)

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
    if (!wordList.includes(endWord)) return 0
    let set = new Set(),
        visited = new Set(),
        len = 1

    set.add(beginWord)
    visited.add(beginWord)
    while (set.size != 0) {
        let tmp = new Set([...set])

        for (let w of tmp) {
            visited.add(w)
            set.delete(w)

            if (changeOneChar(w, endWord))
                return len + 1
            
            for (let word of wordList){
                if (changeOneChar(w, word) && !visited.has(word)){
                    set.add(word)
                }
            }
        }
        len++
    }
    return 0
};

function changeOneChar(a, b) {
    let count = 0
    for (let i = 0; i < a.length; i++)
        if (a[i] != b[i])
            count++
    return count == 1
}

наконец

Запишите, что вы получите после выполнения AC один раз.

  • Я знаю методологию, сделаю много, сделай это.
  • Когда вы сталкиваетесь с проблемами, ищите больше колес, должна быть какая-то методология, которую вы можете использовать.
  • Не умничай и не используй какие-то хитрые уловки, это пустая трата времени, как бы ты об этом ни думал.
  • Не думайте о создании собственных колес (особенно с точки зрения алгоритмов) Для большинства проблем должны быть лучшие и более полные решения. Изготовление собственных колес отнимает много времени, трудоемко и бессмысленно.
  • Видеть ответ и делать самому - разные вещи, только сделав самому можно считаться мастером.
  • Причина, по которой существуют алгоритмы, заключается в том, чтобы адаптироваться к определенным сценариям и решать определенные типы задач. Только выбрав правильный алгоритм в правильном сценарии, можно отразить ценность алгоритма, и не злоупотребляйте алгоритмом.
  • Необязательно владеть всеми алгоритмами, но, по крайней мере, вы сможете найти оптимальный алгоритм для решения проблемы, когда столкнетесь с проблемой. То есть, зная о существовании алгоритма и его назначении, и углублённо изучая его по мере необходимости.

Фактически, алгоритм щетки вопросов все еще очень интересна, после плановБанк вопросов LeetCodeВсе вопросы снова в кисть~

PS: Если есть какие-либо ошибки или области, которые можно улучшить в этой статье и связанных проектах, пожалуйста, выдвиньте их. прогресс вместе ~

Категории