LeetCode 刷题冲刺+逐题总结

今天的话继续复习sql相关的理论知识以及也做了一点题，但是越来越觉得问题不是出在对理论基础不熟悉而是对于一些具体的函数没那么熟悉 - 因为主要会用到mysql，所以明天计划是看mysql tutorial上面的文档并配合做题，加上复习lc上面binary search相关的题目~（总结继续鸽一天zzz)

支持一下楼主，同在刷题，感觉楼主刷的题很有意思并且思路总结有帮助

加油，共勉！

拉面qf 发表于 2019-10-8 23:30
支持一下楼主，同在刷题，感觉楼主刷的题很有意思并且思路总结有帮助

加油，共勉！

谢谢谢谢！我开这个帖子一方面是督促自己，一方面也希望能帮到一些同在刷题的人。有帮到你我就很开心啦，一起加油~

今天主要看了一下mysql相关的基本操作并且把lc上最高频的20道sql题刷到还剩一道了（有点刷不动了...有一说一lc上的错误提示真的蠢...)，明天打算把这些题总结一下，并且复习bs以及各种sort的lc的题目~
这几天sql的题号就先不放了（有点多，就是db部分按frequency往下前19题），感觉刷这个就是个熟练度的问题，从最开始easy都点卡壳（主要是各种syntax忘了不少）到后来基本上拿来就能写了（虽然也经常被syntax卡23333）

今天又是典型的时间规划出问题的一天。。。写sql写嗨了做了将近20道，然后耽误了别的时间...
之后打算每天做几道，然后主要复习之前做过的lc的题~
另外把之前做过的sql题在这里挑重点总结一下（题量是实际的题量，题号是挑有代表性的）
总计：19
Hard: 3
185. Department Top Three Salaries
可以写成像我一样的2层subquery，也可以像大神一样两个join，join左小又大然后group by + having count. (like a boss)

262. Trips and Users
这题对sql的熟练度要求很高，if else, ifnull, round等函数得熟练掌握（我自己debug就debug了半天...)

601. Human Traffic of Stadium
标准答案给的是3个join加一堆where，我自己就是3个union（写起来省事儿呀，复制粘贴稍微改一改就完了2333）

Medium: 5 (从med就只挑个人觉得有必要说一说的了，剩下的就只粘题号~)
177. Nth Highest Salary
第一次遇见的也是卡壳的sql题，其实就是考察一个limit的用法 - limit 1 offset N-1  或者 limit N-1,1

178. Rank Scores
直接用dense_rank()或者count()

184, 180,614

Easy: 11 (真不是我挑软柿子捏，他frequency拍下来就是这个分布zzzz，当然一直捏软柿子一直爽也是真的)
181. Employees Earning More Than Their Managers
题目稍微有一点绕，其实join一下就好了

627. Swap Salary
case when/if else的经典练习题目

196. Delete Duplicate Emails
mysql一个delete技巧 - 没法直接delete自己的时候，用一层subquery套住就好啦

183. Customers Who Never Order
left outer join一下然后order id is null就ok了

175，176，595，197, 610, 1113, 597 (这道题不建议花时间做，叙述又长又有问题而且意义不大)

老规矩，今天做的这些明天来进行总结~

今天主要精力花在复习binary search的题以及一些附带的DP/two pointer的题，顺便又练习了一点SQL...要看的题比预计的多很多，需要拿出最佳状态了~
总结的话明天再写吧（整个bs的），明天的目标是bs复习完，然后bfs/dfs/tree的部分，外加先了解一下OOD
看的话打算采取看完题稍微思考一下就直接看答案的策略以便提高效率，然后没有秒的题就记下来等到13/14日再集中复习一下

今天剩下的bs部分看完了，感觉还好，不过到了dfs/bfs/tree部分感觉之前刷的忘了好多...不过发现问题也是好事情，查缺补漏嘛
上昨天的一些重点题号~（下面数量都是总结的数量，真正的总数量会虚高觉得也没什么必要报了）
Hard: 2
174. Dungeon Game
经典中的经典，反向dp

354. Russian Doll Envelopes
也是很经典的一道dp，套娃信封，先按长宽排序然后做dp

（这俩hard说实话跟bs关系都不是特别大...标bs tag也是挺神奇的）

Medium: 8
162. Find Peak Element
判断条件变化的binary search，出发点就是只需要找local max的话，如果中值本身就是那不用再找了返回就行，如果向右斜坡则左方一定有local max，反之亦然

209. Minimum Size Subarray Sum
其实是一道two pointer/sliding window的经典题，滑窗即可（binary search的话可以先搞出prefix sum arrary然后挨个查，不过复杂度会多O(logn)没必要）

