2019年11月20日 星期三

code review筆記



最終目標: 讓code base越來越好

  1. 符合各檢查項目,且能改善code base就可以進
  2. 避免code base越來越亂,越來越難maintain,越來越想打掉重來

2019年7月15日 星期一

ascii 流程圖


筆記一下方便畫ascii 流程圖的方法(例如RFC 文件內的流程圖,或是寫在程式註解內的)

  • graph easy: 流程圖:文字轉ascii
    • 安裝方式參考: https://blog.csdn.net/u012247418/article/details/84674991
      • sudo apt-get install cflow graphviz perl cpan
      • sudo perl -MCPAN -e shell
        • install Graph::Easy <== 安裝需要一陣子
    • grapy-easy xxx.txt
      • xxx.txt類似這樣
        • [a]->[b]->[c]->[d]->[e]
        • [b]->[d]
        • [b]->[e]
        • [e]->[a]
      • 輸出
      •   +---------------------------------------+
          |                                       |
          |                                       |
          |         +-------------------+         |
          v         |                   v         |
        +---+     +---+     +---+     +---+     +---+
        | a | --> | b | --> | c | --> | d | --> | e |
        +---+     +---+     +---+     +---+     +---+
                    |                             ^
                    +-----------------------------+
        
雖然graph easy很強大,可以調整很多參數,
但若是簡單的圖,畫完後直接用下列tool 調整一下就很快了

2019年6月3日 星期一

製作可上傳Facebook的全景照片

步驟 


  • 準備一張投影模式為Spherical的全景照
    • 也可以使用一般相機照多張照片後,透過Microsoft ICE(Image Composite Editor) 合成為全景照
  • 從下列github project 取得convert.py(可能需要安裝相關python 套件)
  • 轉換方法:
    • convert.py [-h] [-o OUTPUTIMG] [-w IMGOUTWIDTH] [-b IMGBGCOLOR] inputImage
    • example: 
      • python convert.py examples\PANO0001_stitch.jpg -o out.jpg


Requirements of Facebook's Panorama image:

  • Image smaller than 6000×3000 pixels
  • Image ratio(width:height): 2:1
  • EXIF:
    • make: RICOH
    • model: RICOH THETA S

2019年5月10日 星期五

線上共同編輯與編譯程式


共同編輯與編譯程式:
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處理的方便性,可以快速解決

2019年5月8日 星期三

[leetcode][python] 1. Two Sum


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




2019年3月31日 星期日

2019年3月26日 星期二

[leetcode][python]40. Combination Sum II

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

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

因此用DP 的方式做:

2019年3月14日 星期四

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



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

做法如下:

2019年3月13日 星期三

[leetcode][python]32. Longest Valid Parentheses

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

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


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


2019年3月10日 星期日

[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 <=下一個又跳回第一組從小到大的組合

2019年3月8日 星期五

[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


2019年3月3日 星期日

[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. 避免重複的答案(因為輸入的測試資料可能包含重複的數字

我的作法是:

2019年2月28日 星期四

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

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


[leetcode] 分享leetcode 的解法

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

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