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的网上招聘系统的设计与实现
摘要 在这样一个经济飞速发展的时代,人们的生存与生活问题已成为当代社会需要关注的一个焦点。对于一个刚刚 踏入社会的年轻人来说,他对就业市场和形势了解的不够详细,同时对自己的职业规划也很模糊,这就导致大量的 时间被花费在…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
