乐趣区

关于leetcode:leetcode-932-Beautiful-Array-漂亮数组中等

一、题目粗心

标签: 分治

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 洗衣服涤不干会有味
退出移动版