Monthly Archive: March 2020

算法練習 kth smallest element in BST with known subtree size,在已知子樹大小的二叉搜索樹里找第k小的元素

最簡單暴力的就是直接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

利用統計節省病毒試紙的方法

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

算法練習 Leetcode 力扣 69. Sqrt(x) Python, Java, C++, Scala 解法

這題是經典算法二分查找(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表示 時間上好像沒差太多,半斤八兩。

怎樣在 Mac OS X 上乾淨安裝 Scala?(不用homebrew)

非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 了。

算法練習 Leetcode 力扣 1145. Binary Tree Coloring Game 解法

這題描述巨長無比,可以當一篇閱讀理解來做了,看完也不是很容易就能想到是屬於哪類的題目,圖也畫的非常有迷惑性,藍色應該畫在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值。還有定義函數記得要加 =