📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: soliloquyyy
跳转到指定楼层
上一主题 下一主题
收起左侧

面试刷题咯~每天10道~

🔗
 楼主| soliloquyyy 2019-2-15 11:15:38 | 只看该作者
全局:
FEB 11:
124. Binary Tree Maximum Path Sum
这道题需要一个很重要的观察。就是maximal path sum一定是root.val + left path + right.path。我这里说的root并不是整个tree的root,而是任意一个subtree。有了这个观察之后,我们就可以便利所有的顶点,然后maintain一个变量。这里可以用dfs来做,但是注意的是,path 不是path sum,path只能选择左右的一条边。所以dfs return的是val.root + Math.max(left,right);另外就是要注意negative value,我们不加入他们,视作0即可。

297. Serialize and Deserialize Binary Tree
Preorder 做一次 把null 变成xx
deserialize就是把xx return null

269. Alien Dictionary

FEB 13:
146 LRU Cache
先把宏观框架先搭建起来,再去补足相关的function

10 Regular Expression Matching
如果s = null || p = null 直接返回false
这道题弄懂了之后还是很好解决的。对于*的用法,有两种情况,要么任何char带着*代表0,要么代表1个或多个。那么我们只需要检查pattern前一个字符是不是和S目前的字符一样就可以了,如果一样说明是第二种情况,不一样则代表是0个

76 Minimum Window Substring
注意corner case,如果windows的size大于string的话,直接return empty string

9 Palidrome Number
非常easy的方式,先看是不是负数,是的话,直接false
然后我们倒着组成一个数,比如785 我们把它变成587,明显不相等,false
Res = res * 10 + x % 10;
x /= 10;

322 Coin Change
Dp 的思想,一层层递进。要记得判断coin是不是比i大,还有就是dp【i】 不能为MAX_VALUE






31 Next Permutation
最后的一个permutation一定是降序的,也就是说我们要从后往前找,找到从后往前不是increasing的地方,让后在这个index后面找到一个比index所在的element稍大的数(我们可以最后找起,如果小于index的element就往- -index, 这样就会停在比index element大的最小的数上) 然后再reverse整个nums的index后面的部分

17 Letter Combination of phone number
简单的DFS

22 Generate Parentheses
简单的DFS, 但是在循环调用dfs的时候,需要注意,只要还有剩余的左括号可以增加,就可以调用dfs
但是右括号调用有限制,必须现有的左括号的数量大于右括号才能调用
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2019-3-29 06:44:48 | 只看该作者
全局:
我又开始来刷题了。这一次是Amazon的tag,最近6个月的题目按照频率来。总共308题。希望能够每天完成25道题目,总结于这个帖子下面。
回复

使用道具 举报

🔗
 楼主| soliloquyyy 2019-6-17 05:23:48 | 只看该作者
全局:
975. Odd Even Jump
这题要求我们找出一个int数组中good starting index(gsi)的数量,这里的gsi的定义是说:一个数从奇数次跳是选择后面数中大于它本身的最小的数,欧数次跳是选择后面数中小于它本身中最大的数,如果能够经过奇偶跳最终抵达最后一个数的话,最开始的starting index就算做gsi。当我们在草稿纸上手动跑一下过程就可以get到两个规律。首先,最后一个数永远是gsi。第二,index i 的奇数跳 如果是gsi,那么index i - 1的偶数跳也是。同样的,如果index i 的偶数跳 如果是gsi,那么index i - 1的奇数跳也是gsi。第一条和第二条规律让我们能够构建出一个dp。为了能够快速选择奇偶跳的下一个数,我们可以时候用treemap的ceilingkey和floorKey。
  1. class Solution {
  2.     public int oddEvenJumps(int[] A) {
  3.         if(A == null || A.length == 0) return 0;
  4.         
  5.         TreeMap<Integer, Integer> map = new TreeMap<>();
  6.         
  7.         int n = A.length;
  8.         int res = 1;
  9.         boolean[][] dp = new boolean[n][2];
  10.         
  11.         dp[n-1][0] = true;
  12.         dp[n-1][1] = true;
  13.         
  14.         map.put(A[n-1], n-1);
  15.         
  16.         for(int i = n - 2; i >= 0; i--) {
  17.             Integer nextOddJumpNum = map.ceilingKey(A[i]);
  18.             if(nextOddJumpNum != null) {
  19.                 dp[i][0] = dp[map.get(nextOddJumpNum)][1];
  20.             }
  21.             Integer nextEvenJumpNum = map.floorKey(A[i]);
  22.             if(nextEvenJumpNum != null) {
  23.                 dp[i][1] = dp[map.get(nextEvenJumpNum)][0];
  24.             }
  25.             map.put(A[i], i);
  26.             if(dp[i][0] == true)
  27.             res++;
  28.         }
  29.         
  30.         

  31.         
  32.         return res;
  33.     }
  34. }
复制代码


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表