有趣的位操作

位操作总给人一种直接安排计算机0/1的感觉,这里搜集整理一些有趣的题目。

朝闻道家庭基金201707月报

本月所持股票基本在横盘调整,贵州茅台再次接近历史新高,银行股经历了一次上涨。清空试验仓位瑞贝卡,因为看到一篇瑞贝卡的专题报道,说它的高管工资特别特别低,我觉得这是很不正常的,还是不碰为妙,搞笑的是卖了就大跌了。减仓万科,前期越跌越买的资金可以减少一些了。中青旅换成了中国国旅,主要是考虑到中国国旅较高的股息率以及免税店的火爆生意。建仓永辉超市,看好超市的消费升级。

比特币本月月底的变化值得一提,比特币的扩容问题一直是妨碍比特币成长的争议焦点,比特币核心开发组早前几个月就有人因为理念不一致愤怒的离开。目前的核心开发组希望增加一种称为闪电网络的特性,以侧链的方式来解决,而以部分矿工为代表的人,则希望简单的提升区块的大小。我在研究过两种方案后,个人倾向于矿工的解决方案,所谓的闪电网络提高了结算机构的地位,而提升区块大小则简单直接,至于提升区块大小被诟病的占磁盘空间大导致全节点会变少的问题,我觉得随着硬盘空间的变大并不是严重的问题,而且中本聪很早就给出了缩减容量的技术方案。因为本月底是算力对升级方案进行投票的重要节点,有消息称比特币将要分裂,因此币价遭到打压,我觉得分裂的风险很小,因此也小小玩了一把高抛低吸。目前币价又回归到了分裂消息之前的价格,如果这几个月平稳过渡,解决了容量问题,相信币价还有一波大的增长。此外,投入了部分比特币购买算力,参与挖矿活动。

拍拍贷完成了银行存管接入。将拍拍贷所有投资都变成了散标投资。拍拍贷散标累计年化收益率15.78%。

本月股票市值降低,比特币市值升高,总的来说净值和上月相比基本持平。

时间 净值 沪深300(比率)
20160101 1.0000 3470.41 (1.0000)
20161231 1.2526 3297.76 (0.9503)
20170126 1.2566 3387.96 (0.9762)
20170226 1.3245 3473.85 (1.0010)
20170331 1.3604 3456.05 (0.9959)
20170430 1.4060 3439.75 (0.9912)
20170531 1.5623 3492.88 (1.0065)
20170630 1.7505 3666.80 (1.0566)
20170731 1.7594 3737.87 (1.0771)

期末持仓品种:

  1. A股:贵州茅台、双汇发展、伊利股份、恒瑞医药、格力电器、美的集团、老板电器、苏泊尔、中国国旅、宇通客车、福耀玻璃、万科A、雅戈尔、平安银行、兴业银行、涪陵榨菜、中国建筑、海康威视、永辉超市、中国巨石。
  2. 基金:广发中证养老产业指数A、富国中证红利指数增强。
  3. 其他:拍拍贷散标、比特币。

在线编程(刷题)的低级错误

最近几天在一些OJ网站上刷了不少算法题,都是直接在网页上写代码,脑中调试,然后提交,发现提交通不过大概有以下几种情况:

  1. 算法设计出现根本性错误,一般是对题意有误解,或重要的分支情况未考虑到;
  2. 算法设计基本正确,但是有一些边界情况未考虑到;
  3. 时间复杂度太高;
  4. 低级错误。

以上的1、2、3属于算法的基本功,无论你是在线刷题,还是用IDE刷题,都避免不了,但是对于低级错误,IDE的编辑器静态分析就能发现一批,编译时又能发现一批,似乎也不是什么问题。

问题在于,技能的反面就是解决问题,解决一些低级错误是会浪费时间的,而且,有一些低级错误会躲过编译器,造成更大的危害,因此很有必要尽量减少这些低级错误。在线刷题时,我自己常见的低级错误(主要是java语言的):

  1. 没有写分号,或者写了中文分号;
  2. 括号未匹配;
  3. 未记住一些API的名称,比如HashMap中的containsKey而不是contains;
  4. 拼写错误,导致API调用错误,甚至标识符前后不一致;
  5. 更改了某个标识符,但是没有更改完全;
  6. 忘记写返回语句,或者某些支路忘记写返回语句,甚至返回了错误的变量或变量类型;
  7. 重复声明变量,比如循环内外各申明一次;
  8. 想要在循环外使用循环变量,但没有在外面声明;

暂时这些,以后不断补充。

