首页 > 编程语言 > 详细

【算法题】LeetCode刷题(六)

时间:2020-08-08 19:37:44      阅读:74      评论:0      收藏:0      [点我收藏+]

数据结构和算法是编程路上永远无法避开的两个核心知识点,本系列【算法题】旨在记录刷题过程中的一些心得体会,将会挑出LeetCode等最具代表性的题目进行解析,题解基本都来自于LeetCode官网(https://leetcode-cn.com/),本文是第六篇。

1.颜色分类(原第75题)

给定一个包含红色、白色和蓝色,一共?n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、?1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

(1)知识点

原地算法

(2)解题方法

方法转自:https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode/

方法:一次遍历

相比之前的题目经常用到的双指针法,这个其实是个三指针。事实上,一般遇到要排序的问题,无非就是多加几个指针就可以解决了。
我们用三个指针(p0, p2 和curr)来分别追踪0的最右边界,2的最左边界和当前考虑的元素。本解法的思路是沿着数组移动 curr 指针,若nums[curr] = 0,则将其与 nums[p0]互换;若 nums[curr] = 2 ,则与 nums[p2]互换。

  • 时间复杂度:O(n),由于对长度 N的数组进行了一次遍历。
  • 空间复杂度:O(1),不需要额外的空间开销。

(3)伪代码

函数头:void sortColors(int[] nums)

方法:一次遍历

  • 定义p0=curr=0,p2=len-1
  • 第一重循环:(curr<=p2)
    • 如果curr=0,交换p0和curr的值,p0++,curr++
    • 如果curr=1,curr++
    • 如果curr=2,交换p2和curr的值,p2--

(4)代码示例




2.子集(原第78题)

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
? [1],
? [2],
? [1,2,3],
? [1,3],
? [2,3],
? [1,2],
? []
]

(1)知识点

子集

(2)解题方法

方法转自:https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode/

方法一:递归

根据题目可以判断,对于n个元素,每个元素都有放or不放两种状态,那么总共就有2^n种情况。
比如集合[1,2,3]:

不放,不放,不放:[]
放,不放,不放:[1]
不放,放,不放:[2]
不放,不放,放:[3]
放,放,不放:[1,2]
放,不放,放:[1,3]
不放,放,放:[2,3]
放,放,放:[1,2,3]

另外,我们考虑:

如果没有元素[],他的子集是[]
如果有一个元素[1],他的子集是[],[1]
如果有两个元素[1,2],他的子集是[],[1],[2],[1,2]
如果有三个元素[1,2,3],他的子集是[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]

发现什么了?每次增加一个元素,只需要在前一个的基础上的末尾添加一个元素就行了,所以总的子集数量是呈指数级别的增长的。这就容易想到递归算法了。

  • 时间复杂度:O(N×2^N),生成所有子集,并复制到输出结果中。
  • 空间复杂度:O(N×2^N),这是子集的数量。
  • 对于给定的任意元素,它在子集中有两种情况,存在或者不存在(对应二进制中的 0 和 1)。因此,N 个数字共有 2^N个子集。

方法二:回溯法

我们知道,在遇到这种排列组合的情况下,基本上都能用到回溯法,而回溯法本身是一棵树,这里就需要每一层的情况都得加到最后的集合中去
技术分享图片

  • 时间复杂度:O(N×2^N),生成所有子集,并复制到输出结果中。
  • 空间复杂度:O(N×2^N),存储所有子集,共 nn 个元素,每个元素都有可能存在或者不存在。

方法三:字典排序(二进制排序)

将每个子集映射到长度为 n 的位掩码中,其中第 i 位掩码 nums[i] 为 1,表示第 i 个元素在子集中;如果第 i 位掩码 nums[i] 为 0,表示第 i 个元素不在子集中。
技术分享图片
例如,位掩码 0..00(全 0)表示空子集,位掩码 1..11(全 1)表示输入数组 nums。
因此要生成所有子集,只需要生成从 0..00 到 1..11 的所有 n 位掩码。
技术分享图片

  • 时间复杂度:O(N×2^N),生成所有子集,并复制到输出结果中。
  • 空间复杂度:O(N×2^N),存储所有子集,共 nn 个元素,每个元素都有可能存在或者不存在。

(3)伪代码

函数头:List<List> subsets(int[] nums)

方法一:递归

  • 定义List<List> res用作返回
  • 将空集加入到res
  • 第一重循环:(num:nums)
    • 定义List<List> sub用作添加当前num的集合
    • 将res里的每一个List都填上num然后放进sub里面(注意java有一个简单的写法(curr是res中的某个list):sub.add(new ArrayList(curr){{add(num);}});)
    • 将sub里面的每个list再加到res中

