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传文件，把旧电脑上的东西考到新电脑上。