222. Count Complete Tree Nodes
binary search in binary search - 首先h-1层肯定是complete的，第h层的话找那个break的点可以用binary search.

230. Kth Smallest Element in a BST
题本身没什么，follow up比较重要：如果update很频繁的话，可以先每个node存上比多少个自己左子树中的大（有点binary index tree的意思但是又不完全一样）；每次update就只需要更新来时的路径（如果有比较）即可。

240. Search a 2D Matrix II
这个的横竖扫描仪（O(n)）解法非常精彩，第二遍做依然没有第一时间想出来； 常规解法其实逐层binary search就ok了

275. H-Index II
这题其实不难，就是给自己提个醒：binary search的定义域不要局限于Index或者某个range，其实整个H-index的所有element也完全可以当作取值域。

287. Find the Duplicate Number
好题强推，题型转换的典范 - 直接看貌似有难度，如果转换成找无向图里的环用快慢指针来做就一目了然了

300. Longest Increasing Subsequence
好题强推，又一个经典题型 - 用stack记录已知最长路径，用binary search来更新stack中的节点（如果不比堆顶大的话）

Easy: 1
392. Is Subsequence
误入easy的准hard题（正文medium, followup hard级），本身的话建一个char - index arrary的hashmap,然后对每个s里的字符在建好的index array map里面做binary search.
followup的话可以建个trie，然后每遇到一个新string在新string上先找到之前match过的最远的位置，从那个位置开始再来binary search

Ganbatte!!

今天contest那个服务器我不想说什么了...把心态搞崩了，最后一道题罚了5次时才改对...第三次错过前100zzzzz
话不多说，上题上题
（同样也是挑看过的觉得有必要总结一下的放在这里~）
Hard: 9
315. Count of Smaller Numbers After Self
327. Count of Range Sum
493. Reverse Pairs
异曲同工之妙的三道题，利用merge sort这个过程来进行计数以达到O(nlogn)复杂度，会一道=会三道

644. Maximum Average Subarray II
二分法找k (O(logn))，然后判断这个k满不满足条件（O(n)). 这题的思考过程是，直接去求这个k并不只管，但是判断这个平均值k有没有可能达得到是很直观的((num-k)>0)的sliding window解法）。说到底就是把未知问题化为已知问题，虽然这句话说起来容易做起来并不容易23333

774. Minimize Max Distance to Gas Station
这道题也是，昨天看就是秒了的，今天第一反应就是错的... 我看答案有个词用的很准确，"trial and error" - 和上题类似，也是先取个值然后看这个值行不行 - 直接算值很难但是判断取值可不可行很容易，就是这个道理

778. Swim in Rising Water
这题两种解法都不是那么直观需要一些思考 - 第一种是对下一个最低点建heapq (其实就是迪亚克斯拉)，当到达终点时遇见过的最大值即为所需时间；第二种依然是trial and error，两种都是O（N^2logN)

862. Shortest Subarray with Sum at Least K
Sliding window一个典型用例

4. Median of Two Sorted Arrays
好题强推，lc前200值得刷5遍真的名不虚传，找到中间index pair然后binary search真的经典

301. Remove Invalid Parentheses
简而言之是backtrack, 个人很推崇评论区里面dietpepsi的解法，十分推荐去学习一下（大致就是backtrack with pointer，用来避免出现重复的temp result的；另外正向一次反向一次也可以省去对于左括号和右括号的分别讨论）

Medium: 8
1011. Capacity To Ship Packages Within D Days
也是binary search possible space

1060. Missing Element in Sorted Array
这个其实重点在想到用binary search上，想到了就不难了

98. Validate Binary Search Tree
可以铺开成array来判断，也可以recursive返回最大最小值，然后和中间节点来进行判断

105. Construct Binary Tree from Preorder and Inorder Traversal
从preorder/inorder/postorder traversal构建回binary search的都是经典，recursive + global pointer的做法值得多练 - 其实弄明白了的话，这些都是literally根据定义逆推即可~

116. Populating Next Right Pointers in Each Node
学会利用上一层的next pointer为这一层提供便利是核心思路，II也是一样的

261. Graph Valid Tree
这题的一个陷阱就是，不能直接判断是否有n-1条边，必须n-1条边并且全联通才可以。

417. Pacific Atlantic Water Flow
经典的两边向中间逆推的题

513. Find Bottom Left Tree Value
bfs，关键是注意审题 - 不是最左端而是最底层的最左边的leaf

今天忙于准备ood和bq，明天上飞机后天昂塞，祝自己好运吧:D

招工季算是基本结束啦，不过打算继续更新这个帖子~这两天休息两天，以后继续加油 :)