文章目录
剑指 Offer II 084. 含有重复元素集合的全排列
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
https://leetcode.cn/problems/7p8L0Z/
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null) {
return null;
}
int len = nums.length;
if (len <= 0) {
return null;
}
dumpLen = len;
// 需要标记数组
visted = new boolean[len];
dfs(new ArrayList<>(), nums);
return new ArrayList<>(res);
}
private Set<List<Integer>> res = new HashSet<>();
private int dumpLen = 0;
private boolean[] visted;
private void dfs(List<Integer> onePath, int[] nums) {
if (onePath.size() == dumpLen) {
res.add(new ArrayList<>(onePath));
return;
}
for (int i = 0; i < dumpLen; i++) {
if (visted[i] == false) {
onePath.add(nums[i]);
visted[i] = true;
dfs(onePath, nums);
onePath.remove(onePath.size() - 1);
visted[i] = false;
}
}
}
}
剑指 Offer II 079. 所有子集
剑指 Offer II 079. 所有子集
给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
// 解法一：按照子集的长度进行 dfs 搜索。
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if (nums == null) {
return null;
}
int n = nums.length;
for (int k = 0; k <= n; k++) {
// 每一个长度 k 的子集都从 index = 0 开始
dfs(0, k, nums.length, nums);
}
return res;
}
private void dfs(int start, int k, int n, int[] nums) {
if (k == 0) {
res.add(new ArrayList<Integer>(path));
return;
}
for (int i = start; i < n; i++) {
path.add(nums[i]);
dfs(i + 1, k - 1, n, nums);
path.remove(path.size() - 1);
}
}
}
// 解法二：递归法实现子集枚举
class Solution02 {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
dfs(0, nums);
return ans;
}
public void dfs(int cur, int[] nums) {
if (cur == nums.length) {
ans.add(new ArrayList<Integer>(t));
return;
}
// 考虑选择当前位置
t.add(nums[cur]);
dfs(cur + 1, nums);
t.remove(t.size() - 1);
// 考虑不选择当前位置
dfs(cur + 1, nums);
}
// 解法三：实现所有三位数 01 字符串生成，0 表示不存在，1 表示存在。代码略
}
- 时间：O(n*2^n)
- 空间：O(n)
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
class Solution {
// 记得初始化
private List<List<Integer>> result = new LinkedList<>();
// 一般保存地图，不保存 onePath
private int[] candidates_dump;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null) {
return result;
}
candidates_dump = candidates;
dfs(0, 0, target, new LinkedList<>());
return result;
}
private void dfs(int index, int sum, int target, List<Integer> onePath) {
if (sum == target) {
// 注意写法
result.add(new LinkedList<>(onePath));
return;
}
for (int i = index; i < candidates_dump.length; i++) {
int tmpSum = sum + candidates_dump[i];
if (tmpSum <= target) {
onePath.add(candidates_dump[i]);
dfs(i, sum + candidates_dump[i], target, onePath);
// 回溯
onePath.remove(onePath.size() - 1);
}
}
}
}
- 时间：O(S) :S 为所有可行解的长度之和
- 空间：O(target)
剑指 Offer 12. 矩阵中的路径
https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
class Solution {
private char[][] globalBoard;
private int m = 0;
private int n = 0;
private char[] wordChar;
private int[][] dir = new int[][]{
{
0, 1}, {
1, 0}, {
-1, 0}, {
0, -1}};
private boolean check(int xx, int yy, int index) {
if (xx < 0 || xx > m - 1) {
return false;
}
if (yy < 0 || yy > n - 1) {
return false;
}
if (globalBoard[xx][yy] != wordChar[index]) {
return false;
}
return true;
}
private boolean dfs(int x, int y, int index) {
if (index == wordChar.length - 1) {
return true;
}
for (int i = 0; i < 4; i++) {
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (this.check(xx, yy, index + 1)) {
globalBoard[xx][yy] = '0';
if (dfs(xx, yy, index + 1)) {
return true;
}
// 回溯回去
globalBoard[xx][yy] = wordChar[index + 1];
}
}
return false;
}
public boolean exist(char[][] board, String word) {
if (board == null || word == null) {
return false;
}
m = board.length;
if (m > 0) {
n = board[0].length;
}
globalBoard = board;
wordChar = word.toCharArray();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (this.check(i, j, 0)) {
globalBoard[i][j] = '0';
if (dfs(i, j, 0))
return true;
globalBoard[i][j] = wordChar[0];
}
}
}
return false;
}
}
- 时间：O(n)
- 空间：O(1)
222. 完全二叉树的节点个数
https://leetcode-cn.com/problems/count-complete-tree-nodes/
// 解法一
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
// 解法二
class Solution {
private int bfs(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int res = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
res += 2;
}
return res;
}
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
// 解法三：见 leetcode
- 时间：O(n)
- 空间：O(n)
剑指 Offer 34. 二叉树中和为某一值的路径
https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
class Solution {
// 一般是比较复杂的数据结构：会放在类的成员变量中
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> onePath = new ArrayList<>();
private void dfs(TreeNode root, int target) {
// 这里面要处理 root
if (root == null) {
return;
}
onePath.add(root.val);
target -= root.val;
if (root.left == null && root.right == null && 0 == target) {
result.add(new ArrayList<>(onePath));
}
dfs(root.left, target);
dfs(root.right, target);
// 回溯（target 因为是 不断压栈和进栈的，所以不需要回溯）
onePath.remove(onePath.size() - 1);
}
public List<List<Integer>> pathSum(TreeNode root, int target) {
if (root == null) {
return result;
}
dfs(root, target);
return result;
}
}
- 时间：O(n)
- 空间：O(n)
剑指 Offer 38. 字符串的排列
思路：
- 还是按照正常思路来理解即可，先遍历所有字符，在循环中固定循环的这一位为x，然后dfs搜索，直到 length == s.length-1，就得出一种结果。需要注意剪枝操作。
- 因为只是交换操作，所以就不需要
class Solution {
Set<String> result = new HashSet<>();
char[] c;
public String[] permutation(String s) {
if (s == null) {
return null;
}
c = s.toCharArray();
dfs(0);
return result.toArray(new String[result.size()]);
}
void dfs(int x) {
if (x == c.length - 1) {
result.add(String.valueOf(c)); // 添加排列方案
return;
}
// 考虑 abc 以及 abb 的情况
HashSet<Character> set = new HashSet<>();
for (int i = x; i < c.length; i++) {
// 会存在重复，因此剪枝
if (set.contains(c[i]))
continue;
set.add(c[i]);
// swap(c[i], c[x]); (不能这样交换，这样子是值传递，并没有发生数组意义上的交换操作)
// 交换，将 c[i] 固定在第 x 位
swap(i, x);
// 开启固定第 x + 1 位字符
dfs(x + 1);
// 恢复交换
swap(i, x);
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
}
- 时间：O(N!)
- 空间：O(N^2)
22. 括号生成
https://leetcode-cn.com/problems/generate-parentheses/
给定一个 N，输出所有可能的括号匹配结果。
思路：
- N 确定后，我们生成的一定就是 2N 的字符串序列。而每个位置放的数据要么就是"(“，要么就是”)"，所以我们直接使用 DFS 搜索遍历其就可以了。相当于DFS+保存路径
class Solution {
private List<String> result = new ArrayList<>();
private int count;
private void dfs(int left, int right, String path) {
if (left == count && right == count) {
result.add(path);
return;
}
// 左括号没用完，就加 “(” 括号
if (left < count) {
// dfs时，注意是 left+1,不要写成 left++
dfs(left + 1, right, path + "(");
}
// 右括号没用完，就加 “)” 括号
// 剪枝：
// right < left 是因为 左括号数量一定要大于右括号，否则就是霸王硬上弓，直接上了右括号
if (right < count && right < left) {
dfs(left, right + 1, path + ")");
}
}
public List<String> generateParenthesis(int n) {
result.clear();
count = n;
if (n <= 0) {
return result;
}
dfs(0, 0, "");
return result;
}
}
- 时间：O(2^n)
- 空间：O(n)
N皇后的问题
// 52 题
class Solution {
//撇 的特点是：x+y =c
//捺 的特点是：x-y =c
private void dfs(int n, int row, Set<Integer> colSet, Set<Integer> pieSet, Set<Integer> naSet) {
// 找到其中一种解法
if (row >= n) {
result++;
return;
}
//搜索 列 即可
for (int col = 0; col < n; col++) {
if (colSet.contains(col) || pieSet.contains(row + col) || naSet.contains(row - col)) {
continue;
}
//标记
colSet.add(col);
pieSet.add(row + col);
naSet.add(row - col);
dfs(n, row + 1, colSet, pieSet, naSet);
//恢复
colSet.remove(col);
pieSet.remove(row + col);
naSet.remove(row - col);
}
}
int result = 0;
public int totalNQueens(int n) {
if (Objects.equals(null, n) || n <= 0) {
return result;
}
Set<Integer> colSet = new HashSet<Integer>();
Set<Integer> pieSet = new HashSet<Integer>();
Set<Integer> naSet = new HashSet<Integer>();
dfs(n, 0, colSet, pieSet, naSet);
return result;
}
}