雲林SONG

題目連結 https://leetcode.com/problems/ugly-number-ii/ 。因為 Ugly Number I 比較容易，跳過直接解此題，此題的Hint實在太好了，於是筆者寫了這樣子的解法： class Solution { public: int nthUglyNumber( int n) { if (n == 0 ) return false ; if (n == 1 ) return true ; vector< int > ugly(n); int m2, m3, m5; ugly[ 0 ] = 1 ; m2 = m3 = m5 = 0 ; int k = 1 ; while (k < n) { ugly[k] = min(ugly[m2] * 2 , min(ugly[m3] * 3 , ugly[m5] * 5 )); if ( ugly[k] == ugly[m2] * 2 ) m2++; if ( ugly[k] == ugly[m3] * 3 ) m3++; if ( ugly[k] == ugly[m5] * 5 ) m5++; k++; } return ugly[k- 1 ]; } }; 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 29. Divide Two Integers 兩數相除

題目連結 https://leetcode.com/problems/divide-two-integers/ ，題目要求不可以用乘法、除法與餘數運算子。從題目分類的Tag上，筆者看到了Binary Search後，就想到位元運算子，只是筆者考慮欠周詳，因為送出後一直得到Wrong Answer阿，原來是忘了考慮Overflow的問題，於是看了此Discuss 後，寫了如下的程式碼： class Solution { public: int divide( int dividend, int divisor) { if ( divisor == 0 ) return INT_MAX; // Handling overflow if ( dividend == INT_MIN ) { if ( divisor == - 1 ) return INT_MAX; else if ( divisor == 1 ) return INT_MIN; else return ( (divisor & 1 ) == 1 ) ? divide( dividend + 1 , divisor) : divide( dividend >> 1 , divisor >> 1 ); } if ( divisor == INT_MIN ) return 0 ; int sign = (dividend >= 0 ) ^ (divisor >= 0 ) ? - 1 : 1 ; long dEnd = abs(dividend); long dSor = abs(divisor); int quotient = 0 ; while (dEnd >= dSor) { long tmpSor = dSor, q = 1 ; while ( dEnd >= (tmpS...

LeetCode OJ: 300. Longest Increasing Subsequence 最長遞增子序列

題目連結 https://leetcode.com/problems/longest-increasing-subsequence/ ，此題用動態規劃解。 class Solution { public: int lengthOfLIS(vector< int >& nums) { if ( nums.size() == 0 ) return 0 ; short *best; best = new short [ nums.size() ]; best[ 0 ] = 1 ; short maxLen = 1 ; // Dynamic Programming: // if( num[i] > num[k] ) // best[i] = max(best[0] ... best[k]) for ( int i = 1 ; i < nums.size(); i++ ) { short tempBest = 0 ; //找出比數字比 num[i] 小且序列長度為最大的值 for ( int k = i - 1 ; k >= 0 ; k-- ) { if ( nums[i] > nums[k] ) { if ( tempBest < best[k] ) { tempBest = best[k]; } } } best[i] = tempBest + 1 ; if ( best[i] > maxLen ) maxLen = best[i...

C++ STL：找質數 ( Prime Number with C++ STL )

因為STL的 iteractor 算是指標(還是有差異)，那麼就可以先將有可能成為質數的整數都放進vector裡，然後採埃拉托斯特尼篩法加上雙指標將非質數的整數給刪除。 /* Prime Number using STL */ #include <iostream> #include <functional> #include <algorithm> #include <iterator> #include <vector> using namespace std; int main ( void ) { vector< int > primes; int n; cin >> n; for ( int i= 2 ; i <= n; i++) primes.push_back(i); vector< int >::iterator primeBegin= primes.begin(), primeEnd= primes.end(); while ( primeBegin != primeEnd ) { primeEnd= remove_if ( primeBegin+ 1 , primeEnd, not1 ( bind2nd ( modulus< int >(), *primeBegin))); primeBegin++; } primes. erase ( primeEnd, primes.end()); copy( primes.begin(), primes.end(), ostream_iterator< int >( cout, " " )); cout << endl; return 0 ; } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

用Yocto Project建立樹莓派2的最小映像檔

