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

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;
}

解题思路:

  1. 初始化全局变量和棋盘表示
    • solutionsSize:用于记录所有可能解决方案的数量。
    • generateBoard函数:根据给定的queens数组(记录每行皇后的列位置),生成一个直观的棋盘表示。棋盘使用字符数组表示,其中'Q'表示皇后,'.'表示空位。
  2. 回溯算法
    • backtrack函数是核心的回溯函数,用于递归地尝试在棋盘上放置皇后,并检查是否满足不互相攻击的条件。
    • 参数解释:
      • solutions:用于存储所有有效的棋盘布局的指针数组。
      • queens:记录当前棋盘布局中每行皇后的列位置。
      • n:棋盘的大小,即N×N。
      • row:当前正在尝试放置皇后的行。
      • columns:一个布尔数组,用于记录哪些列已经被占用。
      • diagonals1diagonals2:两个数组,用于记录两个方向上的对角线是否已被占用。由于对角线的斜率可以是正或负,使用两个数组分别表示从左上到右下和从右上到左下的对角线。
  3. 回溯的具体步骤
    • 如果当前行row等于n,表示所有皇后都已成功放置,将当前棋盘布局添加到解决方案中。
    • 否则,尝试在当前行的每一列放置皇后,并检查该位置是否合法(即不在同一列、同一对角线):
      • 如果位置合法,更新queens数组、columns数组和两个对角线数组,然后递归地尝试在下一行放置皇后。
      • 如果递归返回后没有找到有效布局,回溯到当前位置,尝试下一列。
      • 在每次回溯时,需要将之前的状态恢复(即将皇后位置和相关数组标记清除)。
  4. 解决N皇后问题的主函数
    • solveNQueens函数是解决问题的入口点。
    • 初始化解决方案数组solutionsqueens数组、columns数组和两个对角线数组。
    • 调用backtrack函数开始尝试放置皇后。
    • 返回解决方案的数量solutionsSize和每个解决方案的大小(均为n),以及所有解决方案的指针数组。
  5. 内存管理
    • generateBoard函数中,为每个棋盘布局分配内存。
    • solveNQueens函数中,为解决方案数组和每个解决方案的大小数组分配内存。
    • 注意:代码中未显示释放分配的内存,实际使用时需要注意内存泄漏问题,应在不再需要时释放这些内存。

相关文章:

Leecode刷题C语言之N皇后

执行结果:通过 执行用时和内存消耗如下&#xff1a; 代码如下&#xff1a; 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技术加持下的社交体验

即时通讯作为互联网的重要应用之一&#xff0c;见证了中国互联网30年发展的辉煌历程。 它从最初的文字交流&#xff0c;发展到如今的语音、视频通话&#xff0c;甚至是虚拟现实社交&#xff0c;已经渗透到生活的社交、娱乐、商务等方方面面&#xff0c;成为现代社会不可或缺的一…...

repo仓库转移到自己本地的git服务器

前提条件&#xff1a;搭建好gitolite 以转移正点原子rk3568_linux工程为例子&#xff0c;将其转移到自己的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 关系数据…...

人工智能-深度学习-神经网络-激活函数

激活函数通过引入非线性来增强神经网络的表达能力&#xff0c;对于解决线性模型的局限性至关重要。由于反向传播算法(BP)用于更新网络参数&#xff0c;因此激活函数必须是可微的&#xff0c;也就是说能够求导的。 满足激活函数的条件 1.可微分&#xff0c;也就是可求导 激活函…...

vue3+ts+uniapp微信小程序顶部导航栏

这是colorui改的&#xff0c;不用就不用看啦 color-ui(https://docs.xzeu.com/#/) 新建component文件夹创建topNavigation.vue <template><view><view class"cu-custom" :style"height: CustomBar px"><view class"cu-bar…...

IAR中编译下载未下载问题

第一张图片是正常下载&#xff0c;第二张未正常下载。经过查看download选项发现 启用了 suppress download &#xff08;禁用下载)...

springboot(20)(删除文章分类。获取、更新、删除文章详细)(Validation分组校验)

