Python-practise

1-20

Index	Name	source code	Improved	Note
1	Two Sum		Ok
2	Add Two Numbers		Yes
3	Longest Substring Without Repeating Characters		Yes
4	Median of Two Sorted Arrays		Yes
5	Longest Palindromic Substring		Bad	Need improve
6	ZigZag Conversion		Yes
7	Reverse Integer		Yes
8	String to Integer (atoi)		Yes
9	Palindrome Number		Yes
10
11	Container With Most Water		Yes
12	Integer to Roman		Yes
13	Roman to Integer		Yes
14	Longest Common Prefix		Yes	My approach, 1, compare two shorest string, 2, compare char by char
15	3Sum		Yes	1, can use hashmap, too. 2, can choose set, 3, my approach, less space cost
16	3Sum Closest		Yes	Trick, if find target, return immediately
17	Letter Combinations of a Phone Number		Yes	IMPORTANT, Bracktracking method, need to redo it again
18	4 Sum		Yes	2, 3, 4 sum summary Best approach is O(kn^2), k is the hashvalue average length 哈嘻表, LESSONS Learned, When using API like set.add(). be careful. It is very costly
19	Remove Nth Node From End of List		Ok	My apporoach: 1, change the node, delete the last one. 2, inorder traverse(n = total - n). Other approach: Remove directly or using list as extra storage. TRY recursive later
20	Valid Parentheses		Yes

21-40

Index	Name	source code	Improved	Note
21	Merge Two Sorted Lists		Yes	Note, not best performance need to improve
22	Generate Parentheses		Yes	poor performance, I used iteration, Can try recursion, I also have it in CC150
23
24	Swap Nodes in Pairs		Yes	It is not a hard problem, but it is very easy to make mistake. if seperate the reverse pair into two case: 1, the init case and other cases. The inital case is simple and do not need to think about the connections between previous nodes
25
26	Remove Duplicates from Sorted Array		Yes	The question itself does not state clear, Two points: 1, return length 2, new list with no-duplicate elements and it doesn't matter what you leave beyond the new length.
27	Remove Element		Yes	Tips, be careful about changing and iterating the list at the same time
28	Implement strStr()		Yes
29	Divide Two Integers		Yes	NNNEED to redo it. Some tricks. 1, two nested while loop, only decrease in the inner loop. 2, the difference between the <<= and <<: 1, << shifts things, but if you don not assign the result to anything, nothing will be record. ex: y = 8. y<<1 -> this gives you 16, but y will still be 8. But for <<=, y = 8. y <<=1 -> y becomes 16
30
31	Next Permutation		Yes	Detailed alg, 3 major steps, 1, find, 2, swapping, 3 sorting.Trick, do not return, you need an in-place sorting alg
32
33
34	Search for a Range		Yes	Tips, if I wanna 6, I search for both 5.5 and 6.5, then find both lower and upper boundaries for 6.
35	Search Insert Position		Yes	Easy, maybe have some other cool way to solve it
36	Valid Sudoku		Yes
37
38	Count and Say		Yes
39	Combination Sum		Yes	First, sorted. Then, dfs: index keep the same position for recursion
40	Combination Sum II		Yes	Performance matters, the recursive call need to prevent the duplicate cases. First, increasing index, Second, the consecutive duplicated integer should be ignored. tracking the current value. GOOD LUCK

41-60

Index	Name	source code	Improved	Notes
41
42
43	Multiply Strings		Yes	May try some other methods, the API is pretty simple. Do not see the point adding char by char
44
45
46	Permutations		Yes	Permutations: 1, bracktrack question using recursion to solve, faster. 2, the increment normally used in the input, not seperate. the function will auto becoming append and pop. Not hard question overall
47	Permutations II		Yes	Need to redo by iteration. Tricks, 1, similar to closet sum. avoid duplicate iteration. 2, using a list of bool to track the integer used or not.
48	Rotate Image		Yes	for i in( 0, len/2) , then 1, first = i, 2, last = len - i - 1, inner for j in (first, last). Finally, offset = last -i. Neet to draw the matrix. It is not hard, but easy to make a tiny mistake
49	Group Anagrams		Yes	NEED huge improve, the normal way is not efficient. maybe string compression
50	Pow(x, n)		Yes	The odd or even power is different. Also, the positive and negative power is different
51
52
53	Maximum Subarray		Yes	Poor perfornamce, the DP method will be better, Need to redo later
54	Spiral Matrix		Yes	Trick for 2d Matrix, 1, the matrix: [[]]: len(matrix) == 1 2, the matrix: []: len(matrix) == 0. So we need to check both of cases, before we do the pop operation
55	Jump Game		Yes	First, I disagree this question uses greedy alg, it is not taking the sub-optimal solution for every step. COOL question, track the max every iteration, step increase, max-1. O(n) method can be found
56
57
58	Length of Last Word		Yes	Nothing hard
59	Spiral Matrix II		Yes	The odd and even cases need to be careful, the logic is similar to array rotating 90 degree
60	Permutation Sequence		Yes	EX: [1, 2, 3, 4], we will have 6! permutation first digit is "1". The next iteration: factorial number: f2 = 6!/i, i = 3. => f2 = 2!

61-80

Index	Name	source code	Improved	Notes
61	Rotate List		Yes	The rotation k can be larger than len(list). First, k = k % len(list)
62	Unique Paths		Yes	Dp program, using the bottom-up approach to save the result for the subproblems. However, the trick is the initialize the matrix at the beginning
63	Unique Paths II		Yes	Similar method as Question 62. Set 1 to None
64	Minimum Path Sum		Yes	Need an improvement
65
66	Plus One		Ok	May be need some other approach, nothing hard
67	Add Binary		Ok	Need an improvement
68
69	Sqrt(x)		Yes
70	Climbing Stairs		Yes
71	Simplify Path		Yes
72
73	Set Matrix Zeroes		Yes
74	Search a 2D Matrix		Yes
75	Sort Colors		Yes
76
77	Combinations		Yes
78	Subsets		Yes
79	Word Search		Yes
80	Remove Duplicates from Sorted Array II		Yes

80-100

Index	Name	source code	Improved	Notes
81	Search in Rotated Sorted Array II		Yes
82	Remove Duplicates from Sorted List II		Yes	Trick, dummyhead, return dummyhead.next
83	Remove Duplicates from Sorted List		Yes
84
85
86	Partition List		Yes
87
88	Merge Sorted Array		Yes
89	Gray Code		Yes
90	Subsets II		Yes
91	Decode Ways		Yes
92	Reverse Linked List II		Yes
93	Restore IP Addresses		Yes
94	Binary Tree Inorder Traversal		Yes	Iteration also have space complexity is O(1)
95	Unique Binary Search Trees II		Yes
96	Unique Binary Search Trees		Yes
97
98	Validate Binary Search Tree		Yes
99
100	Same Tree		Yes

61-80

Index	Name	source code	Improved	Notes
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

Index	Name	source code	Improved
36	Valid Sudoku		Yes
37	Count and Say		Ok
146	LRU Cache		Ok, need other approach
202	Happy Number		Yes