九章算法笔记 5.深度优先搜索 Depth First Search
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了九章算法笔记 5.深度优先搜索 Depth First Search，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6005字，纯文字阅读大概需要9分钟。
内容图文
DFS cs3k.com
什么时候用dfs?
短, 小, 最问题
而90%DFS的题, 要么是排列, 要么是组合
组合搜索问题 Combination
问题模型:求出所有满足条件的“组合”
判断条件:组合中的元素是顺序无关的
时间复杂度:与 2^n 相关
递归三要素
一般来说,如果面试官不特别要求的话,DFS都可以使用递归(Recursion)的方式来实现。
递归三要素是实现递归的重要步骤:
? 递归的定义
? 递归的拆解
? 递归的出口
Combination Sum
cs3k.com
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
为什么是正整数?
如果有0:
取一次是一种方案, 取两次是一种方案, 最后有无数种方案.
新题和老题的关系:
看到新题要和老题产生关系, 哪儿像哪儿不像
这道题和subset的关系:
- 可以无限制的取
-
限制了一个和
-
去重: {1,2} == {2,1} 选代表
{2,2,3} = {2,3,2] = {3,2,2]
其中49行, [2’,2”,3]可能有三种:
[2’,2”,3]
[2’,2’,3]
ps: 也可以用hash set去重
去重
Given an array of integers, remove the duplicate numbers in it.
You should:
- Do it in place in the array.
-
Move the unique numbers to the front of the array.
-
Return the total number of the unique numbers.
class Solution {
public:
/**
* @param A: a list of integers
* @return : return an integer
*/
int removeDuplicates(vector<int> &nums) {
if (nums.size() == 0) {
return 0;
}
int len = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[len] != nums[i]) {
nums[++len] = nums[i];
}
}
return len + 1;
}
};两点需要注意：
- for 之后的i从1开始
-
return的不是index，二是数量，所以要加1
时间复杂度
cs3k.com
答案个数不知道, 假设为S;
每个答案用的时间=target;
所以总的时间复杂度= O(S*target), 是个NP问题
Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
其中:
if (i != startIndex && candidates[i] == candidates[i - 1]) {
continue;
}去重的方式是相同的从第一个开始选, 不能跳过第一个选第二个.
Palindrome Partitioning
cs3k.com
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
这道题的本质是组合问题:
aab怎么分割的问题, 就是要不要缝隙
三个字符两个空隙, 每个空隙我可以选择要或者不要, 所以有4个答案.
一边切, 一边验证是不是回文串:
因为搜索是一种尝试, 是把以这个方案开头的所有都找到.
找完之后, 还要回到原来的状态, 要记得remove
Permutation
cs3k.com
Given a list of numbers, return all possible permutations.
排列搜索问题 Permutation
问题模型:求出所有满足条件的“排列”。
判断条件:组合中的元素是顺序“相关”的。
时间复杂度:与 n! 相关。
此题的时间复杂度是: O(n! * n)
和subsets的关系是:
- permutation是凑齐再加到答案上; 而subsets是中间结果也存.
-
permutation是可以回头取的, 但是不能重复取, 所以没有startIndex.
Permutation II
cs3k.com
Given a list of numbers with duplicate number in it. Find all unique permutations.
- 边排列边看有没有斜线攻击.
- 左上到右下的斜线上的点符合差相等:x1 – y1 = x2 – y2
- 右上到左下和相等.
- 每个function不超过三十行, 不容易出bug
Word Ladder
cs3k.com
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
搜索，动态规划，二叉树的时间复杂度计算通用公式
搜索的时间复杂度：O(答案总数 * 构造每个答案的时间)
举例：Subsets问题，求所有的子集。子集个数一共 2^n，每个集合的平均长度是 O(n) 的，所以时间复杂度为 O(n * 2^n)，同理 Permutations 问题的时间复杂度为：O(n * n!)
动态规划的时间复杂度：O(状态总数 * 计算每个状态的时间复杂度)
举例：triangle，数字三角形的最短路径，状态总数约 O(n^2) 个，计算每个状态的时间复杂度为 O(1)——就是求一下 min。所以总的时间复杂度为 O(n^2)
用分治法解决二叉树问题的时间复杂度：O(二叉树节点个数 * 每个节点的计算时间)
举例：二叉树最大深度。二叉树节点个数为 N，每个节点上的计算时间为 O(1)。总的时间复杂度为 O(N)
public class Solution {
public int ladderLength(String start, String end, Set dict) {
if (dict == null) {
return 0;
}
if (start.equals(end)) {
return 1;
}
dict.add(start);
dict.add(end);
HashSet hash = new HashSet();
Queue queue = new LinkedList();
queue.offer(start);
hash.add(start);
int length = 1;
while(!queue.isEmpty()) {
length++;
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
for (String nextWord: getNextWords(word, dict)) {
if (hash.contains(nextWord)) {
continue;
}
if (nextWord.equals(end)) {
return length;
}
hash.add(nextWord);
queue.offer(nextWord);
}
}
}
return 0;
}
// replace character of a string at given index to a given character
// return a new string
private String replace(String s, int index, char c) {
char[] chars = s.toCharArray();
chars[index] = c;
return new String(chars);
}
// get connections with given word.
// for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}
// it will return ['hit', 'hog']
private ArrayList getNextWords(String word, Set dict) {
ArrayList nextWords = new ArrayList();
for (char c = 'a'; c <= 'z'; c++) {
for (int i = 0; i < word.length(); i++) {
if (c == word.charAt(i)) {
continue;
}
String nextWord = replace(word, i, c);
if (dict.contains(nextWord)) {
nextWords.add(nextWord);
}
}
}
return nextWords;
}
}难点一: BFS
难点二:
L单词长度远小于N词典里的单词数, 所以
L: 10 N:10K
可以把时间从100k变成2.5k
ps: hash_map的时间是O(key.size())
因为key变成hash code即为index
Word Ladder II
cs3k.com
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
既有all又有shortest
BFS+DFS
- 小人往A走, 走的是回头路;
往B走, 没走的更近;
C才是正确的路线.
- start -> end BFS
end ->start DFS
再reverse
Subsets
非递归和其他组合题不一样, 用位操作构造一个0~2^(n-1)的大循环
Permutation Next
cs3k.com
Given a list of integers, which denote a permutation.
Find the next permutation in ascending order.
Notice
The list may contains duplicate integers.
1 5 2 4 3找这些数字组成的稍微大那么一点的数
从右往左找第一个降序的地方, 把它和右边比他大的最小的换, 换完reverse回来
1 5 3 4 2
1 5 3 2 4
内容总结
以上是互联网集市为您收集整理的九章算法笔记 5.深度优先搜索 Depth First Search全部内容，希望文章能够帮你解决九章算法笔记 5.深度优先搜索 Depth First Search所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。