CS专科／在职多年／刷题+健身+学AI

freemanlax 发表于 2017-9-3 19:27
LC   79   Word Search：一碰到递归，老是尼玛多多少少要出点低级错误！这次居然把base condition 给写反了 ...

LC  211 Add and Search Word - Data structure design：挺煎熬！说明自己对树／trie的递归结构还没达到游刃有余的境界 (还在过去的trie笔记中找出一个不小的错误，也不知道是该高兴还是该惭愧？！)，只是能磕磕绊绊地挤牙膏一样的做出来！但毕竟是自己做出来的:)
LC 212 Word Search II：还正在做笔记和总结...回头补上！夜里爬起来，仔细看了半天，觉得自己已经没什么好总结的了，这也就是 Word Search I + LC 211        Add and Search Word - Trie_design 的一个supersized-combo吗？！！！唯一的技巧（勉强称为技巧吧）是要根据Trie的prefix逐步生成DFS搜索的动态target。=== 又及：看来这个所谓的技巧有悖于Trie的设计初衷，还得回锅！
没锻炼，还是热得苟延残喘:(

唉！N queens 一天都没搞定！尚在努力中

补充内容 (2017-9-7 18:44):
出现的错误汇总：
用for循环控制recursion退出 vs 用recursion的参数判定控制退出;
recursioin函数是否需要有return value ／ return statement;
避免在recursion外部caller中用循环调用recursion，省得把自己搞乱

补充内容 (2017-9-7 18:48):
做了个
LC 50 Pow(x, n)：给自己打打气！

补充内容 (2017-9-8 01:49):
在做N Queens时自己多加了一层外面的for循环，以及用强制return bool是对递归backtracking 的不完全理解(信任:) )。

LC 93 Restore IP Addresses：完成以后有点不相信是自己写的:) 虽然在2个判断源string的边界条件上有小错。technically 这道题和N Queens I 几乎在递归结构上一模一样：recursion的外循环由function的参数递增来控制终止条件，recursion内部的validation所在的循环由一个for控制，如果本层recursion validation工作都不能成功，或不能从base condition退出，那么回溯到上一层的for循环去操作下一个index指向的recursion直到所有for所控的recursion穷尽。而且使用for循环可以保证找出所有解，而不是只是第一个解。

提醒自己：一步一个脚印，要么自己攻克，要么在帮助下生成自己的natural版本；不求刷XX遍LC，但求做一遍，甚至50%，也能顶别人刷N遍！

健身：胸部 （左肘内侧韧带痛，注意运动前的拉伸）

找了下面一堆300之前的resursion 题目准备打个快速歼灭仗，谁想到第一个 LC 78 就摔了个嘴啃泥：整个周六一天愣是没鼓捣出来！！！ 靠，上次我到底是怎么做出来的？？？看了看 “微软工程师：蔡克贺与他的Leetcode刷题之道” 给自己提提气== “该吃吃该睡睡”
LC 78        Subsets
LC 90        Subsets II         
LC 77        Combinations
LC 39        Combination Sum
LC 40        Combination Sum II
LC 216        Combination Sum III
LC 17        Letter Combinations of a Phone Number

停了5天的引体向上，今天做起来有点down grade。用进废退！！！


补充内容 (2017-9-11 08:51):
睡觉真的又帮了我！礼拜天早上起床后，自己从白纸上从头推出排列，组合的最最最基本公式，分解出子集生成的的推导公式，Subsets I终于写出来了（估计上次这道题是看答案后实现的） 。哈哈！

补充内容 (2017-9-11 09:02):
看了看https://youtu.be/8MvDdcdclGU
估计这位没怎么太狠刷题？哼！
但他的“重复训练自己弱点”+“写伪码从而节省时间并cover更多的题目”挺有帮助。

补充内容 (2017-9-11 09:09):
回头看了看Subsets I的“标准答案”，又对照自己的代码，想把自己的头埋进沙子里面去 :)  == 简直是用火箭打蚊子！:(

昨天工作的任务有所变动，开始出任最麻烦的烙印组的tech lead，一堆代码和KT会议，开到满眼"发黑"。
只能在间歇喝咖啡的时间想想LC，在地铁里把伪码搞定。之后看到一个大神用了“尾递归”的超简洁代码，人家既不用push也不用pop, 唉！自惭形秽！
LC 17        Letter Combinations of a Phone Number
LC 77        Combinations
LC 90        Subsets II （复习了一把，手动画了画递归树，没想到3个elements的输入居然push pop了20多回，画到烦 :) ）

