当前位置: 首页 > news >正文

[Algorithm][回溯][字母大小写全排列][优美的排列][N皇后]详细讲解

目录

  • 1.字母大小写全排列
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 2.优美的排列
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 3.N 皇后
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现


1.字母大小写全排列

1.题目链接

  • 字母大小写全排列

2.算法原理详解

  • 本题逻辑与子集大致相同
    • 思路一:每次盯着一个字符,变或是不变
      • 全局变量
        • string path
        • vector<string> ret
      • DFS()设计
        • 函数头void DFS(string, pos)
          • pos:下一层递归要选的元素
        • 函数体
          • 字母可能变/不变,数字一定不需要变
        • 递归出口pos == nums.size()
      • 回溯:变完函数返回时需要回溯
        请添加图片描述

3.代码实现

class Solution 
{string path;vector<string> ret;
public:vector<string> letterCasePermutation(string s) {DFS(s, 0);return ret;}void DFS(string& s, int pos){if(pos == s.size()){ret.push_back(path);return;}char ch = s[pos];// 不改变path += ch;DFS(s, pos + 1);path.pop_back(); // 回溯,恢复现场// 改变if(ch < '0' || ch > '9'){ch = Change(ch);path += ch;DFS(s, pos + 1);path.pop_back(); // 回溯,恢复现场}}char Change(char ch){if(ch >= 'a' && ch <= 'z'){ch -= 32;}else{ch += 32;}return ch;}
};

2.优美的排列

1.题目链接

  • 优美的排列

2.算法原理详解

