怎样在 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值。还有定义函数记得要加 =

怎样使用sftp command line?怎样在sftp里用pem file登陆

sftp是基于ssh的文件传输命令行工具,UNIX系统比如Mac和Linux里都有。各大平台,包括Windows也有图像界面的。还有个叫ftp的工具,是sftp的前辈,功能基本一样。s是secure的意思,就是ftp都是明码传输而sftp加密了。本文主要专注在命令行上面。

如果你需要使用AWS EC2,那么登陆需要用pem file,可以用如下命令

$ sftp -i <pem file name>.pem <user>@<ip>

用pem file的话不需要密码,登陆后进入交互式界面,和shell很像

sftp>

可以看服务器上的文件

sftp> ls

看本地文件

sftp> lls

上传文件

sftp> put <local file path> <remote file path>

上传目录加个-r,代表recursive

sftp> put -r <local file path> <remote file path>

下载文件

sftp> get <remote file path> <local file path> 

同理下载目录用-r

sftp> get -r <remote file path> <local file path> 

帮助就直接问号 ?

sftp> ?
Available commands:
bye                                Quit sftp
cd path                            Change remote directory to 'path'
chgrp grp path                     Change group of file 'path' to 'grp'
chmod mode path                    Change permissions of file 'path' to 'mode'
chown own path                     Change owner of file 'path' to 'own'
df [-hi] [path]                    Display statistics for current directory or
                                   filesystem containing 'path'
exit                               Quit sftp
get [-afPpRr] remote [local]       Download file
reget [-fPpRr] remote [local]      Resume download file
reput [-fPpRr] [local] remote      Resume upload file
help                               Display this help text
lcd path                           Change local directory to 'path'
lls [ls-options [path]]            Display local directory listing
lmkdir path                        Create local directory
ln [-s] oldpath newpath            Link remote file (-s for symlink)
lpwd                               Print local working directory
ls [-1afhlnrSt] [path]             Display remote directory listing
lumask umask                       Set local umask to 'umask'
mkdir path                         Create remote directory
progress                           Toggle display of progress meter
put [-afPpRr] local [remote]       Upload file
pwd                                Display remote working directory
quit                               Quit sftp
rename oldpath newpath             Rename remote file
rm path                            Delete remote file
rmdir path                         Remove remote directory
symlink oldpath newpath            Symlink remote file
version                            Show SFTP version
!command                           Execute 'command' in local shell
!                                  Escape to local shell
?                                  Synonym for help

退出

sftp> bye
# 或者
sftp> exit

或者 Ctrl + d

基本还是一个很容易使用的在本地和服务器传文件的小工具。

经典算法 非递归遍历二叉树 binary tree in order traversal without recursion

Binary in order traversal 一般是大多数人学习的第一个recursion算法,非常简单,3行就能写完。但这其实是compiler帮我们写了大部分的code,练习不用recursion能更好的帮助我们理解under the cover发生了什么。如果没练习过,其实还是不容易想到和写对的。

代码如下

Java

import java.util.Stack;
import TreeNode;

public class BstTraversal {
    public static void traversal(TreeNode root) {
        if (root == null)  {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        pushLeft(root, stack);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            System.out.println(cur.val);
            if (cur.right != null) {
                pushLeft(cur.right, stack);
            }
        }
    }

    public static void pushLeft(TreeNode node, Stack<TreeNode> stack) {
        TreeNode cur = node;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }

    // test
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;

        traversal(node1);
    }
}

其中TreeNode class如下

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public  TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}

经典算法 binary search 二分查找怎么实现?

二分查找很经典,当年看哈佛CS50是这么讲解的:怎么在字典里找某个单词?我们知道字典是按字母顺序排好序的。比如目标单词是cat,翻开字典中间,现在是g开头的词,那么我们知道cat肯定不在后半部分,那么可以把字典撕开,扔了后半部分。然后重复以上过程,中间翻开,这回是b开头的,就可以把前半部分仍了。如此下去,每次都把要搜索的空间减少一半,这样只用O(lgN)时间就能找到目标。不然的话一页页找的话就需要O(N)。虽然算法不复杂,但是要写对还是不容易的,以下经典实现最好背下来,内化到自己的知识库,就不用担心用到的时候边界条件不对。不然很容易进入死循环不返回,亲身经历。

代码如下:

Java

import java.util.Arrays;
import java.util.List;

