蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【深度优先 回溯法 DFS】相关题目汇总 分析 总结

发表于 更新于 分类于 阅读次数： Valine：

题目汇总

以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。

目前范围：Leetcode前150题

深度优先/回溯法题目

输入手机键盘的数字，组合所有可能的字母。

求一组不重复的数的全排列

求一组数的全排列（有重复数字），返回不重复的全排列

给定n，生成n对括号，必须正常关闭所有符号

计算数独，假设解唯一

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

经典的八皇后问题

找出由[1,2,3…n]中所有数字组成的序列中第k大的。

求在1到n个数中挑选k个数的所有的组合类型。

给定一个由不同数字组成的集合，罗列出该集合的所有子集。

给定一个含有重复数字组成的集合，罗列出该集合的所有子集。

在一个二维矩阵中，每个元素都是一个字母，要判断目标字符串能否由该矩阵中的元素连接而成。所谓连接就是从矩阵中的某一个元素开始，向前后左右不断前进，但不允许再次经过走过的元素。

找出一个由纯数字组成的序列能够构成的不同的IP地址。

将一个字符串分割成若干个子字符串，使得子字符串都是回文字符串，要求列出所有的分割方案。

给定一个目标字符串和一组字符串，判断目标字符串能否拆分成数个字符串，这些字符串都在给定的那组字符串中。

给定一个目标字符串和一组单词，将目标字符串进行拆分，要求拆分出的部分在那个单词组中，拆分后的单词用空格隔开，给出所有可能的拆分情况。

深度优先总结

递归与迭代

二者相互关系

  1. 从计算机角度讲，递归是迭代的特例。这个例子是两种方式计算阶乘的javascript代码实现，可以在浏览器中，按F12调出控制台，在控制台中进行实验。// 迭代，重复一定的算法，达到想要的目的。数学上二分法，牛顿法是很好的迭代例子
1
2
3
4
5
6
function iteration(x){
   var sum=1; 
   for(x; x>=1; x--){
       sum = sum*x;
   }
}

// 递归，自身调用自身的迭代就是递归。
// 但是正式定义好像不是这么说的。这只是我个人理解

1
2
3
4
5
6
7
function recursion(x){
   if(x>1){
       return x*recursion(x-1);
   }else{
       return 1;
   }
}
  1. 任何一个迭代的例子都有它的递归表示法，反之亦然。比如请将下列冒泡排序（由大到小）从迭代形式改写为递归形式
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    ：function swap(array, i, j){
        const temp = array[i]
        array[i] = array[j]
        array[j] = temp
    }
    function bubble(array){
        let length = array.length
        for(let i = length-1; i>0; i--){
            for(let j=0; j<i; j++){
                if(array[j] < array[j+1]){
                    swap(array, j, j+1)
                }
            }
        }
        return array
    }
    answer：function swap(array, i, j){
        const temp = array[i]
        array[i] = array[j]
        array[j] = temp
    }
    function bubble(array, i = array.length-1, j = 0){
        if(i===1){
            return array
        }
        if(j > i){
            j = 0
            i--
        }
        if(array[j] < array[j+1]){
            swap(array, j, j+1)
        }

        return bubble(array, i, j+1)
    }

从代码优雅美观角度讲，递归的形式缩进会更少一些，显得平整。

递归的劣势

1.递归容易产生”栈溢出”错误（stack overflow）因为需要同时保存成千上百个调用记录，所以递归非常耗费内存。这也就是为什么会有『尾递归调用优化』而迭代对于浏览器的影响顶多是由于计算量大而发生线程长时间占用的假死现象，不至于在运行时栈溢出而抛错的问题。【备注：后来发现 Chrome v61.0.3163.100 根本没有做尾递归优化处理。】

2.效率方面，递归可能存在冗余计算使用递归的方式会有冗余计算（比如最典型的是斐波那契数列，计算第6个需要计算第4个和第5个，而计算第5个还需要计算第4个，所处会重复）。迭代在这方面有绝对优势。但是这并不表明递归可以完全被取代。因为递归有更好的可读性。