CodeSky 代码之空

双端队列，也就是栈和队列的结合，同时可以从头和尾进行进出栈 / 队列的功能，看一下他的数据结构就懂了：

1public class Deque<Item> implements Iterable<Item> {
2   public Deque()                           // construct an empty deque
3   public boolean isEmpty()                 // is the deque empty?
4   public int size()                        // return the number of items on the deque
5   public void addFirst(Item item)          // add the item to the front
6   public void addLast(Item item)           // add the item to the end
7   public Item removeFirst()                // remove and return the item from the front
8   public Item removeLast()                 // remove and return the item from the end
9   public Iterator<Item> iterator()         // return an iterator over items in order from front to end
10   public static void main(String[] args)   // unit testing (optional)
11}
12

双端队列的实现还是比较简单的（虽然实际上还会是踩了一些微小的坑）。

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

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

数据结构介绍

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

这篇文章其实是讲Java和Python的，其他的语言并不知道。

在Java里你可能会遇到这样一个问题：

1public class JavaIntegerCache {
2    public static void main(String... strings) {
3
4        Integer integer1 = 3;
5        Integer integer2 = 3;
6
7        if (integer1 == integer2)
8            System.out.println("integer1 == integer2");
9        else
10            System.out.println("integer1 != integer2");
11
12        Integer integer3 = 300;
13        Integer integer4 = 300;
14
15        if (integer3 == integer4)
16            System.out.println("integer3 == integer4");
17        else
18            System.out.println("integer3 != integer4");
19
20    }
21}
22

那么问题来了，答案是什么，首先，我们应该比较的是地址，这是引用类型，那么应该两个都不等吗？

运行结果是：

integer1 == integer2
integer3 != integer4

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

00000

00001

00010

00011

00100

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

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

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

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

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

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

ABCDEFG

BABCDEF

CBABCDE

DCBABCD

EDCBABC

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

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

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

1import java.util.*;
2
3public class AlphamosicGraphics {
4	public static void main(String[] args) {
5		Scanner in = new Scanner(System.in);
6
7		int n = in.nextInt();
8		int m = in.nextInt();
9
10		char[][] arr = new char[n][m];
11
12		for (int i = 0; i < n; i++) {
13			arr[i][0] = (char)('A' + i);
14		}
15
16		for (int i = 0; i < m; i++) {
17			arr[0][i] = (char)('A' + i);
18		}
19
20		for (int i = 1; i < n; i++) {
21			for (int j = 1; j < m; j++) {
22				arr[i][j] = arr[i - 1][j - 1];
23			}
24		}
25
26		for (int i = 0; i < n; i++) {
27			for (int j = 0; j < m; j++) {
28				System.out.print(arr[i][j]);
29			}
30
31			System.out.println("");
32		}
33	}
34}
35

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

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

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

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

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

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

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

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

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

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

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

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

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

很早写好了一直没写笔记，其实算法是个很微妙的数学问题，简单的题还是难得题基本上感觉都是数学不过关……

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。 当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

以前用C语言也写过斐波那契数列，不过内容不同，如果不知道斐波那契是什么的话，可以看看：http://codesky.me/archives/c-fibonacci-series.wind

事实证明，用直接递归求的方法确实不现实，但是人家有提示嘛：

在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

由于在下的数学实在是一团糟，所以根本不知道发生了什么。

最近在刷蓝桥杯的题，主要是比较简单，顺便可以练练自己的Java能力，因为光看书记不住实在不靠谱。

入门训练其实是熟悉OJ，理论上而言没什么好说的，但其实还是有很多疑问的。

比如这道圆的面积：

给定圆的半径r，求圆的面积。 输入包含一个整数r，表示圆的半径。

学校里有作业，需要实现生产者消费者模型，最简单的就是用synchronized同步锁一包，什么事情都没有了，不过由于是从最外层包起来的，所以总体而言就Low很多了。

一共用了四种方法，心好累：

synchronized