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

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

Unity3D中Gfx.WaitForPresent优化方案

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

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

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

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

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

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

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

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

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