資料科學小嫩嫩 9/26 - Day 6 Leetcode two sum

前篇: Leetcode setup

資料科學小嫩嫩 - 9/26

ITHome Day 6 Leetcode 1 TwoSum

之所以用 C++ 刷題, 是因為最近看狗狗幣

    ( 可以參考 這篇 狗狗幣 簡介 )

似乎是用 C/C++ 來做, 初期目標是先幫它解一個 github issue.. 

以前有用過 Ｃ刷題 leetcode, 如這篇 Linux kernel 的 hash by C

但底層一些 algorithm 如 hash 要自己做.. 有點麻煩.. 

所以先用 C++ 來印證一下, 雖然程式語言上有些不同, 

程式原理 思考邏輯 是相通的

-- 

引述 社團中 維元老師所說的: 

維元老師建議我們不要就直接刷了，然後一題接一題，而是採取下面四個步驟，

1. 先看一下題目描述
2. 再搭配範例理解題目
3. 開始實作：從「#初探直覺解」開始並且一起嘗試「#刻意優化」的過程。維元老師更建議花多一點在一個題目中，盡可能地持續迭代、持續優化並且思考沈澱，讓你從一個題目掌握到更深更廣的效益。不要急就章的一題接一題。

--

1. Two Sum

    方法ㄧ: 兩個迴圈的暴力搜尋法就不特別寫了. 

    方法二: 用雜湊表 Hash

                C++ 的 unordered_map 就是 hash map. 

     github

如果不是加法而是其他複雜的運算的話, 多 thread 多工來處理的方式已經是常態. 

畢竟 PC 現在已經是多核, 

另外若 nums[] 資料龐大的話, 還需要搭配多工時考慮各 CPU cache 放的資料位置.

15. 3 Sum

   方法三: 如果有排序的話, 可以用迴圈加雙指針來做. 

   以 3 sum 為例, 可以取頭一個, 簡化為 two sum, 接著用迴圈+雙指針來做

    github

C++ 可以用 qsort

18 - 4sum

    github

    借助前一個 3sum 加一個迴圈, 要注意重複同樣數字時, 在4sum 也要處理略過

167 - two sum II - input array is sorted

    github

    這個就是方法三, 雙指針迴圈, 有排序的都可以這麼做

653 - two sum IV - input is a BST

    github

    BST 可用在排序, 轉換成 vector 就和前面一樣了

不過這似乎還不是最快速的方式, 之後有機會繼續再看看能否繼續優化. ^^