问题描述

写一个函数，输入n，求斐波那契（Fibonacci）数列第n项。
斐波那契数列定义为：f(n) = f(n-1) + f(n-2) (n>1) ,其中f(0)=0, f(1)=1。

算法思想

归并排序利于分治法的思想，在待排序序列选取位于中间位置的元素将序列一分为二，然后再对这两部分分别排序，最后将两部分合并，合并后的序列为已排序序列。

分的过程：设序列长度为N,则以(N-1)/2位置的元素为分界线，将队列分为两部分：位置从0到(N-1)/2的元素为一部分、位置从((N-1)/2)+1到N-1的元素为一部分（或者0到((N-1)/2-1)为一部分，(N-1)/2到N-1为一部分）。

合的过程：比较两个队列（两个队列已各自排好序）的队首元素，将小的从该队列中移除并插入到新队列的第一个位置，然后在比较两队列的首元素大小，将小的从该队列移除并将其添加到新队列上次添加的元素的后面，重复上述步骤直到有一个队列为空。最后将不为空的队列剩下所有的元素依次添加到新队列的最后，新队列则为一个已排序的队列。

插入排序

排序思想

将排序序列分为两部分，前一部分是已排序的序列，后一部分为待排序序列。

每次从待排序序列中选择一个元素，依次比较其和已排序序列中的元素的大小，直到找到一个比它大的元素，并将其插入到这个元素前边。重复上步，直到待排序序列中没有元素了。

基础概念

完全二叉树

完全二叉树(Complete Binary Tree)：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

堆

堆总是满足以下两个特性：

• 堆是一棵完全二叉树。
• 堆中每个结点的值总是不大于（或不小于）其子结点的值。

基本思想

在一趟排序过程中，选择一个基准值，通过交换的方式将待排序序列分为两个序列。其中一个序列在基准值左侧，这部分中所有数值都小于基准值；另一序列在基准值右侧，这部分中所有数值都大于基准值。然后对分割出的两个序列重复上述过程，直到排序结束。

问题描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

冒泡排序是一种稳定排序，时间复杂度为O(n^2)。

排序思想

依次交换相邻两个元素，使得大的数据往下沉（或小的数据往上附浮）。

排序过程

1. 比较相邻的两个元素，如果前者比后者大，则交换两元素。否则，不交换。
2. 重复第一步直到最后两个元素比较完成，此时，最大的元素已经在最后面了，此趟排序完成。
3. 去除最后元素，重复上述两步，对最后元素之前的数据进行排序。
4. 每趟排序完成后，大的数据会往下沉，也就是需要排序的数据会越来越少，直到没有任何一对数据需要排序，排序成功。

项目上出于安全因素考虑，提出了Android App是不能运行在已经Root过的设备上的需求，下面介绍下常见的Root检测方法（具体安全问题，不在本文讨论范围内）。

查看系统是否测试版本

我们可以通过查看系统版本方式检测，系统版本分为：test-keys（测试版）、release-keys（发布报）。在代码中可以通过android.os.Build.TAGS获取到当前系统的版本，如果不是release-keys，则有可能已经root过，存在风险。

在做项目的过程中，碰到了App需要使用双向认证的问题，记录下解决方法。

什么是双向认证？

简单来说，在一次请求中，客户端需要校验服务端证书合法性，服务端同时校验客户端合法性。
详细过程为：

制作SSL证书前，需要先了解两个概念：证书（certificate）和证书请求（certificate sign rquest）

1. 证书是自签名或CA签名过的凭据，用来进行身份认证。
2. 证书请求是对签名的请求，需要使用私钥进行签名。

1. 生成CA证书

第一步，生成 CA 私钥：

1

[root@py ssl_test]# openssl genrsa -out ca.key 1024

• ca.key 为私钥文件名;
• 1024为密钥长度，单位为bits，不写即为默认值为512。
  openssl genrsa 命令详细参数可参考维基百科：https://wiki.openssl.org/index.php/Manual:Genrsa(1)