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

( 数组和矩阵) 667. 优美的排列 II ——【Leetcode每日一题】

❓667. 优美的排列 II

难度:中等

给你两个整数 nk ,请你构造一个答案列表 answer ,该列表应当包含从 1n n 个不同正整数,并同时满足下述条件:

假设该列表是 answer = [a1, a2, a3, ... , an] ,那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。

返回列表 answer 。如果存在多种答案,只需返回其中 任意一种

示例 1:

输入:n = 3, k = 1
输出:[1, 2, 3]
解释:[1, 2, 3] 包含 3 个范围在 1-3 的不同整数,并且 [1, 1] 中有且仅有 1 个不同整数:1

示例 2:

输入:n = 3, k = 2
输出:[1, 3, 2]
解释:[1, 3, 2] 包含 3 个范围在 1-3 的不同整数,并且 [2, 1] 中有且仅有 2 个不同整数:1 和 2

提示:

  • 1 < = k < n < = 1 0 4 1 <= k < n <= 10^4 1<=k<n<=104

💡思路:

k=1 时,我们将 1∼n 按照 [1,2,⋯ ,n]的顺序进行排列,那么相邻的差均为 1,满足 k=1 的要求。

k=n−1 时,我们将 1∼n 按照 [1, n, 2, n−1, 3, ⋯ ]的顺序进行交叉排列,那么相邻的差从 n−1 开始,依次递减 1。这样一来,所有从 1n−1的差值均出现一次,满足 k = n−1的要求。

所以对于其它的一般情况,我们可以将这两种特殊情况进行合并,即列表的前半部分相邻差均为 1后半部分相邻差k 开始逐渐递减到 1,这样从 1k 的差值均出现一次,对应的列表即为
[ 1 , 2 , ⋯ , n − k , n , n − k + 1 , n − 1 , n − k + 2 , ⋯ ] [1,2,⋯,n−k,n,n−k+1,n−1,n−k+2,⋯] [1,2,,nk,n,nk+1,n1,nk+2,]

🍁代码:(Java、C++)

Java

