前言
打卡代码随想录算法训练营第49期第二十五天 ○( ＾皿＾)っHiahiahia…
首先十分推荐学算法的同学可以先了解一下代码随想录，可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解，卡哥清晰易懂的算法教学让我直接果断关注，也十分有缘和第49期的训练营大家庭一起进步。
今日题目
在学习今日的题目前先看：回溯理论(文字)、卡哥讲解 —— 回溯理论
LeetCode 491 递增子序列
题目链接：491 递增子序列
文章讲解：递增子序列
视频讲解：卡哥讲解 —— 递增子序列
本题使用了新的去重方式，原因是因为之前的used去重只适用于有序数组，而本题无法做到有序，所以使用HashSet来进行本层去重。
public class Solution {
public List<IList<int>> res = new List<IList<int>>();
public List<int> path = new List<int>();
public IList<IList<int>> FindSubsequences(int[] nums) {
BackTracking(nums , 0);
return res;
}
public void BackTracking(int[] nums , int startIndex)
{
if(path.Count >= 2)
res.Add(new List<int>(path));
//使用哈希来进行本层去重
HashSet<int> hs = new HashSet<int>();
for(int i = startIndex; i < nums.Length; i++)
{
//本层去重
if(path.Count > 0 && nums[i] < path[path.Count - 1] || hs.Contains(nums[i]))
continue;
hs.Add(nums[i]);
path.Add(nums[i]);
BackTracking(nums , i + 1);
path.RemoveAt(path.Count - 1);//回溯
}
}
}LeetCode 46 全排列
题目链接：46 全排列
文章讲解：全排列
视频讲解：卡哥讲解 —— 全排列
本题明确说了所有元素不相同，所以直接使用used就可以解决。
public class Solution {
public List<IList<int>> res = new List<IList<int>>();
public List<int> path = new List<int>();
public IList<IList<int>> Permute(int[] nums) {
//使用used记录使用过的元素
int[] used = new int[nums.Length];
BackTracking(nums , used);
return res;
}
public void BackTracking(int[] nums , int[] used)
{
//当记录数量等于数组数量 则可以加入
if(path.Count == nums.Length)
{
res.Add(new List<int>(path));
return;
}
for(int i = 0; i < nums.Length; i++)
{
if(used[i] == 1)//used[i] = 1代表元素使用过
continue;
path.Add(nums[i]);
used[i] = 1;
BackTracking(nums , used);
used[i] = 0;//回溯
path.RemoveAt(path.Count - 1);//回溯
}
}
}LeetCode 47 全排列II
题目链接：47 全排列 II
文章讲解：全排列 II
视频讲解：卡哥讲解 —— 全排列 II
这个题目和全排列基本一致，就是多了数组中有重复元素的条件，那么就需要用HashSet进行单层去重，剩下完全一致。
public class Solution {
public List<IList<int>> res = new List<IList<int>>();
public List<int> path = new List<int>();
public IList<IList<int>> PermuteUnique(int[] nums) {
int[] used = new int[nums.Length];
BackTracking(nums , used);
return res;
}
public void BackTracking(int[] nums , int[] used)
{
if(path.Count == nums.Length)
{
res.Add(new List<int>(path));
return;
}
//单层去重
HashSet<int> hs = new HashSet<int>();
for(int i = 0; i < nums.Length; i++)
{
if(used[i] == 1 || hs.Contains(nums[i]))
continue;
hs.Add(nums[i]);
path.Add(nums[i]);
used[i] = 1;
BackTracking(nums , used);
used[i] = 0;//回溯
path.RemoveAt(path.Count - 1);//回溯
}
}
}LeetCode 332 重新安排行程
题目链接：332 重新安排行程
文章讲解：重新安排行程
本题十分复杂，建议直接看代码随想录网站内容。
public class Solution {
//dic<出发机场,dic<到达机场,到达次数>>
public Dictionary<string, Dictionary<string,int>> targets = new Dictionary<string, Dictionary<string,int>>();
public LinkedList<string> res = new LinkedList<string>();
public IList<string> FindItinerary(IList<IList<string>> tickets) {
foreach (var list in tickets) {
string from = list[0];//起始位置
string to = list[1];//到达位置
//添加对应关系
if(!targets.TryGetValue(from, out var temp))
{
temp = new Dictionary<string, int>();
targets.Add(from, temp);
}
if(temp.ContainsKey(to))
temp[to] += 1;
else
temp.Add(to , 1);
}
res.AddLast("JFK");
BackTracking(tickets.Count);
return res.ToList();
}
public bool BackTracking(int ticketNum)
{
//终止条件根据规律可以得到为票数 + 1
if(res.Count == ticketNum + 1)
return true;
//上一站的到达的位置
string currentPlace = res.Last();
//如果不存在这里出发的机票 则返回false
if(!targets.ContainsKey(currentPlace))
return false;
var dic = targets[currentPlace].OrderBy(x=>x.Key).ToDictionary(x=>x.Key, x=>x.Value)/*排序 先走排序靠前的*/;
foreach(var ticket in dic)
{
if(ticket.Value > 0)
{
res.AddLast(ticket.Key);
targets[currentPlace][ticket.Key] -= 1;
//判断走这条路行不行的通
if(BackTracking(ticketNum))
return true;
res.RemoveLast();//回溯
targets[currentPlace][ticket.Key] += 1;//回溯
}
}
//到这里证明没有任意一条路可以满足条件，只能返回上一次再寻找
return false;
}
}LeetCode 51 N皇后
题目链接：51 N皇后
文章讲解：N皇后
视频讲解：卡哥讲解 —— N皇后
本题十分复杂，建议直接看代码随想录网站内容与卡哥讲解内容。
public class Solution {
public List<IList<string>> res = new List<IList<string>>();
public IList<IList<string>> SolveNQueens(int n) {
//初始化棋盘
char[][] board = new char[n][];
for(int i = 0; i < n; i++)
{
board[i] = new char[n];
for(int j = 0; j < n; j++)
{
board[i][j] = '.';
}
}
BackTracking(n , 0 , board);
return res;
}
public void BackTracking(int n , int row , char[][] chessBoard)
{
if(row == n)//终止条件
{
res.Add(chessBoard.Select(x => new string(x)).ToList());
return;
}
for(int i = 0; i < n; i++)
{
if(CheckCanIn(chessBoard , row , i , n))
{
chessBoard[row][i] = 'Q';
BackTracking(n , row + 1 , chessBoard);
chessBoard[row][i] = '.';//回溯
}
}
}
//检测该位置是否能放入皇后
public bool CheckCanIn(char[][] chessBoard , int row/*行*/ , int col/*列*/ , int n)
{
for(int i = 0; i < row; i++)
{
if(chessBoard[i][col] != '.')
return false;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
{
if (chessBoard[i][j] == 'Q')
return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
{
if (chessBoard[i][j] == 'Q')
return false;
}
return true;
}
}LeetCode 37 解数独
题目链接：37 解数独
文章讲解：解数独
视频讲解：卡哥讲解 —— 解数独
本题十分复杂，建议直接看代码随想录网站内容与卡哥讲解内容。
public class Solution {
public void SolveSudoku(char[][] board) {
BackTracking(board);
}
public bool BackTracking(char[][] board)
{
for(int i = 0; i < board.Length; i++)
{
for(int j = 0; j < board[0].Length; j++)
{
//找到需要填数的位置
if(board[i][j] != '.')
continue;
//从1 - 9挨个试
for(char k = '1'; k <= '9'; k++)
{
if(IsValid(board , i , j , k))
{
board[i][j] = k;
if(BackTracking(board))
return true;
board[i][j] = '.';//回溯
}
}
return false;
}
}
return true;
}
//判断是否可以填某个数字
public bool IsValid(char[][] board, int row/*行*/, int col/*列*/, char val)
{
for (int i = 0; i < 9; i++)//判断这一列是否有相同数字
{
if (board[i][col] == val) return false;
}
for (int i = 0; i < 9; i++)//判断这一行是否有相同数组
{
if (board[row][i] == val) return false;
}
//判断3 * 3内是否有相同数字
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++)
{
for (int j = startCol; j < startCol + 3; j++)
{
if (board[i][j] == val) return false;
}
}
//前面都没返回false 则可以填写此数
return true;
}
}学完回溯，在看看：回溯总结。
今天的后三道题算是比较难的内容，需要反复练习哦，明天见~~~
标签：排列,nums,int,res,随想录,322,new,path,public From： https://blog.csdn.net/tancxiaohei23/article/details/143997731