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

递归算法学习——N皇后问题,单词搜索

目录

​编辑

一,N皇后问题

1.题意

2.解释

3.题目接口

4.解题思路及代码

二,单词搜索

1.题意

2.解释

3.题目接口

4.思路及代码


一,N皇后问题

1.题意

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

2.解释

这道题其实就是在下国际象棋。国际象棋的皇后是可以走上下左右和斜对角六个方向的。所以在放置皇后时我们就要考虑一下在那个位置放入一个皇后我们才不会被攻击。直到将所有能防止皇后的位置放好以后便返回放好皇后以后的棋盘。

3.题目接口

class Solution {
public:vector<vector<string>> solveNQueens(int n) {}
};

4.解题思路及代码

class Solution {
public:vector<vector<string>>ret;//存结果vector<string>board;//开棋盘bool rowCheak[10];bool colCheak[10];bool digit1[20];bool digit2[20];//因为对于一条对角线有row = col+b->row-col = b。但是b在[-n,n]。//为了将负数下标去掉所以在左右两边都加上n:row-col+n = b+n->[0,2*n]//所以diagonal要开20个空间int n;vector<vector<string>> solveNQueens(int _n) {n = _n;board.resize(n);for(int i = 0;i<n;i++){board[i].append(n,'.');}dfs(0);return ret;} void dfs(int row){if(row == n){ret.push_back(board);return;}for(int col = 0;col<n;col++){if(board[row][col]=='.'&&!rowCheak[row]&&!colCheak[col]&&!digit1[row-col+n]&&!digit2[row+col]){board[row][col] = 'Q';rowCheak[row]=colCheak[col]=digit1[row-col+n] = digit2[row+col] = true;dfs(row+1);board[row][col] = '.';rowCheak[row]=colCheak[col]=digit1[row-col+n] = digit2[row+col] = false;}}}
};

对于这道题,采用的便是类似于哈希表的解决方法。

1.首先我们得找四个布尔类型的数组:rowCheak,colCheak,digit1,digit2。这四个布尔类型的数组分别标记的是行,列,左对角线,右对角线。

2.然后便是递归的设计了,我们可以采用一个一个的试的方法,但是这样效率太低了。所以我们便采用一行一行试的方法来设计递归函数。

 dfs(0);

首先从第0行开始。每次遍历一行,每次在dfs函数里面遍历每一行的每一列。当对应行列下标的位置不是'Q'并且这一个格子的行,列,对角线都没有被使用过便可以插入Q。然后再遍历下一行,假设这一行填下的皇后会导致得不到结果便要回溯处理。

3.当row越界的时候说明我们的皇后已经填完了,在这个时候便可以返回了。

二,单词搜索

1.题意

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

2.解释

这一道题让我们做的便是在给定一个m*n大小的棋盘并且给定一个单词word的情况下让我们去在这个棋盘里面找到这个单词的每一个字母。并且这个单词的每一个相邻字母在棋盘中还是相邻的。

3.题目接口

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {}
};

4.思路及代码

1.第一种解法:

class Solution {
public:vector<vector<bool>>used;int m,n;bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();used.resize(m);for(int i = 0;i<m;i++){used[i].resize(n);}for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){     if(dfs(board,i,j,word,0)) return true;//df函数只有在将word的全部字母找到以后才能返回true。}}return false;//全部遍历完了还没有结果便返回false} bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos){if(i<0||i>=m||j<0||j>=n||used[i][j]||board[i][j]!=word[pos]) //答案不对的情况{return false;}if(pos == word.size()-1)//当最后一个字母也被匹配到了便可以返回true{return true;}used[i][j] = true;//使用过了便标记一下bool res = dfs(board,i,j-1,word,pos+1)||dfs(board,i,j+1,word,pos+1)||dfs(board,i-1,j,word,pos+1)||dfs(board,i+1,j,word,pos+1);//在这个位置的上下左右寻找used[i][j] = false;//res可能是false所以要恢复现场调整上一层的寻找的下标return res;}
};

2.第二种解法

class Solution {
public:vector<vector<bool>>used;int m,n;bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();used.resize(m);for(int i = 0;i<m;i++){used[i].resize(n);}for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){     if(board[i][j] == word[0]){used[i][j] =true;if(dfs(board,i,j,word,1)) return true;used[i][j] = false;}}}return false;} bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos){if(pos == word.size()){return true;}int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};//用数组和for循环来表示上下左右寻找for(int k =0;k<4;k++){int x = i+dx[k],y = j+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&board[x][y] ==word[pos]&&!used[x][y])//只统计对的情况{used[x][y] = true;if(dfs(board,x,y,word,pos+1)) return true;used[x][y] = false;}}return false;}
};

