Menu Sidebar
Menu

Search in a Sorted Array of Unknown Size

给一个api,输入一个index, 返回元素值, 问怎么用这个api在一个不知道大小(并不是无限大)的已排序的数组上做二叉搜索.

二叉肯定要有右边的大小, 所以问题变成怎么快速找到右边的值, 用二次倍增法找

Binary Tree Pruning

给一个二叉树, 求删除值为0并且左右两边都是nullptr的分支.

Diameter of N-Ary Tree

给一个n-ary的树, 求周长. 就是任意两个node之间的最长距离, 可以不经过root.

最长的路径出现在两个情况, 情况一是路径经过node, 那么就是左右两边的最长路径相加, 要不然就是一侧,就是最长路径. 所以要求出最长路径和次长路径, 然后比较一下.

Find All Duplicates in an Array

给一个数组, 里面的数字出现一次或者两次, 求出现一次的数字的数组.

这题要用set很简单, 不用的话, 可以把负数当作set查重用. 当数字做为坐标的时候 用abs取下值

Queens That Can Attack the King

给一堆国际象棋的queen的坐标, 和一个king的坐标, 问那些queen可以找到king.

主要是看到queen坐标的边界是63, 然后8个方向dfs找即可.

Maximum Difference Between Node and Ancestor

给一个二叉树, 求任意父节点和子节点的最大差.

按个找..

Two Sum BSTs

给两个bst, 然后看是不是能做two sum.

先用inorder变成array, 然后做two sum.

Distinct Numbers in Each Subarray

给一个数组和一个数字k, 求数组中k大小的subarray的不同的数字的个数.

用map当滑窗计算一下

Replace All Digits with Characters

给一个string, 里面有偶数位的字符和奇数位的数字组成, 给一个方法decode这个string, 是用字符后的数字位个字符代替数字位. 求decoded string.

Seat Reservation Manager

设计一个座位预约系统.

用treeset,因为里面有可以直接访问第一个可用key的方法.

Older Posts

书脊

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