LeetCodeDaily

Menu 目录

• Problem Set

Week	Mon	Tue	Wed	Thu	Fri	Sat	Sun
24		394	43	15	51	1
25	46	21	172	223	136	300
26	19	78	335	587	72	18
27	53	120	100	70	93
28	H	H	H	H	H	H
29	H	H	H	H	H	H
30					121	85
31	345	37	733	749

• My Solutions
• Group Members
• References
• Rules

Problem Set 每日一题

【2018/06/12题目】394. Decode String

• 题目类型 #simulation
• 第一天我们来一道摸底题吧，不是太难，也不是two sum那么简单

【2018/06/13题目】43. Multiply Strings

• 题目类型 #高精度计算
• 不可以使用Java内置的BigInt。
• 建议大家用C或者C++写，这题比较合适给大家做C cpp练手
• 【可以先做这道练练手】66. Plus One
• 思路参考 浙江大学SCL 高精度计算章-大数 leetcode大部分的题都能在这个小手册里找到思路
• 附 楼教主十几年前出的男人八题

【2018/6/14题目】15. 3Sum

• 我们来一道经典面试题threesome吧
• python中list对象的存储结构采用的是线性表，因此其查询复杂度为O(n),而dict对象的存储结构采用的是散列表(hash表)，其在最优情况下查询复杂度为O(1)。

【2018/06/15题目】51. N-Queens

• 题目类型 #N皇后
• 在建立棋盘的时候用乘法可能会导致棋牌某一列均相同，因为在python中复杂类型是浅拷贝、简单类型是深拷贝
• 在棋盘中确认是否重复时，从左上到右下的一斜行坐标差值相同，右上到左下的一斜行坐标和相同，所以可以用这一数值统一标记，无需单个确认。（在非常大的棋盘时可能会加快速度？）

【2018.06.16】1. Two Sum

• 附加要求：虽然比3sum简单，但请大家实现尽可能快的版本，最快的人将会获得一笔bonus奖金（数额保密）

【20180618】46. Permutations

• 全排列
• 全排列那个可以就用回溯做，递归n层，每层在前面诸层中未选择的数字集合中选择candidate，选好了就进入下一层。各层share一个全局的长度为n的布尔数组，来标记每个数字是否被使用

【2018/06/19】21. Merge Two Sorted Lists

• 类型：#合并链表
• 大二作业题，不能更水了

【2018/06/20】172. Factorial Trailing Zeroes

• 阶乘最末0

【2018/06/21】223. Rectangle Area

• 类型#简单计算几何
• 分解836. Rectangle Overlap

【2018-06-22】136. Single Number

• 类型： #不要看答案不要看discuss不要搜，自己想

【2018-06-23】300. Longest Increasing Subsequence

• type #LIS

【2018-06-25】19. Remove Nth Node From End of List

• type #LinkedList
• 希望大家能实现一趟扫描就完成任务的版本，不要扫完了再倒着找
• 俩指针，一个指针比另一个指针提前跑n位，每一步俩指针各动一步，前面的指针碰到尾巴的时候回，落在后面的指针就自动落在倒数第n个上
• 你用单指针把它一个个读下来，存到一个大小为n的队列里，不就行了，但是耗空间多
• 双指针是O(1)空间，单指针存队列是O(n)空间
• 双指针的另一个典型应用是找链表中点
• 链式存储不允许随机访问，如果n特别大，又是在单片机上，哪来的那么大内存放数据呢
• 我强调下一下，这题是不能不用双指针的，如果面试中没写出双指针的代码，面试官会问你有没有优化方法要求你想想再写的。
• 如果你在一台单片机上编程，内存往往非常小，不用双指针，一个数组只能存几千个数字，就保存不下这个问题了。这种问题的考点就在这里，面试官就是想问这个。你们要触碰他们的点。
• 这题一定一定一定！要用！双！指！针！[睡]
• 程序员，尤其是出面试题的程序员，就是一群这么喜欢抠小聪明的人，这种细节答出来了，他们就会感觉是对的人，要是答不出来，他们就会有连这都不知道的一种感觉
• 北京很多公司的面试题，其实是外包给一些acm选手出的，出一套几千块
• 刷LeetCode其实跟刷五三是一回事，都是过拟合

【2018-06-26】78. Subsets

• type#backtrack
• 明天做这道吧，用不用递归都行

【2018-06-27】335. Self Crossing

• type#计算几何
• 这题的关键在于判断是否相交，可能有些难度
• 这是我们出的第一道标记为Hard题

【20160628】587. Erect the Fence

• type # computational geometry
  https://leetcode.com/problems/erect-the-fence/description
• 希望大家做出来，不要diserect

【2018-06=29】72. Edit Distance

