请大伙看看这道很简单的华为 OD 算法题是不是描述的不清楚？

昨晚半夜参加了一下华为 OD 的机试，直接挂了。我感觉有一题描述的有问题，我做题是愣是没能找到一种逻辑能够通过示例，导致在这一题浪费了太多时间，最后还没通过用例，只能放弃这题。

不过没考过的主因不是这一题。试卷总共三题，两题 100 分，一题 200 分，这道题是 100 分的。主要是后面 200 分的题没做出来（后面我会描述下那个 200 分的题，大伙看下简单不简单。)，即使这题过了最多也就 200 分还是过不了，是我自己的问题，还需加倍努力。

这一题的描述如下（我考完从网上找的题，一模一样，可惜之前没刷到。）

按照自己的理解实现的，硬是没能通过用例，我还以为是我程序的 BUG 调了半天还是不对最后放弃。后面我去网上找到别人的题解，看明白后，心中一万个 CNM ，不知道是我开始理解的有问题，还是题目本来描述的就不好？？

5oiR5byA5aeL5oOz55qE5pivNTA9MSo1MO+8jDM2PTEqMzbvvIzov5nml7blgJnnspLluqbkuLox55qE6L+Y5YmpNDLkuKrvvIznhLblkI7nrKzkuInkuKrpnIDopoE2NO+8jOWImeebtOaOpeS7jjY0KjLph4zpnaLlj5bkuIDkuKrvvIznhLblkI4xMjjku44xMjgqMeWPluS4gOS4qu+8jOacgOWQjuS4gOS4qjEyN+WPluS4jeWIsO+8jOaJgOS7peaYrzTkuKp0cnVl5LiA5LiqZmFsc2XjgILogIPor5XlkI7nnIvkuobliKvkurrnmoTpopjop6PvvIznrKzkuIDkuKo1MO+8jOS4jeiDveS7jjHlj5Y1MOS4qu+8jOiAjOaYr+imgeS7jjY05Y+WMeS4quOAgue7iOS6juaYjueZveS6hu+8jOKAnOWGheWtmOS4jeiDveaLhuWIhuS9v+eUqOKAneeahOaEj+aAne+8jOaIkeeQhuino+aIkOS6huWBh+WmguesrOS4gOS4quS4ujEyOe+8jOS4jeiDvei/meagt+aLvDEqMTI4KzY0KjHmiJbogIUxKjY0KzY0KjHvvIzogIzlrp7pmYXkuIoxKjEyOOmDveaYr+mdnuazleeahOOAguWFs+mUrui/meS4qumimOebru+8jOekuuS+i+i+k+WFpei+k+WHuuayoeacieS4quino+mHiuOAgg==

然后是 200 分的第三题，抽象出来说就是有个长度为 N 的增序不重复字符数组，然后有个数字 K ，例如 arr=[0,1,2,3,4,5]，K=3 。找出数组下所有长度大于等于 K 的排列，并按照字典序输出，例如这一题，正确结果就是 012,0123,01234,012345,01235,0124,01245,0125,013,0134,...345

这题我思考了半天，感觉可以用递归做，但是没想出来递归条件，我准备上午不看答案，自己慢慢抠看看多久能抠出来。

msaionyc

2023-08-02 11:07:01 +08:00

@qwerthhusn
“所以，我取的是 64*2 。

但是看了题解才发现，1*12 ，64*2 ，128*2 都不允许，只允许 256 乘 1 。”

感觉你这是基础有点不牢了，正常情况程序去申请内存，比如申请 2M 的内存，但现在内存中未被占用的都是一堆 1M 的碎片，那肯定是无法满足这次内存分配了，只能 GC （把占用的内存块调整到连续的内存区域，让这些剩余的未被占用的形成一块连续的内存以达到可以分配的目的），或者报内存不足。这应该是个常识了

当然你问我为什么明明有两块 1M 的，加起来是 2M 符合条件，我可以简单解释一下，单次内存分配的结果是操作系统给程序返回了内存的首地址，让程序在这块内存里执行运算和存储，所以就算有多个小块可以满足容量总和符合的要求，但不是一个完整的块还是无法分配的。当然，我们都可以想到，让程序申请两次，但申请内存是系统调用，需要性能开销，而且有些程序结构，比如我一个 array 就是需要 2048k （假设），你让我分配两次，我没法做了。

算法题有很多都是有实际应用场景的，比如 LRU ，包括这题也是，哪怕不能 ac ，但是基本的思想还是应该明白的

另外，我没 diss 楼主你的意思，就事论事

lubanban

2023-08-02 14:07:56 +08:00

200 分的第三题
解决：回溯
public LinkedList<List<Integer>> res = new LinkedList<>(); // 结果
public LinkedList<Integer> track = new LinkedList<>(); // 记录路径

public void solution(int[] nums, int k) {
backtrack(nums, 0, k);
System.out.println(res.toString());
}

public void backtrack(int[] nums, int satrt, int k) {
// 所有长度大于等于 K 的排列
if (track.size() >= k) {
res.add(new LinkedList<>(track));
}
for (int i = satrt; i < nums.length; i++) {
track.add(nums[i]); // 做选择
backtrack(nums, i + 1, k); // 只选择 start 之后的值，通过 start 参数控制树枝的遍历
track.removeLast(); // 撤销选择
}
}

mingl0280

2023-08-02 16:03:21 +08:00

@msaionyc 你这个说法在 Linux 上对于连续的物理内存页的映射(kmalloc)是对的，对于 vmalloc 是错的。

vmalloc 可以一次性申请多个碎片块（不连续）的内存并映射到虚拟内存地址中，表现是进程空间的一个虚拟内存地址可以映射到不同大小不同位置的物理内存块中，例如申请一个 128K 的块，映射到物理内存里面实际上是 64K +32K+16K+16K 这样的（这只是一个例子）。

所以这个题真的描述没说清楚。