假期四个月计划 - 刷题|补基础|看网课|做项目

5.14 做题

101. Symmetric Tree. This is similar with the same tree problem. There are only two differences. 1) the signature of method only has one parameter, which means we need create a helper function; 2) this problem is about Symmetric Tree rather than the same tree. In the Same Tree problem, we need make sure all roots are equal and the left and right child nodes are equal. So we call recursion function on (left, left) && (right, right). While here we need make sure the they are symmetric. So we call recursion function on (left, right) && (right, left).

226. Invert Binary Tree. Postorder. Base case is returning current root if root is null; then call recursion function on both left and right subtree; at last the post-processing is inverting the left and right node.

257. Binary Tree Paths. Typical dfs problem. We need a helper function to do the DFS process. And the parameters of helper dfs function should include result list, current root node, and current path String. Every time we add the value of current root node to the current path String, using StringBuilder and append. Then we check if we can still go down to the child nodes. If there is node left or right child nodes, we can add the current path String to the result List and return; if there is , we continue to call recursion function on left and right nodes. The recursion tree is just like the given binary tree. There number of levels is the number of given tree levels and the nodes in each parent are two.

112. Path Sum. Corner case is if root is null, then return false; Base case is if there is no left or right node in current root, we can compare the value of current root with the current sum. If there is still child node, we call recursion function on both left and right nodes, and the current sum should minus the value of current root.

113. Path Sum II. This is almost the same problem as Path Sum I. The DFS process is similar and we just need to pat attention to the design of signature and how to store all valid path.

今天因为做题都忘记看库里的比赛了，我库新一代西决之王！

楼主加油啊，我没找到实习，也想着暑假好好学一下

这个思路挺好的 共勉加油

楼内怎么加米。。

楼主很棒 加油！！！

5.15 做题

78. Subsets. There are two ways to construct the recursion tree of this problem. The solution in discussion construct a k-nary tree, while mine is a binary tree. The number of levels of my recursion tree is equal to the number of elements in given array. And each node has two child nodes in recursion tree. So we need call recursion function twice, one is adding current element while the other is not. Then we continue to the next elements in given array. I think the design of signature is really important.

90. Subsets II. This is the same problem as the last one. The only two differences are we need to add a HashSet and sort the given array before we do DFS, in order to avoid the repetition. It really confuses me why to sort first?

77. Combinations. Still very similar with the Subset problem. The only difference is in base case. Since this is the combinations problem, we must make sure all results have length exactly equal to given K. And we use this as the base case.

39. Combination Sum. There are two important points in this problem. First, we need sort the given candidates array first. Since in recursion function, we scan from left to right, and the elements in left-side will be first inserted into the solution. I think all following discussion are based on this large element. If the elements in left-side are too large, the target in following recursion calls will be too small. So we just need to put smaller elements in left so we still have target values in following recursion functions call. The other thing is, how do we call the recursion function? In this case, we are allowed to use elements repeatedly to sum up. So we call recursion function with the same index, rather than index + 1, which is different from the last few dfs problems. However, if we call recursion function like that, there will be stackoverflow since there is no difference in recursion function. We need to change the target value, just like what we do in Path Sum problem. So the base case is when target value is equal to Zero, we will get one result. Besides, in the loop condition, we need add a condition, the one that the current target should always be larger than current candidate elements. Since every time we call recursion function, we will minus target by current candidate elements. And since the base case is target equal to Zero. If we don't add the condition that target should be always larger than current element, in following recursion functions call the target will be negative, will continually decrease. And it will never meet the base case. In this case, the stackoverflow will happen.

40. Combination Sum II. 和前面那个题差不多一样，要注意的就是这个题目的given candidates array allow duplicates while in the solution, both solu and res, the duplicates are not allowed. So I use a HashSet as res, and the recursive rule is a bit different.

5.16 做题 今天效率特别低，只做了三个题目，视频也没怎么看，其他时间都在发愣玩手机看youtube小视频

216. Combination Sum III. Almost the same problem as the Combination II except for the base case. Here we need values in given numbers, which are between 1 to 9, and sum them up to be equal to the target. Based on this, we can have our base case. The recursion rule is almost the same as the last one. Be careful about the pass-value when calling recursion functions. The cur should be i + 1 rather than cur + 1.

377. Combination Sum IV. 这个题目当然可以用recursion用dfs的方法去做，但是会遇到TLE的问题。所以想到用DP去做，DP的话就需要从小的结果推导出大的结果。这里，对于一个数字n的组成来说，如果有dp[n]种组成方法，那么对于数字n+k，就应该有dp[n] + dp[k]种组成方法，这是显而易见的；因此，dp[target]就代表着，要组成target这个数字有多少种组成方法；按照刚刚说的推导方式，dp[target] = (dp[target - 1] + dp[1]) + (dp[target - 2] + dp[2]) + ......。当然，这个题目给了一个array，那么所有的数字都要从这个array里面取才行，如果target - 1和1不在array内部，那么这一个部分就不能加进去。所以最后的推导方式就像discussion里面给出的：comb[target] = sum(comb[target - nums[i]]), where 0 <= i < nums.length, and target >= nums[i]。

254. Factor Combinations. 这个题跟加法的组合一模一样，套路完全相同，只不过call recursion function的时候，由减变成了除，而且因为整除的缘故，recursion tree还要有剪枝的过程，也就是说必须n能够整除当前的数才可以往下进行dfs下去

5.17 做题

60. Permutation Sequence. Only iterative way ...... According to discussion, we need to form the permutation based on K, rather than form all possible permutation first then take the K.

31. Next Permutation. just follow the rule given by wikipedia. four steps. it's not difficult to implement it.

206. Reverse Linked List. Recursive way to solve Reverse Linked List.

141. Linked List Cycle. 快慢指针

