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

[qwerthhusn]

昨晚半夜参加了一下华为 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

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

看了各位的发言，我也悟了，就是自己的问题。

针对这个“描述不清晰”的题，确实自己理解的不对。但是这题描述不清晰我觉得没法洗，而且示例也没有解释，直接一个输入输出结束。我之前刷过小部分华为 OD 的题，感觉大部分都挺简单的，不过有部分确实“我瞅半天也理解不明白”，不过一般根据示例说明也能猜出来。。奈何这次运气不好，题目对我来说描述不清晰，题目中的示例也没有任何解释。

针对那个 200 分的题：完全就是刷的题不够多，平时不刷题。。只有刷的够多了，常用的算法思想和应用场景才能知道，常见的题型才能信手拈来。不过也有运气不好，我又看了几道 200 分的题，很多都能通过简单算法暴力破解拿个保底分，但是这题由于 k 不固定，导致想暴力都不好写。

这次挂了之后，我都在想是继续深入背八股文还是继续刷算法题。

现在是失业状态，感觉现在才开始刷 DSA 是不是来不及了？还不如直接深入八股文，找一些不考算法的公司。。

**强烈建议目前未毕业的不刷算法的同学把算法题刷起来，如果会数据结构和算法感觉机会多一点，外面太卷了。我极其后悔当初在舒适区的时候不看算法，不学习，只能被动接受被淘汰的命运！**

[idealhs]

没关系，华为 OD 不是人干的

[zydxn]

我觉得描述没什么问题，内存信息存到 treemap 里就完了

[msaionyc]

第一题描述的很清楚了吧。就一堆内存，容量和数量都给了，然后有用户来申请，你要给他分配大于等于他申请容量的内存，每块内存只能用一次。能完成该次分配就 true ，否则 false 。

[sobev]

第二题应该是全排列吧 leetcode 有

[mingl0280]

第一个确实描述有问题，不是“内存不能拆分使用”，而是“每次申请的块必须完整地大于申请的内存大小”

[bitkuang8]

op 面啥岗的

[linauror]

第二题试着用 go 写了一下，暂不考虑特殊情况
```
arr := []int{0, 1, 2, 3, 4, 5}
k := 3
var newArr [][]int
for i := 0; i < len(arr)-k+1; i++ {
for j := k + i; j <= len(arr); j++ {
newArr = append(newArr, arr[i:j])
}
}
fmt.Println(newArr)
```

输出：[[0 1 2] [0 1 2 3] [0 1 2 3 4] [0 1 2 3 4 5] [1 2 3] [1 2 3 4] [1 2 3 4 5] [2 3 4] [2 3 4 5] [3 4 5]]

[linauror]

算了，忽略上面的代码，只考虑了连续...

[aibx01]

可以找 hr 要一下题，先刷。刷完再约机考。

[avadakur]

内存不能拆违使用？那可以合并使用吗？ 1:128 这个 128 个粒度为 1 的节点都分给一个用户

[iOCZ]

200 分这题用回溯算法，在最后判断下长度，大于等于 K 就加入结果，否则就抛弃。

void xxxxx(vector<int> &arr, int k){
vector<string> ans;
string current;


auto backtrace = [](vector<int> &arr, string &current, int index){
if(index == arr.size()){
if(current.size()>=k){
ans.push_back(current);
}
return;
}
for(int i = index; i<arr.size();i++){
current.push_back(arr[i]);
backtrace(arr,current,index+1);
current.pop_back();
backtrace(arr,current,index+1);
}
}

backtrace(arr,current,0);
}

[Abmcar]

od 的题确实好多问题
有的题纯思维题，但是题目写的很不正规，比如 op 的这个
还有的题用例都有问题，逆天格式错误或者超题目描述的范围
还有的题一看就是之前搞竞赛出的，难得一 b ，比如《核&酸检测》，很少能写出来


不过现在新题库大部分题都是基础的题，感觉最难也就 lc 周赛 t3 这种难度，平时多刷点题，不说 350,150 肯定没啥问题

