Menu Sidebar
Menu

Archive: October 8, 2019

Set Mismatch

给一个数组, 里面是从1到n, 但是有一个元素重复, 并且少一个元素, 找到重复的和丢失的数. 这个我用的是map 存一下找到了几个数, 我看有很多做法, 这个属于一般的解法.

Trim a Binary Search Tree

给一个BST, 然后给一个L和R两个整数, 给BST剪枝(trim), 问剪枝后的树. 这个题很有意思, 首先要理解剪枝这个操作, 仅仅是针对当前node的. 而对于node的子树,需要重新判断, 那么这个题就是一个子问题划分的题, 我们要通过递归不断把问题分解. 通过观察example, 我们可以看出, node.val如果大于R, 那么node的右边的子树都大于R, 那么都应该剪掉, 所以返回node的左边, 并且继续子问题探索. 同理对node.val小于R的情况. 如果node.val在L和R之间, 那么我们只需要继续分开讨论左边和右边子问题即可.

书脊

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