Monthly Archive: March 2020

最簡單暴力的就是直接dfs做in order traversal，記錄現在是第幾個元素，當等於k時就返回。這樣時間複雜度是O(N)，空間O(logN)。但是這樣就沒有利用到子樹大小已知的屬性。 最優解法是利用子樹大小信息推出當前節點的index，如果比k大，那麼目標在當前節點左邊，如果比k小則在當前節點右邊，如果等於k，就找到了。這樣可以把時間減到O(logN)，空間則是O(1)，優於暴力解法不少。 推出當前節點的index，可以用一個變數記錄range，也就是子樹可能的最小和最大index。 一道挺有意思的題目。 Python # 50 (10) # / \ # 30 (4) 70 (5) # / \ / \ # 20 (2) 40 (1) 60 (3) 80 (1) # / / \ # 5 (1) 55…
Read more

Python Java 最大整數或最小整數 為什麼是31次方，有一位用來表示正負號了

病毒流行，試紙短缺。網上偶爾看到的，把5個病人的血液混合一起測，如果是陰性，皆大歡喜。如果不幸是陽性，再重新對每人單獨測試。為什麼這樣能節省試紙呢？以下計算一下所用試紙的期望。 假設感染人數佔20%，那麼沒被感染概率是80%。連測5個全部健康的概率是0.8^5 = 32.8%。那麼非5個全健康的概率是67.2%。5個混合測出陰性用一個試紙，陽性呢，除了已經用了的一張試紙外，還需要對5人重新測，所以需要6張。 那麼試紙數的數學期望是 1*0.328 + 6*0.672 = 4.36 < 5 !

類型 位數 Byte 8 bit Short 16 bit Int 32 bit Long 64 bit Float 32 bit Double 64 bit Char 16 bit

這題是經典演算法二分查找（binary search）的應用。做題之前先複習binary search的經典實現，注意幾個細節。但是和一般binary search不同，這題不是找一個特定的數，而是要找到一個整數正好是sqrt(x)的整數部分，而又不能直接求出sqrt(x)。我想了一下，可以表達成從[0, x]中找出一個整數，這個整數ans滿足ans^2 <= x，而同時(ans + 1)^2 > x。 Python實現 Scala 實現1 使用while loop，思路比較像Java 和 Python 不一樣的是，Scala Int 平方後會溢出，而float精度不夠，必須用double才能過OJ。用Long（64位）也可以。 Scala 實現2 使用recursion代替while loop，平方用Long表示 Scala 實現3 使用recursion代替while loop，平方用Double表示 時間上好像沒差太多，半斤八兩。

非Brew方式，乾淨安裝。 到Scala官網下載頁面 https://www.scala-lang.org/download/ 下載 Mac OS X 那個，解壓，放在任意喜歡的路徑，比如home里 然後修改 ~/.zprofile 文件。(如果是bash就修改 ~/.bash_profile)，如下修改，記得把<user>替換成自己的user name source ~/.zprofile 或者 打開一個新的terminal就可以用 scala REPL 或者 scalac 了。

這題描述巨長無比，可以當一篇閱讀理解來做了，看完也不是很容易就能想到是屬於哪類的題目，圖也畫的非常有迷惑性，藍色應該畫在1位置能多佔一個。熱愛做腦筋急轉彎的同學可以挑戰一下，沒時間的同學就直接記住結論就好，藍色的可能選擇其實只有3個：紅色的左邊，右邊，和上面，分別切斷和佔領左右上三部分，然後看看每部分能不能超過一半就好。有了這個思路，用DFS跑一次就行，時間是O(n)，沒有explicit extra space，但算上DFS遞歸佔用stack也是O(n) Python 實現 還有一種寫法，可以把查找和運算元樹節點個數合併成一個DFS，trick就是用一個container參數記錄當找到x時，他的左中上能控制的節點樹，其他部分就是正常的DFS。能縮短代碼。 Python 實現 Java 實現 Scala 實現 Scala和Java基本一樣，就是注意沒有return statement，最後一個表達式就是return值。還有定義函數記得要加 =

用 -p 或者 –parents 參數，意思是 make parent directories as needed，如果需要的話創建上級目錄 刪除目錄的話用 -r，意思的recursive，用遞歸的方式把 目錄和裡面的東西一層層刪光

ssh 到wordpress主機上，cd到wordpress目錄。用 看看 wp-content 的許可權。 如果是這樣的 說明沒有寫許可權，解決方法如下 這樣應該就沒問題了。

新買的Macbook一般是都是關了ssh許可權的。本文講怎麼開通這個許可權。 先點設置 (System Preferences) 然後選 Sharing 選上 Remote login 就可以ssh到這台Mac上了。 開通ssh有什麼好處呢？比如可以用sftp傳文件，把舊電腦上的東西考到新電腦上。