一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 4835|回复: 40
收起左侧

[其他] 1/24~3/24 60天刷题全力冲冲冲

[复制链接] |试试Instant~ |刷题
我的人缘0

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

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

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

x
在12月末的时候就开始重操刷题了,上周开始全力刷,身边很多人也都上岸了,哭。这个贴子的目的最终不是找得到工作(当然找到最好啦~),只是享受60天的刷题过程~ 尽人事,听天命,平和心态。

欢迎大家互相监督学习 -> https://github.com/Haixiang6123/lintcode-python

补充内容 (2020-1-23 09:50):
打卡 2020/1/22,开始刷 VMWare 的题 + Follow Up

补充内容 (2020-1-24 14:14):
打一波卡,皮肤过敏搞得昨天晚上都没睡好,3点就起床不知道要干嘛了

补充内容 (2020-1-25 05:57):
今天快点搞完了,晚上吃火锅过年啦

补充内容 (2020-1-27 08:44):
昨天去 SD 和同学过生日了,今天继续~ 还有,疫情越来越严重了,希望大家都平平安安~

补充内容 (2020-1-28 11:57):
过敏真的太难受了,睡也睡不好

补充内容 (2020-1-29 07:18):
今天做的基本是 hard 题,Sliding Window 认真学了一下

补充内容 (2020-1-30 06:03):
今天主要是复习以前的题+follow up 和 related questions

补充内容 (2020-1-31 10:08):
把 databricks 的题和 follow up 写了,还搞了一下午的报税,结果还是没搞好

补充内容 (2020-2-1 07:26):
还是没有 VMWare 的回信,就先找 FB 的题来写写~

补充内容 (2020-2-2 10:21):
今天继续写 FB 的题,明天奖励自己休息一天!

补充内容 (2020-2-4 07:45):
还有3天就 Karat 面试了,所以这三天基本就是复习+leetcode 里 databricks 的题

补充内容 (2020-2-5 10:11):
继续刚 databricks 的题。最近发现过敏好像快没了,刷题的时候总算不会抓耳挠腮了,哈哈哈哈

补充内容 (2020-2-6 11:53):
明天面试,加油!

补充内容 (2020-2-7 10:00):
面试第三题还是没写完,希望可以大哥可以高抬贵手,让我过了吧

补充内容 (2020-2-8 07:21):
今天吧 FB 春招 OA 的 ladder 写完,明天休息,之后打算开展各个专题的训练

补充内容 (2020-2-9 02:31):
今天是休息天,在等车保养的时候复习了两个题

补充内容 (2020-2-10 09:25):
今天开始 DFS 的专题训练,除去 hard 题就剩下 75 题

补充内容 (2020-2-11 11:20):
Databricks 过了第一面,DFS 专题训练要放一放了,明天开始复习 databricks

补充内容 (2020-2-12 12:17):
今天复习了一下 Databricks 的题库

补充内容 (2020-2-13 09:45):
复习一遍 DataBricks 的题库,再总结了前面几题,终于解决了 Skyline Problem

补充内容 (2020-2-14 08:03):
可算把 Databricks 的题总结完了,每个题基本都看了不同的解法,下午有点不想再写题了,要歇歇,明天 Hiking 去!

补充内容 (2020-2-16 08:39):
昨天去爬了 Powells ,巨累,但是今天也要继续写题呀

评分

参与人数 4大米 +6 收起 理由
abc99 + 1 赞一个
chb123 + 1 给你点个赞!
鱼鹤影 + 2 给你点个赞!
nunuh89 + 2

查看全部评分


上一篇:求解一道NP complete变polynomial算法题
下一篇:备考UIUC Data Structure Proficiency Exam...
我的人缘0
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (10)
 
 
0% (0)    👎
加油。集中刷效果好
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (8)
 
 
0% (0)    👎
咱俩的时间线和计划一毛一样呀兄弟😆 加油了
全职刷感觉有点慢
回复

使用道具 举报

我的人缘0
 楼主| hai_guai 2020-1-23 09:49:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (43)
 
 
0% (0)    👎
# 2020/1/22

436. Maximal Square
二维 dp,dp[i][j] -> 正方形边,dp[i][j] = min(top, left, top_left) + 1,注意边界情况 i == 1 or j === 1 return 1

122. Largest Rectangle in Histogram
单调栈,一直保持递增。遇到递减的: heights[stack[-1]] >= heights[i],就一直弹出一个 prev_height,找到左边界,更新 rectangle -> (i - heights[stack[-1]] - 1 | i) * heights[i],注意最后要加上 -1,在最后一次将所有都弹出

510. Maximal Rectangle
设置 heights 数组,统计每一列的高度,就可以转换成 122. Largest Rectangle in Histogram 的问题。每一行都做一次 122 的求解,对比最大 rectangle

697. Sum of Square Numbers
判断是否 < 0,判断是否可以开根号,将 sprt(num) 作为 upperbound,从 j = 1 -> upperbound 去找是否存在 i * i + j * j == num,j = int(sprt(num - i * i))

64. Merge Sorted Array
设置 position 指针,两个数组从后往前判断哪个大,哪个大就加入到对应在的 position 位置

6. Merge Two Sorted Arrays
先处理 i < m and i < n 再处理 i < m 和 i < n 的情况,指针一起往前

839. Merge Two Sorted Interval Lists
还是和 Merge Two Sorted Arrays 一样,这次的判断条件是 l1[i1].start < l2[i2].start,然后 push_back。push_back 里要针对当前结果最后一个 interval 的 end 来处理: last.end < start -> 直接 append,否则 last.end = max(last.end, curt.end)

