前两周的时候看到有人推荐https://www.coursera.org/learn/algorithms-part1/的算法课，正好基础也忘得差不多了，觉得也是应该复(yu)习(xi)一下了，普林斯顿的这个公开课确实不错。

好了，废话不多说，来总结一下第一周，说说并查集和渗漏问题吧。

数据结构介绍

并查集是一个处理连接问题的数据结构，可以用这个结构快速的找到两个元素是否属于同一集合（或者说连通），和图的连通算法不同的是它忽略了路径的概念，只需要结果。

- 阅读剩余部分 -

上次去Google Girls送了我一本面试金典，前天无聊就看了起来，看到的部分目前还是比较基础也有些意思的，在我看到第一堆算法题的时候我说了一句，这个题看着有点简单啊……然后秒被打脸，可以说，所有的题都是想简单就简单，想难就难，主要看你考虑了多少。

今天就拿其中一道题来说说上面的观点。

实现一个算法，确定一个字符串的所有字符是否不同，假设不允许使用额外的数据结构，又该如何处理。

- 阅读剩余部分 -

在小鱼的gayhub看到了这样的一题，其中就需要用到洗牌程序，当然，我在看到排序算法的时候就想到这样可以用于排序，所以很快就有了第一个排序算法：

var shuffleHack = function(arr) {

    var result = arr.slice();

    result.sort(function() {

        return Math.random() - 0.5;

    });


    return result;

};


- 阅读剩余部分 -

依旧还是面试题，比较麻烦的是，这个排序的关键在于，我们需要时间复杂度为O(n)，空间复杂度为O(1)。

题目大概是这样的，看了输入输出基本就会明白了：

input: arr = ['', 'a', 'b', '', 'a', 'c', '*', 'm']
output: [ '', '', '*', 'a', 'a', 'b', 'c', 'm' ]
问题描述：将数组中的字母与星号分开

这里其实主要没做出来是因为我没有很好地理解怎么计算复杂度，尤其是空间复杂度，时间复杂度我勉强记忆成for循环的嵌套还是可以的，但是空间复杂度呢？

- 阅读剩余部分 -

面试时还被问到多维数组如何转换成一维数组的问题，这个问题比较灵活，其实也有很多种解法，当然，考虑到面试时候比较紧张，还是踏踏实实的用传统的方法来，和深拷贝一样，依旧是使用递归。

由于没有额外需要考虑的东西，因此这题实际上比起深拷贝来说要简单许多：

var convert = function(arr) {
    var newArr = [];

    arr.forEach(function(val) {
        if (val instanceof Array) {
            Array.prototype.push.apply(newArr, convert(val));
        } else {
            newArr.push(val);
        }
    });

    return newArr;
};

- 阅读剩余部分 -

从我学习至今，我有三大心理阴影：递归、正则表达式、动态规划——这三个导致让我怀疑智商怀疑人生。

在这次假期刷题的时候，前两个似乎都已经不是问题了，就差动态规划——昨天不行random到一道题，一眼望着就是动态规划了——可是我不会啊。

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

题目来自LeetCode，本来是不准备写LeetCode的题了，全都在GitHub上了大家看看就行了，不过这题有助于让我们更好地理解（第一次理解）动态规划。

- 阅读剩余部分 -

对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：

00000

00001

00010

00011

00100

请按从小到大的顺序输出这32种01串。

对于这题，你想到了什么吗？

没错，这题其实是二进制加法的变种，依次递增而已，并没有什么区别。

事实上，上学期写过二进制加法的代码，感觉应该不太难，结果脑子生锈了。

本题没有输入，我们来看看代码吧，因为只是一个二进制累加问题：

- 阅读剩余部分 -

利用字母可以组成一些美丽的图形，下面给出了一个例子：

ABCDEFG

BABCDEF

CBABCDE

DCBABCD

EDCBABC

这是一个5行7列的图形，请找出这个图形的规律，并输出一个n行m列的图形。

这题的问题不大，关键是找规律，很快我们就看出来，第一行和第一列是字母顺序，而剩下的则是对角线相同的关系。

数字规模也非常小，那就好说了。

import java.util.*;

public class AlphamosicGraphics {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int m = in.nextInt();

        char[][] arr = new char[n][m];

        for (int i = 0; i < n; i++) {
            arr[i][0] = (char)('A' + i);
        }

        for (int i = 0; i < m; i++) {
            arr[0][i] = (char)('A' + i);
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                arr[i][j] = arr[i - 1][j - 1];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(arr[i][j]);
            }

            System.out.println("");
        }
    }
}

这道坑爹题真是让人绞尽脑汁，实际上我觉得大家应该也能感受到，很多看似不难的算法题实际上难度在于——如何处理大数的情况，这道题也是一样。

这题是一道非常好的题，因为我不熟悉Java，对于各种类都不太清楚，也没什么感觉，但这题让我了解到了很多类/方法的差别，很具有学习价值。

给定n个十六进制正整数，输出它们对应的八进制数。
输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。
输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。

很明显的进制转换，刚开始我们想到的肯定是：既然是Java，大概会有进制转换的函数——一查，当然是有的：

Integer.toOctalString(Integer.valueOf(x, 16))

这个方法的连用也就是将16转成转成10进制再转成八进制。

- 阅读剩余部分 -

这一道题本来应该很简单：

求1+2+3+...+n的值。

简单吧，一个循环就能搞定，看上去是这样，但是事实上，我们要注意到数据规模：

1 <= n <= 1,000,000,000。

本题直接的想法是直接使用一个循环来累加，然而，当数据规模很大时，这种“暴力”的方法往往会导致超时。此时你需要想想其他方法。你可以试一试，如果使用1000000000作为你的程序的输入，你的程序是不是能在规定的上面规定的时限内运行出来。

嗯，那么就会遇到运行的问题。但是这种东西有什么好方法么——答案是，有的，名为等差数列求和公式的东西。

讲到这里，基本上大家也发现了，许多题都是在考你的数学能力。

- 阅读剩余部分 -