• type #dynammic programming #edit distance
• 不管今天写不写得完，请务必学会这道题，这不仅是生物信息学的基础题，而且是大家的第一道动态规划题，现在面试还是挺流行考动态规划的。动态规划题目中，这道可以算是最简单了

【20180630】18. 4Sum

【20180702】53. Maximum Subarray

• type #动态规划
• 最大子序列问题也毫无疑问是个动规问题，网上的解析非常多。我就不多说了，建议大家做动规题时候自己多想想，不要直接看答案，这样比较锻炼大脑。
• vote: 11-20这10天用来马拉松，出15道题，10天内刷完即可，题目偏水，个别题难点，在7号公布。你们同不同意？如果觉得时间不好或者数目不好，投不同意。否决后另案解决

[2018-07-03] 120. Triangle

• type #DP 今天我们再来一道入门动规。
• 关于动态规划，给大家推荐一篇入门文章很久很久以前的一篇科普老文了，初中生都能看懂，讲得比较有趣
• 以前在cpp我们都是用88888888或者0x3f3f3f3f来初始化,因为大概是int最大值的一半，这样两个这样的“无穷大“加在一起仍然不会溢出

【20180704】100. Same Tree

【20180705】70. Climbing Stairs

• type#数学题 动规
• 这一类求解F(n)=aF(n-1)+bF(n-2)+c的问题，叫做 二阶线性非齐次递推关系，闭式解法可以再《具体数学》这本小神书里面找到
• 提示，可以手算几个，然后上oeis上面查:oeis是数列的数据库，支持数列的搜索，专业的。有acm选手作弊的的，就在上厕所的时候偷偷用oeis查手算的数据。当然平时打在线比赛的时候，oeis还是可以光明正大地用的
• 这个数据库就是内部存了海量的各种各样的数列，它把它的各种匹配的都给你，而且是局部比对
• 你随便输一些数字，都会发现是一个意想不到的数列

【20180706】93. Restore IP Addresses

• type #可能比较麻烦

【20180707】292. Nim Game

• type #数学题 博弈论

【20180710-20180720】Hackathon

1. 7. Reverse Integer

2. 13. Roman to Integer

3. 67. Add Binary

4. 189. Rotate Array

• 注意其Note，想一想如何不用额外的空间（in-place）来完成这个任务

5. 191. Number of 1 Bits

• 可以参考前面发给大家的matrix67写的位运算教程

6. 160. Intersection of Two Linked ListsDo it smartly. 去年的本科数据结构课期中考试题

7. 169. Majority Element

8. 151. Reverse Words in a String

• easy problem, especially when using python.
• Finish it and consult the answer, then appreciate how brief it can be!

9. 187. Repeated DNA Sequences

• Write this and you are on the way to D2R

10. 205. Isomorphic Strings & 242. Valid Anagram

• 同态、同构、同伦、同调……，好在这个isomorphism问题还是特别简单的
• 242跟205两题都做出来算一道题（我偏要这么算）

11. 162. Find Peak Element

• Write this and you are on the way to D2R too.
• 实际上，在一个连续信号中识别峰并非一个trivial的问题，让我们通过做这道题引起大家的思考

12. 59. Spiral Matrix II

• 老题，几乎出现在每一本编程入门书的“循环”部分

13. 274. H-Index

• May we all have high h-indices

14. 69. Sqrt(x)

• 面试时候面试官都想听到二分法这个答案，刷过题的一般都这么做
• 前几年有个没刷过题的中国人告诉洋面试官可以用泰勒展开，把面试官听得一愣一愣的。

15. 50. Pow(x, n)

• 传说中的快速幂算法

16. 236. Lowest Common Ancestor of a Binary Tree

• 经典的LCA问题

17）230 https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/ Tree again

18）263 https://leetcode.com/problems/ugly-number/description/ 大家还记不记得很久以前163是中国互联网巨头的时候，还有个大公司叫263

19）289 https://leetcode.com/problems/game-of-life/description/ 这个挺好玩的，matlab上有一个写好的

20）290 https://leetcode.com/problems/word-pattern/description/ pattern match是生物信息永恒的话题

21）371 https://leetcode.com/problems/sum-of-two-integers/description/ 趣题，以前我也没想过这个事情

22）387 https://leetcode.com/problems/first-unique-character-in-a-string/description/ 这一题的扩展，find unique k-mer，有一个非常棒的解法 https://codegolf.stackexchange.com/questions/45257/counting-k-mers 见第一个答案

23）447 https://leetcode.com/problems/number-of-boomerangs/description/ 水

24） 443 https://leetcode.com/problems/string-compression/description/ 注意in-place和O(1)的两个要求

