Leetcode 1 - 10
I am now working on solving all the questions from leetcode. I will write a short description for each question and all the code can be found on https://github.com/Jeky/leetcode.
1. Two Sum
The simple answer is for each number, we try to find another number such that they add up to a specific target. This algorithm is O(n^2). I used an O(n) algorithm which is for each number, we first try to find if there is another number such that they can be summed to target. If there is this number, we return the indexes of these two numbers, otherwise we check next number. The finding step is O(1) based on a set searching (The worst case of this is O(n)).
2. Add two numbers
This question is so easy if using recursion. We need to be careful of 1. the end of linked list; 2. carry when adding.
3. Longest Substring Without Repeating Characters
This problem is to find the longest substring without repeating. So we can go through the string, adding each characters into an array. Once we find there is a character that has already been added in the array, we save the current length of array and remove characters from the array till current character has been removed.
In the answer, I converted all the characters into integers to speed up comparison.
4. Median of Two Sorted Arrays
This is the first question marked as HARD. In fact I didn’t solve this question all by myself. I followed this answer which gave really awesome anwser and explanation of this question.
5. Longest Palindromic Substring
Another simple question about substring. All you need is to search longest palindromic substrings starting at each location on string. Make sure that the length of palidromic substring can be either even or odd.
6. ZigZag Conversion
The example of this question is misleading. If you can convert the example into the following format,
P A H N
A P L S I I G
Y I R
then you can find the relation between the index before converting and the converted index.
1 5 9 13
2 4 6 8 10 12 14
3 7 11
7. Reverse Integer
This is the easiest one in the first 10 questions. Just be careful about negitive value and overflow.
8. String to Integer (atoi)
Another easy question. Try to think about every possible input case, including blanks and letters. Overflow need to be checked as well. (However, I solved all the questions in Python, in which overflow of an integer is not possible.)
9. Palindrome Number
Another integer reversion quesion.
10. Regular Expression Matching
A hard one. At first I tried to solve this problem by recursion and forward searching. It turned out to be time exceeding on some regular expressions.
a*a*a*a*a*a*a*a*
This is because for each wildcard, we will create two leaves for different matching.
Then I converted the recursion into stack because I thought this is just because recursion is really slow in Python. After converting the problem remained same. So I found another way, changing searching direction into backward, to speed up the algorithm.