class Solution {public int[] constructArray(int n, int k) {int[] ans = new int[n];for(int i = 1; i <= n - k; i++){//前半部分相邻差均为1ans[i - 1] = i;}int low = n - k + 1;int high = n;int i = n - k;while(low <= high){//后半部分交叉排序ans[i++] = high--;if(i >= n) break;ans[i++] = low++;}return ans;}
}

C++

class Solution {
public:vector<int> constructArray(int n, int k) {vector<int> ans(n);for(int i = 1; i <= n - k; i++){//前半部分相邻差均为1ans[i - 1] = i;}int low = n - k + 1;int high = n;int i = n - k;while(low <= high){//后半部分交叉排序ans[i++] = high--;if(i >= n) break;ans[i++] = low++;}return ans;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n)
  • 空间复杂度 O ( 1 ) O(1) O(1),这里不计入返回值需要的空间,只需常数级空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!

相关文章:

( 数组和矩阵) 667. 优美的排列 II ——【Leetcode每日一题】

❓667. 优美的排列 II 难度&#xff1a;中等 给你两个整数 n 和 k &#xff0c;请你构造一个答案列表 answer &#xff0c;该列表应当包含从 1 到 n 的 n 个不同正整数&#xff0c;并同时满足下述条件&#xff1a; 假设该列表是 answer [a1, a2, a3, ... , an] &#xff0…...

【python基础语法七】python内置函数和内置模块

内置全局函数 abs 绝对值函数 print(abs(-1)) # 1 print(abs(100)) # 100round 四舍五入 """奇进偶不进(n.5的情况特定发生)""" res round(3.87) # 4 res round(4.51) # 5 # res round(2.5) # 2 # res round(3.5) # 4 res round(6.5) # …...

81. read readline readlines 读取文件的三种方法

81. read readline readlines 读取文件的三种方法 文章目录 81. read readline readlines 读取文件的三种方法1. 读取文件的三种方法2. read方法3. readline方法4. readlines方法5. 代码总结5.1 read方法读取全部内容5.2 readline方法读取一行&#xff0c;返回字符串5.3 readli…...

【社区图书馆】【图书活动第四期】

目录 一、前言 二、作者简介 三、《PyTorch高级机器学习实战》内容简介 四、书目录 一、前言 今天&#xff0c;偶尔逛到csdn社区图书馆&#xff0c;看到有活动 “【图书活动第四期】来一起写书评领实体奖牌红包电子勋章吧&#xff01;”&#xff08;活动到今天结束&#xf…...

webpack学习指南(上)

构建流程 Webpack 的构建流程可以分为以下几个步骤&#xff1a; 解析配置文件&#xff1a;Webpack 会读取项目中的 webpack.config.js 文件&#xff0c;并解析其中的配置项。 解析入口文件&#xff1a;Webpack 通过配置文件中设置的 entry 入口&#xff0c;递归地解析出所有依…...

刷题记录˃ʍ˂

一、1033. 移动石子直到连续 思路 这道题是一道数学题&#xff0c;它一共分为三种可能 第一种可能为三个石子本来就是连续的时候 第二种可能为最少步数为1的时候&#xff0c;相邻石子不能大于一格 第三种可能为最少步数为2的时候&#xff0c;这时相邻石子大于一格 那么第二…...

Word2vec原理+实战学习笔记(二)

来源&#xff1a;投稿 作者&#xff1a;阿克西 编辑&#xff1a;学姐 前篇&#xff1a;Word2vec原理实战学习笔记&#xff08;一&#xff09; 视频链接&#xff1a;https://ai.deepshare.net/detail/p_5ee62f90022ee_zFpnlHXA/6 5 对比模型&#xff08;论文Model Architectur…...

什么是Java的多线程?

Java的多线程是指在同一时间内&#xff0c;一个程序中同时运行多个线程。每个线程都是一个独立的执行路径&#xff0c;可以独立地执行代码。Java中的多线程机制使得程序可以更高效地利用计算机的多核处理器和CPU时间&#xff0c;从而提高程序的性能和响应能力。 创建和使用Jav…...

“use strict“是什么? 使用它有什么优缺点?

严格模式 - JavaScript | MDN Javascript 严格模式详解 - 阮一峰的网络日志 1、"use strict" 是什么? "use strict" &#xff1a;指定代码在严格条件下执行&#xff1b; 2、 使用 "use strict" 有什么优缺点&#xff1f; ① 严格模式通过抛出错…...

【C++】C++11常用特性总结

哥们哥们&#xff0c;把书读烂&#xff0c;困在爱里是笨蛋&#xff01; 文章目录 一、统一的列表初始化1.统一的{}初始化2.std::initializer_list类型的初始化 二、简化声明的关键字1.decltype2.auto && nullptr 三、STL中的一些变化1.新增容器&#xff1a;array &…...

泛型——List 优于数组

数组与泛型有很大的不同&#xff1a; 1. 数组是协变的&#xff08;covariant&#xff09; 意思是&#xff1a;如果Sub是Super的子类型&#xff0c;则数组类型Sub[] 是数组类型Super[] 的子类型。 2. 泛型是不变的&#xff08;invariant&#xff09; 对于任何两种不同的类型Ty…...

JavaScript中对象的定义、引用和复制

JavaScript是一种广泛使用的脚本语言&#xff0c;其设计理念是面向对象的范式。在JavaScript中&#xff0c;对象就是一系列属性的集合&#xff0c;每个属性包含一个名称和一个值。属性的值可以是基本数据类型、对象类型或函数类型&#xff0c;这些类型的值相互之间有着不同的特…...

JavaScript通过函数异常处理来输入圆的半径,输出圆的面积的代码

以下为实现通过函数异常处理来输入圆的半径&#xff0c;输出圆的面积的代码和运行截图 目录 前言 一、通过函数异常处理来输入圆的半径&#xff0c;输出圆的面积 1.1 运行流程及思想 1.2 代码段 1.3 JavaScript语句代码 1.4 运行截图 前言 1.若有选择&#xff0c;您可以…...

Ubuntu 安装 Mysql

主要内容 本文主要是实现在虚拟机 Ubuntu 18.04 成功安装 MySQL 5.7&#xff0c;并实现远程访问功能&#xff0c;以 windows 下客户端访问虚拟机上的 mysql 数据库。 1. 切换至 root 用户 &#xff0c;shell 终端指令均执行在 root 用户下 sudo su 2. 安装并设置 mysql 安…...

【五一创作】【Midjourney】Midjourney 连续性人物创作 ② ( 获取大图和 Seed 随机种子 | 通过 seed 随机种子生成类似图像 )

文章目录 一、获取大图和 Seed 随机种子二、通过 seed 种子生成类似图像 一、获取大图和 Seed 随机种子 注意 : 一定是使用 U 按钮 , 在生成的大图的基础上 , 添加 信封 表情 , 才能获取该大图的 Seed 种子编码 ; 在上一篇博客生成图像的基础上 , 点击 U3 获取第三张图的大图 ;…...

分布式事务 --- Seata事务模式、高可用

一、事务模式 1.1、XA模式 XA 规范 是 X/Open 组织定义的分布式事务处理&#xff08;DTP&#xff0c;Distributed Transaction Processing&#xff09;标准&#xff0c;XA 规范 描述了全局的TM与局部的RM之间的接口&#xff0c;几乎所有主流的数据库都对 XA 规范 提供了支持。…...

SQL(基础)

DDL: 数据定义语言 Definition&#xff0c;用来定义数据库对象&#xff08;数据库、表、字段&#xff09;CREATE、DROP、ALTER DML: 数据操作语言 Manipulation&#xff0c;用来对数据库表中的数据进行增删改 INSERT、UPDATE、DELETE 注意&#xff1a; DDL是改变表的结构 DML…...

「OceanBase 4.1 体验」OceanBase 4.1社区版的部署及使用体验

「OceanBase 4.1 体验」OceanBase 4.1社区版的部署及使用体验 一、前言1.1 本次实践介绍1.2 本次实践目的 二、准备环境资源2.1 部署前需准备工作2.2 本地环境规划 三、部署Docker环境3.1 安装Docker3.2 配置Docker镜像加速3.3 开启路由转发3.4 重启Docker服务 四、检查本地Doc…...

计算机操作系统实验:银行家算法模拟

目录 前言实验目的实验内容实验原理实验过程代码如下代码详解算法过程运行结果 总结 前言 本文是计算机操作系统实验的一部分&#xff0c;主要介绍了银行家算法的原理和实现。银行家算法是一种用于解决多个进程对多种资源的竞争和分配的算法&#xff0c;它可以避免死锁和资源浪…...

机器学习:多项式拟合分析中国温度变化与温室气体排放量的时序数据

文章目录 1、前言2、定义及公式3、案例代码1、数据解析2、绘制散点图3、多项式回归、拟合4、注意事项 1、前言 ​ 当分析数据时&#xff0c;如果我们找的不是直线或者超平面&#xff0c;而是一条曲线&#xff0c;那么就可以用多项式回归来分析和预测。 2、定义及公式 ​ 多项…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...