2015年12月19日 星期六

[LC8] String to Integer (atoi)

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
題目要求: 
實作 atoi, 把 string轉成 int。
 思路:
字串前端的空白必須要完全略過 (利用一個 while迴圈來達成),緊接著可能會是 '+' or '-' 字元來表示數字的正負號 (利用 if 判斷式讀進來)。接下來就用 ASCII code來判斷是否為數字字元,並跟上一題一樣,把數字一個個串上去結果整數,並特別注意 integer overflow即可。當讀到非數字時,return 目前已經有的數字。
實作
Time complexity: O(n)

2015年12月16日 星期三

[LC7] Reverse Integer

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
題目要求: 
反轉一個整數,並維持其原本正負號。例如:
 123  =>   321
-123  =>  -321
 思路:
這題就是用標準的 
  1. % 10 的方式從原數字取個位數
  2. *10 + xxx的方式,把結果數字往前推一位,然後加上剛剛取得的個位數
  3. 原數字 / 10退一位
三步驟來反轉整數。
這題的重點是特別注意反轉後會不會 overflow。 
為了方便起見,我們是先把數字的正負號記起來,然後統一使用正整數來操作。正整數最大為 INT_MAX。要檢查做完乘法之後會不會 overflow,不能寫成:
if (a * 10 > INT_MAX) { cout << "Overflow!!! GG" << endl; } 
因為當你作 a * 10這個動作時,有可能數字已經爆掉。這邊必須改寫成:
 if (a > INT_MAX / 10) { cout << "Overflow!!! GG" << endl; }
 就不會有報掉的疑慮。同理 if (a + num > INT_MAX) 必須改成 if (a > INT_MAX - num)。
另外一種思考方式是,我用 long long來裝 result, 因為 int是用 4 bytes表示,long long用 8 bytes表示,他可以裝的下 INT_MAX ~ LLONG_MAX這些數字,然後再拿 result來跟 INT_MAX相比,就知道有沒有 overflow。
實作:
Time complexity is O(n)

[LC4] Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

題目要求: 
給定兩個排序過的 array: nums1, nums2,size分別為 m, n,找兩個數列的中位數。Time complexity必須是 O(log(m + n))

思路:

原數列的總個數,會影響中位數的求法。當個數為奇數時,中位數就是數列中的第 n/2 + 1個數,當數列為偶數時,就必須拿最接近中間的兩個數字來平均,也就是 avg(num[n/2] + num[n/2 + 1] )。
另外我們寫一個找出兩數列中第 k個數字的 function來找到我們要的數字。此 function利用divide and conquer 的方式,依序把不可能的 portion給刪除掉。因為nums1 and nums2這兩個數列是排序過的,我們分別在兩個數列中,找第 k/2個數,如果這兩個數相等,就代表在 nums1中有 k/2個數<=這個數,nums2中也是一樣,如此得知,這個數在這兩個數列中,是第 k大,就是我們要的答案。
如果 nums1[k/2] < nums2[k/2],代表小於 nums1[k/2]那些數都太小了,不可能成為兩個數列中第 k大的數字。換句話說,nums2這個數列,會貢獻 > k/2個數,吃掉nums1會貢獻的數目,他只貢獻 < k/2個數,所以比nums1[k/2]小那些數,都只是當墊被的,不可能成為第 k個,所以可以刪去:
a1 a2 a3 ... nums1[k/2] ... nums2[k/2] ...  (第 k大的數,不可能由 < nums1[k/2]那些數字所貢獻)
 反之,如果 nums2[k/2] < nums1[k/2],代表小於 nums2[k/2]那些數都太小了,不可能成為兩個數列中第 k大的數字:
a1 a2 a3 ... nums2[k/2] ... nums1[k/2] ...  (第 k大的數,不可能由 < nums2[k/2]那些數字所貢獻) 
為了更有效率,我們一開始就 ensure size of nums1 < size of nums2,如此一來,nums1會比較早切完,當他被切完時,就直接找 nums2的第 k個數,就是答案。當然我們這邊保證 k一定小於 (m + n) 
實作:
Time complexity is O(log(m + n))

2015年12月11日 星期五

[LC3] Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

題目要求: 
給定一個字串,在其中找一個最長的字母不重複的子字串。 
By the way, substring指的是字母必須連在一起的子字串; 如果是 Subsequence就有點不大一樣,字母不一定要連在一起,只要是個順序即可。
思路:
Create一個 128大小的 integer array,index是 ASCII number代表每個 character,一個蘿蔔一個坑。Value代表那個字元上次出現的位置,初始值為 -1,代表尚未出現過。
另外,create 兩個 int position variable,分別紀錄目前正在運算中的增長中的子字串的起始位置,與目前位置。還需要一個 value variable來紀錄最大值。 
 例如:
