線上共同編輯與編譯程式

共同編輯與編譯程式:
https://repl.it/
https://codebunk.com/

共同編輯文字檔，有程式語言syntex highlight:
http://collabedit.com/

I2C 筆記

參考資料:
http://wiki.csie.ncku.edu.tw/embedded/I2C
http://www.ti.com/lit/an/slva704/slva704.pdf


I2C

• 連線基本上是wired-and，有一個裝置拉low 則整個bus都low
• 基本上1 master -> n slave
• 但可有多master
• 基本上master在有資料傳輸時會等待
• 若兩個master很剛好同時要運作，wired-and 特性會讓其中一個master發現到有人同時在傳而停止傳輸
• 若 Master 1 欲將 SDA logic 拉高，最後卻 SDA logic 為低，代表仲裁輸了，該 master 立即停止動作。
• 若同時起始傳輸，與較小slave address 溝通的master會拿到bus(因為與較大slave address溝通的master會在address內的某個bit寫1，但bus卻仍為0)
• 同理，若slave address 相同，則write 的master 拿到bus(因為write bit為0, read 的master 發現設1但讀出為0)
• 若兩個master 皆為Read, 則沒差，
• 若兩個master 皆為write, 則看誰比較先遇到寫1時另一個master寫0
• 輸掉的 master 寧可先放棄 (Back Off) 等候，到看見停止狀態的出現才開始傳送。
• Serial, 8-bit oriented, bidirectional data transfers
• slave address: 
• 7bit, 保留16個，故最多只能跟112個節點通訊
• 1byte
• addr bit 6~0 + R/W bit
• 10bit, 分2byte傳輸, ，address 開頭固定為11110
• byte1: 11110 + bit9 bit8 + R/W
• byte2: bit 7~0
• bus 
• speed: 
• 低速 10Kbit/s 
• 標準 100Kbit/s standard-mode
• 快速 400Kbit/s fast-mode
• 快速+ 1Mbit/s fast-mode plus\
• 高速 3.4Mbit/s high-speed mode
• 超快速: 5Mbps ultra fast-mode(uni-direction)
• 2 pin, 需要pull high, 
• SDA: data
• SCL: clock
• terminology
• Transmitter : the device which sends data to the bus
• Receiver : the device which receives data from the bus
• Master : the device which initiates a transfer, generates clock signals and terminates a transfer
• Slave : the device addressed by a master
• read/write整體流程
• write
• master:
• START
• send slave address(7bit) + 0(1bit, r=1, w=0)
• slave:
• 回ACK(SCL=high 時將SDA 拉low)
• master:
• send register address(8b)
• slave:
• ACK
• master send new register value
• slave ACK
• 這兩步可repeat, 代表接著寫下一個register
• 結束後master 送STOP
• read
• master
• START
• send slave address(7bit) + 0(1bit, r=1, w=0) 注意是write, 因為master 要先寫register address給slave
• slave
• ACK
• master:
• send register address(8bit)
• slave:
• ACK
• Master 
• START again
• send slave address(7bit) + 1(1bit, r=1, w=0) slave已經知道register address, 這邊才跟slave 說要讀
• slave
• ACK
• slave send register value
• master NACK
• master STOP
• 資料傳輸
• 一次傳1 byte, 然後收ack，若無ack則代表出問題，停止傳輸，丟出STOP
• data transmit
• START bit
• SCL high, SDA high->low
• DATA
• SCL high, SDA stable
• SDA 變動時只能在SCL 為low的時候
• STOP bit
• SCL high, SDA low->high

擷取自TI 文件(http://www.ti.com/lit/an/slva704/slva704.pdf):

[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/


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

LED 旋轉顯示器

demo 影片

source code: https://github.com/cy-arduino/led_spin_display

載具(開發用):

馬達: 無刷( 2212, 980KV)

電變: 30A

PWM轉速控制: arduino nano

本體

LED:

單色16顆

供電:

電池

傳輸:

無線(BT HS-05, SPP)

轉速偵測:

光遮斷器

開發版:

arduino nano

設定方法: 

透過BT SPP，下command控制LED 顯示內容

範例:

好棒棒.txt 

gogogo.txt