Host OS: 14.04.1-Ubuntu x86_64 安裝 Yocto Project 所需的套件： sudo apt-get install sed wget cvs subversion git-core coreutils \ unzip texi2html texinfo libsdl1.2-dev docbook-utils gawk \ python-pysqlite2 diffstat help2man make gcc build-essential \ g++ desktop-file-utils chrpath libgl1-mesa-dev libglu1-mesa-dev \ mercurial autoconf automake groff 下載 Yocto Project 與 Raspberry Pi meta layer mkdir rpi2 cd rpi2 git clone git://git.yoctoproject.org/poky.git cd poky git clone git://git.yoctoproject.org/meta-raspberrypi 環境設定： . ./oe-init-build-env build 修改 local.conf nano conf/local.conf 增加下面兩行(如下圖)： MACHINE ??= "raspberrypi2" GPU_MEM = "16" 修改 bblayers.conf nano conf/bblayers.conf 增加下面一行(如下圖)： <strong> /home/jaufranc/edev/rpi/yocto/poky/meta-raspberrypi \</strong> 產生映像檔： bitbake rpi-basic-image 映像檔寫入 SD Card ： sudo dd if = tmp / deploy / images / raspberrypi2 / rpi ...

C++語言教學：STL 概觀 ( STL Overview )

- 2月 21, 2016

投影片下載處： C++ STL 概觀 from PingLun Liao 範例程式： http://www.4shared.com/archive/LrETKOzUba/CppStl_Example.html 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

C++語言教學：函式 Function

- 2月 21, 2016

投影片下載處： C++ Function from PingLun Liao 範例程式： http://www.4shared.com/archive/RyA88CD0ce/CppFunctionExample.html 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

C語言教學：檔案處理 ( File Handling in C )

- 2月 21, 2016

投影片下載處： C 檔案輸入與輸出 from PingLun Liao 範例程式： http://www.4shared.com/archive/ny8F-v2ece/C_FileIO_Example.html 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 219. Contains Duplicate II 有重複數字嗎？

題目連結 https://leetcode.com/problems/contains-duplicate-ii/ 。此題比 LeetCode OJ: 217. Contains Duplicate 有重複數字嗎？難一點點，不過依然用 Java 的 HashMap 來計數： public class Solution { public boolean containsNearbyDuplicate ( int [] nums , int k ) { HashMap < Integer , Integer > numbers = new HashMap <>(); for ( int idx = 0 ; idx < nums . length ; idx ++) { if ( numbers . containsKey ( nums [ idx ]) == false ) { numbers . put ( nums [ idx ], idx ); } else { int preIdx = ( int ) numbers . get ( nums [ idx ]); if ( idx - preIdx <= k ) return true ; numbers . put ( nums [ idx ], idx ); } } return false ; } } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 217. Contains Duplicate 有重複數字嗎？

題目連結 https://leetcode.com/problems/contains-duplicate/ ，直接用 Java 的 HashMap 來計數(這題很容易吧)。 public class Solution { public boolean containsDuplicate ( int [] nums ) { HashMap < Integer , Integer > numbers = new HashMap <>(); for ( int i = 0 ; i < nums . length ; i ++) { if ( numbers . containsKey ( nums [ i ]) == false ) { numbers . put ( nums [ i ], 1 ); } else { return true ; } } return false ; } } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 268. Missing Number 消失的數字

題目連結，因為題目剛好可以用標記的方式紀錄數字是否有出現過，所以就寫了下面的程式囉： public class Solution { public int missingNumber ( int [] nums ) { int size = nums . length + 1 ; boolean [] found = new boolean [ size ]; for ( int i = 0 ; i < size - 1 ; i ++) found [ nums [ i ] ] = true ; for ( int i = 0 ; i < size ; i ++) if ( found [ i ] == false ) return i ; return size ; } } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 287. Find the Duplicate Number 找重複出現的數字

題目連結，筆者採取跟 Single Number , Single Number II , Single Number III 相同解法： public class Solution { public int findDuplicate ( int [] nums ) { int target = 0 ; HashMap < Integer , Integer > numbers = new HashMap <>(); for ( int i = 0 ; i < nums . length ; i ++) { if ( numbers . containsKey ( nums [ i ]) == false ) { numbers . put ( nums [ i ], 1 ); } else { target = nums [ i ]; break ; } } return target ; } } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 204. Count Primes 計算質數個數

