Menu Sidebar
Menu

Count Positions on Street With Required Brightness

给一个数组,里面是灯能覆盖的范围, 给一个数组, 里面是requirement, 求有多少个位置的灯meet requirement.

这题就是range addition升级版, 因为要考虑inclusive的覆盖问题,所以建数组的时候, 我们多加一个数. 这样相当于把数组扩展了1位.

Lexicographically Smallest Equivalent String

给两个字符串, 长度一样, 是字符对应的mapping, 给一个字符串, 求mapping后字典序最小的结果.

典型的并查集模板题.

Can I Win

给两个数组,a和b, 两个人从[1,a]的正整数轮流取数, 不能取相同的数字, 不能取了就算输了, 两个人都是选择自己最佳方案, 求胜负.

看似博弈论, 起始就是便利所有可能, 没有优化的地方.

这题傻逼在于, 它非要让状态压缩, 就tm一个最大32个数字的boolean数组, 非让用bitmask压一下表示状态, 不然就TLE, 我真是服了

Range Addition

给一个长度为length的数组和一个update[from, to, val]query. 求跑完query的结果.

这题用一个diff数组记录变化的起始和结果的地方, 这里可以看成累计频率的记录. 所以在结果的时候要把累积多余的val减去.

Sort Integers by The Power Value

给一个数字n, 按照以下处理后, 求结果第k个大的数字是什么.

  • if x is even then x = x / 2
  • if x is odd then x = 3 * x + 1

肯定要算下的, 用memo算下, 然后建个map存下, 然后排序, 然后找第k个.

Airplane Seat Assignment Probability

给n个人, 坐n个座位, 第一个人随机选, 问第n个人坐到自己座位的概率.

这题就多写几个例子就行了

Number of Visible People in a Queue

给一个数组, 求返回一个数组, 是当前数字往右看到所有的数字的数量.

好吧..有点费劲, 上来能反应过来是单调栈, 然后实现发现怎么也过不了, 原来题意中定义的看到不是说小于当前数,而是问有多少递增的数字. 比如[11,2,1,12]中, 11能看到的只有2和12…..1是看不到的..被2挡住了

Binary Search Tree Iterator II

给一个BST做遍历器.

这题吧, 我答案又不用额外数组的…我做了做实在难…

Number of Good Ways to Split a String

给一个字符串s, 求有多少种分割方法, 让分割的两个字符串的不同字符数量相同.

Range Sum Query 2D – Immutable

也是2d fenwick树.

Newer Posts
Older Posts

书脊

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

December 2022
M T W T F S S
 1234
567891011
12131415161718
19202122232425
262728293031