如何改善?我发现我这么多年来都犯了一个错误,因为自己粗心,又觉得不可能不犯错误,就放弃了改善的机会,有些放任自流,从认识上就需要提高。以下是一些观点和方法,希望慢慢能标本兼治:

  1. 人都会犯错误,甚至犯低级错误,即所谓的粗心,粗心不能根除,但是可以改善;
  2. 意识到自己的低级错误并改善,而不要视而不见,放任自流;
  3. 适当放慢速度,萝卜快了不洗泥;
  4. 第一遍写的时候随时自我复查,要习惯脑子里有一个角色在复查,争取一次写对;
  5. 写完复查一遍。
  6. 及时总结自己犯了哪些低级错误。

这里谈的都是低级错误,还每涉及到如果提高程序的正确性,这一点以后再总结。

逆序对计数问题

有一组数,对于其中任意两个数组,若前面一个大于后面一个数字,则这两个数字组成一个逆序对。计算给定数组中的逆序对个数。

《建军大业》:创业的细节

建军大业

跑到电影院去看这部一般来说应该免费接受教育的电影,一是满足某人的恶趣味去数星星,二是自己也对一切创业史感兴趣。主旋律的题材,香港导演,一堆小鲜肉演员,作为电影来说还是及格的,只是这个故事我们已经看过无数遍了。反倒是一些细节我比较感兴趣,而还有一些细节却在电影中看不出来,看来真感兴趣还是得去读史料。

  1. 电影中有一段南昌起义后征用南昌银行中金条的小场景,甚至还有拿枪顶着人头同时又打欠条的镜头,一般历史的角度都是从政治军事来看的,但是我对经济的角度却最感兴趣,想知道民国时期,军阀割据时,各家是如何解决军饷问题的。
  2. 南昌起义基本失败后,朱德手下只剩下八百人,但是到了井冈山会师时,又拉出了几万人的队伍,包括打散了的叶挺、贺龙等等,后来都扩充了军队,我其实对这些人在阶段性失败后如何东山再起比较感兴趣,一般的文艺作品貌似着墨不多,可能一般对毛泽东的路线斗争与邓小平的几起几落写得多一些。
  3. 这次电影的战斗效果很爆表,我都很怀疑真正的历史火力有没有那么猛。然后,电影中还有毛泽东买军火的片段,我对当年的军火的来源与流动也很感兴趣。电影中还提到了汉阳兵工厂,它的百年历史,拍成电影或电视剧应该也很有意思。

硬币组合问题

假设我们有面值为1,2,5,10,25的硬币,那么组成面值共有多少种可能的情况?这是美分的情况。

一般的假设我们有面值为的硬币,其中,那么组成面值共有多少种可能的情况?

按照一般找钱的顺序,我们从大钱开始考虑,这样剩下的面值才能比较迅速的减小。

1.递推式1

考虑美分的情况,假设我们要组成面值101,记组合数为f(101),如果使用了一个25分的,那么剩下的情况数应该是f(76),但是注意,这个f(76)已经不能使用25分的硬币了,简单起见,我们把硬币种类编号引入组合数,当可以用编号1~k时,组合数记为f(m,k),所以上面的分析可以记为组合数f(101,5),使用了一个25分时,剩下的情况数为f(76, 4),针对25美分的使用,可以得到下表

25分个数 剩余
0 f(101, 4)
1 f(76, 4)
2 f(51, 4)
3 f(26, 4)
4 f(1, 4)

将第二列的数字相加,就得到了结果。现在要求的问题简化了,只需要考虑面值为1,2,5,10的情况,同样的以f(76, 4)为例,可以化简为f(76,3),f(66,3)…f(6,3),这样递归迭代下去,我们最终要解决的子问题是f(m,1),用一种面值来组成m,显然,只需要面值m能被整除即可,由此结束了递归迭代。

按照这种思路,直接写成Java代码如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        return countCoins(n, coins.length - 1, coins);
    }

    public int countCoins(int n, int level, int[] coins) {
        if(level == 0) {
            return n % coins[0] == 0 ? 1 : 0;
        }
        int ways = 0;
        for(int i = 0; i*coins[level] <= n; i++) {
            ways += countCoins(n-i*coins[level], level-1, coins);
        }
        return ways;
    }

2. 递推式1的动态规划

在1中,我们通过不断的减去大的硬币面值,求解各个子问题,得到最终的结果,不难发现,这些子问题存在很多重复,比如考虑如下的计算路径:f(101, 5)->f(76, 4)->f(16,3)…和f(101, 5)->f(26, 4)->f(16,3)…后面的计算时完全重合的,因此,如果把这些计算结果缓存起来,可以大大提高计算的速度,这就是动态规划的思想。我们需要建立如下的一张表,以下考虑计算f(6,5)

  0 1 2 3 4 5 6