目录 一、删除文章分类功能。 &#xff08;1&#xff09;接口文档。 1、请求路径、请求参数。 2、请求参数。 3、响应数据。 &#xff08;2&#xff09;实现思路与代码书写。 1、controller层。 2、service接口业务层。 3、serviceImpl实现类。 4、mapper层。 5、后端接口测试。…...

英语系统语法书面记载:高级语法 8 的状语从句

在英语高级语法中&#xff0c;状语从句是一种用来修饰动词、形容词、副词或整个句子的从句&#xff0c;它提供有关时间、地点、原因、条件、方式、让步等信息。状语从句通常由特定的连词引导。以下是常见的几种状语从句类型及其用法&#xff1a; 1. 时间状语从句 (Adverbial Cl…...

C语言:深入理解指针(1)

一.内存和地址 在讲内存和地址之前&#xff0c;我们想有个生活中的案例&#xff1a; 假设有一栋宿舍楼&#xff0c;把你放在楼里&#xff0c;楼上有100个房间&#xff0c;但是房间没有编号&#xff0c;你的一个朋友来找你玩&#xff0c;如果想找到你&#xff0c;就得挨个房子去…...

priority_queue--优先队列

一、认识优先队列 priority_queue&#xff08;优先队列&#xff09;是 C 标准模板库&#xff08;STL&#xff09;中的一个容器适配器。它的底层实现通常是用堆&#xff08;一般是二叉堆&#xff09;来实现的。优先队列中的元素按照一定的优先级顺序进行排列&#xff0c;在队首的…...

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 来记录此次操作&#xff1b;git reset 是把 HEAD 指针向前挪动一次&#xff0c;会减少一个 commit。 回退用 git revert 回退还是用 git reset&#xff0c;核心就一点&#xff1a; 是否需要记录这次回退。 如果需要记录这次回退&#xff0c…...

【docker】多阶段构建与基础构建,及企业案例展示

基础构建与多阶段构建对比 基础构建&#xff08;单阶段构建&#xff09; 在基础构建中&#xff0c;所有构建过程和最终的应用程序都在同一个镜像中进行&#xff0c;构建工具和最终应用程序都会在最终镜像中。 这样构建镜像时会包含所有的构建工具和依赖&#xff0c;因此最终镜…...

基于链表的基础笔试/面试题

1. 反转链表 问题描述&#xff1a;反转一个单向链表。 示例&#xff1a; 输入&#xff1a;1 → 2 → 3 → 4 → 5 输出&#xff1a;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}; % 获取第一列数据% 划分训练集和测试集&#xff0c;80% 训练&#xff0c;20% 测试 trainSize floor(0.8 * length(y)); trainData y(1:trainSize); testData y(trainSize1:end);% 创建时间序列…...

第八课 Unity编辑器创建的资源优化_特效篇(Particle System)详解

无论是CPU还是GPU&#xff0c;粒子系统对其的影响面都是不容小觑的。随着项目的重度化和3A化&#xff0c;玩家的口味变挑剔了、游戏玩法复杂度变高了、画面的特效表现变复杂了......所以我们还是更加谨慎地对待粒子系统。 特效&#xff08;Particle System&#xff09; 游戏效…...

Oracle对比表与表之间的结构

自己首先想到的就是,navicat有提供结构同步 但是有些时候情况不一样,比如我遇到的是连接不同,而且是互相同步,以最多的列的那个表为样 没有说一个固定的源 那么还可以通过导出表结构去另一个库中执行看是否报错,以此来判断结构的不同 但是我感觉有点儿麻烦 最后想到通过sql语…...

基于JSP+MySQL的网上招聘系统的设计与实现

摘要 在这样一个经济飞速发展的时代&#xff0c;人们的生存与生活问题已成为当代社会需要关注的一个焦点。对于一个刚刚 踏入社会的年轻人来说&#xff0c;他对就业市场和形势了解的不够详细&#xff0c;同时对自己的职业规划也很模糊&#xff0c;这就导致大量的 时间被花费在…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 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

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...