題目連結，此題在Wiki上有個埃拉托斯特尼篩法： Input : an integer n > 1 Let A be an array of Boolean values, indexed by integers 2 to n , initially all set to true . for i = 2, 3, 4, ..., not exceeding √ n : if A [ i ] is true : for j = i 2 , i 2 +i , i 2 +2i , i 2 +3i , ..., not exceeding n : A [ j ] := false Output : all i such that A [ i ] is true . Wiki上還有動畫說明： public class Solution { public int countPrimes ( int n ) { boolean [] primes = new boolean [ n ]; for ( int i = 2 ; i < n ; i ++) primes [ i ] = true ; for ( int i = 2 ; i * i < n ; i ++) { if ( primes [ i ] ) for ( int j = i * i ; j < n ; j = j + i ) primes [ j ] = false ; } int primeCnt = 0 ; for ( int i = 0 ; i < n ; i ++) if ( primes [ i ]) primeCnt ++; return primeCnt ; } } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

讀書心得：誰說人是理性的！

< 誰說人是理性的！ >此書用嚴謹的科學方法：統計的方式。來驗證人到底是不是理性的，書中提到一個觀念-->比較是相對的，此點在商場上更是常見。另外還有預期心理的效應，預期心理是不是失望的來源之一呢？底下附上作者在 TED 上的演講：若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 260. Single Number III 尋找出現一次的數字

題目連結，和 LeetCode OJ: 136. Single Number 與 LeetCode OJ: 137. Single Number II 相同的想法，加上一些變化就解題了。 public class Solution { public int [] singleNumber ( int [] nums) { HashMap<Integer, Integer> numbers = new HashMap<>(); for ( int i = 0 ; i < nums. length ; i++) { if ( numbers. containsKey (nums[i]) == false ) { numbers. put (nums[i], 1 ); } else { numbers. remove (nums[i]); } } int [] target = new int [numbers. size ()]; int i = 0 ; for (Integer key : numbers. keySet ()) { target[i] = key. intValue (); i++; } return target; } } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 137. Single Number II 尋找出現一次的數字

題目連結，筆者採和 LeetCode OJ: 136. Single Number 一樣的想法，這樣子就很好解題囉。 public class Solution { public int singleNumber ( int [] nums) { int target = 0 ; HashMap<Integer, Integer> numbers = new HashMap<>(); for ( int i = 0 ; i < nums. length ; i++) { if ( numbers. containsKey (nums[i]) == false ) { numbers. put (nums[i], 1 ); } else { numbers. put (nums[i], 2 ); } } for (Integer key : numbers. keySet ()) { if ( numbers. get (key) == 1 ) { target = key. intValue (); break ; } } return target; } } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 136. Single Number 尋找出現一次的數字

題目連結，筆者的想法很簡單，就是用Java裡含有 <Key, Value> 的Data Structure，利用Key來作檢查有無重複資料的出現，在 Discuss 裡頭，有用XOR的作法，只不過筆者所想為：【若所要找的資料型態不是Integer時，要怎麼解題？】 import java.util.HashMap ; public class Solution { public int singleNumber ( int [] nums) { int target = 0 ; HashMap<Integer, Integer> numbers = new HashMap<>(); for ( int i = 0 ; i < nums. length ; i++) { if ( numbers. containsKey (nums[i]) == false ) { numbers. put (nums[i], 1 ); } else { numbers. remove (nums[i]); } } for (Integer key : numbers. keySet ()) { target = key. intValue (); } return target; } } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 191. Number of 1 Bits (Hamming weight) 漢明重量

題目連接，筆者一開始很單純一個一個bit去算： int hammingWeight ( uint32_t n) { int bitCnt = 0 ; uint32_t v = n; while ( v > 0 ) { if ( v & 0x01 ) bitCnt ++ ; v = v >> 1 ; } return bitCnt; } 但看了 Discuss 後，才知道原來在 Wiki 上有幾種比較快速的解法，底下列出筆者比較容易理解的版本： //This is better when most bits in x are 0 //It uses 3 arithmetic operations and one comparison/branch per "1" bit in x. int popcount_4 ( uint64_t x ) { int count ; for ( count = 0 ; x ; count ++ ) x &= x - 1 ; return count ; } 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 292. Nim Game

題目連結，這題的分析結果如下： 1 5 9 13 ... ==> 1 You Win. 2 6 10 14 ... ==> 2 You Win. 3 7 11 15 ... ==> 3 You Win. 4 8 12 16 ... ==> 0 You lost. 所以程式碼也很簡單： class Solution { public: bool canWinNim( int n) { return n % 4 ; } }; 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

LeetCode OJ: 12. Integer to Roman 十進制整數轉成羅馬數字