1 1 1 1 1 1 1 1
2 1 1 2 2 3 3 4
5 1 1 2 2 3 4 5
10 1 1 2 2 3 4 5
25 1 1 2 2 3 4 5

注意到我们的递推式,每次分解出很多项,那么在动态规划填表时,也就需要很多项目相加才行。动态规划时,先填满第一行,再根据递推式计算第二行,直到计算最后一行。

由此得到Java代码如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[][] ways = new int[coins.length][n + 1];
        for(int j = 0; j <= n; j++) {
            ways[0][j] = j % coins[0] == 0 ? 1 : 0;
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = 0; j <= n; j++) {
                if(j < coins[i]) {
                    ways[i][j] = ways[i-1][j];
                }
                else {
                    for(int k = 0; k*coins[i] <= j; k++) {
                        ways[i][j] +=  ways[i-1][j-k*coins[i]];
                    }
                }
            }
        }
        return ways[coins.length - 1][n];
    }

注意到最后一行其实只需要计算最后一个元素。(因为它只跟前一行相关),所以上述代码还可以修改节约时间,不过代码会变得不太美观,这里就不写了。

3 递推式2及其动态规划

我们发现,递推式1中,一项被分解成多项,导致计算过程中做了相当多的加法,能不能简化一下呢?

还是考虑f(101,5),我们可以这样考虑,首先不使用25美分,情况数为f(101,4),其次是使用25美分的情况,那么至少要使用一个25美分,如果去掉这个25美分,则相当于剩下的76美分,既可以使用25美分,也可以不用,实际上就是f(76,5),由此得到递推关系,这样在动态规划填表时,每次取上一行的数与本行之前相距的数相加。注意当

由此得到动态规划的代码如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[][] ways = new int[coins.length][n + 1];
        for(int j = 0; j <= n; j++) {
            ways[0][j] = j % coins[0] == 0 ? 1 : 0;
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = 0; j <= n; j++) {
                if(j < coins[i]) {
                    ways[i][j] = ways[i-1][j];
                }
                else {
                    ways[i][j] = ways[i-1][j] + ways[i][j-coins[i]];
                }
            }
        }
        return ways[coins.length - 1][n];
    }

4 递推式2的简化

仔细考察我们填表的过程,填第二行时,左边的较小元素和第一行一样,右边较大的元素在第一行的基础上加上本行较小的一个元素,所以其实只需要存储一行元素就行了,计算 时, 在左边已经计算出来了,而直接使用自身存储便可。由此得到更加简化的动态规划代码:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[] ways = new int[n + 1];
        for(int j = 0; j <= n; j++) {
            ways[j] = j % coins[0] == 0 ? 1 : 0;
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = coins[i]; j <= n; j++) {
                ways[j] += ways[j-coins[i]];
            }
        }
        return ways[n];
    }

考虑第一行,如果设置ways[0] = 1,j<coins[0]时,ways[j] = 0,那么第一行同样可以用递推式ways[j] += ways[j-coins[i]]得到。代码可进一步简化如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[] ways = new int[n+1];
        ways[0] = 1;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= n; j++) {
                ways[j] = ways[j] + ways[j-coins[i]];
            }
        }
        return ways[n];
    }

全排列生成算法实现

我们知道n个相异元素的全排列种数为n!,那么由程序如何生成n个相异元素的排列呢,对此问题的研究很多,本文首先用Java实现了《算法设计与分析基础》一书中4.3节的三个算法。

1 插入法

这种算法最直观,基于排列的递推定义。符合所谓减治法的思想,或者说是数学归纳法的思想,如果n-1个元素已经排好,我们只需要把第n个元素插入这些排列中所有可能的位置即可,每个元素有n个位置可以插入,刚好是(n-1)!*n=n!种情况。如果插入的时候,方向先从右到左,再从左到右循环,那么每两个相邻的排列将只有最小的差异,即只有某两个相邻元素相异。比如已经有12,21则12从右到左插入3,21从左到右插入3,最终得到123,123,312,321,231,213。具体的Java代码如下,这是一个递归算法。

