力扣热门算法题 52. N 皇后 II,53. 最大子数组和,54. 螺旋矩阵

52. N 皇后 II,53. 最大子数组和,54. 螺旋矩阵,每题做详细思路梳理,配套Python&Java双语代码, 2024.03.20 可通过leetcode所有测试用例。

目录

52. N 皇后 II

解题思路

完整代码

Python

Java

53. 最大子数组和

解题思路

完整代码

Python

Java

54. 螺旋矩阵

解题思路

完整代码

Python

Java


52. N 皇后 II

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。

示例 1:

输入:n = 4
输出:2
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:1

提示:

  • 1 <= n <= 9

解题思路

        可以使用回溯法,类似于解决 n 皇后问题摆放方案的方法,但这次我们只需要计算不同解决方案的数量。关键点在于合理地放置皇后,以避免她们相互攻击。

  1. 初始化数据结构:使用数组或其他数据结构来标记哪些列、对角线(左上到右下和右上到左下)已经被占用。

  2. 递归回溯:从第一行开始,尝试在每一列放置皇后。对于放置在 (row, col) 的皇后,需要标记第 col 列、(row + col) 的左上到右下对角线和 (row - col) 的右上到左下对角线为占用状态。

  3. 检查冲突:在尝试放置每个皇后之前,检查当前列和两个对角线是否已经被其他皇后占用。

  4. 统计解决方案数量:每当成功放置了 n 个皇后(即达到了最后一行的下一行),就将解决方案数量加一。

  5. 回溯:尝试当前行的下一列或回到上一行,撤销当前放置的皇后,并尝试新的位置。

完整代码

Python
class Solution:def totalNQueens(self, n: int) -> int:def backtrack(row = 0, hills = 0, next_row = 0, dales = 0, count = 0):if row == n:  # 如果已经放置了 n 个皇后count += 1  # 解决方案数量加一else:# 在所有可用的列中free_columns = columns & ~(hills | next_row | dales)while free_columns:# 选择最右侧的可用列curr_column = - free_columns & free_columns# 放置皇后并去掉当前列free_columns ^= curr_columncount = backtrack(row + 1, (hills | curr_column) << 1, next_row | curr_column, (dales | curr_column) >> 1, count)return count# 初始化可用列columns = (1 << n) - 1return backtrack()
Java
public class Solution {private int size;private int count;private void solve(int row, int ld, int rd) {if (row == size) {count++;return;}int pos = size & ~(row | ld | rd);while (pos != 0) {int p = pos & -pos;pos -= p;  // 放置皇后并移除当前位置solve(row | p, (ld | p) << 1, (rd | p) >> 1);}}public int totalNQueens(int n) {count = 0;size = (1 << n) - 1;solve(0, 0, 0);return count;}public static void main(String[] args) {Solution solution = new Solution();int n = 4;System.out.println(solution.totalNQueens(n));}
}

53. 最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组

是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

解题思路

        我们可以使用一个称为“Kadane算法”的高效方法。Kadane算法通过一次遍历数组来找到最大的连续子数组和。该算法的基本思想是维护一个局部最大和一个全局最大变量,随着数组的遍历,更新这两个变量。

  1. 初始化两个变量currentMax 用于追踪当前位置的最大子数组和,globalMax 用于记录迄今为止找到的最大子数组和。初始时,两个变量都设置为数组的第一个元素。

  2. 遍历数组:从数组的第二个元素开始遍历。

  3. 更新 currentMax:对于每个元素,更新 currentMax 为当前元素本身和当前元素加上之前的 currentMax 之间的较大者。这一步骤确保了 currentMax 总是维护着到当前位置为止的最大子数组和。

    currentMax = max(nums[i], currentMax + nums[i])

  4. 更新 globalMax:如果更新后的 currentMax 大于 globalMax,则更新 globalMaxcurrentMax 的值。这确保了 globalMax 总是全局最大子数组和。

    globalMax = max(globalMax, currentMax)

  5. 返回结果:遍历完成后,globalMax 将包含整个数组的最大子数组和。

完整代码

Python
class Solution:def maxSubArray(self, nums: List[int]) -> int:currentMax = globalMax = nums[0]for num in nums[1:]:currentMax = max(num, currentMax + num)globalMax = max(globalMax, currentMax)return globalMax
Java
public class Solution {public int maxSubArray(int[] nums) {int currentMax = nums[0];int globalMax = nums[0];for (int i = 1; i < nums.length; i++) {currentMax = Math.max(nums[i], currentMax + nums[i]);globalMax = Math.max(globalMax, currentMax);}return globalMax;}public static void main(String[] args) {Solution solution = new Solution();int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(solution.maxSubArray(nums));}
}

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

解题思路

        要按顺时针螺旋顺序返回矩阵中的所有元素,我们可以模拟整个过程,遵循从左到右、从上到下、从右到左、从下到上的顺序,每完成一圈后,缩小遍历的范围。

  1. 初始化四个方向的边界topbottomleftright 分别代表了上下左右四个方向的边界。初始化时,top = 0bottom = m-1left = 0right = n-1

