Find Elements in a Contaminated Binary Tree
给一个二叉树, 里面全是-1, 返回一个二叉树, root是0, root.left = 2 * root.val + 1, root.right = 2 * root.val + 2 . 这个就直接写就好了
December 2019
Greatest Sum Divisible by Three
给一个数组, 求用其中的数组成的最大的和能被3整除. 这个题是dp题, 设max[i]为余数等于i的组成的最大数的数. 那么我们每个数都试一下, 看看他的余数和max[i]组成的新数组cur[i]是否比以前大. 通过不断更新max[i]找到答案. 现在的问题就变成了, 如何找到状态转移方程式, 这里, 我们想要的状态方程是找到新的max和旧的cur的关系. 这个关系是当我们遇到一个新的数字的时候, 我们更新那些数字呢? 通过观察我们知道, 当我们遇到一个新的数字, 我们需要更新这个数字的余数+数组的余数后, 新的数所在的值. 即cur[(i + n) % 3] = Math.max(max[(i + n) % 3], max[i] + n) where i = 1..k
Minimum Time Visiting All Points
给一个2d数组,表示坐标轴的点, 问最少时间走过每个点, 可以走对角线. 这个题因为可以走对角线,所以我们充分利用这个优势, 走对角线的数学意义是x可以和y一起加减, 所以两个点之间用的时间就是x轴和y轴坐标差较大的那个. 如果一样大,两个点就共线了.
Sample Sale已经无所不能了
nyc的sample sale已经慢慢把魔爪伸向各大品牌, Moncler, LV, 羊绒王, Thom Browne. 啥都sample sale, 商家已经毫无底线的卖货了, 二手贩子, 现场黄牛坐地起价出门就卖, 已经疯狂的一批. 今年我收了一个moncler fragment的长款大衣 , 两件Brunello Cucinelli的毛衣, 一个moncler fragment的hoodie. 我就想看看这几个啥时候也进sample sale. 对了, 老婆收了个moncler的大衣, 普通长款, 在nm买的, 那个款式, 我感觉应该正在去sample sale的路上.
Maximum Side Length of a Square with Sum Less than or Equal to Threshold
给一个2d数组, 给一个数threshold. 返回最大的square的边长, 能让里面的数字和等于或者小于 threshold. 这个题主要考察presum的范围理解, 我们用presum的时候,因为扫描数组是从左往右从上到下, 所以我们想用squares的范围的时候, 需要减去重复的部分. 比如, sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] – sum[i][j] + mat[i][j]; 而不能单纯的sum[i+1][j+1] + mat[i][j] 同理, 当我们检查是否有新的max的时候, 也是用这个方法. 我看到答案里面有别的做法, 比如用二分搜索+测试, 我觉得没必要, 因为复杂度不可能少于O(M*N), 因为不看到最后一个, 怎么知道是不是有可能有最大的square.
Convert Binary Number in a Linked List to Integer
用一个list表示二进制的数, 返回它的十进制表示.
美国住房趣事之割草
我家的草地面积分成两个部分, 一个是屋子前的左右两侧草地, 另一个是后花园的草地. 后边的草地虽然面大, 但是很平整, 用割草机很快的搞定, 屋前的草地则不然. 屋子前边的草地分左右两侧, 左边的草地上有变电箱加一个小树加邻居的一些杂物. 每次割草, 割草机推不了几下就进不去了, 大部分的还是要用edge trimmer去一点点割掉. 右侧的草地是有一个mailbox, 因为邮递员叔叔每天都要投递邮件, 所以那边的草地格外的要平整, 所以每次割完了也要trim一下. 割草完了后, 以前就把割掉的草扔到垃圾回收中心的袋子里, 然后收垃圾的每周四会收走, 后来看看邻居大爷大妈都是直接割到草地上, 也没人管杂草, 全靠风吹…那帮大爷大妈很懒, 秋天叶子靠风吹, 夏天杂草靠风吹.. 所以最后我也就直接扔地上了..
Count Servers that Communicate
给一个2d的0,1数组, 每个点表示一个服务器, 它的列和行上有其他服务器就Communicate, 问有多少个. 先记录一下每行有几个, 每列有几个, 然后就直接写就出来了.
Search Suggestions System
给一个字符串数组, 里面是products, 给一个searchword, 求写一个推荐系统. 这个用treeset来做, 注意两个特殊情况, 一个是第一位就不匹配的时候, 就别推荐了… 一个是treeset的highkey和lowkey不能判断字符串的匹配, 他们只是判断字典序的顺序, 需要多加一句匹配判断.