数据结构和算法是编程路上永远无法避开的两个核心知识点,本系列【算法题】旨在记录刷题过程中的一些心得体会,将会挑出LeetCode等最具代表性的题目进行解析,题解基本都来自于LeetCode官网(https://leetcode-cn.com/),本文是第六篇。
给定一个包含红色、白色和蓝色,一共?n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、?1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,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]互换。
函数头:void sortColors(int[] nums)
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
? [1],
? [2],
? [1,2,3],
? [1,3],
? [2,3],
? [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]
发现什么了?每次增加一个元素,只需要在前一个的基础上的末尾添加一个元素就行了,所以总的子集数量是呈指数级别的增长的。这就容易想到递归算法了。
我们知道,在遇到这种排列组合的情况下,基本上都能用到回溯法,而回溯法本身是一棵树,这里就需要每一层的情况都得加到最后的集合中去
将每个子集映射到长度为 n 的位掩码中,其中第 i 位掩码 nums[i] 为 1,表示第 i 个元素在子集中;如果第 i 位掩码 nums[i] 为 0,表示第 i 个元素不在子集中。
例如,位掩码 0..00(全 0)表示空子集,位掩码 1..11(全 1)表示输入数组 nums。
因此要生成所有子集,只需要生成从 0..00 到 1..11 的所有 n 位掩码。
函数头:List<List
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
[‘A‘,‘B‘,‘C‘,‘E‘],
[‘S‘,‘F‘,‘C‘,‘S‘],
[‘A‘,‘D‘,‘E‘,‘E‘]
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
回溯法
这个题同样考虑回溯法,因为每跑到一个点就会遇到几种不同的情况,比如下图中的‘C‘,到这里就有两个路可以走,如果“走错了”,就需要回来换一条路,这里就用到了回溯算法。
我们考虑从第一个点开始遍历,直到找到待查的第一个字母,然后上下左右(可以自定义顺序)来找到下一个,如果不对就回溯。并且在行进的过程中,需要标记已经走过的点,因为不能重复。
函数头:boolean exist(char[][] board, String word)
boolean backtrack(int i, int j, int start):start是word中的某个字符
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
回溯法
这个题和子集那题不同,如果依旧按照那个方法的话会得出很多重复的结果。我们以[1,2,2]为例,利用回溯法,并且对每种情况进行判断。要实现同层比较的关键就是比较for循环里的j和回溯函数的实参i,j是当前检查元素下标;i是本层开始检查的元素下标
如果nums[j]是在同层的在for循环里重复出现的,那么j肯定大于i,否则比较的两个元素就处于不同层。实际上就是判断j是否大于i,然后还需要nums[j]!=[j-1]
下图中第一层第三个说明有点错误。(应该是nums[2]==nums[1])
函数头: List<List
void backtrack(int i)
原文:https://www.cnblogs.com/echizen/p/13450612.html