public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if(n <= 0) return permutations;
        if(n == 1) {
            permutations.add( new int[]{1});
            return permutations;
        }
        ArrayList<int[]> remainders = getPermutations(n-1);
        for(int i = 0; i < remainders.size(); i++) {
            int[] remainder = remainders.get(i);
            for(int j = 0; j < n; j++) {
                int[] permutation = new int[n];
                if(i % 2 ==0) {//insert from right to left
                    System.arraycopy(remainder, 0, permutation, 0, n - 1- j);
                    permutation[n - 1 - j] = n;
                    System.arraycopy(remainder, n - 1 - j, permutation, n - j, j);
                }
                else {//inset from left to right
                    System.arraycopy(remainder, 0, permutation, 0, j);
                    permutation[j] = n;
                    System.arraycopy(remainder, j, permutation, j + 1, n - 1- j);
                }
                permutations.add(permutation);
            }
        }
        return permutations;
	}

2 JohnsonTrott算法

在Johnson-Trotter算法中,每次循环都进行一次满足条件的相邻元素的交换,直到不存在满足条件的可交换的元素,此时说明所有排列的情况均已输出,算法结束。

具体过程如下:

  1. 初始化所有元素的移动方向为左,输出序列本身
  2. 移动最大的可移动的元素(当元素移动方向上的元素比自己小时,才能移动)
  3. 反转所有比移动元素大的所有元素的移动方向
  4. 重复2~3步,直到不能移动为止

具体例子

上面的算法流程有些抽象,现在举个例子来加深理解。假设现在要计算所有排列。首先是将所有元素的移动方向为标记为向左,我们可以表示成这样,然后根据算法流程中的步骤2,移动最大的可移动元素。这里的可移动元素是指在其移动方向上的相邻元素比自己小时,例如都是可移动元素,因为在他们的移动方向上(左移)的相邻元素:1,2分别比2,3小,而每次都只移动这些可移动元素中最大的那个项。接着,在每次交换完成之后,寻找所有比当前交换元素大的元素,将他们的移动方向反转一下。

下面列出在计算过程中所有的情况

Java代码如下:

