Implicit Graph DFS

-
Implicit Graph DFS

Implicit Graph DFS

Combinations（组合）

需要注意的是以下几点：

  1. 空值：看清题目，如果当nums的个数为0的时候，需要不需要加入空列，如果需要就不能在判断空条件下加入.length
  2. 排序：在做组合类题目之前一定要确定这个nums是个有序的数组，如果不是就需要排序
  3. dfs()：一般都是dfs(collection, [condition], index, level result, final results)
  4. 添加result到results中：如果没有特殊条件直接添加，否则在特殊条件下加入并返回return
  5. for循环：注意i的初始值是index
  6. for循环体：dfs老套路，加入，再dfs，再删去，dfs时，注意[condition]是否需要改变，index传的是和i相关的，如果不可以重复传入i + 1，如果可以重复传入i

SubSets（最简单的Combination）

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums == null) {
            return results;
        }
        // 一定要排个序之后再做
        Arrays.sort(nums);
        dfs(nums, 0, new ArrayList<Integer>(), results);
        return results;
    }
    private void dfs(int[] nums, int index, List<Integer> result, List<List<Integer>> results) {
        results.add(new ArrayList<Integer>(result));
        for (int i = index; i < nums.length; i++) { // 注意 index 不是 0
            // 判断是否有重复
            if (i > index && nums[i] == nums[i - 1]) {
                continue;
            }
            result.add(nums[i]);
            dfs(nums, i + 1, result, results); // 注意 i + 1 不是 index
            result.remove(result.size() - 1);
        }
    }
}

Combination（限制entry个数的Combination）

public class Solution {
  public List<List<Integer>> combine(int n, int k) {
      List<List<Integer>> results = new ArrayList<>();
      if (n == 0) {
          return results;
      }
      // 题目特殊性：n 无序排序，如果是nums当然还是要排一下序的
      dfs(n, k, 0, new ArrayList<Integer>(), results); // 多传入一个条件，这里是 k
      return results;
  }
  private void dfs(int n, int k, int index, List<Integer> result, List<List<Integer>> results) {
      // 条件是每个结果的个数是 k 个，所以这里在加入到results时候就需要考虑条件了
      if (result.size() == k) {
          results.add(new ArrayList<Integer>(result));
          return;
      }
      for (int i = index; i < n; i++) {
          result.add(i + 1); // 题目特殊性：放入的不是 index 是第几个所以需要 index + 1
          dfs(n, k, i + 1, result, results);
          result.remove(result.size() - 1);
      }
  }
}

Combination（限制entry中每个元素最大能到几的Combination）

public class Solution {
  public List<List<Integer>> combine(int n, int k) {
      List<List<Integer>> results = new ArrayList<>();
      if (n == 0) {
          return results;
      }
      // 题目特殊性：n 无序排序，如果是nums当然还是要排一下序的
      dfs(n, k, 0, new ArrayList<Integer>(), results); // 多传入一个条件，这里是 k
      return results;
  }
  private void dfs(int n, int k, int index, List<Integer> result, List<List<Integer>> results) {
      results.add(new ArrayList<Integer>(result));
      // 由于每个i最初是index，每次自增1，i < k 的意思就是最多i可以到几
      // 在循环体内部result添加的是 i + 1 所以每个元素最多能到 i = k
      // 我们当然可以写成Math.min(n, k)，但是为了理解清晰，不混淆n和k，在这里分开写
      for (int i = index; i < n && i < k; i++) {
          result.add(i + 1); // 题目特殊性：放入的不是 index 是第几个所以需要 index + 1
          dfs(n, k, i + 1, result, results);
          result.remove(result.size() - 1);
      }
  }
}

Combination Sum（限制entry和的Combination）

public class Solution {
  public List<List<Integer>> combinationSum(int[] nums, int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums == null) {
            return results;
        }
        // 一定要排个序之后再做
        Arrays.sort(nums);
        dfs(nums, target, 0, new ArrayList<Integer>(), results); // 多传入一个条件，这里是 target
        return results;
    }
    private void dfs(int[] nums, int target, int index, List<Integer> result, List<List<Integer>> results) {
        // 条件是每个entry的和为 target，所以在加入 results 之前需要考虑
        if (target == 0) {
            results.add(new ArrayList<Integer>(result));
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            // 判断是否有重复
            if (i > index && i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            result.add(nums[i]);
            dfs(nums, target - nums[i], i + 1, result, results); // 注意每次目标和需要抛去 nums[i] 传入下一层
            result.remove(result.size() - 1);
        }
    }
}

Permutations（排列）

需要注意的是以下几点：

  1. 空值：看清题目，如果当nums的个数为0的时候，需要不需要加入空列，如果需要就不能在判断空条件下加入.length
  2. 排序：在做排列类题目之前一定要确定这个nums是个有序的数组，如果不是就需要排序
  3. dfs()：一般都是dfs(collection, [condition], visited, level result, final results)
  4. 添加result到results中：如果没有特殊条件，默认在长度和原nums相同的情况下添加，否则在特殊条件下加入并返回return
  5. for循环：注意i的初始值是0
  6. for循环体：dfs老套路，加入，此时visited置true，再dfs，再删去，visited置false，dfs时，注意[condition]是否需要改变

