[leetcode][python] 54. Spiral Matrix

題目要求是對一個matrix 以螺旋方式取出

利用python 對list處理的方便性，可以快速解決

[leetcode][python] 1. Two Sum

使用hash table 的特性(最快可達到O(1) 速度的查找) 來加速，若hash table查找速度為O(1), 此演算法複雜度即為O(n)

[leetcode][python]44. Wildcard Matching

這題看起來不難，實際上跑了之後才知道原來難在速度

[leetcode][python]40. Combination Sum II

這題的目標是要從提供的組合內(內容可能重複) 選出加總為target 的組合

但選出的組合又要求不能重複

因此用DP 的方式做:

[leetcode][python]33. Search in Rotated Sorted Array

這題要求O(log n) 的時間複雜度，因此我使用binary search的方式
但由於這個排序的數列的起始點並不是在第一個元素，而是可能在任何地方，所以需要做額外判斷

做法如下:

[leetcode][python]32. Longest Valid Parentheses

這題一開始想用記數去做，
從串列每一個元素當開始，往後一個一個元素加進去

• 看到'('就+1，看到')' 就-1
• 若計到0就代表是一串合法的組合
• 若>0 則代表這串中間有合法的組合(一到多組)，開頭往後一個元素
• 若計到-1代表這串不合法，因此這串不用再檢查，下一個run檢查的開頭就跳到這串之後

這樣做出來結果正確，但是時間複雜度太高，會跑到timeout

[leetcode][python][c]31. Next Permutation

這題雖然難度是中等，但想了好久才想到規則，因此紀錄一下


舉一個例子

[1,2,3] 的所有排列組合順序:

1. 1,2,3
2. 1,3,2
3. 2,1,3
4. 2,3,1
5. 3,1,2
6. 3,2,1 <=下一個又跳回第一組從小到大的組合

[leetcode][c]25. Reverse Nodes in k-Group

大致想法是這樣:
[framePrev]->[frame: k nodes]->[frameNext]

然後allocate stack(k 個pointer), 用來存放一個k個node 的指標
將此frame 反轉後，再將frame 往後移

[leetcode][python]21. Merge Two Sorted Lists

沒有重新allocate memory, 只是單純修改指標

source code:

https://github.com/cy-arduino/leetcode/blob/master/21.%20Merge%20Two%20Sorted%20Lists.py

[leetcode][python]20. Valid Parentheses

這題主要概念是使用stack，若是左括號類型就丟進stack，右括號類型則從stack 取出對應的符號

[leetcode][python]17. Letter Combinations of a Phone Number

這題做法很簡單，
使用遞迴的方式，將目前所有的組合上加上下一個數字可能產生的所有字元



舉例來說

[leetcode][python][c] 15. 3Sum

這題主要有兩個需要注意的部分:

1. 降低尋找所有組合的複雜度
1. 暴力法: (n-2)*(n-2)*(n-2) = O(n^3)
2. 我的作法: O(n^2)
2. 避免重複的答案(因為輸入的測試資料可能包含重複的數字

我的作法是:

[leetcode][C][python] 53. Maximum Subarray

這題雖然是easy, 但是還是卡了一下，一開始雖然想到大致上O(n)的做法，但是沒有想得很透徹，寫了一堆例外處理卻一直有處理不完的case
後來重新整理一下思緒，終於將架構改得比較完整

[leetcode] 分享leetcode 的解法

最近剛好有一段空閒，想說刷一下leetcode
也順便把有跑過的code放到github上，成績較好或是想法比較有趣的部份就在blog做一下紀錄

以前寫過的部分題目當初皆用C 寫，
現在新刷的部分由於想要快速驗證想法，皆使用python3來做，有空才會再用C 寫一遍

[leetcode][python] 46. Permutations

leetcode 連結:
https://leetcode.com/problems/permutations/



這題是找出一組不重複的集合的所有排列組合


做法很簡單，使用遞迴的方式，輪流從集合內拿出不同的內容放入解答內，直到集合內所有內容被挑完，這樣解答就是其中一種可能性

[leetcode][C] 50. Pow(x, n)

https://leetcode.com/problems/powx-n/



顧名思義，這題是想自己實做pow(x, n)

最簡單的方法當然是直接把x 乘以n次，但這樣時間複雜度就變成O(n)，

要加快速度，有一個做法就是重複利用已經乘過的數

舉例來說，pow(2,5) = 2*2*2*2*2 = (2*2)*(2*2不用重算)*2

[leetcode][python] 48. Rotate Image

leetcoded 連結:
https://leetcode.com/problems/rotate-image/


這題基本概念是把矩陣想成是像"回" 字形一樣一圈圈，一次處理一圈