LeeCode Practice Journal ｜ Day25_Backtracking04

491. 非递减子序列

题目：491. 非递减子序列 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)

solution

public class Solution {public List<IList<int>> results = new List<IList<int>>();public IList<IList<int>> FindSubsequences(int[] nums) {List<int> result = new List<int>();subTraversal(nums, 0, result);return results;}public void subTraversal(int[] nums, int start, List<int> result){HashSet<int> numbers = new HashSet<int>();for(int i = start; i < nums.Length; i ++){if(result.Count > 0 && nums[i] < result[result.Count - 1]) {continue;  }if(numbers.Add(nums[i])){result.Add(nums[i]);if(result.Count > 1) results.Add(new List<int>(result));subTraversal(nums, i + 1, result);result.RemoveAt(result.Count - 1);}}}
}

summary

key：

HashSet同层查重

错误：

1、题意理解有误
递增子序列指在数组原顺序下的

2、子序列至少有两个元素

46. 全排列

题目：46. 全排列 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
排列问题，使用数组或哈希表记录元素，也算一种树枝去重？

solution

public class Solution {public List<IList<int>> results = new List<IList<int>>(); public IList<IList<int>> Permute(int[] nums) {List<int> result = new List<int>();HashSet<int> numbers = new HashSet<int>();permuteTraversal(nums, numbers, result);return results;}public void permuteTraversal(int[] nums, HashSet<int> numbers, List<int> result){if(result.Count == nums.Length){results.Add(new List<int>(result));return;}for(int i = 0; i < nums.Length; i ++){if(numbers.Add(nums[i])){result.Add(nums[i]);permuteTraversal(nums, numbers, result);result.RemoveAt(result.Count - 1);numbers.Remove(nums[i]);}}}
}

summary

47. 全排列Ⅱ

题目：47. 全排列 II - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
同一树枝使用数组标记元素是否已选过，同一树层使用HashSet去重

solution

public class Solution {public List<IList<int>> results = new List<IList<int>>(); public IList<IList<int>> PermuteUnique(int[] nums) {List<int> result = new List<int>();int[] mark = new int[nums.Length];permuteTraversal(nums, mark, result);return results;}public void permuteTraversal(int[] nums, int[] mark, List<int> result){if(result.Count == nums.Length){results.Add(new List<int>(result));return;}HashSet<int> layer = new HashSet<int>();for(int i = 0; i < nums.Length; i ++){if(mark[i] == 0){if(layer.Add(nums[i])){mark[i] = 1;result.Add(nums[i]);permuteTraversal(nums, mark, result);result.RemoveAt(result.Count - 1);mark[i] = 0;}}}}
}

summary

332. 重新安排行程

题目：332. 重新安排行程 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)

solution

summary

51. N皇后

题目：51. N 皇后 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)

solution

using System;
using System.Collections.Generic;
using System.Text;public class Solution {public List<IList<string>> results = new List<IList<string>>();public IList<IList<string>> SolveNQueens(int n) {List<StringBuilder> result = new List<StringBuilder>();for (int i = 0; i < n; i++) {StringBuilder row = new StringBuilder(new string('.', n));result.Add(row);}queensTraversal(result, 0, n, new bool[n], new bool[2 * n], new bool[2 * n]);return results;}public void queensTraversal(List<StringBuilder> sbs, int row, int n, bool[] cols, bool[] d1, bool[] d2) {// 可以加入结果集的情况if (row == n) {List<string> Result = new List<string>();foreach (StringBuilder sb in sbs) {Result.Add(sb.ToString());}results.Add(Result);return;}for (int col = 0; col < n; col++) {int id1 = col - row + n;int id2 = col + row;if (!cols[col] && !d1[id1] && !d2[id2]) {sbs[row][col] = 'Q';cols[col] = d1[id1] = d2[id2] = true;// 递归queensTraversal(sbs, row + 1, n, cols, d1, d2);// 回溯sbs[row][col] = '.';cols[col] = d1[id1] = d2[id2] = false;}}}
}

summary

错误：

1、理解错题意：
皇后不能互相攻击的限制：不能同行/同列/同斜线。指的是当前棋盘上所有皇后，而不是上下两行。。。
判断当前棋盘是否有效的条件

2、StringBuilder列表初始写法
错误写法如下：

List<StringBuilder> result = new List<StringBuilder>(n);
for(int i = 0; i < n; i ++)
{result[i] = new StringBuilder(n);for(int j = 0; j < n; j ++){result[i][j] = '.';}
}

37. 解数独

题目：37. 解数独 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)

solution

public class Solution {public void SolveSudoku(char[][] board) {Solve(board);}private bool Solve(char[][] board) {for (int row = 0; row < 9; row++) {for (int col = 0; col < 9; col++) {if (board[row][col] == '.') {for (char num = '1'; num <= '9'; num++) {if (IsValid(board, row, col, num)) {board[row][col] = num;if (Solve(board)) {return true;}board[row][col] = '.';}}return false;}}}return true;}private bool IsValid(char[][] board, int row, int col, char num) {for (int i = 0; i < 9; i++) {if (board[row][i] == num || board[i][col] == num || board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num) {return false;}}return true;}
}

summary