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

SuperLukedin 发表于 2019-5-9 23:30
便宜的不是一点点

哈哈对，其实那些培训班带着同学做得项目跟udemy上的根本没差多少；就比如某章的全栈课，一共就十八个小时，感觉最多带着做一个项目，结果要收七八百块……去udemy上面买同样设计到相关技术的视频一共也就五六十块，时间都得奔着一两百个小时去了……

赞~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

5.10 做题

41. First Missing Positive. Assuming there is k positive numbers. If there is missing positive, the first missing positive must be within [1, k]; if not, the first missing positive must be k+1. Now we want to set all the valid numbers, the number that within[1, k], to the right places, so that we can check and find out the result. So do first loop. Whenever we meet the cases that the valid number is in the wrong place, we will change it to the right place. Since the right place of a nums[i] is the index "nums[i] - 1", we will swap the nums[nums[i] - 1] with nums[i]. But since nums[nums[i] - 1] may also be the valid number and we can't just skip it, we need stay here in next step to check it and find out whether we need to do any operations. In any other cases, like 1) the valid number is in the right place; 2) there is an invalid number, we will just skip it. After all the things above, we can check the current array one by one from start and find out the result.

299. Bulls and Cows. We can do this in one pass. 1) It's easy to calculate the number of bulls. We just compare the characters in same positions of these two Strings. 2) It's a bit difficult to calculate the number of cows. For a letter in secret, we will want to know if there is already a same letter in the guess. And for a letter in guess, we will also want to know if there is already a same letter in the secret. So for each letter in one string, we need to find if there is a match in another letter. And after that we need to minus one to avoid repeating calculation. So how should we if there is a letter in another String? We will use a HashMap to check. The letter will be the key and the number of the valid letter will be the value. Of course in many cases we can just use an Array to replace the HashMap.

134. Gas Station. The first idea in the discussion is easy to understand. If B is the first station that A can't reach, then all the stations between A and B can't reach B (since A can reach any of them). So we just scan and check to find out if there is any A and B pairs in the first idea. If there is, we just skip all the station and jump to B station. After this one pass, we have a start position that may be a valid start. Since this is a circle path but we now have only one pass, which can only make sure the current start station can reach the nums.length-1 station. We want to know if the current start station can reach the start-1 station. So we need to keep a debt and remain. The remain is the remaining gas that from start station to nums.length-1 station, and the debt is the extra gas we need to make sure the car in the 0 station can reach start-1 station. If the remain gas is more than debt gas, the current start is the solution. If not, there is no solution.

118. Pascal's Triangle. Each length of array is longer than the array above by one and it's easy to calculate the values in current array based on the array above. Time complexity is O(n^2)

119. Pascal's Triangle II. It seems there is no difference from the last one. Just pay attention to the space. We can generate the next row based on the current row in place.

5.10 看网课

今天只看了bootstrap前面的一点点，效率好差，做完了题目就不想干别的了……明天一定要把网课里的bootstrap部分看完

当年感觉题能刷完就不错了 😂
system design都是胡乱看的

5.11 做题

28. Implement strStr(). Just two for loop. The outer loop is to scan if there is a letter in haystack that is equal to the first letter of needle. If there is, do the inner loop. The inner loop is to scan if the substring starting from the current index is equal to the whole needle. If all letters are same, return the current index.

14. Longest Common Prefix. It's easy to find common prefix between two Strings. We can just compare the letters of these two Strings one by one. But How can we find common prefix among more than two Strings? We may compare the letters of first two letters, then find the prefix of the first two, then compare the current prefix with next String, do this until the last String. Here I use another way easier to do. Since it's easy to find common prefix between two Strings, I want to find two Strings from these String Array to compare. First I sort the given String Array. After that, I can reach the first and the last Strings in this Array. As far as I'm concerned, if there is any difference among these Strings in the array, the most different String must be in either the first place, or the last place. I think this is easy to understand what the most different String is. After getting the first and the last, we just need to compare them, just like what we will do when we find the common prefix between two Strings.

58. Length of Last Word. There is a simple way to solve this problem. It gives us a sentence and requires us to find the length of the last word. We may see the given sentence as a String Array and the last word as the last element of the array. So only if we can reach the last element of this array, we will get the length of it. And there is no array now, we can use s.split() method to create a String Array based on the given sentence.

387. First Unique Character in a String. Usually, to find out if there is an unique element in given data structure, we will consider to use HashMap. We will first put all the elements into the HashMap as keys and the value of each element will be their numbers. Then, we will check the key to find out if its value is one. The first key with value one will be the result and we will return its index. And how should we get the first unique character? We just scan the given String from the first letter to the last and check it in HashMap.

