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

LeetCode 第47题:旋转数组

LeetCode 第47题:旋转数组

题目描述

给定一个 × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例1:

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

 示例2:

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

提示:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

解题思路:

方法一:使用辅助数组

对于矩阵中第i行的第j个元素,在旋转后,它出现在倒数第i列的第j个位置。

对于矩阵中的元素matrix[row][col]在旋转后,它的新位置为matrix[col][n-row-1]。 

void rotate(int** matrix,int matrixSize,int* matrixColSize)
{int matrix_new[matrixSize][matrixSize];for(int i=0;i<matrixSize;i++){for(int j=0;j<matrixSize;j++)matrix_new[i][j]=matrix[i][j];}for(int i=0i<matrixSize;i++){for(int j=0;j<matrixSize;j++)matrix[j][matrixSize-i-1] = matrix_new[i][j];}
}

方法二:原地旋转

  • 采用一个临时变量temp暂存matrix[col][n-row-1]的值,即:

\left\{\begin{matrix} temp& \quad\quad\quad\quad=matrix[col][n-row-1]\\ matrix[col][n-row-1]& =matrix[row][col] \end{matrix}\right.

  • matrix[col][n-row-1]经过旋转之后,得到关键公式:

matrix[n-row-1][n-col-1] = matrix[col][n-row-1]

  • 再重复一次之前的操作,matrix[n-row-1][n-col-1]经过旋转之后得到:

matrix[n−col−1][row]=matrix[n−row−1][n−col−1]

  • 再重复一次操作,matrix[n−col−1][row]经过旋转之后得到:

matrix[row][col]=matrix[n−col−1][row]

  • 以上四项处于一个循环当中,因此我们可以使用一个临时变量temp完成上述四项的原地交换。
  • 当n为偶数时,需要枚举n^2/4=(n/2)×(n/2)个位置,当n为奇数时,需要枚举(n^2-1)/4个位置,中心的位置经过旋转后位置不变。
void roate(int** matrix,int matrixSize,int* matrixColSize)
{for(int i=0;i<matrixSize/2;i++){for(int j=0;j<(matrixSize+1)/2;j++){int temp = matrix[i][j];matrix[i][j]=matrix[matrixSize-j-1][i];matrix[matrixSize-j-1][i]=matrix[matrixSize-i-1][matrixSize-j-1];matrix[matrixSize-i-1][matrixSize-j-1]=matrix[j][matrixSize-i-1]matrix[j][matrixSize-i-1]=temp;}}
}

方法三:翻转代替旋转

以题目中的示例2作为例子:

\begin{Bmatrix} 5 & 1 &9 &11 \\ 2& 4 &8 &10 \\ 13& 3 &6 &7 \\ 15& 14 & 12 &16 \end{Bmatrix}

首先将其通过水平轴翻转得到:

matrix[row][col]经过水平轴翻转变为matrix[n-row-1][col]

\begin{Bmatrix} 15 &14 &12 &16 \\ 13 & 3 & 6 &7 \\ 2& 4 & 8 & 10\\ 5& 1 &9 &11 \end{Bmatrix}

然后根据主对角线翻转得到:

matrix[row][col]经过主对角线翻转变为matrix[col][row]

\begin{Bmatrix} 15 &13 &2 &5 \\ 14 &3 & 4& 1\\ 12& 6& 8 &9 \\ 16& 7 & 10 &11 \end{Bmatrix}

将上述两步进行联立,即可得到:

matrix[row][col]经过水平轴翻转变为matrix[n-row-1][col],再经过主对角线翻转得到matrix[col][n-row-1]。

void swap(int* a,int* b)
{int t=*a;*a = *b;*b = t;
}
void rotate(int** matrix,int matrixSize,int* matrixColSize)
{//水平翻转for(int i=0;i<matrixSize/2;i++)for(int j=0;j<matrixSize;j++)swap(&matrix[i][j],&matrix[matrixSize-i-1][j]);//主对角线翻转for(int i=0;i<matrixSize;i++)for(int j=0;j<i;j++)swap(&matrix[i][j],&matrix[j][i]);
}

相关文章:

LeetCode 第47题:旋转数组

LeetCode 第47题&#xff1a;旋转数组 题目描述 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例1&#xff1a; 输入&#xf…...

数据库管理工具实战:IDEA 与 DBeaver 连接 TDengine(二)

五、DBeaver 连接 TDengine 实战 5.1 安装 DBeaver 下载安装包&#xff1a;访问 DBeaver 官方网站&#xff08;https://dbeaver.io/download/ &#xff09;&#xff0c;根据你的操作系统选择合适的安装包。如果是 Windows 系统&#xff0c;下载.exe 格式的安装文件&#xff1…...

4S店汽车维修保养管理系统 (源码+lw+部署文档+讲解),源码可白嫖!

摘要 二十一世纪我们的社会进入了信息时代&#xff0c;信息管理系统的建立&#xff0c;大大提高了人们信息化水平。传统的管理方式已经与当今4S店汽车维修保养管理系统的业务需求不相适应,也与4S店汽车维修保养管理系统化建设的发展趋势不相适应。本文针对这一需求设计并实现了…...

【Mysql】主从复制部署(保姆级)

本次部署用到三台Ubuntu虚拟机&#xff08;一主两从&#xff09;&#xff1a; Master服务器&#xff1a;192.168.166.107 Slave1服务器&#xff1a;192.168.166.101 Slave2服务器&#xff1a;192.168.166.103 一、部署思路 首先我们要先捋清主从复制的部署思路…...

华为AR1200密码忘记

1、通过Console口连接设备并重启设备。在设备启动过程中&#xff0c;看到提示信息“Press CtrlB to break auto startup...”时&#xff0c;在三秒内按下CtrlB&#xff0c;输入BootLoader密码后&#xff0c;默认密码&#xff1a;Adminhuawei &#xff0c;进入BootLoader主菜单…...

高级java每日一道面试题-2025年3月26日-微服务篇[Nacos篇]-在Spring Cloud项目中如何集成Nacos?

如果有遗漏,评论区告诉我进行补充 面试官: 在Spring Cloud项目中如何集成Nacos&#xff1f; 我回答: 在Spring Cloud项目中集成Nacos&#xff0c;可以充分利用Nacos作为服务注册与发现中心以及配置管理中心的功能。以下是详细的步骤和说明&#xff0c;帮助你完成这一集成过程…...

YOLO-LLTS:低光照实时交通标志检测算法详解

论文地址:https://arxiv.org/pdf/2503.13883 目录 一、论文概述 1.1 研究背景 1.2 论文结构 二、核心创新点 2.1 CNTSSS数据集 2.2 HRFM-TOD模块 2.3 MFIA模块 2.4 PGFE模块 三、实验与结果 3.1 实验设置 3.2 性能对比 ​编辑3.3 消融实验 四、代码复现建议 4.…...

golang 性能优化分析工具 pprof

pprof简介 pprof 是 Go 语言标准库提供的一个强大的性能分析工具&#xff0c;它能帮助开发者深入了解程序的运行时行为&#xff0c;找出性能瓶颈&#xff0c;进而对代码进行优化。下面从多个方面对 pprof 进行详细介绍&#xff1a; 主要功能 CPU 性能分析&#xff1a;能够记…...

机器学习 Day09 线性回归

1.线性回归简介 线性回归知识讲解 定义与公式 定义&#xff1a;线性回归是利用回归方程&#xff08;函数&#xff09;对自变量&#xff08;特征值&#xff09;和因变量&#xff08;目标值&#xff09;之间关系进行建模的分析方式 。自变量只有一个时是单变量回归&#xff0c;…...

2025高频面试算法总结篇【字符串】

文章目录 直接刷题链接直达如何找出一个字符串中的最大不重复子串给定一个数&#xff0c;删除K位得到最大值字符串的排列至少有K个重复字符的最长子串 直接刷题链接直达 如何找出一个字符串中的最大不重复子串 滑动窗口 --> 滑动窗口直到最后一个元素&#xff0c;每当碰到重…...

JavaScript性能优化(上)

1. 减少 DOM 操作 减少 DOM 操作是优化 JavaScript 性能的重要方法&#xff0c;因为频繁的 DOM 操作会导致浏览器重绘和重排&#xff0c;从而影响性能。以下是一些具体的策略和技术&#xff0c;可以帮助有效减少 DOM 操作&#xff1a; 1.1. 批量更新 DOM 亲切与母体&#xff…...

数据结构与算法——链表OJ题详解(1)

文章目录 一、前言二、OJ题分享2.1移除链表元素——非val尾插法2.2反转链表2.2.1头插法2.2.2三指针法 2.3链表的中间结点——快慢指针法2.4合并两个有序链表2.4.1空链表法2.4.2非空链表法 2.5链表的回文结构2.5.1投机取巧数组法2.5.2反转链表法 三、总结 一、前言 前几天博主已…...

sedex认证2025年变化重点

近日&#xff0c;SEDEX突然宣布&#xff1a;2025年7月1日起&#xff0c;全通知审核正式退出历史舞台&#xff0c;取而代之的是至少3周窗口期的半通知突击审核。这场被业内称为“供应链透明化革命”的调整&#xff0c;或将重塑全球工厂合规生态。 三大变化划重点&#xff1a; 1…...

Scala课后总结(8)

集合计算高级函数 过滤&#xff08;filter&#xff09; 从集合里挑出符合特定条件元素组成新集合 。比如从整数集合里选出偶数&#xff0c; list.filter(x > x % 2 0) &#xff0c;就是筛选出能被2整除的元素。 转化/映射&#xff08;map&#xff09; 对集合每个元素应…...

老硬件也能运行的Win11 IoT LTSC (OEM)物联网版

#记录工作 Windows 11 IoT Enterprise LTSC 2024 属于物联网相关的版本。 Windows 11 IoT Enterprise 是为物联网设备和场景设计的操作系统版本。它通常针对特定的工业控制、智能设备等物联网应用进行了优化和定制&#xff0c;以满足这些领域对稳定性、安全性和长期支持的需求…...

蓝桥杯冲刺题单--二分

二分 知识点 二分&#xff1a; 1.序列二分&#xff1a;在序列中查找&#xff08;不怎么考&#xff0c;会比较难&#xff1f;&#xff09; 序列二分应用的序列必须是递增或递减&#xff0c;但可以非严格 只要r是mid-1&#xff0c;就对应mid&#xff08;lr1&#xff09;/2 2.答…...

计网 2025/4/8

CDMA? CRC循环冗余检验 PPP协议的帧格式 字节填充&#xff08;异步传输、7E->7D5E&#xff09;零比特填充&#xff08;同步传输、确保不会出现连续6个1&#xff09; CSMA/CD协议 多点接入载波监听碰撞检测 一些概念&#xff1a; 争用期 一些公式&#xff1a; 最短有效帧…...

java设计模式-工厂模式

工厂模式 简单工厂模式 请看类&#xff1a; org.xwb.springcloud.factory.simple.PizzaStore 1、简单工厂模式是属于创建型模式&#xff0c;是工厂模式的一种&#xff0c;简单工厂模式是由一个工厂对象决定创建出哪一种产品类的实力。简单来工厂模式就是工厂模式家族中最简单最…...

2025年客运从业资格证备考刷题题库

题库中通常包含大量的题目&#xff0c;以全面覆盖考试的知识点。通过做大量的题目&#xff0c;考生可以熟悉各种考试题型和命题方式&#xff0c;提高答题的速度和准确性&#xff0c;同时也能发现自己在知识掌握上的薄弱环节&#xff0c;有针对性地进行复习和强化训练。 1、驾驶…...

Zephyr、FreeRTOS、RT-Thread 任务创建对比分析

一、任务模型与核心概念 特性ZephyrFreeRTOSRT-Thread任务术语线程&#xff08;Thread&#xff09;任务&#xff08;Task&#xff09;线程&#xff08;Thread&#xff09;执行单元线程&#xff08;单地址空间&#xff09;任务&#xff08;共享内存空间&#xff09;线程&#x…...

RK-realtime Linux

rk3562实时性数据:最大76us rk3568实时性数据:最大126us rk3588实时性数据:最大30us 注意事项 (1)RK3568 需要使用RT版本的BL31,实时性能更好 ​ a)rkbin需要更新到最新,且包含这个补丁:...