public class Binarysearch {
    public static boolean binarySearch(int target, List<Integer> sortedlist) {
        if (sortedlist == null || sortedlist.isEmpty()) {
            return false;
        }
        int lower = 0;
        int upper = sortedlist.size()-1;
        while (lower <= upper) {
            int m = lower + (upper - lower) / 2;
            if (target == sortedlist.get(m)) {
                return true;
            } else if (target < sortedlist.get(m)) {
                upper = m - 1;
            } else {
                lower = m + 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<Integer> sortedList = Arrays.asList(1, 3, 3, 7, 20, 48, 64, 72, 1024);
        int [] targets = {20, 32, 55, 72, 100};
        for (int target : targets) {
            System.out.println(String.format("%d in list? %b", target, binarySearch(target, sortedList)));
        }
    }
}

主要以下要点

  • while里面条件要是 lower <= upper
  • update lower bound 要是 m + 1
  • update upper bound 要是 m - 1
  • 计算中指用 m = lower + (upper - lower) / 2,而不是 (upper + lower) / 2,这样可以去除整数相加overflow问题。当然如果类型是bigint之类就无所谓了。

算法练习 Leetcode 222 Count Complete Tree Nodes 解法

leetcode 222 解法

题目如下:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

最简单的做法就是直接遍历一边,不管是DFS还是BFS,时间复杂度都是O(N)。但是这样就没利用到complete binary tree的条件。优化的解法如果没练过的话其实不太好想。这题要的其实是找到最后一层有几个node。而每层的node的index就是在[2^h, 2^(h+1)-1]区间之内。如果有个function可以告诉你某个index在不在tree里,那么可以对[2^h, 2^(h+1)-1]做binary search,找到其中index最大并且在tree里的node。Binary tree的最后一层大概有N/2个node(每加一层,node数量翻倍!),那么需要做O(lgN)次search。

至于这个告诉某个node在不在tree里的函数可以这样写:写几个例子观察一下,如果一个node的index是n, 每个node的parent的index都是floor(n/2)。那么我们就能把从root到达目标node的path找出来,比如如果目标node是5,那么path就是[5, 2, 1],入股目标是8,那么path就是[8, 4, 2, 1]。然后从root,也就是1号node出发,如果最后我们按照这个地图能走到目标,那么这个node就在tree里面,否则就不在。这个function需要O(lgN)时间和O(lgN)空间。

最后总的时间复杂度这样计算,O(lgN)次search,每次 O(lgN)时间,总时间O((lgN)^2)。空间O(lgN)用来保存path。

代码如下

C++

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int h = findHeight(root);
        int i_min = pow(2, h);
        int i_max = pow(2, h + 1) - 1;
        int ans = i_min;
        while(i_min <= i_max) {
            int m = i_min + (i_max - i_min) / 2;
            if (inTree(root, m)) {
                ans = m;
                i_min = m + 1;
            } else{
                i_max = m - 1;
            }
        }   
        return ans;
        
    }
    
    int findHeight(TreeNode* root) {
        int h = 0;
        TreeNode* cur = root;
        while (cur != NULL) {
            cur = cur->left;
            h += 1;
        }
        return h - 1;
    }
    
    bool inTree(TreeNode* root, int i) {
        if (root == NULL || i < 0) {
            return false;
        }
        vector<int> path;
        int cur = i;
        while (cur != 0) {
            path.push_back(cur);
            cur /= 2;
        }
        TreeNode* curNode = root;
        for (int j = path.size() - 2; j >= 0; j--) {
            if (path[j] == path[j + 1] * 2) {
                curNode = curNode->left;
            } else {
                curNode = curNode->right;
            }
            if (curNode == NULL) {
                return false;
            }
        }
        return true;
    }
};

Java

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int h = findHeight(root);
        int i_min = (int)Math.pow(2, h);
        int i_max = (int)(Math.pow(2, h + 1) - 1);
        int ans = i_min;
        while (i_min <= i_max) {
            int m = i_min + (i_max - i_min) / 2;
            if (inTree(root, m)) {
                ans = m;
                i_min = m + 1;
            } else{
                i_max = m - 1;
            }
        }   
        return ans;
        
    }
    
    public int findHeight(TreeNode root) {
        int h = 0;
        TreeNode cur = root;
        while (cur != null) {
            cur = cur.left;
            h += 1;
        }
        return h - 1;
    }
    
    public boolean inTree(TreeNode root, int i) {
        if (root == null || i < 0) {
            return false;
        }
        List<Integer> path = new ArrayList<>();
        int cur = i;
        while (cur != 0) {
            path.add(cur);
            cur /= 2;
        }
        TreeNode curNode = root;
        for (int j = path.size() - 2; j >= 0; j--) {
            if (path.get(j) == path.get(j + 1) * 2) {
                curNode = curNode.left;
            } else {
                curNode = curNode.right;
            }
            if (curNode == null) {
                return false;
            }
        }
        return true;
    }
}