My Leetcode solution collection.

# milestone

Title Description Solution Speed & Percentile
1. Two Sum find a pair summing to target value. hashmap with early stop. 7ms, 98%
3. Longest Substring Without Repeating Characters as title. bitmap in replace of hashmap recording most recent position. if there is a collision then found a repeated character. 19ms, 98%
4. Median of Two Sorted Arrays find median number from two sorted arrays. do binary search on the shorter array between nums1 and nums2, compare the max\min number of left\right hand side. Median is a position that the number of elements at two sides are equal. 42 ms. 98%
5. Longest Palindromic Substring as title. straightforward: for loop each element and expand at both side; best: only expand at right and jump through repeated elements as repeated one no matter how long it is will definitely be a valid palindrome string 4ms, 100%
6. ZigZag Conversion given a string, and place it in a zigzag way, then collect them row by row to form a new string. create zigzag moving iterator that follows the pattern of the normal for loop iterator. Essentially, to have a direction indicator that will change the zigzag iterator’s moving direction. 21 ms, 98.44%
7. Reverse Integer as title. check integer overflow before potential operations, trick is to check if applying reverse operation can yield original result. 16 ms, 99.17%
8. String to Integer (atoi) as title, with some edge cases. convert each character to integer, check if overflow before any further operations. 4ms, 100%
11. Container With Most Water an array of integer, as vertical lines on coordinates, together with x-axis forms a container, find the one holds most water. two pointer at two ends moving inwards. we can prove that moving the longer line inward is always worse than the current result. Thus we move the shorter line inward. 4ms, 100%

## todo

• summarize common modular operations and helpful algorithm functions, with their time complexity, such as “longest common substring\subsequence”, “check if integer overflow”.

• summarize common data structure implementation, such as trie tree. put the above two section on Leetcode算法思路.

• also recording each solution’s time & space complexity.

• check “Discussion” tab for smart tricks.

# 1 two sum

• 最快的算法里对std::sort的使用。

• 想清楚什么时候需要引入dummy node。

• map

# 14 longest common prefix

problem: as title.

## ideas

• [me] vertical scanning. time complexity: O(S), where S is the sum of all characters in all string. space complexity: O(1).
• divide and conquer. because LCP satisfies the associative property, that LCP(1,…, n) = LCP(LCP(1,…, n/2), LCP(n/2+1,…, n)). as like in finding min or max. time complexity is O(S), space complexity is O(mlogn), n is the number of string, m is the average length, since divide and conquer requires to store intermediate results.
• binary search. an improvement on the vertical scanning. apply the binary search on the shortest string and do the vertical scanning to validate if it’s LCP. time complexity is O(S * log(min string length)), space complexity is O(1).

# 866 prime palindrome

problem: find a prime number that is also a palindromd over N.

## ideas

• find palindrome then check if prime.

the set of palindrome is smaller, and for each palindrome, we can test whether it is prime in O(N^1/2).

-> find the set of palindrome number over N.

-> how to find the next palindrome number.

from the center move outward, find the critical digit to add 1.

## summary

define the palindrome root. say 121 is 12. thus we can use palindrome root to construct palindrome number by increase it by 1 at a time.