383. Ransom Note. First, put all letters in magazine into a HashMap; then, check all letters in ransomNote if there is already a same letter as key in HashMap. If not, the letters in magazine cannot form this ransomNote and we return false. If there is, we take one of them to form this letter and the number of this letter in HashMap should minus by one. If the number of current letter is negative, the letters in magazine are not enough to form the current ransomNote and we return false.

今天按照列表做得题目，都特别简单，但是感觉自己不是那么敏感了主要是对于某些客观上应该很简单的题目来说，很难想到一些很明显的方法……不是很高兴

Husky_wang 发表于 2019-5-10 22:07
哈哈对，其实那些培训班带着同学做得项目跟udemy上的根本没差多少；就比如某章的全栈课，一共就十八个小 ...

我以前也上过贵贵的课，后来想想，里面的技术栈我都在udemy里面一个一个学，效果会不会更好，我都学全了，融汇贯通, 只需要一个线，就可以全串起来，效果会不会不比贵贵的课差。

5.11 看网课

今天看了web bootcamp的Bootstrap3和JS入门，希望明天把JS看到DOM至少

5.12 做题

344. Reverse String. Just use two pointers and swap.

151. Reverse Words in a String. Several utility methods: 1) split(); 2) trim(); 3) Collections.reverse(); 4) String.join(); 5) Arrays.asList()

186. Reverse Words in a String II. This is better than the last. Given a char array and dont need to care about the multiple blanks. Just reverse every single word and reverse the whole char array.

345. Reverse Vowels of a String. First create a HashSet to store all the target letters. Then use two pointers to find out the target letters in given String. When both pointers are pointing to the target, then swap.

205. Isomorphic Strings. When we try to compare to String or Array or any kinds of linear data structure, we may scan from left to right one by one. Sometimes we need use previous comparing results to get the current comparing result. So we use HashMap here. We have had pairs already and store them into HashMap and next time if we meet the same key, we will want to check that in HashMap. And remember usually HashMap may be replaced by an Array.

5.13 刷题

144. Binary Tree Preorder Traversal. There are two kinds of memories in computer, Stack and Heap. Stack is small while Heap is large. If we use recursion here and there are too many recursion calls, it may cause StackOverFlow. So we will want to use Heap, which means we need to use iterative way. But the idea of iteration and recursion methods are same. We may simulate the recursion process in Heap, which means we will create a Stack in Heap. The iterative way to solve preorder traversal problem is similar with BFS. We use an auxiliary data structure to store the node. Expand the top of stack and generate the two children nodes, right first then left, into the stack. In this way, we can print the Binary tree preorder.

94. Binary Tree Inorder Traversal. Here I use a helper pointer. Helper pointer should point to the next node we want to scan. And every scanned node we will push it into the stack. If helper pointer is null, which means there is no next node and the last node we put into the stack is the final node, we will pop the top node in stack and print it. After that, the helper pointer should point to another 'next' node. What is the next node? What's the path of helper pointer? Since this is Binary Tree Inorder Traversal, the helper pointer should follow the in-order path, which is left - root - right. At first, the next node should always be the left node. So helper pointer should always go down left. Then, when helper pointer is null, which means the current root has no left child, we just pop it from the stack and print. Then the next node should be the right child of current node so we let the helper pointer point to it.

145. Binary Tree Postorder Traversal. Still use iterative way. We need maintain a previous node, storing the previous visiting node, so that we know what the direction we're visiting now and what visiting next. Each time we get the top element of stack, as the current node, and if the previous node is null, the current node is the root node and we need go down with priority in left child. if the previous node is the parent of current node, we need go down with priority in left child. If the previous node is the left child of current node, which means we have completed the traversal of left sub tree, we need turn to right subtree. If the previous node is the right child of current node, which means both children we have completed, and we go up. Each time if there is no left and right nodes, we go up, and print.

102. Binary Tree Level Order Traversal. BFS problem based on Queue. For level order traversal, we need to keep the size of current level before expanding and generating. Then putting all expanded nodes into current solution. Do this until the Queue is empty. This is a basic problem.

100. Same Tree. Recursive way to solve this problem. First check the base case: 1) if the two root are both null? 2) if there is only one null root? 3) if the values of two root are equal? After the base case checking, and since two roots have left and right children and each child node may be the root of subtree, we will call recursion function to compare two left children and two right children.