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的网上招聘系统的设计与实现
摘要 在这样一个经济飞速发展的时代,人们的生存与生活问题已成为当代社会需要关注的一个焦点。对于一个刚刚 踏入社会的年轻人来说,他对就业市场和形势了解的不够详细,同时对自己的职业规划也很模糊,这就导致大量的 时间被花费在…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
OCR MLLM Evaluation
为什么需要评测体系?——背景与矛盾 能干的事: 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。干不了的事: 碰到复杂表格(合并单元…...
Vue 3 + WebSocket 实战:公司通知实时推送功能详解
📢 Vue 3 WebSocket 实战:公司通知实时推送功能详解 📌 收藏 点赞 关注,项目中要用到推送功能时就不怕找不到了! 实时通知是企业系统中常见的功能,比如:管理员发布通知后,所有用户…...