通電技能樹

此篇文章要探討的問題Best Time to Buy and Sell Stock,意指如何在股市波段中找出最大的利潤.題目原文如下: Say you have an array for which the  i th  element is the price of a given stock on day  i . If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) Example 2: Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0. 在這題中假設只能買賣一次,你必須在這一次買賣中就獲得最大的利潤.對我們來說這是很簡單從肉眼即可判斷出解答為何(意即:投資者常在看的"K線圖"),那麼對電腦來說,這應該要如何解決? 首先要思考的是:我們自己是 如何判別怎樣算賺錢呢? 對投資者來說,股票賺錢的本質就只是低買高賣,所以重要的往往不是單一的價格本身,而是兩個價格之間的差為多少? 因此,以題目的範例來說,我們感興趣的不是陣列中[7,1,5,3,6,4]的每個值,而是前後兩兩之間的 差 : [ (1-7) , (5-1) , (3-5) , (6-3) , (4-6) ] = [  -6 , 4 , -2 , 3 , -2 ] 接者就可以再進一步判斷, 要從哪一個數開始作連續相加,並要停在哪一個數值上呢? 例如假設是要從-6開始加到4,-2,3的值,還是要從4開始連續加到-2,3的值? 處理序列的...

本篇文章要闡述的是筆者在LeetCode上碰到的一種題型:冪次(Power),大概有三個題目與其相關.題目的原文為: Given an integer, write a function to determine if it is a power of two/three/four. 給定一個整數,則你能否撰寫一個布林函數來判斷這是不是為2/3/4的冪次項呢? 根據這種類型的題目,於演算法的角度來看我們可以用多種不同的方法來解.以下在此一一分析: (一)暴力破解 對於不熟悉撰寫程式或是投機取巧的人常會用的方法,單純就是為了解題而迫不得已才使的笨方法. 暴力破解還可分成兩種: (1)把所有的2/3/4的冪次項列出來 由於變數型態Int的數值範圍在-2147483648 ~ 2147483647之間, 我們把因此在此範圍的 所~~有~~次方項 的值都列出來, 看給定的整數符不符合來判斷. 但這畢竟是個曠日廢時且效率極差的寫法 (2)只找出2/3/4的最大次方值 由於變數型態Int的數值範圍在-2147483648 ~ 2147483647之間 所以我們找出在此範圍所能容納的最大次方數為多少 (例如3的19次方為1162261467) 那麼我們只要看給定的整數能否被這數字整除即可,即寫成: bool isPowerOfThree(int n) {         return (n > 0 && 1162261467 % n = = 0);     } 這比第一種暴力解法還要省事的多,但終究是取巧的辦法 (二)迴圈解題 這算是大部分人會想嘗試下手的寫法,利用while迴圈或是函數本身遞迴解題. 通常我們在做數學題碰到這題的時候 很直覺地會用直向因數分解的辦法來找這個數是否因數皆為2/3/4, 因此在程式中最直接的方法就是不斷地對數值除以2/3/4, 看最後的餘數是否為1,若是1則傳回true,不是的話即傳回false. 並加上考慮是否為大於0的情況, 最後程式的寫法即為如下(舉3為例): if (n==0)      return false else {   while...

Leetcode於每周末都會舉辦線上的程式解題比賽,在比賽結束後便會釋出最新的題目供大家練習.這次要介紹的便是上週出現的新題目.題目原文如下: Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to  the original place . The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are  R  (Right),  L (Left),  U  (Up) and  D  (down). The output should be true or false representing whether the robot makes a circle. Example 1: Input: "UD" Output: true Example 2: Input: "LL" Output: false 題目假設有一機器人在原點位置,則給定字串UDLR來讓它上下左右在二維平面中移動,回傳最後位置是否還停留在原點上. 一開始看到時我的想法是先假設好一個二維的空間, 若程式偵測到有'U'的話,則在Y軸方向加1, 有'R'的話則在X軸方向加1....諸如此類. 但是其實就程式的結果來看,我們並不需要知道機器人最後會落在座標平面上的哪個位置,重點是只要知道"在不在原點上"就好了. 因此程式設計的邏輯還可以再簡單 精簡成為一目標就是"走向左邊的步數"等於"走向右邊的步數",並且"走向上的步數"等於"走向下的步數" 意指在要看字串中"U的個數=D的個數"並且"L的個數=R的個數" 達成這個條件就知道...

本篇的問題與處理資料樹狀結構有關,題目原文如下: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. Example 1: Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: Merged tree: 3 / \ 4 5 / \ \ 5 4 7 Note:  The merging process must start from the root nodes of both trees. 除此之外,原始程式碼還有附上二元樹的定義: /**  * Defini...

這篇要講的題目是Number Complement,即為"補數"的意思.題目原文如下: Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation. Note: The given integer is guaranteed to fit within the range of a 32-bit signed integer. You could assume no leading zero bit in the integer’s binary representation. Example 1: Input: 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2. Example 2: Input: 1 Output: 0 Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.題目的ㄧㄠ 題目是要求某數二進位翻轉過後的結果是甚麼數字. 這題跟我先前解過的  [思路]LeetCode Problems- 461. Hamming Distance  有些相似, 都要求出十進位轉二進位, 所以一開始我的想法是: 1.十進位轉二進位 2.0跟1互換,1變0,0變1 3.在反求二進位轉十進位的數值 看起來還蠻合理的,但是在開始著手之後,就發覺整個過程變得很複雜.... 首先是在於,我在算十進位轉二進位的方法,主要是一開始先創設32位元的0元素陣列(考慮到int變數的位元範圍下), 再用除法除2時,把求得的餘數1或0放進去 例如對5做轉換求到的值,在陣列中被表...

 這次要來解決的問題是複數相乘Complex Number Multiplication. C語言不像在大學時期所碰的MATLAB一樣有方便的數學函數工具箱,可以幫學生做計算-----應該說要用C計算數學也是可以,但基本上兩種軟體的功用大不相同-----這次的問題在為自己將來有可能會碰到MATLAB轉C的需求作準備. 題目原文如下: Given two strings representing two  complex numbers . You need to return a string representing their multiplication. Note i 2  = -1 according to the definition. Example 1: Input: "1+1i", "1+1i" Output: "0+2i" Explanation: (1 + i) * (1 + i) = 1 + i 2 + 2 * i = 2i, and you need convert it to the form of 0+2i. Example 2: Input: "1+-1i", "1+-1i" Output: "0+-2i" Explanation: (1 - i) * (1 - i) = 1 + i 2 - 2 * i = -2i, and you need convert it to the form of 0+-2i. Note: The input strings will not have extra blank. The input strings will be given in the form of  a+bi , where the integer  a  and  b  will both belong to the range of [-100, 100]. And  the output should be also in this form . 題目的大意為給定兩個以a+bi表示的複數,並且還是字串的形態, 求兩個複數相乘的結果,同樣要以a...

有鑑於上次按隨機鍵出來的題目難度特高,花了不少心思, 並且上週去成大一個禮拜沒碰到程式許久, 我決定這次來解決一些較簡單的題目, 並嘗試不用C++而用C語言來完成 這次練習的題目是Hamming Distance,題目原文如下: The  Hamming distance  between two integers is the number of positions at which the corresponding bits are different. Given two integers  x  and  y , calculate the Hamming distance. Note: 0 ≤  x ,  y  < 2 31 . Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ? ? The above arrows point to positions where the corresponding bits are different. 漢明距離(Hamming Distance)在通訊領域裡是頗重要的編碼應用,個人最早是在學習通道編碼的Viterbi演算法中碰到的. 在Viterbi演算法中需要透過編碼器的格狀架構找出一條最短路徑，找出擁有「最大可能性」路徑的方法,而這就需要應用到漢明距離.最簡單的解釋 就是 位元數不同的數目總和 例如：(wiki) 10 1 1 1 01 與 10 0 1 0 01 之間的漢明距離是2 2 14 3 8 96 與 2 23 3 7 96 之間的漢明距離是3 跟先前寫過的題目來比,這一題的邏輯脈絡就清楚許多,可分成三個步驟: 1.十進位轉換成二進位 2.轉換後資料存成字串或陣列 3.比對兩個字串或陣列的內容 首先要來處理的就是位制轉換問題,十進位轉換成二進位的方法如下所示: 簡言之 這演算法有兩個重要skill: 1.取得餘數(1或者是0) 2.針對除法所得到的商數繼續做除法 ...

在做完  [思路]LeetCode Problems- 441. Arranging Coins 這題之後 隔天一早十點多起床想說再繼續挑戰一題來試看看 於是按下了LeetCode首頁右下的"Pick One"鍵 跳出了這一題, 原文如下: Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given  [10, 9, 2, 5, 3, 7, 101, 18] , The longest increasing subsequence is  [2, 3, 7, 101] , therefore the length is  4 . Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O( n 2 ) complexity. Follow up:  Could you improve it to O( n  log  n ) time complexity? Credits: Special thanks to  @pbrother  for adding this problem and creating all test cases. 當下看到時有點傻眼 天啊這題目到底想要求甚麼啊~?? 多看幾次才逐漸明瞭 好像是要求這有序數列裡   最長的遞增數列  的個數 如上述那一串數列中,最長的遞增數列為 2 3 7 101  其長度是4 但就數列"內容"來說這不算是唯一的答案, 也應該能寫成2 5 7 101 或者是2 3 7 18 這類 當發覺答案不會是唯一解的時候,其實內心覺得有點怕怕的@@ (心中OS開始 ) 認真在看題目想如何解的時候,腦袋想法變得十分稀少,不知道要如何下手 相信在寫code的初學者或大學生(例如我)...