hoho的日子

Algorithm Time Complexity Space Complexity Best Average Worst Worst Quicksort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n)) Mergesort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n) class Solution(object):     def sortIntegers1(self, A):         # merge sort         # https://www.geeksforgeeks.org/merge-sort/         def merge(left, right):             llen, rlen = len(left), len(right)             l, r = 0, 0             result = []             while l < llen and r < rlen:                 if left[l] <= right[r]:                     result.append(left[l])   ...

In Leetcode Binary Search problems, it provide better search O(log n) instead of O(n) regular search. [ basically, steps are ] 1. determine low and high starting value 2. set mid equal (low + high) / 2 2. give a while loop when low < high 3. return target value if found else increase low or reduce high's value base on mid [ why those steps ] first, it's important to know the range we are going to search. then we can choose the middle element compare list[mid] with target and then adjust low or high. Said you want to find 83 in a list from [1,2,...,100], you only need log2 100 ~= 6.6 times search which much better than 100 times, right? [ 153. Find Minimum in Rotated Sorted Array ] Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,  0 1 2 4 5 6 7  might become  4 5 6 7 0 1 2 ). Find the minimum element. You may assume no duplicate exists in the array. 1.low = 0 , high = length of list - 1...

In Leetcode graph problems, it usually uses BFS or DFS to retrieval the data. It depends on what problem ask and the understanding of the algorithm, I put notes here to help myself review in the future. [ basically, steps are ] 1. determine whether the problem is directional or unidirectional graph? 2. use dictionary or different way to translate the problem into the graph 3. analysis the problem and choose the algorithm 4. design, run algorithm(BFS or DFS) 5. return the answer [ why those steps ] for 1 & 2 it's important to understand the relationship between vertex( or node) and edge (sometimes I like to call it neighbors). Without step1, I'll not able to build up properly graph to represent the problem. for 3,4,5, decompose the problem and solve with most efficient way consider as engineering virtue. Problems.  [ Problem 133 Clone Graph ] Clone an undirected graph. Each node in the graph contains a  label  and a list of its  neighbors . ...

168. Excel Sheet Column Title 思路: 數字 轉 字母. reference map 0 ~ 25 對應到 A - Z 所以在處理n 的時候要 做 (n - 1) // 26. 26 => (26 - 1) % 26 = 25, ref[25] = 'Z' class Solution(object):     def convertToTitle(self, n):         """         :type n: int         :rtype: str         """         dic = {}         res = []         for i in range(65, 91):             dic[i - 65] = str(unichr(i))         while n:             res.insert(0, dic[(n-1) % 26])             n = (n-1) // 26         return "".join(res) 171. ...

Given a string  s , find the longest palindromic substring in  s . You may assume that the maximum length of  s  is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example: Input: "cbbd" Output: "bb" 思路: DP http://yumodev.com/2016/08/16/ leetcode-5-LongestPalindrome. html https://www.youtube.com/watch?v=Fi5INvcmDos Time: O(n^2) Space: O(n^2) 1. 起一個 2 維 矩陣 dp, dp[start][end] 表示 s[start][end] 是否為 迴文 假設字串 為 "babad" 我們可以看到從左上到右下 都為 1 (True), 因為子字串 "b" "a" "b" "a" "b" 都只有一個字 所以一定是 迴文 (line 14) 2. 接者如何判斷一個子字串是否是迴文呢? 假設現在要判斷 "babab" 是否是迴文, 我們可以拆成兩步, a) 字串 頭尾是不是相等 (line 18) b) 中間的子串 在這裡是 "aba" 是否為迴文 (line 16). 上面黃色的位置     另外 如果現在要判斷的字串長度等於 2. 比方說 "bb" 這裡因為沒有中間的子串     所以直接算是 True (line 17) 3. 每次字串被判定為 迴文的時候 就比較一下現在最長的字串