一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 794|回复: 4
收起左侧

SDE在职刷题刷题记录

[复制链接] |只看干货 |打卡, 打卡组队
我的人缘0

升级   68%


分享帖子到朋友圈
fyfyzzk | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
在湾区工作了一两年,希望今年能跳槽到一个大公司,尽快开始绿卡process。
之前陆陆续续有刷过一两百道题。面对目前越来越高涨的leetcode数目和难度,希望打卡记录下自己日常刷题,通过可视化找到更多成就感,战胜拖延症。

目前刚开始,计划weekdays每天刷题1-3道,周末3-6道,养成习惯,接下来逐步增加数量。
一个tag挨一个tag的刷,先从最拿手的树开始刷起,使用leetcode explorer 再加上各类topic的高频题目。










上一篇:leetcode合买
下一篇:盐湖城刷题
我的人缘0

升级   68%

 楼主| fyfyzzk 2020-2-10 21:41:56 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
本帖最后由 fyfyzzk 于 2020-2-10 21:42 编辑

今日计划
Tree的explorer已做完,总结下
construct BS 三种方法的pattern
inorder + postorder

inorder + preorder

pre + post

回复

使用道具 举报

我的人缘0

升级   68%

 楼主| fyfyzzk 2020-2-11 12:40:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
本帖最后由 fyfyzzk 于 2020-2-11 12:45 编辑

889 由preorder和postorder数组构成一个Binary Tree
思路:

比如例子
[1,2,4,5,3,6,7]
[4,5,2,6,7,3,1]

先建立1 的TreeNode,接下来,从postorder左侧第一个元素出发,找到与pre下一个元素2相等的区间,这段区间在preorder中,就是Tree的左子树。剩下的就是右子树。

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
  int[] pre, post;
  
  public TreeNode constructFromPrePost(int[] pre, int[] post) {
    this.pre = pre;
    this.post = post;
    return make(0, 0, pre.length);
  }

  private TreeNode make(int i0, int i1, int N) {
    if (N == 0) return null;
   
    TreeNode root = new TreeNode(pre[i0]);
   
    if (N == 1) return root;
   
    int L = 1;
   
    for (; L < N; L++) {
      if (post[i1 + L - 1] == pre[i0 + 1]) {
        break;
      }
    }
   
    root.left = make(i0 + 1, i1, L);
    root.right = make(i0 + L + 1, i1 + L, N - L - 1);
   
    return root;
  }
}

回复

使用道具 举报

我的人缘0

升级   68%

 楼主| fyfyzzk 2020-2-17 07:55:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
总结一下BST寻找目标节点的
Successor:
one step right, than go left til u can.

Predecessor:
one step left, than go right til u can.


Successor

public TreeNode successor(TreeNode root, TreeNode p) {
  if (root == null)
    return null;

  if (root.val <= p.val) {
    return successor(root.right, p);
  } else {
    TreeNode left = successor(root.left, p);
    return (left != null) ? left : root;
  }
}


Predecessor

public TreeNode predecessor(TreeNode root, TreeNode p) {
  if (root == null)
    return null;

  if (root.val >= p.val) {
    return predecessor(root.left, p);
  } else {
    TreeNode right = predecessor(root.right, p);
    return (right != null) ? right : root;
  }
}


回复

使用道具 举报

我的人缘0

升级   68%

 楼主| fyfyzzk 2020-2-17 12:32:59 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
本帖最后由 fyfyzzk 于 2020-2-17 12:36 编辑

BST 的 successor
right child 存在
  以right child开始的leftmost node
不存在
  null

iterative解法:

  public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode succ = null;
   
    while (root != null) {
      if (root.val <= p.val) {
        root = root.right;
      } else {
        succ = root;
        root = root.left;
      }
    }

    return succ;
  }


recursion 解法

public TreeNode successor(TreeNode root, TreeNode p) {
  if (root == null)
    return null;

  if (root.val <= p.val) {
    return successor(root.right, p);
  } else {
    TreeNode left = successor(root.left, p);
    return (left != null) ? left : root;
  }
}


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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