Menu Sidebar
Menu

May 2021

Distribute Coins in Binary Tree

给一个二叉树, 然后给一个node的值是coin的数量, 求把这个coins分给每个node需要几步, 一步只能往下推一个node. 这题就是divide and conquer, 例题给的很明确, 如果是root有3个, 左右是0, 那么分下去需要2步(给左边一个, 给右边一个), 这题还给了一共n个node和n个coin, 所以不存在溢出的情况. 所以只需要计算left和right的和-1 就是需要的步骤.

Finding Pairs With a Certain Sum

给两个数组设计一个数据结构, 可以add一个数字到第二个数组, 还有count两个数组的数字等于total有几对儿. 这个就是第一个数组大, 第二个小, 所以先处理大的数组. 然后count的时候直接减一下即可.

Rotating the Box

各一个2d数组, 里面有石头, 空格和障碍, 求右转90度后, 石头落下, 数组的状态. 这题先转90度, 然后从下往上看到空格就往上找石头然后swap, 注意检查边界.

Maximum Subarray Min-Product

给一个数组, 求里面最大的子数组中, 最小元素*子数组和的乘积. 把每个元素看做子数组的最小元素, 这样就变成求由这个元素组成的最长子数组. 用以前的https://leetcode.com/problems/next-greater-element-ii/solution/ 中的stack方法, 找到所求子数组的左界和右界.

Older Posts

书脊

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