相关文章:

递归算法学习——N皇后问题,单词搜索

目录 ​编辑 一&#xff0c;N皇后问题 1.题意 2.解释 3.题目接口 4.解题思路及代码 二&#xff0c;单词搜索 1.题意 2.解释 3.题目接口 4.思路及代码 一&#xff0c;N皇后问题 1.题意 按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上…...

【SpringBoot】mockito+junit 单元测试

1.POM 引入以下依赖 <dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.13.2</version><scope>test</scope></dependency><dependency><groupId>org.springframework.b…...

webserver 同步 I/O 模拟 Proactor 模式的工作流程

服务器基本框架、I/O 模型、事件处理模式 一、服务器编程基本框架 虽然服务器程序种类繁多&#xff0c;但其基本框架都一样&#xff0c;不同之处在于逻辑处理。 二、五种 I/O 模型 阻塞/非阻塞、同步/异步&#xff08;网络IO&#xff09;_呵呵哒(&#xffe3;▽&#xffe3;)&…...

mysql8-基于docker搭建主从同步

一、环境信息 系统版本&#xff1a;CentOS Linux release 7.9.2009 (Core) cat /etc/centos-release Docker版本&#xff1a;Docker version 20.10.6, build 370c289 docker --version Docker-compose版本&#xff1a;Docker Compose version v2.10.2 docker-compose --versio…...

智能水表远程控制系统:引领节水新时代

随着科技的不断发展&#xff0c;物联网技术逐渐融入到我们的日常生活中。其中&#xff0c;智能水表远程控制系统成为一项重要创新&#xff0c;对于提高水资源利用率、实现绿色节水具有重要意义。下面小编就来为大家介绍下智能水表远程控制系统吧! 一、智能水表远程控制系统定义…...

【FusionInsight 迁移】HBase从C50迁移到6.5.1(03)6.5.1上准备Loader

【FusionInsight 迁移】HBase从C50迁移到6.5.1&#xff08;03&#xff09;6.5.1上准备Loader HBase从C50迁移到6.5.1&#xff08;03&#xff09;6.5.1上准备Loader登录新集群FusionInsight 6.5.1的Manager准备Loader服务准备Loader Role准备Loader User HBase从C50迁移到6.5.1&…...

redis多线程操作

今天更新一个redis多线程操作&#xff0c; 可直接搬运 import redis, os, threading, queue import pandas as pd# 创建一个任务队列 task_queue queue.Queue()def read_excel(folder_path):total_list []for filepath, dirnames, filenames in os.walk(folder_path):for fi…...

OpenCV(十七):拉普拉斯图像金字塔

1.拉普拉斯图像金字塔原理 拉普拉斯图像金字塔是一种多尺度图像表示方法&#xff0c;通过对高斯金字塔进行差分运算得到。它能够提供图像在不同尺度上的细节信息&#xff0c;常用于图像处理任务如图像增强、边缘检测等。 下面是拉普拉斯图像金字塔的原理和步骤&#xff1a; 构…...

OpenCL编程指南-10.2使用C++包装器API的矢量相加示例

选择OpenCL平台并创建一个上下文 建立OpenCL的第一步是选择一个平台。第2章介绍过&#xff0c;OpenCL使用了ICD模型&#xff0c;其中可以有多个OpenCL实现在一个系统上并存。类似于HelloWorld示例&#xff0c;这个矢量相加程序展示了选择OpenCL平台的一种最简单的方法&#xf…...

mysql数据库,字符串使用双引号““导致报错,使用单引号‘‘不报错,Unknown column ‘user-test‘ in ‘where clause‘

文章目录 一、完整报错二、报错数据三、报错原因四、解决方式1、更改执行sql2、更改sql数据校验模式&#xff08;改为默认校验&#xff09; 一、完整报错 > 1054 - Unknown column user-test in where clause二、报错数据 SELECT * FROM config_info WHERE config_info.da…...

[华为云云服务器评测] 华为云耀云服务器 Java、node环境配置

