【算法题】螺旋矩阵IV (求解n阶折线蛇形矩阵)

一、问题的提出

n阶折线蛇形矩阵的特点是按照图1所示的方式排列元素。n阶蛇形矩阵是指矩阵的大小为n×n,其中n为正整数。

题目背景

一个 n 行 n 列的螺旋矩阵可由如图1所示的方法生成,观察图片,找出填数规律。填数规则为从 1 开始填到 n×n

 图1 8行8列的螺旋矩阵

现在给出矩阵大小 n 以及 i 和 j,请你求出该矩阵中第 i 行第 j 列的数是多少。

题目描述

输入格式

从标准输入读入数据。 共一行,包含三个整数 n(1≤n≤1,000)、i(1≤in)、j(1≤jn),每两个整数之间用一个空格隔开,分别表示矩阵大小、待求的数所在的行号和列号。

输出格式

输出到标准输出。一个整数,表示相应矩阵中第 i 行第 j 列的数。

输入输出样例

输入 #1复制

8 2 8

输出 #1复制

51

说明/提示

子任务

对于 30% 的测试数据,n≤10;对于 60% 的测试数据,n≤100;对于 100% 的测试数据,n≤1,000;特别地,对于 20% 的测试数据,i=j=1。

二、解题的思路

由图2可知,这是个水平、垂直转弯的蛇形矩阵。仔细看图2发现:当在第1行(行号为0)时则向右(行号不变,列号加1)填数,然后向下,当行列值相等转向左侧,如是列号到0时则向下(行号加1),然后向右方填数,如行列值相等则转向上,如是行号到0时则向右(行号不变,列号加1),然后向下,如此重复直到最后行的0列,或最后列的0行为止。

 图2 蛇形矩阵分析图

三、矩阵生成算法

nn列,第一行为0行,第一列为0列。从(0, 0)1开始,方向设为向上。

当向上时,如行号已为0则列号加1、方向向反(向下),否则行号减1,如列号为n-1且行号为0时结束填写。

当向下时,如列号==行号则转弯(向左),否则行号加1

当向左时,如列号已为0则行号加1、方向向反(向右),否则列号减1,如行号为n-1且列号为0时结束填写。

当向右时,如行号==列号则转弯(向上),否则列号加1

程序代码如下:

def prt(hm):                 # 打印二维列表for i in range(N):for j in range(N):print("%3d" % hm[i][j], end='')print()def Helix_MatrixII(n):cnt = 1i = j = 0k = 1while True:matrix[i][j] = cntif (i == 0 and j >= n-1 and k == 1) or (i >= n-1 and j == 0 and k == 3):break            # 向上填写时,最后1列并到0行 或 向左填写时,最后1行并到0列if k == 0:           # 向右填写j +=1if i == j:       # 转向向上k = 1elif k == 1:         # 向上填写if i == 0:       # 到0时,转下一列调头j += 1k = 2else:i -=1elif k == 2:         # 向下填写i +=1if i == j:       # 转向向左k = 3elif k == 3:         # 向左填写if j == 0:       # 到0时,转下一行调头i += 1k = 0else:j -=1cnt += 1N = 6
matrix = []                  # 初始化二维矩阵matrix(二维列表)
for i in range(N):matrix.append([])for j in range(N):matrix[i].append(0)
Helix_MatrixII(N)
prt(matrix)

执行结果:

四、题目求解算法

题目要求输入矩阵规模n和坐标(i, j)三个参数,求出矩阵(i, j)处的元素值。所以先按n求出矩阵,现按坐标输出元素值。

程序代码如下:

def Helix_MatrixII(n):cnt = 1i = j = 0k = 1while True:matrix[i][j] = cntif (i == 0 and j >= n-1 and k == 1) or (i >= n-1 and j == 0 and k == 3):break          # 向上并最后1列到第0行 或 向左并最后1行到第0列if k == 0:         # 向右填写j +=1if i == j:     # 转向向上k = 1elif k == 1:       # 向上填写if i == 0:     # 向上到0行,列号加1并转向下j += 1k = 2else:i -=1elif k == 2:       # 向下填写i +=1if i == j:     # 转向向左k = 3elif k == 3:       # 向左填写if j == 0:     # 向左到0列,行号加1并转向右i += 1k = 0else:j -=1cnt += 1N, x, y = map(int, input().split())
matrix = []                # 初始化二维矩阵matrix(二维列表)
for i in range(N):matrix.append([])for j in range(N):matrix[i].append(0)
Helix_MatrixII(N)
print(matrix[x-1][y-1])

执行结果:

 

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

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

相关文章

HTTP 协议的基本格式和 fiddler 的用法

目录 一. HTTP 协议 1. HTTP协议是什么 2. HTTP协议的基本格式 HTTP请求 首行 GET和POST方法: 其他方法 经典面试题: URL Header(请求报头)部分 空行 ​HTTP响应 状态码总结: 二、Fiddler的用法 1.Fidder的安装 2.Fidder的使用 一. HTTP 协议 1. H…

如何在 iOS 上安装并使用 ONLYOFFICE 文档

借助 iOS 版文档应用,您可在移动端设备上访问存储于 ONLYOFFICE 账户中的文件,查看和编辑现有文本文档、电子表格和演示文稿,创建新文档并对其进行整理,以及连接第三方云存储服务。您可与其他门户网站用户协作编辑文档&#xff0c…

多环境_部署项目

多环境: 指同一套项目代码在不同的阶段需要根据实际情况来调整配置并且部署到不同的机器上。 为什么需要? 1. 每个环境互不影响 2. 区分不同的阶段:开发 / 测试 / 生产 3. 对项目进行优化: 1. 本地日志级别 2. 精简依赖&a…

图像的镜像变换之c++实现(qt + 不调包)

