hoho的日子

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ Given an array of integers where 1 ≤ a[i] ≤  n  ( n  = size of array), some elements appear twice and others appear once. Find all the elements of [1,  n ] inclusive that do not appear in this array. Could you do it without extra space and in O( n ) runtime? You may assume the returned list does not count as extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [5,6] Subscribe  to see which companies asked this question 關鍵在不能用額外的空間 和 run time O(n) 這裡用一個 "字典", 兩個 loop 做快速搜索已出現過的 數字

https://leetcode.com/problems/reverse-string/ Write a function that takes a string as input and returns the string reversed. Example: Given s = "hello", return "olleh". Subscribe  to see which companies asked this question 這題需要考量空間 跟 時間的使用 所以 不能多申請一個 string, 也不能跑好幾個 loop 思路: 1. python 的 string 不能更改element, 所以先改成 list 2. 用兩個pointer 分別指到 頭跟尾 3. 用一個for loop 掃 len(s)/2 次

https://leetcode.com/problems/max-consecutive-ones/ Given a binary array, find the maximum number of consecutive 1s in this array. Example 1: Input: [1,1,0,1,1,1] Output: 3 Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3. Note: The input array will only contain  0  and  1 . The length of input array is a positive integer and will not exceed 10,000 Subscribe  to see which companies asked this question 很常見的題目類型 給一個字串(array, 數字) 找連續的元素. 不要看這種題型看似簡單 外面經常考變化題 或是 連續應用題 比如說 給你一個字串 "jjhhhhgsdjgjhsgSWQRgajn554avbnvbnvanb6545svdnbsvan2346456" 1) 先印出 j: 2 h: 4 format 2) 在統計有多少個元素 出現超過3次以上 ? 3) 連續出現最多次的是哪個元素 最少的又是哪些 ? 4) 如果區分大小寫呢?

https://leetcode.com/problems/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. 思路: 計算2的補數, 把一個整數(小於32bits) 轉成 2進位. 然後 0 變 1, 1 變 0.

https://en.wikipedia.org/wiki/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 . 題目給出了 x, y 的大小定義, 大大降低題目難度. 思路: 1.用python 內建的string format 成帶0的二進為字串 2.比較 x, y 的二進為字串長度, 找出差距(overflow). 因為一個字串有 另一個沒有 所以compare一定不同. Overflow 的值一定是 hamming distance 3.用一個 for loop 掃一遍 並 比較 x, y 4.最後加上 overflow 並回傳

https://leetcode.com/problems/valid-palindrome/ Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama"  is a palindrome. "race a car"  is  not  a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome. Subscribe  to see which companies asked this question 只考慮字母的並驗證 一串字串是不是 回文字串. class Solution(object):     def isPalindrome(self, s):         s = str(s)         temp = filter(str.isalnum,  s.lower())  // 只考慮字母 並全部轉小寫         i = 0         j = len(temp)-1         while( i <= j ):                         ...

Object-oriented programming  ( OOP ) is a programming language model organized around objects rather than "actions" and data rather than logic. 物件導向程式 最重要的觀念還是在 封裝, 繼承, 多型 老師通過大量的 例子 使我們理解這些特性. 1) 那什麼是 封裝? combined data and member function into a class. 舉例來說 有個 "人" 的class, class 人{ int 身高; double 體重; void 跳舞(int x, int y); }; 他有身高體重 並且還可以跳舞. 2) 什麼是繼承? 就是一個 class 可以繼承另一個 class的特性 並且 外加自己的data 或是 member function class 男人 extend 人{ string 玩具; }; 這裡 這個新的男人 class  就 有身高體重 外加 玩具的 data了 3) 什麼又是多型? https://www.youtube.com/watch?v=MUhJ2MGFuWo 一個介面, 多個使用方法. 當然實現上 有不同的方法 https://www.youtube.com/watch?v=qtw3Wbjust8&t=341s 好文一篇(作者把 virtual 翻譯成 " 名存實亡 ") http://blog.csdn.net/wang7890/article/details/3923580 類別 (class) 繼承的一些特性 http://140.127.40.1/~jwu/c/cpgch16.htm

用了兩週來說 運算子重載 可以說是很精彩的章節 簡單說 a=a+b; 這裡這個 加 是怎麼做到的? 如果今天 a, b 是 object 的話 就需要做 運算子重載 不然 complier 不會知道要怎麼 處理這種情況 http://monkeycoding.com/?p=930 那有什麼情況需要用哩, 1)  Dog a; cin   >> a;  cout << a;  這裡大於小於符號都不懂 什麼是 cin 一個 object. 所以運算子重載就派上用場啦 2)  cout << a; 其實就等於 operator  << (cout , a); 3) Dynamic memory allocation