系列文章目录 第一章 [linux实战] 华为云耀云服务器L实例 Java、node环境配置 文章目录 系列文章目录前言一、任务拆解二、修改密码三、配置安全规则四、远程登录并更新apt五、安装、配置JDK环境5.1、安装openjdk,选择8版本5.2、检查jdk配置 六、安装、配置git6.1、安装git6.2…...

中企绕道突破封锁,防不胜防 | 百能云芯

韩国的财经媒体Business Korea最新报道指出&#xff0c;尽管美方在《通胀削减法案》&#xff08;IRA&#xff09;的补贴中排除了中国&#xff0c;但中国企业正通过多种方式积极应对美国在半导体和电动汽车电池领域的封锁&#xff0c;这包括建立合资企业、设立生产基地以及开展技…...

动手实践:从栈帧看字节码是如何在 JVM 中进行流转的

Java全能学习面试指南&#xff1a;https://www.javaxiaobear.cn/ 前面我们提到&#xff0c;类的初始化发生在类加载阶段&#xff0c;那对象都有哪些创建方式呢&#xff1f;除了我们常用的 new&#xff0c;还有下面这些方式&#xff1a; 使用 Class 的 newInstance 方法。使用…...

PEX装机

目录 一、PXE是什么&#xff1f; 二、PXE的组件&#xff1a; vsftpd/httpd/nfs tftp dhcp 三、配置vsftpd 四、配置tftp 1.安装tftp-server 2.启动tftp 五、准备pxelinx.0文件、引导文件、内核文件 1.准备pxelinux.0文件 2.准备引导文件、内核文件 六、配置dhcp …...

异地远程访问内网BUG管理系统【Cpolar内网穿透】

文章目录 前言1. 本地安装配置BUG管理系统2. 内网穿透2.1 安装cpolar内网穿透2.2 创建隧道映射本地服务3. 测试公网远程访问4. 配置固定二级子域名4.1 保留一个二级子域名5.1 配置二级子域名6. 使用固定二级子域名远程 前言 BUG管理软件,作为软件测试工程师的必备工具之一。在…...

论文笔记:一分类及其在大数据中的潜在应用综述

0 概述 论文&#xff1a;A literature review on one‑class classification and its potential applications in big data 发表&#xff1a;Journal of Big Data 在严重不平衡的数据集中&#xff0c;使用传统的二分类或多分类通常会导致对具有大量实例的类的偏见。在这种情况…...

下单时如何保证数据一致性?

原创 哪吒 哪吒编程 2023-09-07 08:03 发表于辽宁 收录于合集#Redis11个 &#xff08;给哪吒编程加星标&#xff0c;提高Java技能&#xff09; 大家好&#xff0c;我是哪吒。 在前几篇文章中&#xff0c;提到了Redis实现排行榜、Redis数据缓存策略&#xff0c;让我们对Redis…...

【C++ Core Guidelines解析】深入理解现代C++的特性和原理

文章目录 &#x1f468;‍⚖️《C Core Guidelines解析》的主要观点&#x1f468;‍&#x1f3eb;《C Core Guidelines解析》的主要内容&#x1f468;‍&#x1f4bb;作者介绍 &#x1f338;&#x1f338;&#x1f338;&#x1f337;&#x1f337;&#x1f337;&#x1f490;&a…...

Go语言高阶:Reflection反射与Files操作 详细示例教程

目录标题 一、Reflection反射1. What is reflection? 什么是反射2. Inspect a variable and find its type 检查变量并找到它的类型3. Reflect.Type and reflect.Value 反射类型和值4. Reflect.Kind 查看底层种类5. NumField() and Field() methods 字段数量和索引值方法6. In…...

谷歌seo技术流

很多外贸企业和独立站都想从Google获得免费的流量&#xff0c;也就是SEO流量&#xff0c;但是在做SEO的过程中&#xff0c;总会面临这样或那样的问题。米贸搜谷歌推广将这些问题总结如下&#xff1a; 既然SEO看起来似乎很难&#xff0c;但还是有很多电商公司愿意投资SEO&#x…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑

精益数据分析&#xff08;98/126&#xff09;&#xff1a;电商转化率优化与网站性能的底层逻辑 在电子商务领域&#xff0c;转化率与网站性能是决定商业成败的核心指标。今天&#xff0c;我们将深入解析不同类型电商平台的转化率基准&#xff0c;探讨页面加载速度对用户行为的…...