Split ways
这是一个Google的OA题. 给一个string, 问通过切分后, 左边string和右边string的unique的char的个数相同, 这样的切分有几个? 说切分, 其实就是counting问题, 先counting一下unique char的个数, 然后再次counting一遍, 从左往右扫, 做切分.
July 2020
Min Amplitude
这是一道google的oa题, 给一个数组, 通过改变三个数后, 使得数组最大值和最小值的差, 最小. 狗家的题都是先观察, 然后再coding, 主要是找到好的思路. 这题也是这样, 首先观察我们可以使用的操作, 就是改变数组中任意的三个数. 因为最后求最值的差, 所以这三个数的选择肯定是选择和最值有关的数. 首先排序一下, 然后找到两头(最大数列,和最小数列). 发现因为只有三个数可以改变, 那么改变后的最值肯定出在以下几种情况: 改变了最小的三个值, 答案= 第四小的值与最大值的差…由此类推即可发现答案有四种可能. 具体实现上, 因为要找到最大的四个数和最小的四个数, 可以sort, 也可以用priority queue.
Employee Free Time
给一个2d数组, 求所有employee的空闲时间. 这个题, 我用的优先队列解的, 但是code很长, 看了solution后, 觉得解法很巧妙, 而且很通用. solution用的是线性扫描, 其中的关键理论是: interval之间有几种情况: 半重叠, 完全重叠和分开, 那么前两种可以作为一种, 通过设计一个balance的variable, track两个interval的start和end就可以, 最后只需要找到分开的interval之间的空隙即可.
Design HashMap
设计一个hashmap, 注意冲突即可.
Valid Palindrome II
给一个字符串问是否能通过删除最多一个字符后变成palindrome. 先写一个check回文的方法, 然后找到不对称的地方, 这时候已经知道要删除一个字符, 所以主要看删除后是否有可能变成回文即可.
Shuffle the Array
给一个array, 一共2n个元素, 求重组后的array, 让前n个元素和后n个元素互相交叉.
Subtree of Another Tree
给一个树, 求另外一个树是不是这个树的子树. 先写一个方法判断isSameTree, 然后遍历即可.
Decode String
给一个k[str]格式的string, 变成decode后k个str, 求decode后的string. 这题主要是case要想全, 并且str里面不会有数字, 这个很关键, 就是只要有数字就是k[str]格式, 那么就简单多了. 我看到有人用stack,我觉得没必要吧….
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
给一个数组, 和一个数, 求数组的子数组最大的长度,使其中的元素的绝对值不大于这个数. 简单的双指针遍历, 注意一下边界.