刷题-搜索

发表于 更新于
  1. [Leetcode 200]
    解法：
DFS：一次遍历，遇到1则进行深搜，遍历过的1设为2，遇到非1或者越界则深搜停止，统计深搜的次数，即为岛屿数量。(这里采用)
BFS: 循环遍历每个点，如果该点是0，则跳过，如果是1，岛屿数目加1，并加入队列，并将该点改为0，避免重复访问，然后进行广搜，取出队首元素，搜索该点周围四个点，如果有1就加入队列，并将1改为0，否则就跳过，当队列空时，一块岛屿搜索完毕，进入下一块搜索。(代码可参考：)
将二维数组重新编号，从0开始，从左到右，从上到下，直到nm-1（其中n为行数，m为列数），对于位置(i,j)则编号为im+j，那么相邻（左右，上下）的为同一个值，则认为他们相通。那么最终只要统计一下father[i]==i且对应值为1的个数即可。(代码可参考: )

代码：

  1. [Leetcode 77]
    模板题：重点在于dfs中的startPos=i+1

代码：

  1. [Leetcode 39]
    基于模板加一些改动即可，由于可重复选择数字，将startPos=i+1 改成startPos=i，判停条件满足目标和就可以了,(前提是有序数组，先拍下序)
    代码：

  2. [Leetcode 40]
    解法：在上一题的基础上使用Set进行去重

代码:

5.[Leetcode 216]
解法:
代码

6.[Leetcode 131]
解法:
按解组合的方式解，解的过程中判断回文串，组合的元素集合是按照从子串的第一个元素开始，到第i个元素截断作为一个新子串进行回文判断，

代码：

规规矩矩没啥说的, 主要注意边界条件

代码: