当前位置: 首页 > 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、定义及公式 ​ 多项…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...