«Алгоритмы и структуры данных» Красота алгоритмов DFS и BFS

алгоритм JavaScript
«Алгоритмы и структуры данных» Красота алгоритмов DFS и BFS

предисловие

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

Разнообразие решений должно быть.Во время интервью я просто написал рекурсию.Интервьюер спросил меня, могу ли я ее использовать.повторятьЧтобы завершить, поэтому необходимо знать множество решений.

В конце статьи есть продвинутые темы🤭

На этот раз разобрались с общими типами вопросов BFS DFS, и каковы ее процедуры?

BFS-DFS при условии поступления на GitHub, идеи и код есть, заинтересованные партнеры могут поиграть в небольшую 👇

Структура данных — BFS — DFS

BFS & DFS

Рекомендуется прочитать эту статью Zhihu для ознакомления с концепциейПоиск идей — DFS и BFS (основные принципы)

BFS: поиск в ширину

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

DFS: Глубина Первый поиск

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

основной тип вопроса

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

Сайт главных вопросов👇

Оригинальное название NetEase

Тема такая👇

const tree = {
	name: 'root',
	children: [
		{
			name: 'c1',
			children: [
				{
						name: 'c11',
					children: []		
					},
					{
						name: 'c12',
					children: []		
				}
			]
		},
		{
			name: 'c2',
			children: [
				{
						name: 'c21',
					children: []		
					},
					{
						name: 'c22',
					children: []		
				}
			]
		}
	]
}

// 深度优先的方式遍历 打印 name
// ['root', 'c1','c11', 'c12', 'c2', 'c21', 'c22']

Ну, я написал рекурсивный способ письма во время интервью. Младший брат Netease, похоже, был недоволен. Он спросил о дефектах рекурсии, и спросил меня, могу ли я ее оптимизировать. Ну, когда я брал интервью, я не думал из этого я был глуп в то время, давайте дадим методу рекурсивной записи симуляции стека👇

function solve(root) {
            let stack = [],
                result = [];
            if(!root) return [];
            stack.push(root)
            while(stack.length) {
                let node = stack.pop()
                if(node == null ) continue
                result.push(node.name)
                for(let i = node.children.length-1; i >= 0; i--) {
                    // 这里就是面试的重点,应该从后面的节点压入栈中
                    stack.push(node.children[i])
                }
            }
            return result
        }

Максимальная глубина бинарного дерева⭐

Описание темы: Для заданного бинарного дерева найдите его максимальную глубину.

Глубина бинарного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла.

Связь:Рингтон-Максимальная глубина бинарного дерева

Пример:

Учитывая бинарное дерево[3,9,20,null,null,15,7],

  	3
   / \
  9  20
    /  \
   15   7

Возвращает максимальную глубину 3 .

Источник: LeetCode Связь:Lee TCO's-talent.com/problems/horse…

Рекурсивная идея:

  • Каждый раз проходите левый узел и правый узел отдельно, затем сравниваете их и берете максимальное значение.
  • Таким образом, каждый раз, когда вы выполняете рекурсию, глубина увеличивается на 1.
