Leecode刷题C语言之N皇后
执行结果:通过
执行用时和内存消耗如下:


代码如下:
int solutionsSize;char** generateBoard(int* queens, int n) {char** board = (char**)malloc(sizeof(char*) * n);for (int i = 0; i < n; i++) {board[i] = (char*)malloc(sizeof(char) * (n + 1));for (int j = 0; j < n; j++) board[i][j] = '.';board[i][queens[i]] = 'Q', board[i][n] = 0;}return board;
}void backtrack(char*** solutions, int* queens, int n, int row, int* columns, int* diagonals1, int* diagonals2) {if (row == n) {char** board = generateBoard(queens, n);solutions[solutionsSize++] = board;} else {for (int i = 0; i < n; i++) {if (columns[i]) {continue;}int diagonal1 = row - i + n - 1;if (diagonals1[diagonal1]) {continue;}int diagonal2 = row + i;if (diagonals2[diagonal2]) {continue;}queens[row] = i;columns[i] = true;diagonals1[diagonal1] = true;diagonals2[diagonal2] = true;backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);queens[row] = -1;columns[i] = false;diagonals1[diagonal1] = false;diagonals2[diagonal2] = false;}}
}char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {char*** solutions = malloc(sizeof(char**) * 501);solutionsSize = 0;int queens[n];int columns[n];int diagonals1[n + n];int diagonals2[n + n];memset(queens, -1, sizeof(queens));memset(columns, 0, sizeof(columns));memset(diagonals1, 0, sizeof(diagonals1));memset(diagonals2, 0, sizeof(diagonals2));backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);*returnSize = solutionsSize;*returnColumnSizes = malloc(sizeof(int*) * solutionsSize);for (int i = 0; i < solutionsSize; i++) {(*returnColumnSizes)[i] = n;}return solutions;
}
解题思路:
- 初始化全局变量和棋盘表示:
solutionsSize:用于记录所有可能解决方案的数量。generateBoard函数:根据给定的queens数组(记录每行皇后的列位置),生成一个直观的棋盘表示。棋盘使用字符数组表示,其中'Q'表示皇后,'.'表示空位。
- 回溯算法:
backtrack函数是核心的回溯函数,用于递归地尝试在棋盘上放置皇后,并检查是否满足不互相攻击的条件。- 参数解释:
solutions:用于存储所有有效的棋盘布局的指针数组。queens:记录当前棋盘布局中每行皇后的列位置。n:棋盘的大小,即N×N。row:当前正在尝试放置皇后的行。columns:一个布尔数组,用于记录哪些列已经被占用。diagonals1和diagonals2:两个数组,用于记录两个方向上的对角线是否已被占用。由于对角线的斜率可以是正或负,使用两个数组分别表示从左上到右下和从右上到左下的对角线。
- 回溯的具体步骤:
- 如果当前行
row等于n,表示所有皇后都已成功放置,将当前棋盘布局添加到解决方案中。 - 否则,尝试在当前行的每一列放置皇后,并检查该位置是否合法(即不在同一列、同一对角线):
- 如果位置合法,更新
queens数组、columns数组和两个对角线数组,然后递归地尝试在下一行放置皇后。 - 如果递归返回后没有找到有效布局,回溯到当前位置,尝试下一列。
- 在每次回溯时,需要将之前的状态恢复(即将皇后位置和相关数组标记清除)。
- 如果位置合法,更新
- 如果当前行
- 解决N皇后问题的主函数:
solveNQueens函数是解决问题的入口点。- 初始化解决方案数组
solutions、queens数组、columns数组和两个对角线数组。 - 调用
backtrack函数开始尝试放置皇后。 - 返回解决方案的数量
solutionsSize和每个解决方案的大小(均为n),以及所有解决方案的指针数组。
- 内存管理:
- 在
generateBoard函数中,为每个棋盘布局分配内存。 - 在
solveNQueens函数中,为解决方案数组和每个解决方案的大小数组分配内存。 - 注意:代码中未显示释放分配的内存,实际使用时需要注意内存泄漏问题,应在不再需要时释放这些内存。
- 在
相关文章:
Leecode刷题C语言之N皇后
执行结果:通过 执行用时和内存消耗如下: 代码如下: int solutionsSize;char** generateBoard(int* queens, int n) {char** board (char**)malloc(sizeof(char*) * n);for (int i 0; i < n; i) {board[i] (char*)malloc(sizeof(char) * (n 1))…...
即时通讯| IM+RTC在AI技术加持下的社交体验
即时通讯作为互联网的重要应用之一,见证了中国互联网30年发展的辉煌历程。 它从最初的文字交流,发展到如今的语音、视频通话,甚至是虚拟现实社交,已经渗透到生活的社交、娱乐、商务等方方面面,成为现代社会不可或缺的一…...
repo仓库转移到自己本地的git服务器
前提条件:搭建好gitolite 以转移正点原子rk3568_linux工程为例子,将其转移到自己的git服务器。 获取完整repo仓库 将正点原子epo仓库sync出来 evanevan-X99:~/SRC/atk$ .repo/repo/repo sync -l -j10 evanevan-X99:~/SRC/atk$ .repo/repo/repo list -n…...
微服务即时通讯系统的实现(服务端)----(2)
目录 1. 语音识别子服务的实现1.1 功能设计1.2 模块划分1.3 模块功能示意图1.4 接口的实现 2. 文件存储子服务的实现2.1 功能设计2.2 模块划分2.3 模块功能示意图2.4 接口的实现 3. 用户管理子服务的实现3.1 功能设计3.2 模块划分3.3 功能模块示意图3.4 数据管理3.4.1 关系数据…...
人工智能-深度学习-神经网络-激活函数
激活函数通过引入非线性来增强神经网络的表达能力,对于解决线性模型的局限性至关重要。由于反向传播算法(BP)用于更新网络参数,因此激活函数必须是可微的,也就是说能够求导的。 满足激活函数的条件 1.可微分,也就是可求导 激活函…...
vue3+ts+uniapp微信小程序顶部导航栏
这是colorui改的,不用就不用看啦 color-ui(https://docs.xzeu.com/#/) 新建component文件夹创建topNavigation.vue <template><view><view class"cu-custom" :style"height: CustomBar px"><view class"cu-bar…...
IAR中编译下载未下载问题
第一张图片是正常下载,第二张未正常下载。经过查看download选项发现 启用了 suppress download (禁用下载)...
springboot(20)(删除文章分类。获取、更新、删除文章详细)(Validation分组校验)
目录 一、删除文章分类功能。 (1)接口文档。 1、请求路径、请求参数。 2、请求参数。 3、响应数据。 (2)实现思路与代码书写。 1、controller层。 2、service接口业务层。 3、serviceImpl实现类。 4、mapper层。 5、后端接口测试。…...
英语系统语法书面记载:高级语法 8 的状语从句
在英语高级语法中,状语从句是一种用来修饰动词、形容词、副词或整个句子的从句,它提供有关时间、地点、原因、条件、方式、让步等信息。状语从句通常由特定的连词引导。以下是常见的几种状语从句类型及其用法: 1. 时间状语从句 (Adverbial Cl…...
C语言:深入理解指针(1)
一.内存和地址 在讲内存和地址之前,我们想有个生活中的案例: 假设有一栋宿舍楼,把你放在楼里,楼上有100个房间,但是房间没有编号,你的一个朋友来找你玩,如果想找到你,就得挨个房子去…...
priority_queue--优先队列
一、认识优先队列 priority_queue(优先队列)是 C 标准模板库(STL)中的一个容器适配器。它的底层实现通常是用堆(一般是二叉堆)来实现的。优先队列中的元素按照一定的优先级顺序进行排列,在队首的…...
Paper -- 建筑物高度估计 -- 基于深度学习、图像处理和自动地理空间分析的街景图像建筑高度估算
论文题目: Building height estimation from street-view imagery using deep learning, image processing and automated geospatial analysis 中文题目: 基于深度学习、图像处理和自动地理空间分析的街景图像建筑高度估算 作者: Ala’a Al-Habashna, Ryan Murdoch 作者单位: …...
开发一套ERP 第八弹 RUst 插入数据
更全面的报错,方便检查错误在哪里,现代高级语言越来越智能 还是得看下原文档怎么操作的 src 目录为crate 的根目录 想在crate 中模块相互引入需要在 main 中声明,各个模块,然后才能在各个模块中相互引入和使用 原始工程引入,避免直接使用 lib.rs 回合cargo 中的一些 工程管理出…...
回退用 git revert 还是 git reset?
git revert 会生成一个新的 commit 来记录此次操作;git reset 是把 HEAD 指针向前挪动一次,会减少一个 commit。 回退用 git revert 回退还是用 git reset,核心就一点: 是否需要记录这次回退。 如果需要记录这次回退,…...
【docker】多阶段构建与基础构建,及企业案例展示
基础构建与多阶段构建对比 基础构建(单阶段构建) 在基础构建中,所有构建过程和最终的应用程序都在同一个镜像中进行,构建工具和最终应用程序都会在最终镜像中。 这样构建镜像时会包含所有的构建工具和依赖,因此最终镜…...
基于链表的基础笔试/面试题
1. 反转链表 问题描述:反转一个单向链表。 示例: 输入:1 → 2 → 3 → 4 → 5 输出:5 → 4 → 3 → 2 → 1 class ListNode {int val;ListNode next;ListNode(int x) {val x;} }public class LinkedList {public ListNode …...
SARIMA 模型Matlab代码
% 导入数据 data readtable(data.xlsx); % 假设数据在第一列 y data{:, 1}; % 获取第一列数据% 划分训练集和测试集,80% 训练,20% 测试 trainSize floor(0.8 * length(y)); trainData y(1:trainSize); testData y(trainSize1:end);% 创建时间序列…...
第八课 Unity编辑器创建的资源优化_特效篇(Particle System)详解
无论是CPU还是GPU,粒子系统对其的影响面都是不容小觑的。随着项目的重度化和3A化,玩家的口味变挑剔了、游戏玩法复杂度变高了、画面的特效表现变复杂了......所以我们还是更加谨慎地对待粒子系统。 特效(Particle System) 游戏效…...
Oracle对比表与表之间的结构
自己首先想到的就是,navicat有提供结构同步 但是有些时候情况不一样,比如我遇到的是连接不同,而且是互相同步,以最多的列的那个表为样 没有说一个固定的源 那么还可以通过导出表结构去另一个库中执行看是否报错,以此来判断结构的不同 但是我感觉有点儿麻烦 最后想到通过sql语…...
基于JSP+MySQL的网上招聘系统的设计与实现
摘要 在这样一个经济飞速发展的时代,人们的生存与生活问题已成为当代社会需要关注的一个焦点。对于一个刚刚 踏入社会的年轻人来说,他对就业市场和形势了解的不够详细,同时对自己的职业规划也很模糊,这就导致大量的 时间被花费在…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
高防服务器价格高原因分析
高防服务器的价格较高,主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因: 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器,因此…...
