算法练习 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 (1)    65 (1)

class TreeNode:
    def __init__(self, val):
        self.size = 1
        self.val = val
        self.left = None
        self.right = None

def build_sample_tree():
    node50 = TreeNode(50)
    node30 = TreeNode(30)
    node20 = TreeNode(20)
    node40 = TreeNode(40)
    node70 = TreeNode(70)
    node60 = TreeNode(60)
    node80 = TreeNode(80)

    node5 = TreeNode(5)
    node55 = TreeNode(55)
    node65 = TreeNode(65)

    node50.left = node30
    node50.right = node70
    node50.size = 10

    node30.left = node20
    node30.right = node40
    node30.size = 4

    node20.left = node5
    node20.size = 2

    node70.left = node60
    node70.right = node80
    node70.size = 5

    node60.left = node55
    node60.right = node65
    node60.size = 3

    return node50

def dfs(root, range, n):
    if n < range[0] or n > range[1]:
        return None
    if root is None:
        return None

    l_size = 0
    if root.left is not None:
        l_size = root.left.size
    idx = range[0] + l_size
    if idx == n:
        return root.val
    elif idx < n:
        range[0] = idx + 1
        return dfs(root.right, range, n)
    else:
        range[1] = idx - 1
        return dfs(root.left, range, n)

def nsmallest(root, n):
    return dfs(root, [1, float('inf')], n)


root = build_sample_tree()
for i in range(12):
    print '{}-th smallest: {}'.format(i, nsmallest(root, i))



利用统计节省病毒试纸的方法

病毒流行,试纸短缺。网上偶尔看到的,把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实现

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l = 0
        h = x
        while l <= h:
            m = l + (h - l) / 2
            sq = m ** 2
            if sq <= x and (m + 1) ** 2 > x:
                return m
            elif sq > x:
                h = m - 1
            else:
                l = m + 1
        

Scala 实现1 使用while loop,思路比较像Java

import scala.util.control.Breaks._

object Solution {
    def mySqrt(x: Int): Int = {
        var l: Int = 0
        var h: Int = x
        while (l <= h) {
            val m : Int = l + (h - l) / 2
            val sq: Double = 1.0 * m * m 
            if (sq <= x && (m + 1.0) * (m + 1.0) > x) {    
                return m
            } else if (sq > x) {
                h = m - 1
            } else {
                l = m + 1
            }
        }
        -1
    }
}

和 Python 不一样的是,Scala Int 平方后会溢出,而float精度不够,必须用double才能过OJ。用Long(64位)也可以。

Scala 实现2 使用recursion代替while loop,平方用Long表示

object Solution {
    def mySqrt(x: Int): Int = {
        helper(x, 0, x)
    }
    
    def helper(x: Int, l: Int, h: Int): Int = {
        val m: Int = l + (h - l) / 2
        val sq: Long = m.asInstanceOf[Long] * m.asInstanceOf[Long]
        
        if (sq <= x && (m + 1).asInstanceOf[Long] * (m + 1).asInstanceOf[Long] > x) {
            m
        } else if (sq > x) {
            helper(x, l, m - 1)
        } else {
            helper(x, m + 1, h)
        }
    }
}

Scala 实现3 使用recursion代替while loop,平方用Double表示

import scala.util.control.Breaks._

object Solution {
    def mySqrt(x: Int): Int = {
        helper(x, 0, x)
    }
    
    def helper(x: Int, l: Int, h: Int): Int = {
        val m: Int = l + (h - l) / 2
        val sq: Double = 1.0 * m * m
        
        if (sq <= x && (m + 1.0) * (m + 1.0) > x) {
            m
        } else if (sq > x) {
            helper(x, l, m - 1)
        } else {
            helper(x, m + 1, h)
        }
    }
}

时间上好像没差太多,半斤八两。

怎样在 Mac OS X 上干净安装 Scala?(不用homebrew)

非Brew方式,干净安装。

到Scala官网下载页面 https://www.scala-lang.org/download/