給定字串:"abcabcdbc"
          Index:   0  1  2  3  4  5  6  7  8
           Char:   a   b  c  a  d  b  f  g   c

          Step1:
               int lastCharPos[128],分別用來紀錄每個 character上次出現的位置,
               初始化為 -1。

          Step2:
               'a', 'b', 'c'的ASCII code分別為:97, 98, 99,
               所以lastCharPos array的值會變成:

               Index:   0    1    2   ......   97   98   99   ......   127
                    int:  -1  -1   -1             0     1     2               -1

                代表 a, b, c上次分別出現在 position 0, 1 and 2。
                Okay,現在 current position指向 pos 3的 a,查表發現 index 97 不是 -1,
                這代表前面已經出現過 'a',這時就必須先做小計,計算這個子字串的長度,
                因為這邊的子字串到此已經不能再延伸,必須捨棄掉上一個重複字元,
                才能另外計算。
                也就是說 current position 3 - start position 0 = 3 是發展到這邊,
                暫時的最長字串。
                然後我們必須捨棄上一個 'a',也就是把 start postion + 1,變成 1 ,
                讓下一次的最長子字串計算不把他算進去,即可達到我們要的效果。

                另外要注意的是,我們小計的 trigger時機點,只有發現字元的出現位置 >=
                子字串的起始位置 ,才必須作小計,否則可以繼續延伸。例如我目前正在運
                算的 substring的 start postion 是 8, 然後我查表發現我現在這個字元
                上次出現的位置是 3,這個可以繼續延伸子字串。
                因為這代表這個字元第一次出現在我正在運算的子字串裡,
                上次出現已經是清朝的事了,現在都中華民國 104年了,ignore it.

          Step3:
                 當current position跑到字尾時,要作最後一次的 substring length check,
                 這樣就萬無一失了。
實作:

2015年12月10日 星期四

[LC2] Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

題目要求:
給定兩個 Linked Lists代表兩個非負數字,每個單獨的位數存在 List node裡,請你相加個數字,並請回傳一個 Linked List來表示答案。
思路:
個別從兩個 Lists中取值相加另外必須再加上前一個位數所進位過來的數值。每個位數中,只取 < 10的數值留下來,> 10的數值必須進位。這題注意進位的處理,就沒啥麼太大問題。
實作:

[AWS] Lambda

什麼是AWS Lambda
1. 它是一個compute service, 可在你事先定義的"觸發事件"發生時,自動幫你執行你事先給定的程式碼。
這個的好處是,你寫了一段程式為你作些事情,你不用特地為了執行它,而大費周章的另外 create一台 EC2 server來跑這段程式。你只要把這段程式碼以及想觸發的時機點告訴 Lambda,它會自動幫你 handle這個 task。
2. 如此一來,你只要 maintain這小段程式碼以及觸發事件即可。可以不用 maintain整個back-end server的 infrastructure,會省下很多功夫。

3. 目前 support三種程式語言
     1) Node.js
     2) Python
     3) JAVA

4. 目前 Lambda supports 下列 AWS services當成 event trigger sources:
      1) S3:
Configure S3 bucket,當它被 create, delete的時候,送個 notification給 Lambda, 請 Lambda馬上執行你給他的對應的程式碼。 
例如你希望當使用者上傳圖片的時候,馬上作縮圖的動作,這時候就可以定義 S3 bucket,當它 detect到有圖片檔上傳時,即送個通知給 Lambda,讓 Lambda去執行縮圖的程式碼。Perfect!
      2) DynamoDB:
可以在 Lambda裡 create一個 event source mapping,去 polling DynamoDB streams,當DynamoDB table有 update時,執行某些 function。例如當有data update時,即時的幫你利用最新的 data來作一些運算,即時回傳結果。
      3) Kinesis:
跟 DynamoDB差不多,只是這次換成了影片檔。可以 create event source mappings讓 Lambda去 polling Kinesis streams。例如當有影片新增時,作即時轉檔之類的事情。
      4) SNS
      5) SES
      6) Cognito
      7) CloudWatch Logs
      8) CloudFormation

2015年12月9日 星期三

[LC1] Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

題目要求:
給定一個integer array以及一個target value,找出兩個數字,他們的總和等於給定的target value,並且return他們的index。假設可以找到唯一的一組solution.
思路:
暴力法是依序抓兩個數來相加,如果結果等於target,即找到答案,但time complexity會是O(n^2),太慢了。
另一種想法是,藉由hash table lookup只要O(1)的優勢,把對應的index找出來,速度會快很多。舉個例子:假設 a and b兩數是答案,因為 a + b = target,所以 b = target - a。然後我們在hash table裡面存的 Key是 array data, Value是 data index,
Array:
Index  0     1     2     3
Data    2     7   11   15
Hash Table:
Key     2     7     11     15
Value  0     1       2       3
假設 target是 9,用一個 loop讓 array data輪流當 a, 假設現在 a是 index 0的 2,9 - 2 = 7,問題變成 hash key是 7,請從 hash table中找對應的 hash value,就會得到 index 1,結束。One pass即可找到答案,time complexity = O(n), Space complexity = O(n)。
特別注意答案要求的 index是 1 base,所以 return之前務必先都加 1。
實作:
C++11的STL:unordered_map實作 hash table,並且可以使用中括號直接用 hash key當 index來存取 hash value。所以選他來當成解法中的 hash table。
http://www.cplusplus.com/reference/unordered_map/unordered_map