像这个 t3 ，基本就是 dfs 板子题，写的多了不用动脑子 10min 都能写完，还是待多练练

[qwerthhusn]

@avadakur 我做的就是这样的，
比如 1 的 128 个，64 的 2 个，128 的 2 个，256 的 1 个。现在想要申请 129 内存。

我理解的内存不能拆开使用，意味着，不能从 1 的池取 128 个，64 的池取一个。（如果允许的话，估计会更难，就是取 1*128+1*64 还是 1*1+64*2 ？？情况复杂点，这是个变种的背包问题了。）

所以，我取的是 64*2 。

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

然后再揣摩了“内存不能拆分使用”的意思实际上是：我申请 N 个内存，不能用多个源中获取，源的意思，128*2 说明有两个 128 ，每一个都是一个源，不能同时从两个源获取。

[iOCZ]

修改两处 current.push_back(to_string(arr[i]));
删除后一处 backtrace(arr,current,index+1);

[jincsheng]

第一题我个人感觉题目描述的是比较清楚的，也符合实际的内存分配的机制和原理。实际的内存区域就是一些不可分割的最小块。

[qwerthhusn]

@bitkuang8 不知道啥岗，就是华为 OD 外包岗，最近 boss 好多华为 OD 的 HR 主动 M 我，随便接了一个，刷了些题，然后未命中之前刷的，就 G 了。

[qwerthhusn]

@Abmcar 层主所言极是，确实是刷的少了，之前上班在舒适区待久了，上班 CRUD 下班游戏爱奇艺。现在毕业了，再临阵抱佛脚感觉有点来不及。

对于没接触过的或者接触很少的题型，或者各种常用的算法思想和应用场景没熟悉一遍，除非天赋异禀，不然临时去思考很难短时间内想出来个方案并实现成功。

[iOCZ]

@qwerthhusn 楼主应该是没有看过 Unix 内核的 malloc 实现，那个是 first in ，就是第一块符合大小的。跟这个有点区别，但是相同的是分配内存不能跨越不同区块，要不然管理起来会非常麻烦。这里有个疑问，如果分配大内存该如何处理。

[LandCruiser]

到底优先分配粒度小的，还是有限分配申请时间早的

[MoYi123]

第三题最简单的写法应该是这样的

ls = [1, 2, 3, 4, 5]
k = 3

for i in range(1 << len(ls)):
____if bin(i).count('1') >= 3:
________tmp = []
________for bit in range(len(ls)):
____________if (i >> bit) & 1:
________________tmp.append(ls[bit])
________print(tmp)

[iOCZ]

根据我的理解，这个内存分配更像是用户空间的行为，malloc 向系统申请内存的时候，会通过 sbrk 来返回一块较大的内存，用户空间就会有很多大小不同的碎片可供使用，不够的时候才继续向系统申请。如果要更大的内存，就要使用 mmap 了。

[Ericality]

只能说我一开始理解的和他说的是同一个意思 因为如果像 op 那样的理解的话 实际上内存细粒度就没有实际意义: 如果可以组合使用 那这所有的细粒度都能串联在一起 除非超过上限 就不存在分配失败问题了 也违背了内存不能拆分使用的原则
不过有时候题目描述确实会不清晰 这时候可以考虑用示例结果反推题目的意思

[UN2758]

dfs,分支返回条件检查一下当前结果长度就好了

[msaionyc]

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

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

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

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

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

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

[chendl111]

第一题感觉用优先队列，第三题用 dfs 搜一遍感觉

[lubanban]

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(); // 撤销选择
}
}

[tangtj]

刷过题就会,没刷过就不会.

[mingl0280]

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

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

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

[learningman]

第 1 个还有个最优化问题，是不是得拿背包跑

[DICK23]

第一题感觉没啥理解问题，就是取可选值，资源存在并大于所需值即可，否则就返回 false.
第二题全排列，直接筛掉长度不符的就是答案，可以倒着查找答案

[gogo789]

“内存不能拆分使用”，这个确实是太有歧义了，我写的时候也是错了。leetcode 的测试示例都有计算过程的文字描述，他这个没有，确实是垃圾