Class 可以說是物件導向的開始, 有class才有所謂的物件. class就是一個"模板" 有了模板就可以創造出 有同樣屬性特徵(data)跟行為方法(member function)的物件. 那為什麼要學物件導向呢. 這裡有個 影片 解釋的還不錯, 好處呢不外乎就是 更容易維護, 更用人的角度來設計程式. 當一個程式大的時候 有物件的觀念會讓事情簡單不少. 至於怎麼設計, 怎樣應對 interview 推薦經典書, Design Patterns - Elements of Reusable Object-Oriented Software 整理以下重點, 1) 如果物件是個pointer 要使用裡面的東西就要用"->" count counter; count *counterPtr = &counter; count &counterRef = counter; counter.x = a; counterRef.x = a; counterPtr -> x = a 2) 系統自動會建立 default的建構子, 當然我們也可以overloading 3) 好的寫法是分成3個檔案. time.h, time.cpp, main.cpp time.h      定義 class time.cpp  定義 class 行為方法實作 main        include time.h 重複的include .h file 我們可以用 #ifndef 做判斷來避免 4) const member function 宣告的方式有些特別, int Time:getHour() const {              return hour; } 5) 物件是可以被複製的 Time t1 = t2; 6) friend function https://www.tutorialspoint.com/cplusplus/cpp_friend_functions.htm ...

這裡開始講到重點了, 以前沒觀念不夠清楚的地方 剛剛好一次性複習. 首先為什麼要用 pointer, https://zh.wikipedia.org/zh-tw/%E6%8C%87%E6%A8%99_(%E9%9B%BB%E8%85%A6%E7%A7%91%E5%AD%B8) 在 高級語言 中，指標有效的取代了在 低階語言 （如 組合語言 與 機器碼 ）直接使用記憶體位址。但它可能只適用於合法位址之中。因為指標更貼近硬體， 編譯器 能夠很容易的將指標翻譯為機器碼，這使指標操作時的負擔較少，因此能夠提高程式的運作速度。 使用指標能夠簡化許多 資料結構 的實作，例如在遍歷字串，查取表格，控制表格及樹狀結構上。對指標進行複製，之後再解參照指標以取出資料，無論在時間或空間上，都比直接複製及存取資料本身來的經濟快速。指標表示法較為直覺，使程式的表達更為簡潔，同時也能夠提供動態機制來建立新的節點。 在 程式編程 （procedural programming）中，指標也被用來儲存系統呼叫流程，以及動態連結資料庫（DLL）的進入點位址。在 物件導向編程 中，使用 函式指標 （Function pointer）來綁定 方法 （method），常見於 虛擬方法表 （Virtual method table）中。 接者重點整理, 1)  pointer只能 assign 0, NULL, 跟 address. 2)  下面這個例子ok嗎? 答案是ok的, 因為這裡的 "&" 是 reference. int a = 10; int &b = a;  3) pointer 容易讓人搞不清楚的原因是, a. 宣告跟使用是不同的意思. int *p = &a;         <=== 宣告一個指標p, 指向a的位置 cout << *p;          <=== 使用, 這裡 *p 等於 a b. pointer 跟 function 使用的多種寫法, 讓人混淆 目前有三種傳法, pa...

陣列(array) 應該是蠻簡單的一節, 教授還是細心的把範例一個一個跟同學過了. 心想難怪 台大同學的程式能力都蠻強的. 老師教的時候觀念清楚 完全不會混淆 聽一次就夠了. 基礎奠定的時候 就好! 上課也很認真 會不斷的問問題, "這樣寫 OK嗎?" 不斷的讓同學產生好奇心, 並且幾乎課本上的重點都講過一遍了. 聽完課 課本稍微看一下(每章幾天吧) 對重點就可以達到舉一反三的效果囉. 繼續整理, 1) 假設 a[6]; 那 a[9] = ? 答案是不確定, complie 也不會出錯. 因為memory本來就是連續的 只是答案應該不會是程式設計者想要的. 2) a[5] = {0,1,2,3,4}; 是ok的. 但是a[5] = {0,1,2,3,4,5}; 是會報 ERROR的喔!! 另外 a[]; 也是會報 ERROR 的, 值得一提的是 a[] = {0,1,2}; 就沒關係, 因為Complier會知道需要分配幾個memory block 就行了. 3) const int // 初始化後 不能再改. 常用來跟 arraySize 一起宣告, 增加程式可讀性. 4) 傳 array 到function 時, 一定是傳 pass-by-reference 所以可以在function 寫const 防止array 被複寫 void f( const int b[] , int sizeOfArray ){ .... } 5) 課本  P 312 insertion sort 改成 descending 很簡單, line_28 data[moveItem -1] > insert 改成小於 " < " 就搞定啦 Insertion sort, https://en.wikipedia.org/wiki/Insertion_sort 時間複雜度 {\displaystyle O(n^{2})} 空間複雜度 總共 {\displaystyle O(n)}  ，需要輔助空間 {\displaystyle O(1)}

