递归算法学习——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皇后问题,单词搜索
目录 编辑 一,N皇后问题 1.题意 2.解释 3.题目接口 4.解题思路及代码 二,单词搜索 1.题意 2.解释 3.题目接口 4.思路及代码 一,N皇后问题 1.题意 按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上…...
【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 模型、事件处理模式 一、服务器编程基本框架 虽然服务器程序种类繁多,但其基本框架都一样,不同之处在于逻辑处理。 二、五种 I/O 模型 阻塞/非阻塞、同步/异步(网络IO)_呵呵哒( ̄▽ ̄)&…...
mysql8-基于docker搭建主从同步
一、环境信息 系统版本:CentOS Linux release 7.9.2009 (Core) cat /etc/centos-release Docker版本:Docker version 20.10.6, build 370c289 docker --version Docker-compose版本:Docker Compose version v2.10.2 docker-compose --versio…...
智能水表远程控制系统:引领节水新时代
随着科技的不断发展,物联网技术逐渐融入到我们的日常生活中。其中,智能水表远程控制系统成为一项重要创新,对于提高水资源利用率、实现绿色节水具有重要意义。下面小编就来为大家介绍下智能水表远程控制系统吧! 一、智能水表远程控制系统定义…...
【FusionInsight 迁移】HBase从C50迁移到6.5.1(03)6.5.1上准备Loader
【FusionInsight 迁移】HBase从C50迁移到6.5.1(03)6.5.1上准备Loader HBase从C50迁移到6.5.1(03)6.5.1上准备Loader登录新集群FusionInsight 6.5.1的Manager准备Loader服务准备Loader Role准备Loader User HBase从C50迁移到6.5.1&…...
redis多线程操作
今天更新一个redis多线程操作, 可直接搬运 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.拉普拉斯图像金字塔原理 拉普拉斯图像金字塔是一种多尺度图像表示方法,通过对高斯金字塔进行差分运算得到。它能够提供图像在不同尺度上的细节信息,常用于图像处理任务如图像增强、边缘检测等。 下面是拉普拉斯图像金字塔的原理和步骤: 构…...
OpenCL编程指南-10.2使用C++包装器API的矢量相加示例
选择OpenCL平台并创建一个上下文 建立OpenCL的第一步是选择一个平台。第2章介绍过,OpenCL使用了ICD模型,其中可以有多个OpenCL实现在一个系统上并存。类似于HelloWorld示例,这个矢量相加程序展示了选择OpenCL平台的一种最简单的方法…...
mysql数据库,字符串使用双引号““导致报错,使用单引号‘‘不报错,Unknown column ‘user-test‘ in ‘where clause‘
文章目录 一、完整报错二、报错数据三、报错原因四、解决方式1、更改执行sql2、更改sql数据校验模式(改为默认校验) 一、完整报错 > 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最新报道指出,尽管美方在《通胀削减法案》(IRA)的补贴中排除了中国,但中国企业正通过多种方式积极应对美国在半导体和电动汽车电池领域的封锁,这包括建立合资企业、设立生产基地以及开展技…...
动手实践:从栈帧看字节码是如何在 JVM 中进行流转的
Java全能学习面试指南:https://www.javaxiaobear.cn/ 前面我们提到,类的初始化发生在类加载阶段,那对象都有哪些创建方式呢?除了我们常用的 new,还有下面这些方式: 使用 Class 的 newInstance 方法。使用…...
PEX装机
目录 一、PXE是什么? 二、PXE的组件: 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 概述 论文:A literature review on one‑class classification and its potential applications in big data 发表:Journal of Big Data 在严重不平衡的数据集中,使用传统的二分类或多分类通常会导致对具有大量实例的类的偏见。在这种情况…...
下单时如何保证数据一致性?
原创 哪吒 哪吒编程 2023-09-07 08:03 发表于辽宁 收录于合集#Redis11个 (给哪吒编程加星标,提高Java技能) 大家好,我是哪吒。 在前几篇文章中,提到了Redis实现排行榜、Redis数据缓存策略,让我们对Redis…...
【C++ Core Guidelines解析】深入理解现代C++的特性和原理
文章目录 👨⚖️《C Core Guidelines解析》的主要观点👨🏫《C Core Guidelines解析》的主要内容👨💻作者介绍 🌸🌸🌸🌷🌷🌷💐&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获得免费的流量,也就是SEO流量,但是在做SEO的过程中,总会面临这样或那样的问题。米贸搜谷歌推广将这些问题总结如下: 既然SEO看起来似乎很难,但还是有很多电商公司愿意投资SEO&#x…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...
