Biweekly Contest 90
简单分享一下思路
1.建一个 dict 把转出来的 list 当 key，原字串 append 进他的 value
python 没办法把 list 直接当 key 要先转成 tuple <- 我竟然今天才知道可以这样...
写的时候用了很白痴的 hash function
最后看哪个 len(value) == 1 就好
2.看到 size 这么小就直接暴力法了 O(n^3)
字和字比对的方法就是看 a[i] != b[i] 的数量有没有大于 2
3.看 Example 1 的例子应该很容易能想到跟余数有关
把 nums[i]%space 同样的元素放在一堆 看哪一堆最多元素
也是用 dict 就能解决
4.先看 size 感觉会是 O(n) 或 O(nlog(n)) 的算法
看 Example 1 的 output 就感觉可能会用到 monotonic stack
一次想出 second greater 的版本可能有点困难
可以先想要怎么找出每个元素右边比他大的第一个元素
如果 nums[i] < nums[i+1] 那 nums[i] 的答案就直接出来了
如果 nums[i] > nums[i+1] 那就代表 nums[i] 要先存起来等 看看后面有没有人比他大
所以可以维护一个递减的 stack 每次检查 nums[i] 有没有大于 stack[-1]
不停 pop 直到 stack[-1] > nums[i] 或是 stack 空了
最后再把 nums[i] append 到 stack 里
这样是 first greater 的版本
接下来就可以接着想怎么改成 second greater 的版本
上面 stack pop 的时候有什么意义 差不多就提示到这
懂的都懂 不懂的我也不好说太多 说了你也不懂
细细品吧