Menu Sidebar
Menu

Adding Two Negabinary Numbers

给两个以-2为base的数字, 用数字表示, 求他们的合. 这个题和adding binary number那个题一样.

Smallest Sufficient Team

给一个数组, 里面是完成一个任务需要的技能, 另一个数组是每个人有的技能, 求完成任务的最少人的数组. 这个题是一个set cover问题, 因为set cover的k决定性问题是NPC, 但是set cover本身不是, 所以这个题应该可以在多项式时间内解决. 首先hints中提示了要做bit编码, 那么就用过反转index,找到每个skill对应的数字, 然后通过左移(<<)标记在int中. 然后就是算法部分. 通过hint2得知, 这题是类似于背包问题的dp问题, 所以我们用一个loop扫描每个人, 然后用一个数组装所有可能的需要完成任务的技能的combination, 比如n个需要的技能, 那么就是 1 << 个位置. 所以我们的答案就在all[(1<<n) – 1]这个位置上.我们比较每个可能技能下的需要的人数, 就可以得知这种组合下的人的最优解(人数最少).

最后要解决的问题是, 如何匹配组合的技能和人的技能.int comb = k | pSkill; k遍历所有的技能, 然后通过与运算和pSkill进行匹配. 对技能的编码如下: {"java":0,"nodejs":1,"reactjs":2} ,

而pSkill的编码比如people: [["java","nodejs","reactjs"]] 编码为111. 即表示这个人会所有技能, 那么如果是 people: [["java","reactjs"]], 编码为101,

k则从1一直遍历到1 << 3,也就是7(111), 这样可以覆盖所有可能的组合, 我们通过k一直update每个人的技能与当前team的匹配结果, 最后得出答案.

Building H2O

多线程的题, 给两个方法, 一边是h一边是o, 问如何即时返回水(h2o). 通过观察可以看到, 水是两个h一个o, 那么当一个o出现的时候, 我们就检查是否有两个h. 当h不够2的时候, 就等h够2再继续运行. 所以一个互斥锁即可.

Check If It Is a Straight Line

给一个数组, 里面是点, 问这些点在不在一个直线上. 这个题要用斜率公式算, y=ax+b, where (x,y) from array. 先用一组算出a, 然后再算b.

Remove Covered Intervals

给一个数组, 里面是intervals, 求移除所有重叠的intervals后, 数组里面元素的个数. 这个题先排序一下, 然后比较intervals的end值即可.

Find Numbers with Even Number of Digits

给一个数组, 找到里面位数为偶数的数字的个数.

Iterator for Combination

写一个Iterator遍历长度为k的n个字符的组合. 这个题就是把Combination写成api. 所以先算出k个n的comb, 然后就直接输出

Sum of Mutated Array Closest to Target

给一个数组和一个target, 求一个数字n, 把数组中所有大于n的数字都替换成n以后, 数组的和与target最接近. 这个题是找最接近target的一个数字n, 那么用二叉搜索找即可, 设lo是0, hi是target, 那么mid就是中间假设的答案, 这个答案可以通过题意的改变数组后, 找到和target的差值, 因为我们知道mid是单调递增的, 所以可以用二叉搜索.

Decompress Run-Length Encoded List

给一个数组, 里面是一对对的数, 偶数位的数字表示频率, 奇数位的数字表示前一个偶数位的值. 求原始数组.

Matrix Block Sum

给一个2d数组和一个k, 求k的范围内的和. 这个题和range sum的那个一样的结构, 只是query部分稍加改动. 附上一个答案里很简练的做法.

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.