  2. 按顺序遍历矩阵:按照顺时针方向遍历矩阵的外围,然后逐层向内缩小范围,直到遍历完所有元素。具体步骤如下:

    a. 从左到右遍历上层元素(top 行),遍历完成后 top++

    b. 从上到下遍历右侧元素(right 列),遍历完成后 right--

    c. 如果 top <= bottom,从右到左遍历底层元素(bottom 行),遍历完成后 bottom--

    d. 如果 left <= right,从下到上遍历左侧元素(left 列),遍历完成后 left++

  3. 收集元素:在每个方向上遍历时,将遍历到的元素添加到结果列表中。

  4. 返回结果:当上述遍历完成后,结果列表中将包含按顺时针螺旋顺序的所有矩阵元素。

完整代码

Python
class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:result = []if not matrix:return resulttop, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1while left <= right and top <= bottom:# 从左到右for i in range(left, right + 1):result.append(matrix[top][i])top += 1# 从上到下for i in range(top, bottom + 1):result.append(matrix[i][right])right -= 1# 从右到左if top <= bottom:for i in range(right, left - 1, -1):result.append(matrix[bottom][i])bottom -= 1# 从下到上if left <= right:for i in range(bottom, top - 1, -1):result.append(matrix[i][left])left += 1return result
Java
public class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> result = new ArrayList<>();if (matrix == null || matrix.length == 0) return result;int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;while (left <= right && top <= bottom) {// 从左到右for (int i = left; i <= right; i++) {result.add(matrix[top][i]);}top++;// 从上到下for (int i = top; i <= bottom; i++) {result.add(matrix[i][right]);}right--;// 从右到左if (top <= bottom) {for (int i = right; i >= left; i--) {result.add(matrix[bottom][i]);}bottom--;}// 从下到上if (left <= right) {for (int i = bottom; i >= top; i--) {result.add(matrix[i][left]);}left++;}}return result;}public static void main(String[] args) {Solution solution = new Solution();int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};System.out.println(solution.spiralOrder(matrix));}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/282725.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

多线程基础 -概念、创建、等待、分离、终止

文章目录 一、 线程概念1. 什么是线程2. 线程的优点3.线程的缺点4. 线程异常5. 线程用途 二、 Linux进程VS线程1. 进程和线程2. 进程和线程的地址空间3. 进程和线程的关系 三、Linux线程控制1. POSIX线程库2. 线程创建3. 线程ID及进程地址空间布局4. 线程终止5. 线程等待6. 线程…

Linux初识环境变量

&#x1f30e;环境变量【上】 文章目录&#xff1a; 环境变量 什么是环境变量 关于命令行参数 环境变量       简单了解       为什么需要环境变量       系统中其他环境变量 总结 前言&#xff1a; 环境变量是一种非常重要的概念&#xff0c;它们对于系统的…

长安链正式发布三周年,技术更迭支撑产业变革

导语&#xff1a; 2024年1月27日长安链正式发布三周年&#xff0c;开源社区借开年之际与大家一同回顾长安链三年来的技术发展历程&#xff0c;每一个里程碑的建设都得益于与长安链同行的合作伙伴与开发者&#xff0c;希望在2024年可以共同携手继往开来&#xff0c;为数字经济发…

Mysql面试题以及答案

1 基础 1.1、MySQL有哪些数据库类型&#xff1f; 数值类型 有包括 TINYINT、SMALLINT、MEDIUMINT、INT、BIGINT&#xff0c;分别表示 1 字节、2 字节、3 字节、4 字节、8 字节的整数类型。 1&#xff09;任何整数类型都可以加上 UNSIGNED 属性&#xff0c;表示无符号整数。 …

Matlab快捷键与函数

注释&#xff1a;注释对于代码的重要性我们就不做过多的解释了。不做注释的代码不是好代码。选中要注释的语句&#xff0c;按快捷键CtrlR,或者在命令行窗口上面的注释地方可以进行注释。当然也可以直接在语句前面“%”就可以&#xff08;注意&#xff1a;一定要用英文符号&…

第十二届蓝桥杯省赛CC++ 研究生组

十二届省赛题 第十二届蓝桥杯省赛C&C 研究生组-卡片 第十二届蓝桥杯省赛C&C 研究生组-直线 第十二届蓝桥杯省赛C&C 研究生组-货物摆放 第十二届蓝桥杯省赛C&C 研究生组-路径 第十二届蓝桥杯省赛C&C 研究生组-时间显示 第十二届蓝桥杯省赛C&C 研究生组…

石油炼化5G智能制造工厂数字孪生可视化平台,推进行业数字化转型

石油炼化5G智能制造工厂数字孪生可视化平台&#xff0c;推进行业数字化转型。在石油炼化行业&#xff0c;5G智能制造工厂数字孪生可视化平台的出现&#xff0c;为行业的数字化转型注入了新的活力。石油炼化行业作为传统工业的重要领域&#xff0c;面临着资源紧张、环境压力、安…

Matlab 双目相机标定(内置函数)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 相机标定的目的就是要找到从世界坐标转换为图像坐标所用到的投影P矩阵各个系数(即相机的内参与外参)。具体过程如下所述: 1、首先我们需要获取一个已知图形的图像(这里我们使用MATLAB所提供的数据)。 2、找到同…

_nodemon自动重启服务器

文章目录 1.安装模块 nodemon1.1安装方式2.jason文件里面可以存储自定义指令 由于每次修改代码都要重启服务器&#xff0c;所以我们希望有一种方式自动监视代码修改&#xff0c;自动启动服务器nodemon模块解决了这个问题 1.安装模块 nodemon 1.1安装方式 全局安装 npm i node…

计算地球圆盘负荷产生的位移

1.研究背景 计算受表面载荷影响的弹性体变形问题有着悠久的历史&#xff0c;涉及到许多著名的数学家和物理学家&#xff08;Boussinesq 1885&#xff1b;Lamb 1901&#xff1b;Love 1911&#xff0c;1929&#xff1b;Shida 1912&#xff1b;Terazawa 1916&#xff1b;Munk &…

TCP | TCP协议格式 | 三次握手

1.TCP协议 为什么需要 TCP 协议 &#xff1f;TCP 工作在哪一层&#xff1f; IP网络层是不可靠的&#xff0c;TCP工作在传输层&#xff0c;保证数据传输的可靠性。 TCP全称为 “传输控制协议&#xff08;Transmission Control Protocol”&#xff09;。 TCP 是面向连接的、可靠…

京东云开发者:DDD 学习与感悟 —— 向屎山冲锋

原文地址:https://mp.weixin.qq.com/s/Hvq1ttBopbxypatVcKcLiA 软件系统是通过软件开发来解决某一个业务领域或问题单元而产生的一个交付物。而通过软件设计可以帮助我们开发出更加健壮的软件系统。因此&#xff0c;软件设计是从业务领域到软件开发之间的桥梁。而DDD是软件设计…

opengl 学习(六)-----坐标系统与摄像机

坐标系统与摄像机 分类引言坐标系统摄像机教程在CMake中使用全局定义预编译宏,来控制是否开启错误检查补充 分类 opengl c 引言 OpenGL希望在每次顶点着色器运行后&#xff0c;我们可见的所有顶点都为标准化设备坐标(Normalized Device Coordinate, NDC)。也就是说&#xff…

OCP NVME SSD规范解读-14.Firmware固件升级要求

4.11节 Firmware Update Requirements 描述了数据中心NVMe SSD固件更新的具体要求&#xff0c;确保固件升级过程既安全又可靠&#xff0c;同时充分考虑了设备在升级过程中的可用性和功能性。 FWUP-1: 设备必须记录每一次固件激活过程。这意味着固件升级过程中&#xff0c;设备会…

【Dynamics 365 FO】在Dynamics 365中建立一个SSRS报表

建立一个SSRS报表主要有以下8个步骤&#xff1a; 目录 1、新建合约类 合约类&#xff08;Contract Class&#xff09;的作用是获取查询数据源所需要的数据&#xff0c;在我们点开报表的时候&#xff0c;系统会弹出一个对话框让我们来选择字段来筛选要查询数据&#xff0c;合…

基于Java的厦门旅游电子商务预订系统(Vue.js+SpringBoot)

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 景点类型模块2.2 景点档案模块2.3 酒店管理模块2.4 美食管理模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 学生表3.2.2 学生表3.2.3 学生表3.2.4 学生表 四、系统展示五、核心代码5.1 新增景点类型5.2 查询推荐的…

CANoe自带的TCP/IP协议中TCP发送时的一个特殊处理(我一定是第一个发现的)

我们知道,CANoe软件中配置以太网通道后,添加的仿真节点可以作为一个主机或者一个应用来实现以太网通信。但不管是作为主机还是应用,仿真节点都需要配置TCP/IP协议栈。 有了TCP/IP协议栈,设置了网卡信息后(IP地址、MAC地址等),仿真节点就可以通过编写CAPL代码的方式发送和…

关于UDP协议

UDP协议是基于非连接的发送数据就是把数据包简单封装一下&#xff0c;然后从网卡发出去就可以&#xff0c;数据包之间没有状态上的联系&#xff0c;UDP处理方式简单&#xff0c;所以性能损耗非常少&#xff0c;对于CPU、内存资源的占用远小于TCP&#xff0c;但是对于网络传输过…

[综述笔记]A Survey on Deep Learning for Neuroimaging-Based Brain Disorder Analysis

论文网址&#xff1a;Frontiers | A Survey on Deep Learning for Neuroimaging-Based Brain Disorder Analysis (frontiersin.org) 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论…

visual studio卸载几种方法

1、控制面板卸载&#xff1b; 2、有时候会发现控制面板卸载会失败&#xff0c;无法卸载&#xff0c;这时候要先把下面目录的关于visual studio的都删除&#xff0c;然后重启电脑后&#xff0c;重新安装vs即可。