方法二:回溯

  • 定义一个回溯方法 backtrack(first, curr),第一个参数为索引 first,第二个参数为当前子集 curr。
  • 如果当前子集构造完成,将它添加到输出集合中。
  • 否则,第一重循环从i: first->n-1
    • 将整数 nums[i] 添加到当前子集 curr。
    • 继续向子集中添加整数:backtrack(i + 1, curr)。
    • 从 curr 中删除 nums[i] 进行回溯。

方法三:字典排序(二进制排序)

  • 生成所有长度为 n 的二进制位掩码。
  • 将每个子集都映射到一个位掩码数:位掩码中第 i 位如果是 1 表示子集中存在 nums[i],0 表示子集中不存在 nums[i]。

(4)代码示例




3.单词搜索(原第79题)

给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
[‘A‘,‘B‘,‘C‘,‘E‘],
[‘S‘,‘F‘,‘C‘,‘S‘],
[‘A‘,‘D‘,‘E‘,‘E‘]
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

(1)知识点

回溯法

(2)解题方法

方法转自:https://leetcode-cn.com/problems/word-search/solution/zai-er-wei-ping-mian-shang-shi-yong-hui-su-fa-pyth/

方法:回溯法

这个题同样考虑回溯法,因为每跑到一个点就会遇到几种不同的情况,比如下图中的‘C‘,到这里就有两个路可以走,如果“走错了”,就需要回来换一条路,这里就用到了回溯算法。
技术分享图片
我们考虑从第一个点开始遍历,直到找到待查的第一个字母,然后上下左右(可以自定义顺序)来找到下一个,如果不对就回溯。并且在行进的过程中,需要标记已经走过的点,因为不能重复。

(3)伪代码

函数头:boolean exist(char[][] board, String word)

方法:回溯法

  • 两重循环遍历board中的每个元素,调用backtrack函数,判断以该字符开头满不满足情况。

boolean backtrack(int i, int j, int start):start是word中的某个字符

  • 如果start是word的最后一个字符,直接判断是否和board[i][j]相等返回。——递归终止条件
  • 如果start位置的字符和board[i][j]相等,进一步判断:
    • 标记i,j位置已经走过(这里需要一个全局变量数组来记录)
    • 第一重循环(k:0->3):这里是分别走i,j位置的上下左右四个方向(这里也需要定义一个全局变量数组来记录偏移量,具体就是int[][]direct={{0,1},{0,-1},{1,0},{-1,0}})
      • 定义newX=i+direct[k][0],newY=j+direct[k][1]
      • 如果newX和newY均未走过,并且newX和newY都在board的范围里面(需要提前定义好全局变量board的范围,所有direct的四个方向不一定都能走到),调用backtrack(newX,newY,start+1)
    • 回溯(标记i,j未走过)
  • 返回false

(4)代码示例




4.子集2(原第90题)

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

(1)知识点

回溯法

(2)解题方法

方法转自:https://leetcode-cn.com/problems/subsets-ii/solution/shi-yong-mapji-shu-yi-bian-sao-miao-jia-ru-suo-you/

方法:回溯法

这个题和子集那题不同,如果依旧按照那个方法的话会得出很多重复的结果。我们以[1,2,2]为例,利用回溯法,并且对每种情况进行判断。要实现同层比较的关键就是比较for循环里的j和回溯函数的实参i,j是当前检查元素下标;i是本层开始检查的元素下标
如果nums[j]是在同层的在for循环里重复出现的,那么j肯定大于i,否则比较的两个元素就处于不同层。实际上就是判断j是否大于i,然后还需要nums[j]!=[j-1]
下图中第一层第三个说明有点错误。(应该是nums[2]==nums[1])
技术分享图片

(3)伪代码

函数头: List<List> subsetsWithDup(int[] nums)

方法:回溯法

  • 需要定义两个全局变量数组(一个二维数组用于返回最后的结果res,一个一位数组用来装临时的子集tmp)
  • 先对nums排序
  • 调用backtrack(0)

void backtrack(int i)

  • 如果i=len,直接返回——递归终止条件
  • 第一重循环(j:i->len-1):
    • 如果j>i且nums[j]==nums[j-1]跳过
    • tmp添加nums[j]
    • res添加一个新List(拷贝tmp)
    • backtrack(i+1)
    • tmp.remove(最后一个元素)——回溯

(4)代码示例




【算法题】LeetCode刷题(六)

原文:https://www.cnblogs.com/echizen/p/13450612.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!