public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        int[] first = new int[n];
        boolean[] mobile = new boolean[n];
        for(int i = 0; i < n; i++) {
            first[i] = i + 1;
            mobile[i] = true;//true:left; false:right;
        }
        permutations.add(first);

        while(true) {
            int[] last = permutations.get(permutations.size()-1).clone();
            int k = findLargestMobile(last, mobile);
            if(k == -1) break;
            int max = last[k];
            int neighbor = mobile[k] ? k - 1 : k + 1;
            swap(last, k, neighbor);
            swap(mobile, k, neighbor);
            reverseLarger(last, mobile, max);
            permutations.add(last);
        }
        return permutations;
    }

    private static int findLargestMobile(int[] array, boolean[] mobile) {
        int k = -1;// -1 means can't find mobile element
        int max = -1;
        for(int i = 0; i < array.length; i++) {
            int j = mobile[i] ? i - 1: i + 1;
            if(j < 0 || j >= array.length) continue;
            if(array[i] > array[j] && array[i] > max) {
                max = array[i];
                k = i;
            }
        }
        return k;
    }

    private static void reverseLarger(int[] array, boolean[] mobile, int max) {
        for(int i = 0; i < array.length; i++) {
            if(array[i] > max) mobile[i] = !mobile[i];
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static void swap(boolean[] array, int i, int j) {
        boolean temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

3 字典序生成法

字典序生成法在当前已经生成的排列上寻找下一个字典序的排列:

  1. 找到最长的递减序列后缀,记这个序列的前一个元素为i,如果找不到i,则证明已经生成了最后一个完全倒序的排列,生成完毕。
  2. 在前述后缀中,找到比元素i大的最小元素j,并交换i和j;
  3. 将后缀逆序排列。
  4. 重复1到3。

比如排列123654,首先找到后缀654,在找到中间最小大于3的4,交换得到124653,然后将后缀逆序得到124356,又如排列123645,找到后缀5,交换得到123654,后缀只有一个,逆序后不变仍未123654。

具体的Java代码如下:

public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if(n <= 0) return permutations;
        int[] first = new int[n];
        for(int i = 0; i < n; i++) first[i] = i + 1;
        permutations.add(first);

        while(true) {
            int[] last = permutations.get(permutations.size()-1).clone();
            int i = n - 1;
            while(i > 0) {
                if(last[i] > last[i-1]) {
                    break;
                }
                i--;
            }
            if(i==0) break;

            int j = n - 1;
            while(j >= i) {
                if(last[j]>last[i-1]) {
                    break;
                }
                j--;
            }
            swap(last, i-1, j);

            int k = n - 1;
            while(i < k) {
                swap(last, i, k);
                i++;
                k--;
            }
            permutations.add(last);
        }
        return permutations;
    }

4 序数法

这个方法把n!个排列与0~n!-1之间的数一一对应起来,这样,我们就可以按照0~n!-1的次序,逐一生成相关的排列。这个对应的关键在于0~n!-1之间的数m,可以用如下的方式表示: ,其中

故m对应序列,现在再把这个序列和排列一一对应起来,n-1位的序列对应n位的排列。

表示排列p中的数i+1所在位置的右边比它小的数的个数。比如对于排列p=4213,4,3,2的逆序数分别为3,0,1,由此对应为,反过来呢,如果知道了逆序数,也可以一一恢复出排列来。比4小的有3个,4只能放最左边,比3小的为0个,3只能放最右边,比2小的一个,2放第二个位置,剩下的放1,故为4213。

0 000 1234 12 200 1423
1 001 2134 13 201 2413
2 010 1324 14 210 1432
3 011 2314 15 211 2431
4 020 3124 16 220 3412
5 021 3214 17 221 3421
6 100 1243 18 300 4123
7 101 2143 19 301 4213
8 110 1342 20 310 4132
9 111 2341 21 311 4231
10 120 3142 22 320 4312
11 121 3241 23 321 4321

Java代码如下:

    public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        int[] factorials = new int[n+1];
        factorials[0] = 1;
        for(int i = 1; i <=n; i++) {
            factorials[i] = i * factorials[i - 1];
        }// init factorial array
        for(int m = 0; m < factorials[n]; m++) {
            int remainder = m;
            int[] permutation = new int[n];
            for(int i = n-1; i >=0; i--) {
                int count = remainder / factorials[i];
                remainder = remainder % factorials[i];
                setPosition(permutation, count, i + 1);
            }
            permutations.add(permutation);
        }
        return permutations;
    }

    private static void setPosition(int[] permutation, int count, int num) {
        int zeros = 0;
        for(int i = permutation.length - 1; i >=0; i--) {
            if(permutation[i] == 0) zeros++;
            if(zeros == count + 1) {
                permutation[i] = num;
                break;
            }
        }
    }

5 轮转法

基准序列,先逐步生成以开头的所有排列:

  1. 先生成以开头的所有排列
  2. 再生成以打头的排列,除了前述2个排列外,再将其后三位从左至右轮转2次,得到4个新排列,一共6个排列;
  3. 再生成以打头的排列,除了前述6个排列外,再将其后四位从左至右轮转3次,得到18个新排列,一共24个排列;
  4. 依次类推,一直到生成以开头的所有排列为止。

然后将基准序列从左到右轮转一次,生成以开头的所有排列,依次类推,直到生成以开头的所有排列。

java代码如下:

    public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        int[] first = new int[n];
        for(int i = 0; i < n; i++) {
            first[i] = i + 1;
        }
        for (int i = 0; i < n; i++) {
            if(i > 0) {
                rotateLeft(first, 0, n);
            }
            int[] base = first.clone();
            permutations.addAll(rotateBase(base));
        }
        return permutations;
    }

    private static ArrayList<int[]> rotateBase(int[] base) {
        ArrayList<int[]> permutations = new ArrayList<int[]>();
        permutations.add(base);
        for(int prefixSize = base.length - 2; prefixSize >= 1; prefixSize--) {
            int currentSize = permutations.size();
            for(int i = 0; i < currentSize; i++) {
                int[] last = permutations.get(i);
                for(int j = 0; j < base.length - prefixSize - 1; j++) {
                    int[] rotated = last.clone();
                    rotateLeft(rotated, prefixSize, base.length);
                    permutations.add(rotated);
                    last = rotated;
                }
            }
        }
        return permutations;
    }

    private static void rotateLeft(int[] permutation, int start, int end) { 
      // rotate from left to right
        int temp = permutation[start];
        for(int i = start; i < end - 1; i++) {
            permutation[i] = permutation[i + 1];
        }
        permutation[end-1] = temp;
    }

6 回溯法

我们将问题形象化,假如你手里有编号为1、2、3的3张扑克牌和编号为1、2、3的三个盒子。现在需要将这3张扑克牌分别放入3个盒子里,并且每个盒子有且只有一张扑克牌。总共有几种放法呢?

首先你来到了1号盒子面前,你现在手里有3张扑克牌,先放哪一张好呢?很显然三者都要尝试,那就姑且约定一个顺序:每次到一个盒子面前,都先放1号,再放2号,最后放3号。于是你在一号盒子里放入了编号为1的扑克牌。来到2号盒子面前,由于之前的1号扑克牌已经不在手中,按照之前约定的顺序,你将2号牌放到了2号盒子里。3号也是同样。你又往后走当你来到第4个盒子面前,诶,没有第四个盒子,其实我们不需要第4个盒子,因为手中的扑克牌已经放完了。