25）403 https://leetcode.com/problems/frog-jump/description/ 倒推的思想或许有助于解题

【2018-07-27】121. Best Time to Buy and Sell Stock

• type #那我们做题就也做这道股票吧 #DP https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

2018-07-28 85. Maximal Rectangle

• type #再来一个dp

【2018-07-30】345. Reverse Vowels of a String

【20180731】37. Sudoku Solver

• Y #天了噜七月过完了

【20180801】733. Flood Fill

• y #今天再放道水

【2018-08-02】749. Contain Virus

• type #DFS/BFS

【2018-8-3】#拓扑排序 207. Course Schedule

【2018-08-04】#栈或者回溯模拟一下 150. Evaluate Reverse Polish Notation

[2018-08-06] #判断二分图 785. Is Graph Bipartite?

• 去年期末考试出的题，但是没被采纳

【2018-08-07】#看来得降点难度 204. Count Primes

• My solution 204
• Reference link with explanation
• The Algorithm Sieve of Eratosthenes

【2018-08-09 -- 08-23】 DParathon

我提议刷序号为5到300的所有Medium的Dynamic Programming题目，总共15道 可以在这个页面 https://leetcode.com/tag/dynamic-programming/ 查看所有的DP题，点击表格title的#可以按照难度序号进行排序

5. Longest Palindromic Substring

• Manacher's algorithm
• Python O(n^2) method with some optimization, 88ms.

62. Unique Paths

63. Unique Paths II

64. Minimum Path Sum

91. Decode Ways

95. Unique Binary Search Trees II

96. Unique Binary Search Trees

• DP Solution in 6 lines with explanation. F(i, n) = G(i-1) * G(n-i)

120. Triangle

139. Word Break

152. Maximum Product Subarray

213. House Robber II

221. Maximal Square

264. Ugly Number II

279. Perfect Squares

300. Longest Increasing Subsequence

My LeetCoding Solutions 我的解答

• 2018/6/12 394. Decode String Solution
• 2018/6/13 66. Plus One Solution and 43. Multiply Strings Solutions
• 2018/6/14 15. 3Sum Solution
• 2018/6/15 51. N-Queens Solution
• 2018/6/16 1. Two Sum Solution
• 2018/6/18 46. Permutations Solution
• 2018/6/19 21. Merge Two Sorted Lists Solution
• 2018/6/20 172. Factorial Trailing Zeroes Solution
• 2018/6/21 223. Rectangle Area Solution and 836. Rectangle Overlap Solution and reviewed 51. N-Queens Solution 52. N-Queens II Solution
• 2018/6/22 136. Single Number Solution
• 2018-6-26 78. Subsets Solution
• 2018-6-27 335. Self Crossing Solution
• 2018-7-5 70. Climbing Stairs Solution
• 2018-7-6 93. Restore IP Addresses Solution
• 2018-7-7 7. Reverse Integer Solution 13. Roman to Integer Solution 67. Add Binary Solution 189. Rotate Array Solution
• 2018-7-8 191. Number of 1 Bits Solution 160. Intersection of Two Linked Lists Solution 169. Majority Element Solution 151. Reverse Words in a String Solution
• 2018-7-14 187. Repeated DNA Sequences Solution
• later solutions are updated just under the problems

Group Members 学习小组成员

Gao Haoxiang

Chen Wenchang

Li Jiaqi

Li Fanhong

References 参考资料

• 短码之美
• 浙江大学SCL

每日Leetcode活动规则

最重要的群规：真诚！真诚！真诚！

• 一、 每人每天上交【10块钱】至会长处，作为刷题鼓励金，会长选择建议的题目。

• 二、刷题奖励金的发放方式：

  • 若所有人都刷题了，第二天会长会把鼓励金返回给大家；刷题完成标准以AC为主，讲不讲得明白作为辅助的主观参考。如果讲不明白，给予major revision或者minor revision的重讲机会。完全讲不出来的，给予rejection处理。
  • 若部分人未刷题，则鼓励金均发给其他运动的会员；
  • 若所有人都未刷题，则鼓励金累积后延，直至出现条件2的情况。

• 三、每晚12：00之前，所有会员把刷题记录截屏发群里，第二天会长根据截屏记录分发红包。希望大家对自己诚实，不要直接粘解题方法，所有刷过的题要能说出解题思路，可以互相考察。

• 四、讲题会活动：每周一下午7pm

• 五、病假制度：每月有3天假期（请假者不收取会费也不参与红包分发），超过3天则每天上交10块会费。

• 六、押金规则：每天中午12点之前，会长会返还昨日押金，会员在领取后顺便上交今日押金，最晚不超过中午12点。已经上交押金后，不能再申请请假。

• 七、退费会用：100块（均分给其他未退群的人）