24. Swap Nodes in Pairs. Still use recursive way as reverse LinkedList. The post-processing is a bit different

328. Odd Even Linked List. in place manipulation. remember there is another helper node, evenHead to keep the first even node.

92. Reverse Linked List II. Dummy Node

楼主我说说我的two cents， 如果有用的话，拜托给加点米， 实在是好多想看的贴看不到。。。真诚脸感谢！当然也欢迎大神来批评指正。。。。

“三、方向：准备SDE，主要希望的中短期发展方向，就是全栈web开发、并把重点放到后端上面，希望能够对用Java实现的RESTful API、Service、MicroService以及各种相关的Tools都有更好的理解；此外希望对Android开发有些初步了解，对DevOps的工具混个眼熟；当然最重要的也还是做题，虽然现在的面试基本上还没到考察我做题的那一步我就凉了，但是最终还是要做题。”

其实好多jd里面讲的full stack就是前端+Restful API，我觉得microservices里面涵盖的内容太多了，这么几个月想有很好的理解真的很难。。。安卓开发的话又有一套自己的工具，虽然我知道楼主可能是想尽可能用不同的项目充实简历，但是我觉得这么多工具这个暑假下来听网课听这么多真的太耗费时间了哇，除非楼主真的炒鸡喜欢mobile.我的建议是把重点放在刷题上（多做多总结不是无脑刷），然后简历上的project可以有多个，但是是重点侧重某一个类型的project，比如full stack dev。mobile的东西可以暂时缓缓，学有余力了再看。DevOps的那些工具，我觉得可以从软件开发流程方面稍作了解，比如你知道它们在CI/CD时候大概起什么作用，有些网课会简单的教教，我觉得你用来写简历就够了，但是想真正理解还是得花时间用花时间学习。。所以也不建议太focus在这上面。。


“3）全栈web开发：主要是前端，希望比较熟练掌握HTML/CSS/JavaScript的各种使用，同时掌握一些基于JS的框架，所以准备重新看一下udemy上面的两个web的网课，也就是有名的web developer bootcamp和后续的advanced web developer bootcamp，希望借此学习有关Bootstrap、JQuery、Node、Express、AJAX、D3、React等等工具库框架，如果学有余力再去看Angular / React专门的网课；”

如果楼主想学学前端框架，建议从React上手，毕竟不像Angular learning curve那么陡，而且使用也很广泛，e.g. fb, walmart, paypal, apple....推荐一下 stephen grider的udemy课程，我觉得讲得非常清晰还很适合入门，因为stephen讲课真是assume你啥都不知道一步步引导着你来给你讲得。。。然后个人觉得jquery这东西楼主这么紧张的时间就不用看了吧。。。Express可以好好看一下，内容少又实用！！D3要是没时间也不建议深究。。除非你对data visualization很有兴趣。。。

“4）后端：希望把Java和Spring相关的关于后端的知识都逐渐补全，主要是用udemy和IMOOC两个平台上的网课去学，学习路线就是先从最基本的用Tomcat管理Java Servlet写RESTful APIs开始，接着学框架，熟悉了Spring、Spring Boot等以后再去学一些周边的Tools（Maven、Docker还有Testing之类的），然后学习用Spring Cloud实现MicroServices的知识，也就是那些Spring Cloud Netflix的项目，希望到最后自己能够熟悉究竟用Java做后端到底是怎么回事；”

Java Spring这些东西想学懂又是一个浩大的工程。。。感觉这里可以量力而行不用花太多时间。。。毕竟只有这个暑假

“6）其他：如果有时间的话，可以去udemy上找个Android的做做，写在简历上也算比较好看；还有Golang，Google Cloud还有BigTable什么乱七八糟的，都可以做；还有udemy上面有好多看起来不是特别不复杂的全栈项目，不知道这个论坛里面为什么很少有人提及，可以跟着做一做，在简历上好好包装一下，可能就可以比较吸引人。”

我个人觉得吧楼主出发点是好的，想在简历上多一些这些技术的字眼，可是比如面试的时候，他问你，哎你使用过这么多gcp的工具有什么心得吗，我觉得如果你不真的了解他们的话这样的问题抛出来真的不一定能答好。。。所以我建议是准备一到两个你自己做的project，并且你对这里面用过的东西很熟悉，如果问起来的话可以胸有成竹的跟面试官掰扯。总而言之，看了楼主写的这些project目标感觉就是这些确实都是当下非常流行非常有用的技术没错，但是放在一个暑假任务实在太重太宏大了。。不如先上好一门网课，先做好一两个js web app，你就对web app dev有一个初步了解了，简历上该怎么吹也就心中有点数了。。。然后多留出时间好好做题。。

最后，真诚恳切大家路过加点米帮我看帖。。。也欢迎大神来批评。。一起学习一起进步！

chenyutong 发表于 2019-5-17 22:26
楼主我说说我的two cents， 如果有用的话，拜托给加点米， 实在是好多想看的贴看不到。。。真诚脸感谢！当 ...

so helpful. 好有建设性的建议真是非常感谢！

然后我现在主要就是先保证每天的刷题；然后看两个web的网课补一补基本概念，因为相关的基础知识实在有点薄弱，其他框架之类的，网课里提及的部分掌握好，没有提及的我再考虑要不要深入；

Spring/Spring Boot/Spring Cloud的话我就是准备先看个视频入个门，知道是怎么回事先，然后再酌情考虑要往简历上放什么，然后如果视频有附带项目的话跟着好好做一下就好，当然这都是建立在如果我有时间的基础上；

然后其实我就是希望能够学习一下server-side programming in Java，你觉得往这方面学习补充的话可以这么做呢？🙏（我在你别的回复有价值的帖子里加米了，这个帖子貌似不能楼内加米