  • 思路:对每个位置挨个尝试填入数字
    • 全局变量
      • int ret
      • vector<bool> check -> 剪枝
    • DFS()设计void DFS(pos, n)
    • 剪枝
      • 之前用过的数字不再使用
      • 不符合情况的不填入
    • 回溯:每层递归返回时回溯
      请添加图片描述

3.代码实现

class Solution 
{int ret = 0;vector<bool> check;
public:int countArrangement(int n) {check.resize(n + 1, false);DFS(1, n);return ret;}void DFS(int pos, int n){if(pos == n + 1){ret++;return;}for(int i = 1; i <= n; i++){if(!check[i] && (i % pos == 0 || pos % i == 0)){check[i] = true;DFS(pos + 1, n);check[i] = false; // 回溯,恢复现场}}}
};

3.N 皇后

1.题目链接

  • N 皇后

2.算法原理详解

  • 本题可以学习二维数组判断行列、主副对角线是否放有数据

  • 思路:在每一行找合适的列放置皇后,即每次枚举都是枚举一行
    - DFS()设计:void DFS(row)

    • 决策树
      请添加图片描述
  • 如何剪枝?-> 当前这个位置,能否放上皇后?

    • 无脑四个循环判断行列、主副对角线 -> ×
    • 类似哈希表的策略,需要一定数学理解
      • 不需要剪枝,收递归限制
      • bool checkCol[n] -> 判断
        • 对应下标表示每列是否放置过皇后
      • bool checkDig1[2 * n] -> 主对角线
        • y = x + b -> y - x = b -> b可以唯一标识一个对角线
        • y - x + n = b + n -> 两边加上一个固有偏移量防止下标出现负数
      • bool checkDig2[2 * n] -> 副对角线
        • y = -x + b -> y + x = b -> b可以唯一标识一个对角线
        • 副对角线不需要固定偏移量,因为副对角线的纵截距都大于0
          请添加图片描述

3.代码实现

class Solution 
{int _n = 0;vector<bool> checkCol;vector<bool> checkDig1;vector<bool> checkDig2;vector<vector<string>> ret;vector<string> path;
public:vector<vector<string>> solveNQueens(int n) {_n = n;checkCol.resize(n, false);checkDig1.resize(2 * n, false);checkDig2.resize(2 * n, false);path.resize(n, string(n, '.'));DFS(0);return ret;}void DFS(int row){// 递归出口if(row == _n){ret.push_back(path);return;}// 对于每一行,枚举每一列for(int i = 0; i < _n; i++){// 剪枝if(!checkCol[i] && !checkDig1[row - i + _n] && !checkDig2[row + i]){checkCol[i] = checkDig1[row - i + _n] = checkDig2[row + i] = true;path[row][i] = 'Q';DFS(row + 1);checkCol[i] = checkDig1[row - i + _n] = checkDig2[row + i] = false; // 回溯path[row][i] = '.';}}}
};

相关文章:

[Algorithm][回溯][字母大小写全排列][优美的排列][N皇后]详细讲解

目录 1.字母大小写全排列1.题目链接2.算法原理详解3.代码实现 2.优美的排列1.题目链接2.算法原理详解3.代码实现 3.N 皇后1.题目链接2.算法原理详解3.代码实现 1.字母大小写全排列 1.题目链接 字母大小写全排列 2.算法原理详解 本题逻辑与子集大致相同 思路一&#xff1a;每…...

.NET_NLog

步骤 1. 添加依赖 ①Microsoft.Extensions.DependencyInjection ②NLog.Extensions.Logging&#xff08;或Microsoft.Extensions.Logging.___&#xff09; Tutorial NLog/NLog Wiki GitHub 2.添加nlog.config文件(默认名称, 可改为其他名称, 但需要另行配置) 文件的基础…...

Linux查看进程命令ps和top

Linux 是一种自由和开放源代码的操作系统&#xff0c;它的使用在全球范围内非常广泛。在 Linux 中&#xff0c;进程是操作系统中最重要的组成部分之一&#xff0c;它代表了正在运行的程序。了解如何查看正在运行的进程是非常重要的&#xff0c;因为它可以帮助你了解系统的运行状…...

深入解析Wireshark1:从捕获到分析,一网打尽数据包之旅

目录 1 认识 Wireshark 1.1 选择网卡界面 1.2 捕获数据包界面 1.3 常用按钮功能介绍 1.4 数据包列表信息 1.5 数据包详细信息 2 数据包案例分析 Frame: 物理层的数据帧概况 Ethernet II: 数据链路层以太网帧头部信息 Internet Protocol Version 4 (IPv4): 互联网层IP…...

C++语法|指向类成员(成员变量和成员方法)的指针及其相关应用场景

文章目录 1.基本语法指向成员变量的指针示例 指向成员函数的指针示例 注意事项 2.应用场景泛型编程和模板&#xff1a;通用成员访问打印函数回调机制和事件处理&#xff1a;基于简单GUI框架的事件处理 1.基本语法 指向类成员的指针是一种特殊的指针类型&#xff0c;用于指向类…...

【C语言】通讯录系统实现

目录 1、通讯录系统介绍 2、代码分装 3、代码实现步骤 3.1制作菜单函数以及游戏运行逻辑流程 3.2、封装人的信息PeoInfo以及通讯录Contact结构体类型 3.3、初始化通讯录InitContact函数 3.4、增加联系人AddContact函数 3.5、显示所有联系人ShowContact函数 3.6、删除联系人D…...

(delphi11最新学习资料) Object Pascal 学习笔记---第12章第1节 ( 类静态方法与Windows API回调)

12.1.4 类静态方法与Windows API回调 ​ 静态类方法没有隐藏的Self参数意味着静态类方法可以作为回调函数传递给操作系统&#xff08;例如&#xff0c;在Windows上&#xff09;。实际上&#xff0c;您可以声明一个具有stdcall调用约定的静态类方法&#xff0c;并将其用作直接的…...

第一个Rust程序

在安装好Rust以后&#xff0c;我们就可以编写程序了。 首先&#xff0c;我们执行下面的命令&#xff0c;尽量让你的rust版本和我的版本相同&#xff0c;或者比我的版本大。 zhangdapengzhangdapeng:~$ cargo --version cargo 1.78.0 (54d8815d0 2024-03-26) zhangdapengzhangd…...

【LInux】<基础IO> 文件操作 | 文件描述符 | 重定向

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前正在学习c和算法 ✈️专栏&#xff1a;Linux &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章有啥瑕疵&#xff0c;希望大佬指点一二 如果文章对…...

MySQL--增、删、改、查,

数据库的概述、发展、现状、历史、分类 MySQL关系型数据库、架构&#xff08;C/S&#xff09; window系统安装MySQL数据库 Linux系统【选学】 数据库对象——数据库&#xff08;database&#xff09; show、create、drop命令 数据库对象——表&#xff08;table&#xff…...

5.12学习总结

一.JAVA聊天室项目 文件发送 使用 Java Socket 实现聊天内容或文件的传输的原理如下&#xff1a; 服务器端启动&#xff1a;聊天室的服务器端在指定的端口上监听客户端的连接。它创建一个 ServerSocket 对象&#xff0c;并通过调用 accept() 方法等待客户端的连接请求。客户…...

ansible利用playbook 部署lamp架构

搭建参考&#xff1a;ansible批量运维管理-CSDN博客 定义ansible主机清单 [rootansible-server ~]# vim /etc/hosts 192.168.200.129 host01 192.168.200.130 host02 [rootansible-server ~]# vim /etc/ansible/hosts [webserver] host01 host02 在ansible端编写index.html…...

SPI通信(使用SPI读写W25Q64)

SPI通信协议 • SPI&#xff08;Serial Peripheral Interface&#xff09;是由Motorola公司开发的一种通用数据总线 • 四根通信线&#xff1a; SCLK:串行时钟线&#xff0c;用来提供时钟信号的。 MOSI:主机输出&#xff0c;从机输入 MISO:从机输出&#xff0c;主机输入 SS:…...

<sa8650>QCX Usecase 使用详解—拓扑图 XML 定义

<sa8650>QCX Usecase 使用详解—拓扑图 XML 定义 一 、前言二、拓扑图 XML 定义2.1 <Node, port, link>2.2 < XML prolog >2.3 < UsecaseDef >2.4 < Usecase>2.5 < Targets>2.5.1 < Target>2.5.2 < Range>2.6 < Pipeline>2.…...

使用C++11实现Golang的defer功能

本文主要用C11标准来实现Golang的defer功能。 背景 目前笔者的主力语言是Golang&#xff0c;其次是C&#xff0c;再次是JS、Delphi。在Golang工程中大量使用了defer关键字实现函数的延迟调用。如打开文件的出错处理。近来在C工程中遇到类似需求&#xff0c;在函数返回时进行某…...

前端之电力系统SVG图低代码

其实所有的图形都是由点&#xff0c;线&#xff0c;面组成的。点线面可以组成一个设备。下面就简单讲讲点线面是怎么画的吧 对于线&#xff0c;可以用path <g><path:d"M ${beginX},${beginY} L ${endX},${endY}":stroke-width"lineWidth":strok…...

括号生成[中等]

优质博文&#xff1a;IT-BLOG-CN 一、题目 数字n代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;["((()))","(()())","(())(…...

配置ubuntu的VNC时遇到报错_XSERVTransmkdir: Mode of /tmp/.X11-unix should be set to 1777

现在win11内嵌了ubuntu系统&#xff0c;我在根据打造基于 VNC 的 Ubuntu 20.04 的远程桌面 配置VNC server时&#xff0c;到了 vncserver :1 这一步&#xff0c;遇到报错&#xff1a; vncserver: /usr/bin/Xtigervnc did not start up, please look into /root/.vnc/xxxxx.:1.…...

openstack部署nova中出现的问题:

[rootcontroller nova]# su -s /bin/sh -c “nova-manage db sync” nova /usr/lib/python2.7/site-packages/pymysql/cursors.py:170: Warning: (1831, u’Duplicate index block_device_mapping_instance_uuid_virtual_name_device_name_idx. This is deprecated and will be…...

【OpenCV 基础知识 3】边缘检测

文章目录 cvCanny完整示例代码 cvCanny 这行代码使用OpenCV库中的 cvCanny 函数对灰度图像进行边缘检测。让我解释一下&#xff1a; cvCanny(gray, dst, 10, 100, 3);gray: 这是输入的灰度图像&#xff0c;即要进行边缘检测的图像。dst: 这是输出的边缘图像&#xff0c;即将结…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...