一、題目大意
標簽: 分治
https://leetcode.cn/problems/beautiful-array
對于某些固定的 N，如果陣列 A 是整數 1, 2, ..., N 組成的排列，使得：
對于每個 i < j，都不存在 k 滿足 i < k < j 使得 A[k] * 2 = A[i] + A[j]，
那么陣列 A 是漂亮陣列，
給定 N，回傳任意漂亮陣列 A（保證存在一個），
示例 1：
輸入：4
輸出：[2,1,4,3]
示例 2：
輸入：5
輸出：[3,1,2,5,4]
提示：
- 1 <= N <= 1000
二、解題思路
題解參考：https://www.cnblogs.com/grandyang/p/12287146.html
分治法，按奇偶來分的話，因為奇數加偶數等于奇數，就不會是任何一個數字的2倍了，這就是奇偶分堆的好處，這時任意兩個數字肯定不能分別從奇偶堆里取了，那可能你會問，奇數堆會不會有三個奇數打破這個規則呢？只要這個奇數堆是從一個漂亮陣列按固定的規則變化而來的，就能保證一定也是漂亮陣列，因為對于任意一個漂亮陣列，若對每個數字都加上一個相同的數字，或者都乘上一個相同的數字，則一定還是漂亮陣列，因為數字的之間的內在關系并沒有改變，明白了上面這些，基本就可以解題了，假設此時已經有了一個長度為n的漂亮陣列，如何將其擴大呢？可以將其中每個數字都乘以2并加1，就都會變成奇數，并且這個奇數陣列還是漂亮的，然后再將每個數字都乘以2，那么都會變成偶數，并且這個偶數陣列還是漂亮的，兩個陣列拼接起來，就會得到一個長度為 2n 的漂亮陣列，就是這種思路，可以從1開始，1本身就是一個漂亮陣列，然后將其擴大，注意這里要卡一個N，不能讓擴大的陣列長度超過N，只要在變為奇數和偶數時加個判定就行了，將不大于N的陣列加入到新的陣列中
三、解題方法
3.1 Java實作
public class Solution {
public int[] beautifulArray(int n) {
List<Integer> ans = new ArrayList<>();
ans.add(1);
while (ans.size() < n) {
List<Integer> t = new ArrayList<>();
for (int num : ans) {
if (num * 2 - 1 <= n) {
t.add(num * 2 - 1);
}
}
for (int num : ans) {
if (num * 2 <= n) {
t.add(num * 2);
}
}
ans = t;
}
return ans.stream() .mapToInt(Integer::intValue) .toArray();
}
}
四、總結小記
- 2022/7/9 洗衣服滌不干會有味
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498635.html
標籤：其他
上一篇：【學習筆記】網路流