42. Trapping Rain Water

42. Trapping Rain Water

思路:

这题蛮hard的,挺考验思路;

思考一下,下雨的过程,水往低处流,一点一点汇聚起来,逐渐逐渐升高水面。我们是否可以在先求出低水平面的水量,在此之上求出高水平面的水量。

43234中就有两个水沟:2上的1*1的水沟,和323上的3*1水沟。

用这种想法,我们只需要遍历得到一个水平面的右边界,记录该水平面的左边界,获取低水平面的高度,填充下新水平面的水量即可。

最小值单调栈S可以帮助我们维持左边界的pos,记S的栈顶元素指向的高度为aa之下的元素指向的高度为b。其性质必然有a > b。遍历到高度c

  • c < a,则对蓄水没有影响。
  • 如果c > b,则三者形成了一个水沟,计算🦁式子见代码,并且该水沟可能可以继续往上“看看”,在适当条件上看看单调栈,循环填充高水位水沟。
  • 如果c==a,则显然应该替换掉a,因为单调栈维持的是等高水沟的最新端,试想33323

经过上述填充过程,单调栈的性质也要维护一下,详细见代码。

Read more

面试题 04.09. BST Sequences LCCI

面试题 04.09. BST Sequences LCCI

懵树下你和我,快乐刷刷题

思路

二叉树的构建,是从根节点开始的,每构建的一个节点,就添加了一个可能两个新扩展节点,我们可以在其中任意选择一个节点新构建,如此递归下去,完成整棵树的构建。

那么,我们需要模拟整棵树的构建遍历过程,用deque存储每次构建时可以选择的节点,递归构造。如果deque为空,说明建构完成,把记录构建顺序的path加入答案即可。建构完成后回溯进行下一个节点的构建。

Read more

331. Verify Preorder Serialization of a Binary Tree

331. Verify Preorder Serialization of a Binary Tree

思路:

  1. 按照字符串提供的数据按前序遍历伪建树,如果用完了所有字符就建树成功。
  2. 前序遍历允许我们的用栈记录当前节点以及之前节点应该生长的分支数,比如碰到一个数字,上一个节点的减一分支数,插入一个当点节点的分支数2。遍历过程中,栈为空或者遍历后,字符数还有剩余,显然建树失败。
Read more

109. Convert Sorted List to Binary Search Tree

思路:

链表实际上给出的是二叉树前序的结果,因为AVL树任意左右子树高度不超过1,我们可以选择链表中点,并将链表的长度尽可能一样长的两部分划分到左右子树,所以高度性质可以维持住。

在中序遍历链表,控制子树长度,即可构建符合题意的AVL树。

Read more

450. Delete Node in a BST

思路:

删除一个只有一个子节点,或者没有子节点的节点,比较简单。

删除有两个子节点的节点A,需要把找一个比A大的最小子节点B来替换该A。那么同时也需要递归的删除节点B

Read more

882. Reachable Nodes In Subdivided Graph

思路:

subdivision nodes可以化为路径的长度,将此问题转化为可以用dijstra求解的问题。

每次遍历到最新最短的节点都可以进行求出此点相连的边的可以累加subdivistion nodes的个数,但是需要控制重复累加比较麻烦。最后采用记录下每条边可到达的点,最后统一累计即可。

Read more

149. Max Points on a Line

149. Max Points on a Line

思路:

思路差不多,但是走歪了。害~

整体思路是两层嵌套的for循环。两点可以确定一条直线,那么选择固定一个点,求其他点与固定点的斜率,如果斜率相同,那么斜率相同的点在同一条直线上。
同时要考虑,斜率可能为无穷大,也有可能两个点为同一个点。键值应该为斜率。

通过dup记录这一次内层循环中与p1相同的点。
通过one_round_res统计每一次内层for循环的结果。
将斜率无穷大定义为FLT_MAX。

键值key为斜率,其数据类型选择为long double即可通过
vector<vector<int>> points = { {0,0},{94911150,94911151},{94911151,94911152} };
来源:力扣(LeetCode)

Read more