在职跳槽刷题打卡及适时分享感悟--计划明年2月面试

11.12 -11.13
739. Daily Temperatures (Medium)
开始想出一个heap的解法，从前往后扫，但是complexity 不是最优
最优的解法是从后往前扫，用一个stack去存hotter temperatures的index，如果stack[-1]的temp 大于 current temp，那么stack[-1]就是最近wamer day

981. Time Based Key-Value Store
需要用到binary search的variation 去找element

125. Valid Palindrome （Easy)

227. Basic Calculator II （Medium）
先要把乘法和除法的结果算出来，然后再做加减法，
105. Construct Binary Tree from Preorder and Inorder Traversal
用到recursion，关键是要看到如何slice 两个list来区分左右子树

楼主可以联系我一起刷～

sanmao0715 发表于 2020-11-2 23:03
lz我这有打卡群和tc讲题群 可以考虑来我们这讲题

我也想组队刷题准备春招，请问可以加我一起嘛~~

sanmao0715 发表于 2020-11-2 23:03
lz我这有打卡群和tc讲题群 可以考虑来我们这讲题

tc是什么

wy_9293 发表于 2020-11-16 13:02:24
我也想组队刷题准备春招，请问可以加我一起嘛~~

私信我联系方式呗

周末依旧有点忙，工作上也有些棘手的事，我自己没太多时间跟大家直接交流，我也不是大神，交流的也不一定能给到太多的帮助，大家想刷题组队跟楼上那位“sanmao”哥们儿联系吧~
若有具体的问题，欢迎大家发帖交流

11.14 - 11.15 做的题
420 Strong Password Checker (Hard)
这题最后几行 除2， 除3 的地方还是没看懂，需要revisit
986 Interval List Intersections (Medium)
这道题花了很多时间才做出来，虽然过了AC，但是解法不容易写，后来发现是自己的思路不清晰，用two pointer来walk through 两个list就好了，每次 merge 这两个pointer interval， 然把interval end小的pointer，move到下一个。
987. Vertical Order Traversal of a Binary Tree （Medium)
比较standard的 recursion + hashmap
509. Fibonacci Number
1 dim DP
226. Invert Binary Tree （Easy）
虽然简单，但用recusion和iterative的解法各做一遍，还是有巩固知识点的用的

一起刷题 lz怎么联系

lz有联系方式吗 要不要一起刷，互相mock

11.17

9 Palindrome Number （Easy）
palindrome number 正着和反着都相等，考的是观察力，有个小优化是不用反着把数全算出来，不断除以10，去缩小选来的数，这样走到一半就可以来判断了
780. Reaching Points （Hard)
这道题重点考的也是观察力，能不能通过两个坐标都是不断增加和，来去判断出最近的一个move是什么？这题从(tx,ty) 往前推到  （sx，sy),  当tx > ty时， tx = some x + n* ty，这时可以用tx % ty来优化，so is the case tx < ty， tx == ty 的情况，是不能reach的, 因为如果存在则会有0的出现。
解这道题看了youtube的 Guifeng Han的解体视频，up主讲得很清楚。

50. Pow(x, n) (Medium)
这题记得在学校的算法课上老师讲过，核心思想在于把computation 二分，然后只算一个就好。需要考虑 exponent是奇偶的情况。exponent是负数和x是负数时候，要变为-n 和 1/x。 Recursion还是比iterative更好写一些

311. Sparse Matrix Multiplication （Medium）
这道题在几年前的面试中见到过，当时没做出来。今天花了点时间，做出来了，但没有1次过AC，写的时候到每个new matrix element 是dot product。
这题的关键是sparse matrix，重点在于非零元素，我将Matrix B用非零元素的column index map来表示，然后再扫A中的非零元素，如果根据B的index map，对应dot product 的B的element也是非0，就把element wise product 加在对应的dot product 的位置上