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的网上招聘系统的设计与实现
摘要 在这样一个经济飞速发展的时代,人们的生存与生活问题已成为当代社会需要关注的一个焦点。对于一个刚刚 踏入社会的年轻人来说,他对就业市场和形势了解的不够详细,同时对自己的职业规划也很模糊,这就导致大量的 时间被花费在…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
电脑桌面太单调,用Python写一个桌面小宠物应用。
下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡,可以响应鼠标点击,并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...
ArcGIS Pro+ArcGIS给你的地图加上北回归线!
今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等,设置经线、纬线都以10间隔显示。 2、需要插入背会归线…...
麒麟系统使用-进行.NET开发
文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的,如果需要进行.NET开发,则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET,所以要进…...