你发现了吗?当你走到第四个盒子前的时候,已经完成了一种排列,即“1 2 3”。然而并没有到此结束,产生了一种排列之后,你需要立即返回。现在你已经退到了3号盒子面前,你需要取回之前放在3号盒子中的扑克牌,再去尝试看看还能否放别的扑克牌,从而产生一个新的排列。于是你取回了3号牌,但由于你手中只有3号牌,你只能再次退回到2号盒子面前。

你回到2号盒子后,收回了2号牌。现在你的手中有2张牌了,分别是2号和3号牌。按照之前的约定,现在需要往2号盒子中放3号扑克牌(上次放的是2号牌)。放好后,你来到3号盒子面前,将手中仅剩的2号牌放入了3号盒子。又来到了4号盒子面前,当然没有4号盒子。此时又产生了一个新的排列“1 3 2”。

接下来按照刚才的步骤去模拟,便会依次生成所有排列:“2 1 3”、“2 3 1”、“3 1 2”和“3 2 1”。

Java代码实现如下:

    public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        boolean[] visited = new boolean[n];
        int[] current = new int[n];
        dfs(permutations, current, visited, 0);
        return permutations;
    }

    private static void dfs(ArrayList<int[]> permutations, int[] current, boolean[] visited, int step) {
        int n = current.length;
        if(step == n) {
            permutations.add(current.clone());
            return;
        }
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                current[step] = i + 1;
                visited[i] = true;
                dfs(permutations, current, visited, step + 1);
                visited[i] = false;
            }
        }
    }

当然,如果改用栈,也可以变成非递归的版本。

后记

对一个问题用不同的算法解决,可以综合复习各种算法思路。

另外重要的一点就是,如果看过一个算法没有写代码实现过,很可能会有一些没有真正理解的细节存在。

如果以后再发现好的算法,还会再补充。

我的PC软件列表

我一直比较喜欢试用各种软件,也喜欢看别人分享的软件推荐的文章,总的来说,我是一个工具控。现在工作告一段落,也想借这闲暇时间把自己目前正在使用的软件总结一下,一是备忘,二是分享,三是留待一两年后再看,什么变了,什么没变。

我目前电脑主要使用的操作系统是Windows 10,但是我倾向于使用一些可以跨平台使用的软件,这样万一我想换平台则成本比较低。下面主要列举的是软件,可能会适当涉及在线服务。

1 操作系统

  • Windows 10 :所有的笔记本、台式机、Surface都使用Windows 10了,一是安全起见,二来我也觉得Windows 10还是比较好用的。开启了Bash On Ubuntu On Windows子系统后,也不用装其他的命令行工具,甚至Linux系统也用得很少了。
  • Deepin Linux :现在已经过了喜欢折腾系统的阶段,觉得操作系统最好开箱即用,而深度在这一点上做到了极致,预装了很多国人必备的软件比如WPS、QQ等。虽然在主力笔记本上使用三硬盘双系统,但是其实现在用得也不多。

2 文本与写作

  • Office365 :其实还是很喜欢Office软件,之前在工作中用得不少,现在买了Office 365服务,其实也用得不多,可能用最多是Excel了。
  • Typora :非常好用的markdown编辑器,这篇博客就是这么写的。
  • Jekyll + Github Pages:这是现在的主力写作平台,在诸多静态博客生成器中选择了Jekyll,只是因为这是GitHub默认支持的,懒得折腾了。

3 浏览器

  • Chrome:主力浏览器。其中重要的插件包括AdBlock、Checker Plus for Gmail™、Proxy SwitchyOmega、Save to Pocket、惠惠购物助、印象笔记·剪藏等。
  • IE11:没办法,工行只能用IE。
  • Firefox:现在用得比较少了,出于感情因素一直装着。

4 通信软件

  • TIM:替代QQ,没有杂七杂八的东西。
  • 微信 for Windows 10:发现都是腾讯家的。
  • Telegram:刚刚接触,看重它的保密通信。

5 系统增强

  • BandZip:压缩软件,界面清爽,功能强大。
  • CCleaner:垃圾清理软件。
  • Geek Unіnstaller:一款小巧的软件卸载工具,卸载时会查找注册表与垃圾文件。
  • RightMenuMgr:右键管理工具,可以删除一些不需要的右键项目。
  • FastCopy:文件快速拷贝工具。
  • f.lux:屏幕色温自动调节工具。
  • Everything:非常强大的文件搜索工具。
  • Wox:快速启动工具。
  • WGestures :全局鼠标手势工具。

