深度优先搜索(DFS) — 20180926
2024-08-24 05:16:31
用DFS的场景：
找出所有方案：DFS
找出所有方案总数 可能是动态规划
DFS时间复杂度：答案个数*构造每个答案的时间
动态规划时间复杂度：状态个数*计算每个状态时间
二叉树时间复杂度：节点数*处理每个节点时间
135. Combination Sum
public class Solution {
/**
* @param candidates: A list of integers
* @param target: An integer
* @return: A list of lists of integers
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// write your code here
List<List<Integer>> result = new ArrayList<>();
if(candidates == null || candidates.length ==0){
return result;
}
Arrays.sort(candidates);
ArrayList<Integer> combination = new ArrayList<>();
Hepler(result,candidates,target,0,combination);
return result;
}
public void Hepler(List<List<Integer>> result,int[] candidates, int target, int startIndex,List<Integer> combination){
if(target == 0){
result.add(new ArrayList(combination));
return;
}
for(int i= startIndex; i<candidates.length; i++){
if(target<candidates[i]){
continue;
}
if(i>0 && candidates[i]==candidates[i-1]){
continue;
}
combination.add(candidates[i]);
Hepler(result,candidates,target-candidates[i],i,combination);
combination.remove(combination.size()-1);
}
}
}
153. Combination Sum II
public class Solution {
/**
* @param num: Given the candidate numbers
* @param target: Given the target number
* @return: All the combinations that sum to target
*/
public List<List<Integer>> combinationSum2(int[] num, int target) {
// write your code here
List<List<Integer>> result = new ArrayList<>();
if(num == null || num.length ==0){
return result;
}
Arrays.sort(num);
List<Integer> combination = new ArrayList<>();
Helper(num,target,0,result,combination);
return result;
}
public void Helper(int[] num, int target, int startIndex, List<List<Integer>> result, List<Integer> combination){
if(target==0){
result.add(new ArrayList<>(combination));
return;
}
for(int i = startIndex; i<num.length; i++){
if(target<num[i]){
break;
}
if(i>0 && num[i] == num[i-1] && i!=startIndex){
continue;
}
combination.add(num[i]);
Helper(num,target-num[i],i+1,result,combination);
combination.remove(combination.size()-1);
}
}
}
136. Palindrome Partitioning
切割问题也就是组合问题
public class Solution {
/*
* @param s: A string
* @return: A list of lists of string
*/
public List<List<String>> partition(String s) {
// write your code here
List<List<String>> result = new ArrayList<>();
if (s == null || s.length() == 0) {
return result;
}
List<String> combination = new ArrayList<>();
Helper(result, combination, 0, s);
return result;
}
public void Helper(List<List<String>> result, List<String> combination, int startIndex, String s) {
if (startIndex == s.length()) {
result.add(new ArrayList<>(combination));
return;
}
for (int i = startIndex; i < s.length(); i++) {
String sub = s.substring(startIndex, i + 1);
if (!isPalindrome(sub)) {
continue;
}
combination.add(sub);
Helper(result, combination, i + 1, s);
combination.remove(combination.size() - 1);
}
}
public boolean isPalindrome(String s) {
int start = 0;
int end = s.length() - 1;
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
15. Permutations
public class Solution {
/*
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public List<List<Integer>> permute(int[] nums) {
// write your code here
List<List<Integer>> result = new ArrayList<>();
if (nums == null) {
return result;
}
boolean[] visited = new boolean[nums.length];
List<Integer> permutation = new ArrayList<>();
Helper(result, permutation, nums, visited);
return result;
}
public void Helper(List<List<Integer>> result, List<Integer> permutation, int[] nums, boolean[] visited) {
if (permutation.size() == nums.length) {
result.add(new ArrayList<>(permutation));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}
permutation.add(nums[i]);
visited[i] = true;
Helper(result, permutation, nums, visited);
permutation.remove(permutation.size() - 1);
visited[i] = false;
}
}
}
16. Permutations II
public class Solution {
/*
* @param : A list of integers
* @return: A list of unique permutations
*/
public List<List<Integer>> permuteUnique(int[] nums) {
// write your code here
List<List<Integer>> result = new ArrayList<>();
if(nums == null){
return result;
}
List<Integer> permutation = new ArrayList<>();
boolean[] visited =new boolean[nums.length];
Arrays.sort(nums);
Helper(result,nums,permutation,visited);
return result;
}
public void Helper(List<List<Integer>> result, int[] nums, List<Integer> permutation, boolean[] visited){
if(permutation.size() == nums.length){
result.add(new ArrayList<>(permutation));
return;
}
for(int i =0; i<nums.length;i++){
if(visited[i]){
continue;
}
if(i>0 && nums[i]==nums[i-1] && visited[i-1] == false){
continue;
}
permutation.add(nums[i]);
visited[i] = true;
Helper(result,nums,permutation,visited);
permutation.remove(permutation.size()-1);
visited[i] = false;
}
}
};
33. N-Queens
public class Solution {
/*
* @param n: The number of queens
* @return: All distinct solutions
*/
public List<List<String>> solveNQueens(int n) {
// write your code here
List<List<String>> result = new ArrayList<>();
if (n < 0) {
return result;
}
List<Integer> queenSolution = new ArrayList<>();
Helper(result, queenSolution, n);
return result;
}
public void Helper(List<List<String>> result, List<Integer> queenSolution, int n) {
if (queenSolution.size() == n) {
result.add(getQueenStr(queenSolution));
return;
}
for (int i = 0; i < n; i++) {
if (!isValid(queenSolution, i)) {
continue;
}
queenSolution.add(i);
Helper(result, queenSolution, n);
queenSolution.remove(queenSolution.size() - 1);
}
}
public boolean isValid(List<Integer> queenSolution, int q) {
int nextcol = queenSolution.size();
for (int i = 0; i < queenSolution.size(); i++) {
//判断是否同一列
if (queenSolution.get(i) == q) {
return false;
}
//判断是否在左斜线
if (nextcol + q == i + queenSolution.get(i)) {
return false;
}
//判断是否在右斜线
if (nextcol - q == i - queenSolution.get(i)) {
return false;
}
}
return true;
}
public List<String> getQueenStr(List<Integer> solution) {
List<String> res = new ArrayList<>();
int strLen = solution.size();
for (Integer i : solution) {
StringBuilder stringBuilder = new StringBuilder();
for (int m = 0; m < strLen; m++) {
stringBuilder.append(m == i ? 'Q' : '.');
}
res.add(stringBuilder.toString());
}
return res;
}
}
121. Word Ladder II
public class Solution {
/*
* @param start: a string
* @param end: a string
* @param dict: a set of string
* @return: a list of lists of string
*/
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
// write your code here
List<List<String>> result = new ArrayList<>();
if (start == null || end == null) {
return result;
}
if (start.equals(end)) {
List<String> solution = new ArrayList<>();
solution.add(start);
solution.add(end);
result.add(solution);
return result;
}
//字典要加入start,end，否则对某些case会fail
dict.add(start);
dict.add(end);
Map<String, Integer> distanceMap = new HashMap<>();
Map<String, List<String>> neighbourMap = new HashMap<>();
getShortestPath(start, end, dict, distanceMap, neighbourMap);
List<String> solution = new ArrayList<>();
//基于nextWord进行递归，所以一开始要将初始值加入solution
solution.add(start);
Helper(result, solution, distanceMap, neighbourMap, start, end);
return result;
}
//bfs 重点注意，得到最短路径之后一定要走完最后一层的BFS，否则会少解
public void getShortestPath(String start, String end, Set<String> dict,
Map<String, Integer> distanceMap, Map<String, List<String>> neighbourMap) {
Queue<String> queue = new LinkedList<>();
queue.offer(start);
distanceMap.put(start, 0);
int distance = 0;
boolean isShortedPath = false;
while (!queue.isEmpty()) {
int size = queue.size();
distance++;
for (int i = 0; i < size; i++) {
String word = queue.poll();
if (neighbourMap.containsKey(word)) {
continue;
}
neighbourMap.put(word, new ArrayList<>());
for (String next : getNextWords(word, dict)) {
neighbourMap.get(word).add(next);
if(!distanceMap.containsKey(next)){
distanceMap.put(next, distance);
queue.offer(next);
}
if (next.equals(end)) {
isShortedPath = true;
}
}
}
if(isShortedPath){
break;
}
}
}
//dfs
public void Helper(List<List<String>> result, List<String> solution,
Map<String, Integer> distanceMap, Map<String, List<String>> neighbourMap,
String word, String end) {
if(word.equals(end)){
result.add(new ArrayList<>(solution));
return;
}
if(neighbourMap.get(word)!=null){
for(String str: neighbourMap.get(word)){
if(distanceMap.containsKey(str) && distanceMap.get(str) == distanceMap.get(word) + 1){
solution.add(str);
Helper(result,solution,distanceMap,neighbourMap,str,end);
solution.remove(solution.size()-1);
}
}
}
}
public List<String> getNextWords(String word, Set<String> dict) {
List<String> result = new ArrayList<>();
int len = word.length();
for (int i = 0; i < len; i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch == word.charAt(i)) {
continue;
}
if (dict.contains(getReplaceWord(word, i, ch))) {
result.add(getReplaceWord(word, i, ch));
}
}
}
return result;
}
public String getReplaceWord(String word, int i, char ch) {
char[] chars = word.toCharArray();
chars[i] = ch;
return new String(chars);
}
}
最新文章
- Extjs MVC学习随笔01
- js 数组赋值问题 ：值传递还是引用？
- cut命令
- Python: 关于nose
- 对Map按key和value分别排序
- 判断是否为ie（包含ie11）
- zepto笔记
- 网站流量统计系统 phpMyVisites
- 系统自动生成ID(比UUID.radom().tostring()要好看)
- 关于php中id设置自增后不连续的问题
- python视频学习笔记3（循环）
- Linux下发送邮件
- u-boot移植（一）---准备工作
- python带参数装饰器使用
- 关于 svn
- fzyzojP3412 -- [校内训练20171212]奇数
- VC6 快捷键
- Kali Nethunter初体验
- zabbix 监控服务器的TCP状态
- 2018.7.13vue知识小结