1.基本原理 1.水平镜像变化 设图像的宽度为width,则水平镜像变化的映射关系如下: 2.垂直镜像变化 设图像的宽度为height,则垂直镜像变化的映射关系如下: 2.代码实现(代码是我以前自学图像处理时写的,代码很…

ARM(汇编指令)

.global _start _start:/*mov r0,#0x5mov r1,#0x6 bl LoopLoop:cmp r0,r1beq stopsubhi r0,r0,r1subcc r1,r1,r0mov pc,lr*/ mov r0,#0x1mov r1,#0x0mov r2,#0x64bl Loop Loop:cmp r0,r2bhi stopadd r1,r1,r0add r0,r0,#0x01mov pc,lr stop:B stop.end

【Leetcode】基础题||合并有序表(击败100%)

step by step. 题目:(超级基础的题) 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 [1,2,4], l2 [1,3,4] 输出:[1,1,2,3,4,4]示例…

自动测试框架airtest应用一:将XX读书书籍保存为PDF

一、Airtest的简介 Airtest是网易出品的一款基于图像识别和poco控件识别的一款UI自动化测试工具。Airtest的框架是网易团队自己开发的一个图像识别框架,这个框架的祖宗就是一种新颖的图形脚本语言Sikuli。Sikuli这个框架的原理是这样的,计算机用户不需要…

React Dva项目小优化之redux-action

之前 我们讲过 models 接下啦 我们来给大家讲一个新的库 这个库的话 有最好 没有影响也不大 它主要是帮助我们处理 action的 我们直接在 GitHub 官网上搜索 redux-action 我们搜出来 第一个就是 从星数来看 还是非常优秀的 我们拉下来 找到这个Documentation 然后点击进去 进…

Jmeter - 函数助手

目录 __StringFromFile __CSVRead __counter __RandomString __StringFromFile StringFromFile函数用于获取文本文件的值,一次读取一行 1、输入文件的全路径:填入文件路径 2、存储结果的变量名(可选) 3、Start file sequence …

绘制世界地图or中国地图

写在前面 在8月初,自己需要使用中国地图的图形,自己就此也查询相关的教程,自己也做一下小小总结,希望对自己和同学们有所帮助。 最终图形 这个系列从2022年开始,一直更新使用R语言分析数据及绘制精美图形。小杜的生信笔记主要分享小杜学习日常!如果,你对此感兴趣可以加…

智慧工地一体化云平台源码:监管端、工地端、危大工程、智慧大屏、物联网、塔机、吊钩、升降机

智慧工地解决方案依托计算机技术、物联网、云计算、大数据、人工智能、VR&AR等技术相结合,为工程项目管理提供先进技术手段,构建工地现场智能监控和控制体系,弥补传统方法在监管中的缺陷,最终实现项目对人、机、料、法、环的全…

SHELL 基础 SHELL注释 及 执行SHELL脚本的四种方法

SHELL 脚本编写规范 : 脚本开头 : # 脚本第一行 : #! /bin/bash 或 #!/bin/sh ( 脚本解释器 ) # 程序段开头需要加 版本版权信息 ,例如 : # Date 创建日期 # Author : 作者 # …

【【STM32-USART串口协议】】

STM32-USART串口协议 USART串口协议 •通信的目的:将一个设备的数据传送到另一个设备,扩展硬件系统 •通信协议:制定通信的规则,通信双方按照协议规则进行数据收发 就是我们并不能在芯片上设计完全部的一下子完成所有的设计&…

下单接口调优实战,性能提高10倍

目录 概述 用到的工具和环境 工具 环境 找瓶颈 总结 概述 最近公司的下单接口有些慢,老板担心无法支撑双11,想让我优化一把,但是前提是不允许大改,因为下单接口太复杂了,如果改动太大,怕有风险。另外…

js的练习

这里写目录标题 工具代码运行结果 工具 HBuilder X 代码 <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title><script>window.onload function() // 需要在body加载完成之后&#xff0c;才能通过docu…

【日常积累】Linux之init系统学习

init系统简介: Linux 操作系统的启动首先从 BIOS 开始&#xff0c;接下来进入 boot loader&#xff0c;由 bootloader 载入内核&#xff0c;进行内核初始化。内核初始化的最后一步就是启动 pid 为 1 的 init 进程&#xff0c;这个进程是系统的第一个进程&#xff0c;它负责产生…

云原生 AI 工程化实践之 FasterTransformer 加速 LLM 推理

作者&#xff1a;颜廷帅&#xff08;瀚廷&#xff09; 01 背景 OpenAI 在 3 月 15 日发布了备受瞩目的 GPT4&#xff0c;它在司法考试和程序编程领域的惊人表现让大家对大语言模型的热情达到了顶点。人们纷纷议论我们是否已经跨入通用人工智能的时代。与此同时&#xff0c;基…

React 全栈体系(一)

第一章 React入门 一、React简介 1. 是什么&#xff1f; 是一个将数据渲染为HTML视图的开源JavaScript库。 2. 谁开发的&#xff1f; 由Facebook开源 3. 为什么要学&#xff1f; 原生JavaScript操作DOM繁琐&#xff0c;效率低&#xff08;DOM-API 操作 UI&#xff09; 使…

【CNN-BiLSTM-attention】基于高斯混合模型聚类的风电场短期功率预测方法(Pythonmatlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

“解锁IDEA的潜力:高级Java Maven项目配置指南”

目录 前言&#xff1a;流程目录&#xff1a;1.确保Java和Maven已安装检查Java是否已正确安装并配置环境变量 2.创建一个新的Maven项目导航到要创建项目的目录配置Maven运行以下命令创建一个新的Maven项目 3.配置项目的pom.xml文件打开项目根目录下的pom.xml文件配置Web.xml 4.配…