6 下载工具

  • 迅雷极速版:虽然迅雷越来越水,但是这款极速版至少还没什么广告,是个比较纯粹的下载工具。
  • 百度网盘:可能是我用的唯二的百度服务了,另外一个是百度糯米。
  • 人人影视Pro:下载人人影视的作品很方便。
  • Resilio Sync:偶尔下点小东西,基于bittorrent原理的网盘工具。

7 影音娱乐

  • 射手播放器:虽然很久不更新了,但基本上还是万能播放器,最好的是还能自动下载字幕。
  • 网易云音乐UWP:主要在网易云音乐听歌,顺便本地歌曲播放也一起搞定了。
  • 多多猫app:可以看漫画的插件式强大软件,不过我也很少看就是了。

8 开发工具

  • Visual Studio 2017:工作中主用Visual Studio,自己的个人电脑习惯装最新版的。宇宙第一IDE,名不虚传。配上JetBrain家的Reshaper插件,写C#简直是所向无敌。
  • Intelij IDEA:偶尔也写写Java代码,再装上插件,写Pyhton之类的也毫无压力。
  • Visual Studio Code:又是微软出品的强大文本编辑器,装上插件后当轻量级的IDE用,写写Python,改改网站代码之类的。
  • Anaconda:一套完整的Python配套软件环境,包括数据分析常用的各种利器,今年开始研究机器学习,这是一个利器。
  • Octave:Matlab的开源版,偶尔写写简单的Matlab代码,或者当计算器算算矩阵。
  • Xshell :远程连接VPS时很好用。
  • GitExtension:一整套Git的解决方案,包括Git的GUI界面,以及文件比较工具等。
  • AutoHotkey:自动化脚本工具。

9 安全软件

  • WIndows Defender:不爱装其他杀毒软件,基本上等于裸奔了。
  • VeraCrypt:加密软件。

10 阅读软件

  • Kindle:偶尔也在电脑上用一下。
  • calibre:现在所有的电子书都交给它来管理了。
  • LightReader:轻量级的epub阅读器。
  • 福昕阅读器领鲜版:Foxit Reader的国内版,有pdf编辑功能。
  • DrowBoard PDF:在Surface上看PDF是神器。

11 其他

  • 印象笔记高级账户:它的特点是在各种笔记软件中比较简约均衡,Office365中的OneNote我也用,但是感觉太重了。
  • 科学上网工具:v2ray、XX-Net、Shadowsocks、Lantern,需要多种手段互为备份。
  • ZeroNet:最近刚接触的新鲜玩意儿,基于类似比特币的原理构建的P2P内容网络。
  • paint.net:偶尔改个图,当PhotoShop用。
  • Zotero:收集论文资料用。
  • Oracle VM VirtualBox:虚拟机软件。
  • FileZilla:FTP软件。
  • GeoGebra:一款有趣的几何作图软件。
  • Bither:一款比特币官方推荐的国人开发的比特币钱包。
  • TeamViewer:给家人远程桌面解决问题时用。

暂时就这些,发现有遗漏的再补充。

复习与复盘

上小学的时候,我们就有单元复习、期中复习、期末复习等等各种复习,整个初等教育学的东西其实总量有限,反反复复学的就是那点东西,因为它要面向大多数学生的水平,而且要打牢基础。

复习其实是学习新的东西中最重要的方法论之一,人的大脑会不断的选择性遗忘很多东西,只有通过复习才能巩固,而且更重要的是,大多数的学习材料是不可能第一遍就完全理解的,比如说你的第一遍学习掌握了30%,那么通过一轮复习可能达到50%,再复习一遍可能达到了80%,而复习的时候,一般不需要花第一次那么多时间,这样看来,复习的性价比是很高的。我觉得有几个原因,第一在复习的间隙,大脑得到机会重建神经网络,而不是一直处在紧绷状态,第二复习的时候由于已经掌握了很多基础,能够减轻自己理解的负担,集中精力在重点和难点上。

我觉得还有一个很重要的类似复习的过程,是回顾自己的思维过程,或者绕口一点,叫思考自己的思考过程,想一想自己在做出决策的时候,获得了哪些知识和信息,有什么样的情绪在其中,当时有多大的把握,是否受到了什么人的影响。这样做的次数多了,就越来越知道做出一个决策需要调研什么知识,需要关注自己的哪些非理性的有害的情绪,怎样建立信心,如何参考他人的意见等等。就像下围棋的人要复盘一样,重要的决策都值得像下围棋一样复盘,这和复习新知识有着相似的道理,复盘的时候,我们往往已经知道了决策的结果,也从当时的情绪中抽离出来,从而获得了更加客观看待自己思维过程的上帝视角。

