【月度刷題計劃同款】常規(guī)"腦筋急轉彎"類構造題

## 題目描述這是 LeetCode 上的 **[667. 優(yōu)美的排列 II](https://leetcode.cn/problems/beautiful-arrangement-ii/solution/by-ac_oier-lyns/)** 蠢护，難度為 **中等**。 Tag : 「構造」养涮、「腦筋急轉彎」給你兩個整數(shù) `n` 和 `k` 葵硕，請你構造一個答案列表 `answer`眉抬，該列表應當包含從 `1` 到 `n` 的 `n` 個不同正整數(shù)，并同時滿足下述條件：假設該列表是 $answer =?[a_1, a_2, a_3, ... , a_n]$ 懈凹，那么列表 $[|a_1 - a_2|, |a_2 - a_3|, |a_3 - a_4|, ... , |a_{n-1} - a_n|]$ 中應該有且僅有 k 個不同整數(shù)蜀变。返回列表 `answer`。如果存在多種答案介评，只需返回其中任意一種库北。示例 1： ``` 輸入：n = 3, k = 1 輸出：[1, 2, 3] 解釋：[1, 2, 3] 包含 3 個范圍在 1-3 的不同整數(shù)，并且 [1, 1] 中有且僅有 1 個不同整數(shù)：1 ``` 示例 2： ``` 輸入：n = 3, k = 2 輸出：[1, 3, 2] 解釋：[1, 3, 2] 包含 3 個范圍在 1-3 的不同整數(shù)们陆，并且 [2, 1] 中有且僅有 2 個不同整數(shù)：1 和 2 ``` 提示： * $1 <= k < n <= 10^4$ ## 構造給定范圍在 $[1, n]$ 的 $n$ 個數(shù)寒瓦，當「直接升序/降序」排列時，相鄰項差值為 $1$坪仇，僅一種杂腰；而從首位開始按照「升序」間隔排列，次位開始按照「降序」間隔排列（即排列為 `[1, n, 2, n - 1, 3, ...]`）時椅文，相鄰差值會從 $n - 1$ 開始遞減至 $1$喂很，共 $n - 1$ 種。那么當我們需要構造 $k$ 種序列時皆刺，我們可以先通過「直接升序」的方式構造出若干個 $1$少辣，然后再通過「間隔位分別升降序」的方式構造出從 $k$ 到 $1$ 的差值，共 $k$ 個羡蛾。顯然漓帅，我們需要 $k + 1$ 個數(shù)來構造出 $k$ 個差值。因此我們可以先從 $1$ 開始，使用 $n - (k + 1)$ 個數(shù)來直接升序（通過方式一構造出若干個 $1$），然后從 $n - k$ 開始間隔升序排列嵌施，按照 $n$ 開始間隔降序排列，構造出剩下的序列豪直。 Java 代碼： ```Java class Solution { public int[] constructArray(int n, int k) { int[] ans = new int[n]; int t = n - k - 1; for (int i = 0; i < t; i++) ans[i] = i + 1; for (int i = t, a = n - k, b = n; i < n; ) { ans[i++] = a++; if (i < n) ans[i++] = b--; } return ans; } } ``` TypeScript 代碼： ```TypeScript function constructArray(n: number, k: number): number[] { const ans = new Array(n).fill(0) const t = n - k - 1 for (let i = 0; i < t; i++) ans[i] = i + 1 for (let i = t, a = n - k, b = n; i < n; ) { ans[i++] = a++ if (i < n) ans[i++] = b-- } return ans }; ``` * 時間復雜度：$O(n)$ * 空間復雜度：$O(n)$ ## 最后這是我們「刷穿 LeetCode」系列文章的第 `No.667` 篇，系列開始于 2021/01/01珠移，截止于起始日 LeetCode 上共有 1916 道題目弓乙，部分是有鎖題，我們將先把所有不帶鎖的題目刷完钧惧。在這個系列文章里面暇韧，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼浓瞪。如果涉及通解還會相應的代碼模板懈玻。為了方便各位同學能夠電腦上進行調試和提交代碼，我建立了相關的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 乾颁。在倉庫地址里涂乌，你可以看到系列文章的題解鏈接艺栈、系列文章的相應代碼、LeetCode 原題鏈接和其他優(yōu)選題解湾盒。更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的 [合集新基地](https://www.acoier.com/archives/) ????

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者

人面猴
序言：七十年代末湿右，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子罚勾，更是在濱河造成了極大的恐慌毅人，老刑警劉巖，帶你破解...
沈念sama閱讀 221,430評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件尖殃，死亡現(xiàn)場離奇詭異丈莺，居然都是意外死亡，警方通過查閱死者的電腦和手機分衫，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,406評論 3贊 398
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門场刑，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人蚪战，你說我怎么就攤上這事☆戆茫” “怎么了邀桑？”我有些...
開封第一講書人閱讀 167,834評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長科乎。經(jīng)常有香客問我壁畸，道長，這世上最難降的妖魔是什么茅茂？我笑而不...
開封第一講書人閱讀 59,543評論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任捏萍，我火速辦了婚禮，結果婚禮上空闲，老公的妹妹穿的比我還像新娘令杈。我一直安慰自己，他們只是感情好碴倾，可當我...
茶點故事閱讀 68,547評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布逗噩。她就那樣靜靜地躺著，像睡著了一般跌榔。火紅的嫁衣襯著肌膚如雪异雁。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,196評論 1贊 308
城市分裂傳說
那天僧须，我揣著相機與錄音纲刀，去河邊找鬼。笑死担平，一個胖子當著我的面吹牛示绊，可吹牛的內容都是我干的锭部。我是一名探鬼主播，決...
沈念sama閱讀 40,776評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼耻台，長吁一口氣：“原來是場噩夢啊……” “哼空免！你這毒婦竟也來了？” 一聲冷哼從身側響起盆耽，我...
開封第一講書人閱讀 39,671評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤蹋砚，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后摄杂，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體坝咐，經(jīng)...
沈念sama閱讀 46,221評論 1贊 320
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 38,303評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年析恢，在試婚紗的時候發(fā)現(xiàn)自己被綠了墨坚。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 40,444評論 1贊 352
活死人
序言：一個原本活蹦亂跳的男人離奇死亡映挂，死狀恐怖泽篮，靈堂內的尸體忽然破棺而出，到底是詐尸還是另有隱情柑船，我是刑警寧澤帽撑，帶...
沈念sama閱讀 36,134評論 5贊 350
?日本核電站爆炸內幕
正文年R本政府宣布，位于F島的核電站鞍时，受9級特大地震影響亏拉，放射性物質發(fā)生泄漏。R本人自食惡果不足惜逆巍，卻給世界環(huán)境...
茶點故事閱讀 41,810評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一及塘、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧锐极，春花似錦笙僚、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,285評論 0贊 24
一樁弒父案味咳，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至檬嘀，卻和暖如春槽驶，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背鸳兽。一陣腳步聲響...
開封第一講書人閱讀 33,399評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工掂铐，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人。一個月前我還...
沈念sama閱讀 48,837評論 3贊 376
代替公主和親
正文我出身青樓全陨，卻偏偏與公主長得像爆班，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子辱姨，可洞房花燭夜當晚...
茶點故事閱讀 45,455評論 2贊 359

【月度刷題計劃同款】常規(guī)"腦筋急轉彎"類構造題

推薦閱讀更多精彩內容