代码随想录算法训练营第二十五天| 491.递增子序列 46.全排列 47.全排列 II 51.N皇后

本文主要是介绍代码随想录算法训练营第二十五天| 491.递增子序列 46.全排列 47.全排列 II 51.N皇后,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 一、LeetCode 491.递增子序列
    • 思路:
    • C++代码
  • 二、LeetCode 46.全排列
    • 思路
    • C++代码
  • 三、LeetCode 47.全排列 II
    • 思路
    • C++代码
  • 四、LeetCode 51.N皇后
    • 思路
    • C++代码
  • 总结


一、LeetCode 491.递增子序列

题目链接:LeetCode 491.递增子序列

文章讲解:代码随想录
视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列

思路:

 非递减子序列要求不能对初始的数组排序,在数组中挑出若干个数组成非递减的一组序列。算法设计思路上,我们只需要对每一位进行判断是否非递减即可;由于存在重复元素,仍然会涉及到我们前面遇到过的同一树层去重问题,本题由于重复元素不一定在原始数组中的前一个,因此我们需要增加一位传参last,记录上一个满足要求的数字,用来判断非递减和去重操作。

C++代码

class Solution {
private:vector<vector<int>> subSeq;vector<int> inc;vector<int> src;void backtrack(int i, int last){//last记录上一位满足要求的数字if(i >= src.size()){if(inc.size() > 1) subSeq.push_back(inc);return;}if(src[i] >= last){inc.push_back(src[i]);backtrack(i+1, src[i]);inc.pop_back();}if(src[i] != last){  //若与前一个数相同则跳过backtrack(i+1, last);}}
public:vector<vector<int>> findSubsequences(vector<int>& nums) {src = nums;backtrack(0, INT_MIN); //使用整数中最小数作为初始值return subSeq;}
};

二、LeetCode 46.全排列

题目链接:LeetCode 46.全排列

文章讲解:代码随想录
视频讲解:组合与排列的区别,回溯算法求解的时候,有何不同?| LeetCode:46.全排列

思路

 这道题是笔者在学习算法设计时,递归章节的经典例题。

 算法的设计思想为,对数组从头进行遍历,在每一位处,分别将这一位与它后面的所有位置进行换位,换位后递归进入下一层,递归返回时还原位置(回溯)。通过在每一位上的换位递归可以实现枚举全排列的目的。
在这里插入图片描述

C++代码

class Solution {
private:vector<vector<int>> permutations;void backtrack(int i, vector<int> nums){if(i == nums.size()){permutations.push_back(nums);return;}for(int j = i; j < nums.size(); j++){swap(nums[i], nums[j]);backtrack(i+1, nums);swap(nums[i], nums[j]);}}
public:vector<vector<int>> permute(vector<int>& nums) {backtrack(0, nums);return permutations;}
};

三、LeetCode 47.全排列 II

题目链接:LeetCode 47.全排列 II

文章讲解:代码随想录
视频讲解:回溯算法求解全排列,如何去重?| LeetCode:47.全排列 II

思路

 与上一题不同的是含有重复元素,就会涉及到去重的问题。笔者在此题去重采用集合unordered_set,记录调换位置的数字,若后面出现一样的数则跳过。

C++代码

class Solution {
private:vector<vector<int>> permutations;void backtrack(int i, vector<int> nums){if(i == nums.size()){permutations.push_back(nums);return;}unordered_set<int> set;for(int j = i; j < nums.size(); j++){if(set.find(nums[j]) != set.end()) continue;set.insert(nums[j]);swap(nums[i], nums[j]);backtrack(i+1, nums);swap(nums[i], nums[j]);}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {backtrack(0, nums);return permutations;}
};

四、LeetCode 51.N皇后

题目链接:LeetCode 51.N皇后

文章讲解:代码随想录
视频讲解:这就是传说中的N皇后? 回溯算法安排!| LeetCode:51.N皇后

思路

 采用纯模拟方法 + 回溯即可。设立一个与方格同样大的二维数组记录当前格能否放置皇后,每当放置一个皇后时,将所在位置同行同列同斜线上的格子设为false,即不能放置皇后,按照行的顺序递归即可。

C++代码

class Solution {
private:  vector<vector<string>> queens;int size;void backtrack(vector<string> sol, vector<vector<bool>> access, int i, int j){if(i >= 0 && j >= 0){sol[i][j] = 'Q';for(int k = 0; k < size; k++){access[k][j] = false;access[i][k] = false;if(i+k < size){if(j+k < size) access[i+k][j+k] = false;if(j-k >= 0) access[i+k][j-k] = false;}}}if(i+1 == size){queens.push_back(sol);return;}for(int q = 0; q < size; q++){if(access[i+1][q]){backtrack(sol, access, i+1, q);}}}
public:vector<vector<string>> solveNQueens(int n) {size = n;vector<vector<bool>> access(n, vector<bool>(n, true));vector<string> sol(n, string(n, '.'));backtrack(sol, access, -1, -1);return queens;}
};


总结

 回溯算法最后一篇,一定要注意设计回溯递归时的还原现场、以及递归函数本身的传参、终止条件要素。在含有重复答案时需要考虑去重,常用方法有同树层去重以及哈希集合的方式。进阶题目二刷时再来练手。


文章图片来源:代码随想录 (https://programmercarl.com/)

这篇关于代码随想录算法训练营第二十五天| 491.递增子序列 46.全排列 47.全排列 II 51.N皇后的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1128775

相关文章

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放