相當精彩的一節, 這節介紹 何時用function 還有 解釋了為什麼 主程式裡用return 0; 是回傳0給OS. 整理補洞如下, 1) main 是特殊的function, default 不寫的話 type為int int main(){ .... } 這裡兩個例子是一樣的. main(){ .... } 2) function define type 和 default value 這個範例解釋 兩個常用的觀念, line_5 是hello 這個function的define type 設定傳入的default value為1. 也就是說 line_8寫成hello() 也是ok的. 再回到line_5, 要注意的是 宣告並沒有說 int x=1 , 在這裡 "x" 寫不寫 都沒有關係 程式都可以跑 寫了只是給人看得更容易理解. line_12 - 15 是function 的description. 3) #include<> 和 #include "" 差別在於前者直接去standard library裡找, 後者是先在local找 user define的library  4) Call random function #include<cstdlib>   <=== include srand() and rand() 可以用srand(seed) 設定種子值, 所以每次產生的亂數會不一樣 5) Storage class and Scope 變數可以在程式裡 活多久叫 Storage class (簡單分有 auto 跟 static) 變數可以在程式哪活 叫 Scope (簡單分有 local 跟 global ) 一般來說function裡的變數, 一旦function 結束了就free memory了 這就叫auto. register 就是把變數放到讀寫更快的 memory方便存取. 如果宣告為static 出了function 還是會hold住 memory的值 直到程式結束. * stat...

老師的語速蠻快的 應該是要先把PPT  和 相對應的課本看過 再開始上課. 由於時間有限 用VLC player 把撥放速度調成1.5倍 快速的聽過相關的知識 繼續補足漏洞, 1) 一般程式 在main裡 有的時候會加 return 0; 這裡建議是 只有兩種寫法. 寫return 0 或者 不寫. 什麼return 100, return 200 之類的寫了可能會有問題. 因為這跟OS 有關. http://stackoverflow.com/questions/22604196/difference-between-return-1-return-0-and-return-1-and-exit return  from  main()  is equivalent to  exit the program terminates immediately execution with  exit status  set as the value passed to  return  or  exit 2) Conditional operator 這東西有陣子完全無法理解 現在看起來蠻簡單的, 看個例子就很清楚了 用conditional operator 可以把程式變得很漂亮 簡潔. 減少if statement的次數. 範例在說 如果 i 大於 j 就印出 "i is greater" 不然就是 "j is greater". https://msdn.microsoft.com/en-us/library/e4213hs1.aspx 3) Stacking VS nesting 在編寫程式的時候 如果不細看 把程式碼當成一幅畫 你會發現, 有的部分 一推一推的(Stacking), 也有的部分是好幾層的(nesting) 4)  變數是有範圍的 (Scpoe) 比方說 for 裡面的變數 只有在for裡面有效. for( int i = 100 ; i >0 ; --i )        cout << i ; 出了for 就沒用了....

看到鄉民問   [問卦] C++練到超強,學任何其他語言都超快嗎? https://www.ptt.cc/bbs/C_and_CPP/M.1418429685.A.9B5.html 整理了幾門好課 心想那就順便修了他們吧 ~ 當年學得有夠爛 現在總覺得講專業的時候 很多部分不夠精通 心裡很虛. 刷算法的時候感覺概念模糊不清. 套句前高手同事的話 "高手就是摳細節" 這次還是好好學習 把不清楚的地方一次理清楚 2017 好好補洞. 1.先聽台大開放式課程當中，台大電機系廖婉君教授的計算機程式 http://ocw.aca.ntu.edu.tw/ntu-ocw/index.php/ocw/cou/101S112 2.再聽電機系于天立教授的計算機概論 http://ocw.aca.ntu.edu.tw/ntu-ocw/index.php/ocw/cou/101S210 3.聽交大開放式課程當中，交大資工系彭文志教授的資料結構 http://ocw.nctu.edu.tw/course_detail_3.php?bgid=9&gid=0&nid=412#.VIuDgSuUena 首先第一堂課 來聽廖教授的計算機程式, 講的深入淺出 重新複習概念上 什麼是電腦 組成部分是什麼. Coding 主要用C++ 沒有推薦用什麼 IDE 開始. 以下概念(technical hole) 補上, 1) Memory, Disk 和 Network 講的 kB(or kBps) 大小是不一樣的, 這裡的KB, B 都是Byte. 差別在於 Memory用的K 大小是 2^10 = 1024 網路用的K 是 10 ^ 3 = 1000 這裡有更多細節  http://www.speedguide.net/articles/bits-bytes-and-bandwidth-reference-guide-115 2) 再來Data Type宣告和 Size 值得注意的是在  Visual Studio 2015 裡, double 和 long double 都是佔8個 bytes https://msdn.microsoft.com/en-us/library/s3f49ktz....