Ubuntu 22 Linux上部署DeepSeek+RAG知识库操作详解(Dify方式)之1

一、安装Docker 1. 更新你的包索引 首先&#xff0c;确保你的包列表是最新的。打开终端并运行以下命令&#xff1a; sudo apt update 2. 安装必要的依赖项 安装Docker之前&#xff0c;你需要安装一些必要的依赖项。运行以下命令来安装它们&#xff1a; sudo apt install apt…...

将飞帆制作的网页作为 div 集成到自己的网页中

并且自己的网页可以和飞帆中的控件相互调用函数。效果&#xff1a; 上链接 将飞帆制作的网页作为 div 集成到自己的网页中 - 文贝 进入可以复制、运行代码...

【C++游戏引擎开发】《几何算法》(3)AABB/OBB碰撞检测

一、AABB(轴对齐包围盒) 1.1 定义 ​最小点: m i n = ( x min , y min , z min ) \mathbf{min} = (x_{\text{min}}, y_{\text{min}}, z_{\text{min}}) min=(xmin​,ymin​,zmin​)​最大点: m a x = ( x max , y max , z max ) \mathbf{max} = (x_{\text{max}}, y_{\text{…...

基于人工智能的高中教育评价体系重构研究

基于人工智能的高中教育评价体系重构研究 一、引言 1.1 研究背景 在科技飞速发展的当下&#xff0c;人工智能技术已广泛渗透至各个领域&#xff0c;教育领域亦不例外。人工智能凭借其强大的数据处理能力、智能分析能力和个性化服务能力&#xff0c;为教育评价体系的创新与发…...

【C++游戏引擎开发】数学计算库GLM(线性代数)、CGAL(几何计算)的安装与使用指南

写在前面 两天都没手搓实现可用的凸包生成算法相关的代码&#xff0c;自觉无法手搓相关数学库&#xff0c;遂改为使用成熟数学库。 一、GLM库安装与介绍 1.1 vcpkg安装GLM 跨平台C包管理利器vcpkg完全指南 在PowerShell中执行命令&#xff1a; vcpkg install glm# 集成到系…...

Python 字典和集合(常见的映射方法)

本章内容的大纲如下&#xff1a; 常见的字典方法 如何处理查找不到的键 标准库中 dict 类型的变种set 和 frozenset 类型 散列表的工作原理 散列表带来的潜在影响&#xff08;什么样的数据类型可作为键、不可预知的 顺序&#xff0c;等等&#xff09; 常见的映射方法 映射类型…...

Qt 自带的QSqlDatabase 模块中使用的 SQLite 和 SQLite 官方提供的 C 语言版本(sqlite.org)对比

Qt 自带的 QSqlDatabase 模块中使用的 SQLite 和 SQLite 官方提供的 C 语言版本&#xff08;sqlite.org&#xff09;在核心功能上是相同的&#xff0c;但它们在集成方式、API 封装、功能支持以及版本更新上存在一些区别。以下是主要区别&#xff1a; 1. 核心 SQLite 引擎 Qt 的…...

按键长按代码

这些代码都存放在定时器中断中。中断为100ms中断一次。 数据判断&#xff0c;看的懂就看吧...

zk源码—3.单机和集群通信原理一

大纲 1.单机版的zk服务端的启动过程 (1)预启动阶段 (2)初始化阶段 2.集群版的zk服务端的启动过程 (1)预启动阶段 (2)初始化阶段 (3)Leader选举阶段 (4)Leader和Follower启动阶段 1.单机版的zk服务端的启动过程 (1)预启动阶段 (2)初始化阶段 单机版zk服务端的启动&…...

车企数字化转型:从“制造工厂”到“移动科技平台”的升维路径

一、战略重构&#xff1a;政策与产业变革的双重倒逼 中国《智能网联汽车技术路线图2.0》明确要求2030年L4级自动驾驶新车渗透率达20%&#xff0c;而麦肯锡数据显示&#xff0c;全球车企数字化投入占比已从2018年的7%跃升至2025年的18%。当前车企面临三大核心挑战&#xff1a;用…...

C++-Mongoose(2)-https-server-openssl

OpenSSL生成HTTPS自签名证书 - 简书 1.Openssl windowsubuntu下载http://www.openssl.vip/download1.VS2019编译OpenSSL 2.VS2019编译第一个OpenSSL项目 1.ubuntu编译OpenSSL 3.0 2.编写第一个OpenSSL 1.windows下编译OpenSSL 安装vs2019 perl nasm安装activePerl…...

nginx正向代理https

一、需求 公司内部服务器向外访问腾讯接口&#xff1a;https://qyapi.weixin.qq.com/cgi-bin&#xff0c;不能使用http直接访问。并且不支持域名&#xff0c;还需要设置互联网出口-出向白名单ip。 如何在尽量少改动代码的情况下实现应用的出向访问链接&#xff0c;考虑使用正向…...

Flask中的蓝图(Blueprint)浅讲

BluePrint Flask中的蓝图&#xff08;Blueprint&#xff09;​是一种强大的组织工具&#xff0c;能够将大型应用拆分为可重用的模块化组件 1. ​模块化组织 用途&#xff1a;将应用按功能拆分为独立模块&#xff0c;提升代码可维护性。​示例&#xff1a; # user/views.py fr…...

虚拟表、TDgpt、JDBC 异步写入…TDengine 3.3.6.0 版本 8 大升级亮点

近日&#xff0c;TDengine 3.3.6.0 版本正式发布。除了此前已亮相的时序数据分析 AI 智能体 TDgpt&#xff0c;本次更新还带来了多个针对性能与易用性的重要增强&#xff1a;虚拟表全面上线&#xff0c;支持更灵活的一设备一表建模&#xff1b;JDBC 写入机制全新升级&#xff0…...

大型语言模型智能应用Coze、Dify、FastGPT、MaxKB 对比,选择合适自己的LLM工具

大型语言模型智能应用Coze、Dify、FastGPT、MaxKB 对比&#xff0c;选择合适自己的LLM工具 Coze、Dify、FastGPT 和 MaxKB 都是旨在帮助用户构建基于大型语言模型 (LLM) 的智能应用的平台。它们各自拥有独特的功能和侧重点&#xff0c;以下是对它们的简要对比&#xff1a; Coz…...

WEB安全--XSS--DOM破坏

一、前言 继XSS基础篇后&#xff0c;我们知道了三种类型的XSS&#xff0c;这篇文章主要针对DOM型XSS的原理进行深入解析。 二、DOM型XSS原理 2.1、什么是DOM 以一个形象的比喻&#xff1a; 网页就像是一座房子&#xff0c;而 **DOM** 就是这座房子的“蓝图”或者“结构图”。…...

持续集成:GitLab CI/CD 与 Jenkins CI/CD 的全面剖析

一、引言 在当今快速迭代的软件开发领域,持续集成(Continuous Integration,CI)已成为保障软件质量、加速开发流程的关键实践。通过频繁地将代码集成到共享仓库,并自动进行构建和测试,持续集成能够尽早发现并解决代码冲突和缺陷。而 GitLab CI/CD 和 Jenkins CI/CD 作为两…...

Go语言sync.Mutex包源码解读

互斥锁sync.Mutex是在并发程序中对共享资源进行访问控制的主要手段&#xff0c;对此Go语言提供了非常简单易用的机制。sync.Mutex为结构体类型&#xff0c;对外暴露Lock()、Unlock()、TryLock()三种方法&#xff0c;分别用于阻塞加锁、解锁、非阻塞加锁操作&#xff08;加锁失败…...

FreeRTOS软件定时器

软件定时器就是"闹钟"&#xff0c;你可以设置闹钟&#xff0c; 用软件定时器的话USE_TIMER要设置为1 在30分钟后让你起床工作每隔1小时让你例行检查机器运行情况 软件定时器也可以完成两类事情&#xff1a; 在"未来"某个时间点&#xff0c;运行函数周期…...

Selenium三大等待

一、强制等待 1.设置完等待后不管有没有找到元素&#xff0c;都会执行等待&#xff0c;等待结束后才会执行下一步 2.实例&#xff1a; driver webdriver.Chrome()driver.get("https://www.baidu.com")time.sleep(3) # 设置强制等待driver.quit() 二、隐性等待 …...

【Ansible自动化运维】一、初步了解,开启自动化运维之旅

在当今数字化时代&#xff0c;随着企业 IT 基础设施规模的不断扩大&#xff0c;传统的手工运维方式逐渐显得力不从心。自动化运维技术应运而生&#xff0c;其中 Ansible 凭借其简洁易用、功能强大的特点&#xff0c;成为众多运维工程师和开发人员的首选工具。本篇文章将从基础概…...

雪花算法、md5加密

雪花算法生成ID是一个64位长整型&#xff08;但是也可以通过优化简短位数&#xff09; 组成部分&#xff1a; 时间戳 机器ID 序列号 用途&#xff1a; 分布式系统唯一ID生成&#xff1a;解决数据库自增ID在分布式环境下的唯一性问题、避免UUID的无序性和性能问题 有序性…...

micro介绍

micro介绍 Micro 的首要特点是易于安装&#xff08;它只是一个静态的二进制文件&#xff0c;没有任何依赖关系&#xff09;和易于使用Micro 支持完整的插件系统。插件是用 Lua 编写的&#xff0c;插件管理器可自动为你下载和安装插件。使用简单的 json 格式配置选项&#xff0…...

电视盒子 刷armbian

参考 中兴电视盒子中兴B860AV3.2-M刷Armbian新手级教程-CSDN博客 1.刷安卓9 带root版本 a. 下载安卓线刷包 链接&#xff1a;https://pan.baidu.com/s/1hz87_ld2lJea0gYjeoHQ8A?pwdd7as 提取码&#xff1a;d7as b.拆机短接 3.安装usbburning工具 使用方法 &#xff0c;…...

(七)lerobot开源项目so100新版本全流程操作(操作记录)

目录 《项目简介》 一、环境配置 1、创建虚拟环境 2、克隆项目并安装所需包 二、主从臂硬件准备 1、舵机配置 &#xff08;1&#xff09;分别查看主从臂的开发板端口号 &#xff08;2&#xff09;分别设置主从臂的舵机 2、组装主从臂 3、查看主从臂端口号和相机端…...

智慧景区能源管理解决方案,为旅游“升温”保驾护航

景区能源管理 当下痛点 1 高峰期用电负荷大 节假日和旅游旺季等高峰期用电需求增大&#xff0c;电力供应不足、电网负荷过大&#xff1b; 2 设备维护困难 景区内电力设备多且散&#xff0c;包括发电机组、变电站、配电设备等&#xff0c;维护和管理困难&#xff0c;特别是…...

LCR 056. 两数之和 IV - 输入二叉搜索树

文章目录 题意思路代码 题意 题目链接 思路 代码 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), …...

AI搜索+法律咨询:在「事实重构」与「程序正义」的博弈场‌

已经写了股票和医疗相关的内容&#xff0c;今天聊一下AI搜索和法律结合的应用场景。AI搜索不替用户做选择&#xff0c;却让我们握住了法律武器的说明书。 ​​​​​​​一、AI重构事实&#xff1a;技术理想与法律现实的碰撞 ‌ 1、案例切入&#xff1a;AI能否还原车祸责任比…...

多模态大模型重塑自动驾驶:技术融合与实践路径全解析

目录 1、 引言&#xff1a;AI与自动驾驶的革命性融合 2、五大领先多模态模型解析 2.1 Qwen2.5-Omni&#xff1a;全模态集大成者 2.2. LLaVA&#xff1a;视觉语言理解专家 2.3. Qwen2-VL&#xff1a;长视频理解能手 2.4. X-InstructBLIP&#xff1a;跨模态理解框架 2.5. …...