september 13 - 15
LC 39        Combination Sum  能轻松完成，只是要注意递归的起始index 没有+1
LC 40        Combination Sum II  能轻松完成，没什么值得再总结的
LC 216      Combination Sum III 能轻松完成，没什么值得再总结的
LC 46       Permutations I  被卡的死死的！怎么就那么想都不想地把for循环的起始设成一个recursive的位置变量start了呢？？？卡在这里2天！
LC 47       Permutations II 同LC 46

看来刷题速度没有达到计划，我只有刷一道秒一道的这条路了！没时间再回头吃回锅肉了 :(

LC 60  Permutation Sequence: 基本思路都对，但卡了许久，原因是没有 “把当前循环中的大组group那位,从permutation候选者的类似123456789xxx 的串中删除掉”
LC 31  Next Permutation: 觉得自己的高中数学没白学！又是 整除+取模的结合题型。跟递归没挂上钩，有点失望 :(

自己老是觉得递归回溯很烦，也许是工作的实际代码中很少能用上的原因，递归算法还是停留在“容易死循环”+“多线程中不好控制中间状态” 的主观记忆中；但刷题时必须把这些抛在脑后！
我觉得DP的bottom up很容易，其实递归也就是DP的top down嘛，怎么把我弄的这么心烦！！！？？？ 总结起来是自己的2个弱点：1是由loop控制次数的递归不熟练，老是觉得只有用in-param来控制退出才保险；2是回溯时，caller层的状态总是被自己在设计算法时忘掉。
下周计划：总结递归，开刷DP

加油！努力刷题，转成码农

freemanlax 发表于 2017-9-18 08:32
LC 60  Permutation Sequence: 基本思路都对，但卡了许久，原因是没有 “把当前循环中的大组group那位,从pe ...

正好过了一周了
股票卖了4波，第四波还没完全通过
LC 188 Best Time to Buy and Sell Stock IV 憋了快3天才憋出来！其实跟(自己练过的)optimal BST非常相似！
LC 121 Best Time to Buy and Sell Stock I  不值得一提
LC 122 Best Time to Buy and Sell Stock II 题意一开始没完全搞清楚; 搞清楚后觉得本题是“马后炮”的缺心眼儿题
LC 123 Best Time to Buy and Sell Stock III 我自己的方法推导公式需要2层for嵌套。学了一种左右各一遍DP的招儿！
LC 139 Word Break I 自己用2d DP 解决。已经有些开始习惯一维DP了
LC 140 Word Break II 还是延续自己用2d DP 解决，太麻烦了！看了看网上别人的方案，都是DFS，哼！
LC 91 Decode Ways OJ的263个test cases还有一些没通过，也不知道哪里进坑了 :(  再耐心通通
正在打家劫舍中... ( 小结明后天补上)
LC 198 House Robber I
LC 213 House Robber II
LC 337  House Robber III

补充内容 (2017-9-26 11:50):
LC 91 Decode Ways OJ的263个test cases进坑了 居然是2个if else的分支中缺了continue, 唉！

周一换换脑子，逛一天二分法，特别是环形array。老实说，的确有滥竽充数的目的！上周DP 弄得我有点倦怠了。说得有点不害臊！。。。
LC 35 Search Insert Position 100%滥竽充数的题
LC 34 search for a range: 坑: 找起点时 在相等时 必须移动右指针 即向起点方向逼近! 找终点时  在相等时 必须移动左指针 即向终点逼近! 俗话 两头夹逼!
LC 33 Search in Rotated Sorted Array：找出好描述的分段-即靠近start 或 end 两端的sections，从而用else 去掉难描述的在cliff附近的sections！ == 千言万语归纳成一句话：丢掉sorted 子串，从而达到折半目的！
LC 81 Search in Rotated Sorted Array II
LC 153 Find Minimum in Rotated Sorted Array：我怎么好像在这种题上就没有开递归的窍？对题目实质还是看得不够透彻，所以想的浅，写起来就累！
LC 154 Find Minimum in Rotated Sorted Array II：个人觉得这题出的失败。记住相关的时间复杂度目的就达到了，反正不难，用反例证明即可。