212. Space Replacement
计算 true length = length + 2 * space_counts,调协双指针:index = true_length - 1, i - length - 1,从后往前修改 string

56. Two Sum
Super easssssy,用 dictionary 和双指针(比较麻烦)都能做

608. Two Sum II - Input array is sorted
双指针,nums[left] + nums[right] < target -> left += 1 else right -= 1, == target -> return [left + 1, right + 1]

607. Two Sum III - Data structure design
这里用一个 dictionary 去存 { num : count },每次要分是否 target - num == num 去判断。和 Two Sum 有点类似,但是这里多了去重的操作,其实大可以将他们变成数组,每次都用 Two Sum 去做,但是这样 worse case 可能复杂度变高了,例如 [2, 2, 2, 2...]

689. Two Sum IV - Input is a BST
中序遍历,遍历左节点的时候加入 target - left_root.val,在遍历到右节点的时候就判断 right_root.val 是否在 node_set 里即可

1797. optimalUtilization
双指针,left 在 A,right 在 B,初始 optimal 是 A[0] + B[0],每次 A[left] + B[right] 都和 optimal 对比,前提是 A[left] + B[right] <= K and > optimal,如果  > K 或者 right 有重复,就 right -= 1

609. Two Sum - Less than or equal to target
先 sorted 数组,在 A[left] + A[right] <= target 的时候 counts += right - left,left += 1,否则 right -= 1

443. Two Sum - Greater than target
和上题同理,取反即可

610. Two Sum - Difference equals to target
nums -> pairs (nums, i), 排序 lambda x: x[0],abs(target),固定 i, j = i + 1 -> n - 1,如果 diff < target,j += 1, > target 就 break,相等就返回结果

587. Two Sum - Unique pairs
注意去重

382. Triangle Count
i: n - 1 -> 0,nums[i] 作为 target,然后变成了 443. Greater than target

57. 3Sum
two sum 基础上包一层 i: 0 -> n - 3,其中 target = -numbers[i], left = i + 1, right = length - 1

58. 4Sum
3Sum 基础上包一层 i: 0 -> n - 4

59. 3Sum Closest
3Sum 基础上每次都判断是否更 closer
回复

使用道具 举报

我的人缘0
dejavoilavu 2020-1-23 13:39:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (39)
 
 
0% (0)    👎
lz一天刷这么多?
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (414)
 
 
1% (5)    👎
就是说啊。一天刷二三十道。真的不会吐吗
回复

使用道具 举报

我的人缘0
ml3749963 2020-1-23 16:43:03 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (8)
 
 
0% (0)    👎
楼主你是怎么个刷题顺序呀 ?
回复

使用道具 举报

我的人缘0
 楼主| hai_guai 2020-1-24 14:13:58 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (43)
 
 
0% (0)    👎
# 2020/1/22

657. Insert Delete GetRandom O(1)
插入和删除都要判断 corner case,删除是将最后元素提到 index 那,再 pop

954. Insert Delete GetRandom O(1) - Duplicates allowed
不同的是,self.positions = { val: set },删除的时候每次要 pop index,然后 self.nums[index] = None

426. Restore IP Addresses
dfs,分成 4 个 part,当 part == 4 和 s == '' 的时候加入到结果,每次要判断 int(s[:i]) <= 255

17. Subsets
注意要先排序,每次 start -> len(nums)

1048. Longest String Chain
按 word 长度排序,对每个 word 都做 bfs,其中要用 memo 记录当前 word 的 Longest Chain

1209. Remove All Adjacent Duplicates in String II
使用 stack 去存 {char: counts},如果 stack and char in stack[-1].keys() and stack[-1][char] + 1 == k 就 pop,< k 就增加 counts。最后 result += char * counts 即可

1047. Remove All Adjacent Duplicates In String
也使用 stack 去 [char],如果 char == stack[-1] 则 pop,否则 append(char)

102. Linked List Cycle
快慢指针同时走,如果相遇则有 cycle

103. Linked List Cycle II
快慢指针同时走, slow = fast = head,相遇后,slow = head,然后快慢指针继续走,直到 slow == fast,return

380. Intersection of Two Linked Lists
获取两个链表的长度,然后逐次递减,然后双指针同时走,直到 node1 == node2 出现,就是 intersection

384. Longest Substring Without Repeating Characters
dict 记录每个 char 最左边的 index,每次 left = max(left, cache[char] + 1),这里要 +1 因为cache[char]还是相同的,要过去一个位置,然后对比 right - left + 1
回复

使用道具 举报

我的人缘0
 楼主| hai_guai 2020-1-24 14:38:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (43)
 
 
0% (0)    👎
codeyy 发表于 2020-1-23 15:23
就是说啊。一天刷二三十道。真的不会吐吗

其实我大部分以复习为主,有些之前写过了,有一些就是一个题不断follow up 所以解起来比较快
回复

使用道具 举报

我的人缘0
 楼主| hai_guai 2020-1-24 14:39:55 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (43)
 
 
0% (0)    👎
ml3749963 发表于 2020-1-23 16:43
楼主你是怎么个刷题顺序呀 ?

先定个10到20道题,刷完之后每个题不断follow up 就是做里面的 related question,做到没有为止,目前我是这个阶段
回复

使用道具 举报

我的人缘0
 楼主| hai_guai 2020-1-24 14:41:03 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (43)
 
 
0% (0)    👎

因为基本以复杂和 follow up 为主,大部分都有想法就可以解,当然碰到hard的也会想好久,即使看了答案。如果累了就打一把红警 哈哈
回复

使用道具 举报

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

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-2-17 06:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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