Permutation（最简单的Permutation）

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums == null) {
            return results;
        }
        // 一定要排个序之后再做
        Arrays.sort(nums);
        // 不需要index了，因为此时需要一个数组来记录是否访问过
        dfs(nums, new boolean[nums.length], new ArrayList<Integer>(), results);
        return results;
    }
    private void dfs(int[] nums, int index, List<Integer> result, List<List<Integer>> results) {
        // 条件是每个entry的排列好了的长度应该和原数组长度相等，所以在相等时才加入results
        if (nums.length == result.size()) {
            results.add(new ArrayList<Integer>(result));
            return;
        }
        // 注意此时的 i 应该从头开始，因为 nums 的顺序是不变的，取值应该从头开始
        // 取过的已经被 visited 过滤掉了，所以可以放心的取下一个可用值了
        for (int i = 0; i < nums.length; i++) {
            // visited 过滤
            if (visited[i]) {
                continue;
            }
            // 去重
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }
            result.add(nums[i]);
            visited[i] = true; // 添加值到 result 中马上记录 visited 为 true
            dfs(nums, visited, result, results);
            result.remove(result.size() - 1);
            visited[i] = false; // 删除值从 result 中马上记录 visited 为 false
        }
    }
}

Divide Conquer (分治法)

需要注意的是以下几点：

  1. results：调用dfs()的函数中要创建结果集，并从dfs()中返回得到

  2. dfs()的定义：一般都是[return type] dfs(collection, [condition], index, level result)，注意不能把results传入dfs()中，要作为返回值返回

  3. dfs()中：创建当前层中所要返回的results，它代表的是以上一层result为prefix的所有可行解的集合

  4. 返回subResults，即divide：对于每一层sub dfs()来说要返回其subResults，其次对于sub dfs()要把添加了当前nums[i]之后的result作为参数传入

  5. inner for循环，即conquer：循环subResults把每一个subResult传入当前的results中

  6. 返回results：由于divide和conquer结束，要把conquer之后得到的results返回给上一级

    SubSets（最简单的Combination）

    public class Solution {
     public List<List<Integer>> subsets(int[] nums) {
         List<List<Integer>> results = new ArrayList<>();
         if (nums == null) {
             return results;
         }
         Arrays.sort(nums);
         // 将返回值赋给结果，不能把results当作参数传入dfs()中
         results = dfs(nums, 0, new ArrayList<Integer>());
         return results;
     }
     // 返回值为results，而参数中没有
     private List<List<Integer>> dfs(int[] nums, int index, List<Integer> result) {
         // 创建当前层的results作为上一层的subResults
         List<List<Integer>> results = new ArrayList<>();
         results.add(new ArrayList<Integer>(result));
         for (int i = index; i < nums.length; i++) {
             if (i > index && nums[i] == nums[i - 1]) {
                 continue;
             }
             result.add(nums[i]);
             // 创建当前层对于下一层的subResults并从下一层的dfs()中返回
             List<List<Integer>> subResults = dfs(nums, i + 1, result);
             result.remove(result.size() - 1);
             // 循环把下一层的subResults添加到当前层的results中
             for (List<Integer> subResult : subResults) {
                 results.add(subResult);
             }
         }
         // 返回当前层的results
         return results;
     }
    }

    Combination（限制entry个数的Combination）

    public class Solution {
     public List<List<Integer>> combine(int n, int k) {
         List<List<Integer>> results = new ArrayList<>();
         if (n == 0) {
             return results;
         }
         // 题目特殊性：n 无序排序，如果是nums当然还是要排一下序的
         // 多传入一个条件，这里是 k
         // 将返回值赋给结果，不能把results当作参数传入dfs()中
         results = dfs(n, k, 0, new ArrayList<Integer>());
         return results;
     }
     // 返回值为results，而参数中没有
     private List<List<Integer>> dfs(int n, int k, int index, List<Integer> result) {
         // 创建当前层的results作为上一层的subResults
         List<List<Integer>> results = new ArrayList<>();
         // 条件是每个结果的个数是 k 个，所以这里在加入到results时候就需要考虑条件了
         if (result.size() == k) {
             results.add(new ArrayList<Integer>(result));
             // 返回当前的results作为上一层的subResults
             return results;
         }
         for (int i = index; i < n; i++) {
             result.add(i + 1); // 题目特殊性：放入的不是 index 是第几个所以需要 index + 1
             List<List<Integer>> subResults = dfs(n, k, i + 1, result); // 创建当前层对于下一层的subResults并从下一层的dfs()中返回
             result.remove(result.size() - 1);
             // 循环把下一层的subResults添加到当前层的results中
             for (List<Integer> item : subResults) {
                 results.add(item);
             }
         }
         // 返回当前层的results
         return results;
     }
    }

    其他同理，不做过多重复refactor

Comments

Post a Comment