下载 Mac OS X 那个,解压,放在任意喜欢的路径,比如home里

然后修改 ~/.zprofile 文件。(如果是bash就修改 ~/.bash_profile),如下修改,记得把<user>替换成自己的user name

# Scala
path+=('/Users/<user>/scala-2.13.1/bin')

export PATH

source ~/.zprofile 或者 打开一个新的terminal就可以用 scala REPL 或者 scalac 了。

% scala
Welcome to Scala 2.13.1 (Java HotSpot(TM) 64-Bit Server VM, Java 13.0.2).
Type in expressions for evaluation. Or try :help.

scala>

算法练习 Leetcode 力扣 1145. Binary Tree Coloring Game 解法

这题描述巨长无比,可以当一篇阅读理解来做了,看完也不是很容易就能想到是属于哪类的题目,图也画的非常有迷惑性,蓝色应该画在1位置能多占一个。热爱做脑筋急转弯的同学可以挑战一下,没时间的同学就直接记住结论就好,蓝色的可能选择其实只有3个:红色的左边,右边,和上面,分别切断和占领左右上三部分,然后看看每部分能不能超过一半就好。有了这个思路,用DFS跑一次就行,时间是O(n),没有explicit extra space,但算上DFS递归占用stack也是O(n)

Python 实现

class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        xnode = self.find(root, x)
        (xcount, lcount, rcount) = self.tree_stats(xnode)
        half = n / 2
        if lcount > half or rcount > half or n - xcount > half:
            return True
        return False
        
    
    def find(self, root, x):
        if root is None:
            return None
        if root.val == x:
            return root
        l = self.find(root.left, x)
        if l is not None:
            return l
        else:
            return self.find(root.right, x)
        
    def tree_stats(self, root):
        if root is None:
            return (0, 0, 0)
        l = self.tree_stats(root.left)
        r = self.tree_stats(root.right)
        return (l[0] + r[0] + 1, l[0], r[0])

还有一种写法,可以把查找和算子树节点个数合并成一个DFS,trick就是用一个container参数记录当找到x时,他的左中上能控制的节点树,其他部分就是正常的DFS。能缩短代码。

Python 实现

class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        ans = []
        self.tree_stats(root, x, n, ans)
        return ans[0] > n / 2
             
    def tree_stats(self, root, x, n, ans):
        if root is None:
            return 0
        l = self.tree_stats(root.left, x, n, ans)
        r = self.tree_stats(root.right, x, n, ans)
        cnt = l + r + 1
        if root.val == x:
            ans.append(max(l, r, n - cnt))
        return cnt

Java 实现

class Solution {
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        int [] ans = new int[1];
        nodes(root, n, x, ans);
        return ans[0] > n / 2;
    }
    
    public int nodes(TreeNode root, int n, int x, int[] ans) {
        if (root == null) {
            return 0;
        }
        int l = nodes(root.left, n, x, ans);
        int r = nodes(root.right, n, x, ans);
        int cnt = l + r + 1;
        if (root.val == x) {
            ans[0] = Math.max(Math.max(l, r), n - cnt);
        }
        return cnt;
    }
}

Scala 实现

object Solution {
    def btreeGameWinningMove(root: TreeNode, n: Int, x: Int): Boolean = {
        val ans: Array[Int] = new Array(1)
        nodes(root, n, x, ans)
        return ans(0) > n / 2
    }
    
    def nodes(root: TreeNode, n: Int, x: Int, ans: Array[Int]): Int = {
        if (root == null) {
            0
        } else {
            val l: Int = nodes(root.left, n, x, ans)
            val r: Int = nodes(root.right, n, x, ans)
            val cnt: Int = l + r + 1
            if (root.value == x) {
                ans(0) = scala.math.max(scala.math.max(l, r), n - cnt) 
            }
            cnt
        }
    }
}

Scala和Java基本一样,就是注意没有return statement,最后一个表达式就是return值。还有定义函数记得要加 =