子曰:吾日三省吾身。我以前只想到道德上的需要,想到“反省”一词,觉得有些负面,而用复盘一词,我觉得更加中性,也更能激励我的热情。

房贷的计算

之前我讨论过分期付款的实际利率,发现比较坑。今天再来讨论一下房贷,房贷的计算有很多在线的计算器,输入贷款额度,利率,以及贷款年数,选择等额本息还是等额本金还款,就可以得到每月还款的数值,下面我来分析一下这里面的原理,并简单讨论一下两种还款方式的优劣,以及提前还款是否有必要。

1.一个例子

假设贷款100万,年利率5%,贷款20年,使用前述计算器计算,得到等额本息还款每月6,599.56元,等额本金还款首月8,333.33元,以后每月递减17.36元。一般的,假设借款总额为T,年华利率为p,贷款年限为Y。

2.基本原理

房贷的利率是很厚道的实际利率,什么叫实际利率呢?就是按你实际占用银行资金的多少来计算利息。当你按月归还了一定的本金了以后,下个月计息的本金就变少了,而不像消费贷的分期付款,计息的本金一直是不变的,才出现实际利率比名义利率高很多的情况。无论是等额本息还是等额本金还款,利率都是实际利率,而按目前的商贷利率4.90%,公积金利率3.25%,甚至还有折扣,所以房贷是普通人能拿到大额低息贷款的最重要的方式。

按照实际利率,如果上一期还欠本金,年化利率为p,本期归还本金C,则本月须还款

M=C+T*p/12,下一期本金变为T-C。

3.等额本金还款

等额本金还款每个月还款数额逐渐减少,看起来比较麻烦,但是在原理和数学计算上其实更简单。首先,我们把借的本金T摊分到所有的月份,为,则首月还款为,T=1,000,000,p=5%,Y=20时,计算得到C=4166.67元,M=8333.33元,以后每月本金减少C,相应的利息减少,为17.36元。可以看到,等额本金还款每月还的本金不变,而利息则在不断减少。

4.等额本息还款

等额本息还款每个月还款数额相同,看起来比较简单,但是原理时数学计算更复杂,关键在于依然要符合2中所说的基本原理,随着待还本金的减少,每月还的利息会减少,但是要求每月归还的本金和利息加起来应该相同,这样的话,每个月归还的本金应该越来越多,才能维持这个平衡,究竟多多少,需要一个细致的计算过程。

我们知道最后一个月归还本金和利息后,贷款还完了,可以据此倒推。假设最后一个月还本金,则利息为,还款总额为,往前推一个月,假设这个月归还本金$M_{n-1}$,则利息为,归还总额为,由于,不难推出,一般的,由 得出

所以每月还款的本金是一个等比数列,它的比值比率是,简单起见,我们计算最后一个月的本金,则

,则,每月还款额度为,第一个月还款,以后每月等比增加,T=1,000,000,p=5%,Y=20,计算得到C=6,599.56,其中第一个月归还本金为2432.89元,每月等比增加1.0041667倍。

5 比较与提前还款

由于等额本金与等额本息还款方式的利率都是实际利率,所以在资金效率上,两者其实没有任何差别,网上有人分析说等额本息还款刚开始还的利息多本金少,所以提前还款相对等额本金的提前还款不划算,我认为是没有道理的,因为银行始终是按你实际占用的本金额度来收取利息的,而提前还款则是将余下的本金一次性还完。而两种贷款方式的选择,乃至是否提前还款,都不影响资金效率,那么该如何选择呢?

首先比较一下等额本金和等额本息,等额本金刚开始还款多,以后还款少,其中归还本金每月固定,而等额本息始终还款数额一样,其中归还本金每月增多,选择哪种方式,取决与你的工资收入水平以及占用资金后资金的投资效率,首先,如果你现在收入少,估计以后收入会不断增长,那么为了减轻现在的负担,自然是刚开始少还一点好,这时建议等额本息,而如果你现在收入高,以后还很难说,那么建议等额本金。但是如果你虽然现在钱很多,但是你的投资收益要高于贷款利率,那么还是建议等额本息,这样你能更多更久的占用银行资金来赚取利率差。

实际上如果你够钱全款买房,但是投资水平超过房贷利率,那么使用房贷依然是一个很好的选择,这种低息高额贷款是很难得的,而哪些炒房团,往往也是通过房贷负债加杠杆迅速的增长自己的财富的。

涉及到提前还款也是如此,如果你当下的投资收益率高过贷款利率,那么没有必要提前还款,反之投资收益率低于贷款利率,则建议提前还款,这跟等额本金或等额本息其实没什么关系。