leetcode note -- 1
In order to understand more about the Arlgorithm and Data Structure, I start my leetcode journey from today. I will mainly focus on the medium to hard questions. Python and C will be used.
NO. | URL | Notes |
---|---|---|
2 | add two numbers | This question’s key point for me is: how to represent link structure by using python, in c, the point is quite easy to make a link, but python has no such concept, so I have to create a fake head for it. The header is just header contains no value, unlike c the header also holds a value. |
3 | Longest Substring Without Repeating Characters | Generally the solution is straitforwad. Note the last substring out of loop, the length need to compare too |
5 | Longest Palindromic Substring | Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. The hard part is thinking the special test cases and how to decrease time and space complexity, my original methods is O(N^3), so sad. o(N) solution is brilliant, algorythm is beautiful. Another interesting solution is suffix tree |
10 | Regular Expression Matching | The difficulty is hard, don’t know why. Since python has RE library, this should be quite simple. However, there’s one situation I didn’t consider so didn’t the admin, what if two strings both has ‘.’ ‘*’? for further thinking. |
11 | Understand the question is important, water container not the area!!! | |
12 | Integer to Roman | http://baike.baidu.com/view/42061.htm explains how to calculate with roman numeral. One solution convert directly, like 900 = XC, one is mine, calculate dynamically. My algorithm is always very straightforward…. hard but always can get the answer |
15 | 3Sum | 1. remove duplicated elements 2. sort, and python has a built-in sort 3. python can also make use of array index, same as c 4. python’s list duplicate is not ‘=’ 5.I thought I know algorithms, actually I just know common sence |
16 | 3Sum Closest | Very similar to the last one, just change the target to be a dynamic value |
17 | Letter Combinations of a Phone Number | A good example of recursion. In order to reduce the time complex, the method i used didn’t consider conbination… |
18 | 4Sum | 2Sum->4Sum is a good series to practice find the target number set. The algorithms for the 3 questions are the same, set a target, compare the sum with it, move the left and right pointer. However the larger the set is the more complex it is. For 4Sum, need to notice that the start point of the second fixed number is the first number’s index+1, i+1 |
22 | Generate Parentheses | use 1 -1 to replace ( ). Notice cant do list append when it’s argument. |
29 | Divide Two Integers | it’s about how to do binary divide, just use shift |
31 | Next Permutation | 1. find the pattern, use many examples. 2. pay attention to the edge |
34 | Search for a Range | Key word: reverse. list(reversed()) |
35 | Search insert Position | Python is the best language to solve this problem…. |
39 | Combination Sum | Reversion + how to use index + how set return condition |
43 | Multiply Strings | Mind the edge check, multiply rule |
46 | Permutations | NOTE* Return value of list.remove() is None…. |
48 | Rotate Image | how to change matrix in place needs to find out the pattern. |
49 | Group Anagrams | I thought about using numbers “‘a’:1,’b’:2,’c’:3,’d’:5,” to do it, however this just makes it a mathimatical problem that is more complicated…. |
50 | Pow | Note conditions, float? negtive? negtive divide? -1/2 = -1, special input n, 0 -1; some binary tree idea |
54 | Spiral Matrix | edge counting |
55 | Jump Game | my weakpoint to solve this kind of algorithm problem. it’s kind of model. Make use of the list value and index together to |
56 | Merge intervals | the importance of sorting, and the direction also makes sence |