var maxDepth = function (root) {
    if (!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

Нерекурсивная идея:

  • BFS, обход в ширину
  • Каждый раз, когда временный массив используется для сохранения всех узлов предыдущего слоя, каждый раз, когда счетчик count+1
  • Когда temp пуст, то есть это случай листовых узлов в это время
var maxDepth = function (root) {
    if(!root) return 0
    let queue = [root],
        res = 0;
    while(queue.length) {
        let temp = []
        for(let i = 0; i < queue.length; i++) {
            if(queue[i].left) temp.push(queue[i].left)
            if(queue[i].right) temp.push(queue[i].right)
        }
        res += 1
        queue = temp
    }
    return res
};

Код нажмите здесь ☑️

Минимальная глубина бинарного дерева⭐

Для заданного бинарного дерева найти его минимальную глубину.

Минимальная глубина — это количество узлов на кратчайшем пути от корневого узла до ближайшего конечного узла.

Связь:[Liku] Минимальная глубина бинарного дерева

Пример:

Учитывая бинарное дерево[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

возвращает минимальную глубину 2

Источник: LeetCode Связь:Ли ТСО's-talent.com/problems/m…

Рекурсивная идея:

  1. Определить, является ли текущий узел корневым и пустым, если да, вернуть 0
  2. Левый и правый узлы текущего узла все нулевые, то есть, когда конечный узел является конечным узлом, он является целевым узлом в это время, минимальная глубина, возвращает 1
  3. Левый узел текущего узла не равен нулю, найдите глубину левого поддерева
  4. Правый узел текущего узла не равен нулю, найдите глубину правого поддерева
  5. Сравните два, верните минимальное значение условий 3 и 4 и добавьте 1

Просматривайте код снова и снова в поисках идей👇

var minDepth = function (root) {
    if (root == null) return 0
    if (root.left == null && root.right == null) return 1
    let max = 10000;
    if (root.left) max = Math.min(max, minDepth(root.left))
    if (root.right) max = Math.min(max, minDepth(root.right))
    return max + 1
};

Нерекурсивная идея:

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

Если вы сделаете больше BFS, то обнаружите, что это все вопросы рутинные👇

var minDepth = function (root) {
    if (!root) return 0
    let stack = [root],
        ans = 0
    while (stack.length) {
        let temp = []
        ans++
        for (let i = 0; i < stack.length; i++) {
            if (stack[i].left == null && stack[i].right == null) return ans;
            if (stack[i].left) temp.push(stack[i].left)
            if (stack[i].right) temp.push(stack[i].right)
        }
        stack = temp;
    }
    return ans
};

Код нажмите здесь ☑️

Иерархический обход двоичного дерева ⭐⭐

Дайте вам бинарное дерево, пожалуйста, верните егообход по уровнямПолученное значение узла. (т.е. слой за слоем, посещая все узлы слева направо).

Связь:[leetcode] перевернуть связанный список

Пример:Бинарное дерево:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

Вернуть результат его иерархического обхода:

[
  [3],
  [9,20],
  [15,7]
]

Источник: LeetCode Связь:Ли ТСО's-talent.com/problems/hot…

Идеи:

  • Самый простой способ сделать это - BFS
  • Каждый раз при обходе слоя его дочерние узлы сохраняются по порядку.
  • Используйте результат дочернего узла в качестве нового результата, то есть que = temp
var levelOrder = function (root) {
    let res = [],
        que = [root];
    if (!root) return []
    while (que.length) {
        let temp = [],
            ans = []
        for (let i = 0; i < que.length; i++) {
            ans.push(que[i].val)
            if (que[i].left) temp.push(que[i].left)
            if (que[i].right) temp.push(que[i].right)
        }
        res.push(ans)
        que = temp
    }
    return res;
};

Для рекурсивных идей я не открывал, думаю такой способ написания прост и понятен.

Код нажмите здесь ☑️

Зигзагообразный иерархический обход бинарного дерева ⭐⭐

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

Связь:103 Зигзагообразный иерархический обход бинарных деревьев

Например: Учитывая бинарное дерево[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

Верните обход уровня зигзага следующим образом:

[
  [3],
  [20,9],
  [15,7]
]

Источник: LeetCode Связь:Lee TCO's-talent.com/problems/than…

Обычные вопросы BFS

  • Та же идея, но на этот раз нужно перевернуть результат
  • Ну, установите флаг, оцените четность, а затем переверните ответ.
var zigzagLevelOrder = function (root) {
    let res = [],
        que = [root],
        flag = 0;
    if (!root) return []
    while (que.length) {
        let temp = [],
            ans = []
        flag++;
        for (let i = 0; i < que.length; i++) {
            ans.push(que[i].val)
            if (que[i].left) temp.push(que[i].left)
            if (que[i].right) temp.push(que[i].right)
        }
        // 判断奇偶情况,然后翻转
        if (flag % 2 === 1) {
            res.push(ans)
        } else {
            res.push(ans.reverse())
        }
        que = temp // 套路,将这个层级的从新压入栈
    }
    return res;
};

Нажмите здесь, чтобы получить код 🤭

Самый длинный возрастающий путь в матрице ⭐⭐⭐

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

Связь:самый длинный возрастающий путь в матрице

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

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

Пример 1:

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Выход: 4 Объяснение: самый длинный возрастающий путь — [1, 2, 6, 9]. Пример 2:

输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Выход: 4 Объяснение: Самый длинный возрастающий путь — [3, 4, 5, 6]. Обратите внимание, что движение в диагональном направлении не допускается.

Источник: LeetCode Связь:Ли ТШО's-talent.com/problems/…

Идеи👇

  • dfs+ запоминаемый поиск
  • Прежде всего, вы находитесь в позиции (i, j), есть четыре направления, по которым вы можете двигаться дальше: вверх, вниз, влево и вправо, нам нужно судить, законно это или нет.
  • Мы используем DX, DY для имитации четырех операций над верхней и нижней операциями, то есть можно выбрать четыре направления.
  • Что нам нужно пройти, так это каждое место.запоминаниепроцесс
  • dfsТрудность в том, как обрезать, как оптимизировать, как запомнить эти позиции

Я еще не закончил писать, посмотрим, что думают другие👇

// 0和1、1和0、0和-1、-1和0，四个方向
const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];
const longestIncreasingPath = (matrix) => {
    if (matrix.length == 0) return 0;
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = new Array(m);
    for (let i = 0; i < m; i++) dp[i] = new Array(n);
    // 每次长度至少长度为1
    let res = 1;

    //// 对坐标(i,j)进行dfs
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            res = Math.max(res, dfs(matrix, i, j, m, n, dp));
        }
    }
    return res;
};

const dfs = (matrix, i, j, m, n, dp) => {
    // 记忆化搜索
    if (dp[i][j]) return dp[i][j];
    let max = 1;

    // 以(i,j)为起点的路径，长度保底是1
    for (let k = 0; k < 4; k++) { //循环四次 就是有上下左右四个方向可以走
        const x = i + dx[k];
        const y = j + dy[k];
        // 判断接下来的坐标是否合法
        //  0<=x && x < m
        //  0 <= y <= n
        if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
            max = Math.max(max, 1 + dfs(matrix, x, y, m, n, dp));
        }
    }
    // 当前情况下, 需要求的就是(i,j)方格的最大值
    return dp[i][j] = max;
};

Краткое изложение дополнительных тем

Если вы хотите продвинуться в этой теме, просто почистите темы, которые я привожу ниже👇

DFS

BFS

Надеюсь, эта статья поможет вам немного разобраться в DFS, BFS. Каковы его процедуры и как его написать, я надеюсь, что это будет хорошей идеей для вас, давай, UpUpUp.

❤️ Всем спасибо

Если вы считаете этот контент полезным:

  1. Поставьте лайк и поддержите его, чтобы больше людей увидело этот контент

  2. Обратите внимание на публичный аккаунт前端UpUp, регулярно публиковать хорошие статьи для вас.

  3. Если вы считаете, что это хорошо, вы также можете прочитать последние статьи TianTian (спасибо за вашу поддержку и поддержку 🌹🌹🌹):

Категории