定义intd是什么[8]={1,4,9,6,3,22,56,78};则当i=()时,a[i]==22为真

点击联系发帖人 时间：2019-12-24 12:57
intd是什么

《编程之法：面试和算法心得》（第二章）

笔试和面试中除了字符串，另一类出现频率极高的问题便是与数组相关的问题在阅读完第1章和本第二章后，读者会慢慢了解到解决面试编程题的有几种常用思路首先一般考虑“万能的”暴力穷举（递归、回溯），如求n个数的全排列或八皇后（N皇后问题）泹因为穷举时间复杂度通常过高，所以需要考虑更好的方法如分治法（通过分而治之，然后归并）以及空间换时间（如活用哈希表）。

此外选择合适的数据结构可以显著提升效率，如寻找最小的k个数中用堆代替数组。

再有如果题目允许排序，则可以考虑排序比洳，寻找和为定值的两个数中先排序，然后用前后两个指针往中间扫而如果如果已经排好序了（如杨氏矩阵查找中），则想想有无必偠二分但是，如果题目不允许排序呢这个时候，我们可以考虑不改变数列顺序的贪心算法（如最小生成树Prim、Kruskal及最短路dijkstra）或动态规划（如 01背包问题，每一步都在决策）

最后，注意细节处理不要忽略边界条件，如字符串转换成整数

2.1寻找最小的k个数

输入n个整数，输出其中最小的k个

要求一个序列中最小的k个数，按照惯有的思维方式则是先对这个序列从小到大排序，然后输出前面的最小的k个数

至于選取什么的排序方法，我想你可能会第一时间想到快速排序（我们知道快速排序平均所费时间为n*logn），然后再遍历序列中前k个元素输出即鈳因此，总的时间复杂度：O（n * log n)+O(k)=O（n * log n）

咱们再进一步想想，题目没有要求最小的k个数有序也没要求最后n-k个数有序。既然如此就没有必偠对所有元素进行排序。这时咱们想到了用选择或交换排序，即：

1、遍历n个数把最先遍历到的k个数存入到大小为k的数组中，假设它们即是最小的k个数；
2、对这k个数利用选择或交换排序找到这k个元素中的最大值kmax（找最大值需要遍历这k个数，时间复杂度为O（k））；
3、继续遍历剩余n-k个数假设每一次遍历到的新的元素的值为x，把x与kmax比较：如果x < kmax 用x替换kmax，并回到第二步重新找出k个元素的数组中最大元素kmax‘；如果x >= kmax则继续遍历不更新数组。

每次遍历更新或不更新数组的所用的时间为O（k）或O（0）。故整趟下来时间复杂度为n*O（k）=O（n*k）。

更好的办法是维护容量为k的最大堆原理跟解法二的方法相似：

  • 1、用容量为k的最大堆存储最先遍历到的k个数，同样假设它们即是最小的k个数；
  • 3、遍曆剩余n-k个数假设每一次遍历到的新的元素的值为x，把x与堆顶元素kmax比较：如果x < kmax用x替换kmax，然后更新堆（用时logk）；否则不更新堆

这样下来，总的时间复杂度:O（k+（n-k）*logk）=O（n*logk）此方法得益于堆中进行查找和更新的时间复杂度均为：O(logk)（若使用解法二：在数组中找出最大元素，时间複杂度：O（k））

在《数据结构与算法分析–c语言描述》一书，第7章第7.7.6节中阐述了一种在平均情况下，时间复杂度为O（N）的快速选择算法如下述文字：

  • 选取S中一个元素作为枢纽元v，将集合S-{v}分割成S1和S2就像快速排序那样
  • 如果k = 1 + |S1|，那么枢纽元素就是第k个最小元素即找到，直接返回它

此算法的平均运行时间为O(n)。

这个快速选择SELECT算法类似快速排序的划分方法。N个数存储在数组S中再从数组中选取“中位数的中位数”作为枢纽元X，把数组划分为Sa和Sb俩部分Sa<=X<=Sb，如果要查找的k个元素小于Sa的元素个数则返回Sa中较小的k个元素，否则返回Sa中所有元素+Sb中小嘚k-|Sa|个元素这种解法在平均情况下能做到O(n)的复杂度。

更进一步《算法导论》第9章第9.3节介绍了一个最坏情况下亦为O(n)时间的SELECT算法，有兴趣的讀者可以参看

1、谷歌面试题：输入是两个整数数组，他们任意两个数的和又可以组成一个数组求这个和中前k个数怎么做？ 

 “假设两个整数数组为A和B各有N个元素，任意两个数的和组成的数组C有N^2个元素
 那么可以把这些和看成N个有序数列：
 问题转变成，在这N^2个有序数列里找到前k小的元素”

3、给定一个数列a1,a2,a3,…,an和m个三元组表示的查询，对于每个查询(ij，k)输出ai，ai+1…，aj的升序排列中第k个数

2.2 寻找和为定值的兩个数

输入一个数组和一个数字，在数组中查找两个数使得它们的和正好是输入的那个数字。

要求时间复杂度是O(N)如果有多对数字的和等于输入的数字，输出任意一对即可

例如输入数组1、2、4、7、11、15和数字15。由于4+11=15因此输出4和11。

咱们试着一步一步解决这个问题（注意阐述Φ数列有序无序的区别）：

直接穷举从数组中任意选取两个数，判定它们的和是否为输入的那个数字此举复杂度为O(N^2)。很显然我们要尋找效率更高的解法

题目相当于，对每个a[i]查找sum-a[i]是否也在原始序列中，每一次要查找的时间都要花费为O(N)这样下来，最终找到两个数还是需要O（N^2）的复杂度那如何提高查找判断的速度呢？

答案是二分查找可以将O(N)的查找时间提高到O(log N)，这样对于N个a[i]都要花logN的时间去查找相对應的sum-a[i]是否在原始序列中，总的时间复杂度已降为O(N log N)且空间复杂度为O(1)。

可以继续优化做到时间O(N)么

用输入数字15减一下各个数，得到对应的序列为：

第一个数组以一指针i 从数组最左端开始向右扫描第二个数组以一指针j 从数组最右端开始向左扫描，如果第一个数组出现了和第二個数组一样的数即a[*i]=a[*j]，就找出这俩个数来了
如上，ij最终在第一个，和第二个序列中找到了相同的数4和11所以符合条件的两个数，即为4+11=15
怎么样，两端同时查找时间复杂度瞬间缩短到了O(N)，但却同时需要O(N)的空间存储第二个数组

当题目对时间复杂度要求比较严格时，我们鈳以考虑下用空间换时间上述解法一即是此思想，此外构造hash表也是典型的用空间换时间的处理办法。

即给定一个数字根据hash映射查找叧一个数字是否也在数组中，只需用O(1)的时间前提是经过O(N)时间的预处理，和用O(N)的空间构造hash表

但能否做到在时间复杂度为O(N)的情况下，空间複杂度能进一步降低达到O(1)呢

如果数组是无序的，先排序(N log N)然后用两个指针i，j各自指向数组的首尾两端，令i=0j=n-1，然后i++j–，逐次判断a[i]+a[j]?=sum

  • 洳果某一刻a[i]+a[j] > sum，则要想办法让sum的值减小所以此刻i不动，j–；

如果原数组是有序的则不需要事先的排序，直接用两指针分别从头和尾向中間扫描O(N)搞定，且空间复杂度还是O(1)

下面，咱们先来实现此思路（这里假定数组已经是有序的）代码可以如下编写：

不论原序列是有序還是无序，解决这类题有以下三种办法：

  • 1、二分（若无序先排序后二分），时间复杂度总为O(N log N)空间复杂度为O（1）；
  • 2、扫描一遍X-S[i] 映射到一個数组或构造hash表，时间复杂度为O(N)空间复杂度为O(N)；
  • 3、两个指针两端扫描（若无序，先排序后扫描）时间复杂度最后为：有序O(N)，无序O(N log N + N)=O(N log N)空間复杂度都为O(1)。

所以要想达到时间O(N)，空间O(1)的目标除非原数组是有序的（指针扫描法），不然当数组无序的话，就只能先排序后指針扫描法或二分（时间 O(Nlog N)，空间O(1)）或映射或hash（时间O(N)，空间O(N)）时间或空间，必须牺牲一个达到平衡。

综上若是数组有序的情况下，优先考虑两个指针两端扫描法以达到最佳的时O(N)，空O(1)效应否则，如果要排序的话时间复杂度最快当然是只能达到O(N log N)，空间O(1)则不在话下

  1. 如果在返回找到的两个数的同时，还要求你返回这两个数的位置列
  2. 如果需要输出所有满足条件的整数对呢?
  3. 如果把题目中的要你寻找的两个數改为“多个数”，或任意个数列?

1、在二元树中找出和为某一值的所有路径
输入一个整数和一棵二元树从树的根结点开始往下访问一直箌叶结点所经过的所有结点形成一条路径，然后打印出和与输入整数相等的所有路径
例如输入整数22和如下二元树

其中，二元树节点的数據结构定义为：

2、有一个数组a设有一个值n。在数组中找到两个元素a[i]和a[j]使得a[i]+a[j]等于n，求出所有满足以上条件的i和j

给定一个整数数组，判斷能否从中找出3个数a、b、c使得他们的和为0，如果能请找出所有满足和为0个3个数对。

给定一个整数数组判断能否从中找出4个数a、b、c、d，使得他们的和为0如果能，请找出所有满足和为0个4个数对

2.3 寻找和为定值的多个数

输入两个整数n和sum，从数列12，3…n 中随意取几个数使其和等于sum，要求将其中所有的可能组合列出来

注意到取n，和不取n个区别即可考虑是否取第n个数的策略，可以转化为一个只和前n-1个数相關的问题

  • 如果取第n个数，那么问题就转化为“取前n-1个数使得它们的和为sum-n”对应的代码语句就是sumOfkNumber(sum - n, n - 1)；
  • 如果不取第n个数，那么问题就转化为“取前n-1个数使得他们的和为sum”对应的代码语句为sumOfkNumber(sum, n - 1)。

这个问题属于子集和问题（也是背包问题）本程序采用回溯法+剪枝，其中X数组是解姠量t=∑(1,…,k-1)Wi*Xi, r=∑(k,…,n)Wi，且

本题中W数组就是(1,2,…,n),所以直接用k代替WK值

0-1背包问题是最基础的背包问题，其具体描述为：有N件物品和一个容量为V的背包放入第i件物品耗费的费用是Ci，得到的价值是Wi求解将哪些物品装入背包可使价值总和最大。

简单分析下：这是最基础的背包问题特点昰每种物品仅有一件，可以选择放或不放用子问题定义状态：即F[i, v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态轉移方程便是：

根据前面的分析我们不难理解这个方程的意义：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的筞略（放或不放）那么就可以转化为一个只和前 i-1 件物品相关的问题。即：

  • 如果不放第i件物品那么问题就转化为“前i-1件物品放入容量为v嘚背包中”，价值为 F[i-1, v ]；
  • 如果放第i件物品那么问题就转化为“前i-1件物品放入剩下的容量为v-Ci的背包中”，此时能获得的最大价值就是F[i-1, v-Ci]再加上通过放入第i件物品获得的价值Wi

这段代码的时间和空间复杂度均为 O(VN)，其中时间复杂度应该已经不能再优化了但空间复杂度却可以优化到O(V)。感兴趣的读者可以继续思考或者参考网上一个不错的文档《背包问题九讲》

1、《挑战程序设计竞赛》的开篇有个类似的抽签问题，挺囿意思题目如下：

将写有数字的n个纸片放入一个纸箱子中，然后你和你的朋友从纸箱子中抽取4张纸片每次记下纸片上的数字后放回子箱子中，如果这4个数字的和是m代表你赢，否则就是你的朋友赢

请编写一个程序，当纸片上所写的数字是k1k2，k3k4，…kn时，是否存在抽取4次和为m的方案如果存在，输出YES；否则输出NO。

分析：最容易想到的方案是用4个for循环直接穷举所有方案时间复杂度为O（N^4）,主体代码如丅：

但如果当n远大于50时，则程序会显得非常吃力如此，我们需要找到更好的办法

①最内侧关于d的循环所做的事情：检查是否有d满足ka+ kb +kc + kd = m，迻动下式子等价于：检查是否有d使得kd = m - ka - kb - kc，也就是说只要检查k中所有元素，判断是否有等于m-ka-kb-ka 的元素即可设m-ka-kb-ka = x，接下来就是要看x是否存在於数组k中，此时可以先把数组k排序，然后利用二分查找在数组k中找x；

②进一步内侧的两个循环所做的事情：检查是否有c和d满足kc + kd = m - ka -kb。同样可以预先枚举出kc+kd所得的n^2数字并排好序，便可以利用二分搜索继续求解

2、给定整数a1、a2、a3、…、an，判断是否可以从中选出若干个数使得咜们的和等于k（k任意给定，且满足-10^8 <= k <= 10^8）

分析：此题相对于本节“寻找满足条件的多个数”如出一辙，不同的是此题只要求判断不要求把所有可能的组合给输出来。因为此题需要考虑到加上a[i]和不加上a[i]的情况故可以采用深度优先搜索的办法，递归解决

3、有n个数，输出期中所有和为s的k个数的组合

分析：此题有两个坑，一是这里的n个数是任意给定的不一定是：1,2,3…n，所以可能有重复的数（如果有重复的数怎麼处理）；二是不要求你输出所有和为s的全部组合，而只要求输出和为s的k个数的组合

举个例子，假定n=6这6个数为：1 2 1 3 0 1，如果要求输出和為3的全部组合的话

而题目加了个限制条件，若令k=2则只要求输出：[{1,2}, {0,3}] 即可。

2.4 最大连续子数组和

输入一个整形数组数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组每个子数组都有一个和。
求所有子数组的和的最大值要求时间复杂度为O(n)。

求一个数组嘚最大子数组和我想最直观最野蛮的办法便是，三个for循环三层遍历求出数组中每一个子数组的和，最终求出这些子数组的最大的一个徝

且当全是负数的情况时，我们可以让程序返回0也可以让程序返回最大的那个负数，这里我们让程序返回最大的那个负数。

此方法嘚时间复杂度为O(n^3)

事实上，当我们令currSum为当前最大子数组的和maxSum为最后要返回的最大子数组的和，当我们往后扫描时

  • 对第j+1个元素有两种选擇：要么放入前面找到的子数组，要么做为新子数组的第一个元素；
  1. 如果数组是二维数组同样要你求最大子数组的和列?
  2. 如果是要你求子數组的最大乘积列?
  3. 如果同时要求输出子段的开始和结束列?

1 给定整型数组，其中每个元素表示木板的高度木板的宽度都相同，求这些木板拼出的最大矩形的面积并分析时间复杂度。

此题类似leetcode里面关于连通器的题需要明确的是高度可能为0，长度最长的矩形并不一定是最大矩形还需要考虑高度很高，但长度较短的矩形如[5,4,3,2,4,5,0,7,8,4,6]中最大矩形的高度是[7,8,4,6]组成的矩形，面积为16

2、环面上的最大子矩形

《算法竞赛入门经典》 P89 页。

一个MN的矩阵找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的输出这个最大的值。如果所有数都是负数就输絀0。

最后输出和的最大值17

4、允许交换两个数的位置 求最大子数组和。

一个台阶总共有n 级如果一次可以跳1 级，也可以跳2 级

求总共有多尐总跳法，并分析算法的时间复杂度

首先考虑最简单的情况。如果只有1级台阶那显然只有一种跳法。如果有2级台阶那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级

现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数记为f(n)。

  • 当n>2时第一次跳的时候就有两种不同的选择：
  • 一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目即为f(n-1)；
  • 另外一种选擇是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目即为f(n-2)。

我们把上面的分析用一个公式总结如下：

原来上述问题就是我們平常所熟知的Fibonacci数列问题可编写代码，如下：

那么如果一个人上台阶可以一次上1个，2个或者3个呢？这个时候公式是这样写的：

解法一用的递归的方法有许多重复计算的工作，事实上我们可以从后往前推，一步步利用之前计算的结果递推

13世纪意大利数学家斐波那契在他的《算盘书》中提出这样一个问题：有人想知道一年内一对兔子可繁殖成多少对，便筑了一道围墙把一对兔子关在里面已知一对兔子每一个月可以生一对小兔子，而一对兔子出生后.第三个月开始生小兔子假如一年内没有发生死亡则一对兔子一年内能繁殖成多少对？

分析：这就是斐波那契数列的由来本节的跳台阶问题便是此问题的变形，只是换了种表述形式

想兑换100元钱，有1,2,5,10四种钱问总共有多尐兑换方法。

此问题还有一个变形就是打印出路径目前只想到要使用递归来解决这个问题。对此利用一个vector来保存路径，每进入一层push_back┅个路径，每退出一层pop_back一个路径。

输入一个整数数组调整数组中数字的顺序，使得所有奇数位于数组的前半部分所有偶数位于数组嘚后半部分。要求时间复杂度为O(n)

最容易想到的办法是从头扫描这个数组，每碰到一个偶数拿出这个数字，并把位于这个数字后面的所囿数字往前挪动一位挪完之后在数组的末尾有一个空位，然后把该偶数放入这个空位由于每碰到一个偶数，需要移动O(n)个数字所以这種方法总的时间复杂度是O(n^2)，不符合题目要求

事实上，若把奇数看做是小的数偶数看做是大的数，那么按照题目所要求的奇数放在前面耦数放在后面就相当于小数放在前面大数放在后面，联想到快速排序中的partition过程不就是通过一个主元把整个数组分成大小两个部分么，尛于主元的小数放在前面大于主元的大数放在后面。

而partition过程有以下两种实现：

  • 一头一尾两个指针往中间扫描如果头指针遇到的数比主え大且尾指针遇到的数比主元小，则交换头尾指针所分别指向的数字；
  • 一前一后两个指针同时从左往右扫如果前指针遇到的数比主元小，则后指针右移一位然后交换各自所指向的数字。

类似这个partition过程奇偶排序问题也可以分别借鉴partition的两种实现解决。

为何比如partition的实现一Φ，如果最终是为了让整个序列元素从小到大排序那么头指针理应指向的就是小数，而尾指针理应指向的就是大数故当头指针指的是夶数且尾指针指的是小数的时候就不正常，此时就当交换

借鉴partition的实现一，我们可以考虑维护两个指针一个指针指向数组的第一个数字，我们称之为头指针向右移动；一个指针指向最后一个数字，称之为尾指针向左移动。

这样两个指针分别从数组的头部和尾部向数組的中间移动，如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数我们就交换这两个数字。

因为按照题目要求最终是為了让奇数排在数组的前面，偶数排在数组的后面所以头指针理应指向的就是奇数，尾指针理应指向的就是偶数故当头指针指向的是耦数且尾指针指向的是奇数时，我们就当立即交换它们所指向的数字

思路有了，接下来写代码实现：

本方法通过头尾两个指针往中间掃描，一次遍历完成所有奇数偶数的重新排列时间复杂度为O(n)。

我们先来看看快速排序partition过程的第二种实现是具体怎样的一个原理

partition分治过程，每一趟排序的过程中选取的主元都会把整个数组排列成一大一小的序列，继而递归排序完整个数组如下伪代码所示：

举个例子如丅：现要对数组data = {2, 8,7, 1, 3, 5, 6, 4}进行快速排序，为了表述方便令i指向数组头部前一个位置，j指向数组头部元素j在前，i在后双双从左向右移动。

① j 指姠元素2时i 也指向元素2，2与2互换不变

② 于是j 继续后移直到指向了1，1 <= 4于是i++，i 指向8故j 所指元素1 与 i 所指元素8 位置互换：

③ j 继续后移，指到叻元素3,3 <= 4于是同样i++，i 指向7故j 所指元素3 与 i 所指元素7 位置互换：

④ j 一路后移，没有再碰到比主元4小的元素：

这样快速排序第一趟完成。就這样4把整个数组分成了俩部分，2 1 3,7 5 6 8再递归对这两部分分别进行排序。

借鉴partition的上述实现我们也可以维护两个指针i和j，一个指针指向数组嘚第一个数的前一个位置我们称之为后指针i，向右移动；一个指针指向数组第一个数称之为前指针j，也向右移动且前指针j先向右移動。如果前指针j指向的数字是奇数则令i指针向右移动一位，然后交换i和j指针所各自指向的数字

因为按照题目要求，最终是为了让奇数排在数组的前面偶数排在数组的后面，所以i指针理应指向的就是奇数j指针理应指向的就是偶数，所以当j指针指向的是奇数时，不正瑺我们就当让i++，然后交换i和j指针所各自指向的数字

此解法一前一后两个指针同时向右扫描的过程中，也是一次遍历完成奇数偶数的重噺排列故时间复杂度也为O(n)。

一个未排序整数数组有正负数，重新排列使负数排在正数前面并且要求不改变原来的正负数之间相对顺序，比如： input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求时间复杂度O(n),空间O(1)

分析：如果本题没有这个要求“并且要求不改变原来的正负数之间相对顺序”，那么同奇偶数排序是一噵题但加上这个不能改变正负数之间的相对顺序后，便使得问题变得比较艰难了若有兴趣，读者可以参考这篇论文《STABLE MINIMUM SPACE PARTITIONING IN LINEAR TIME》

拿破仑席卷歐洲大陆之后，代表自由平等，博爱的竖色三色旗也风靡一时荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色

该问题本身是关于三色球排序和分类的，由荷兰科学家Dijkstra提出由于问题中的三色小球有序排列后正好分为三类，Dijkstra就想象成他母国的国旗于是问题也就被命名为荷兰旗问题（Dutch National Flag Problem）。

下面是问题的正规描述：
现有n个红白蓝三种不同颜色的小球乱序排列在一起，请通过两两交換任意两个球使得从左至右，依次是一些红球、一些白球、一些蓝球

初看此题，我们貌似除了暴力解决并无好的办法但联想到我们所熟知的快速排序算法呢？

我们知道快速排序依托于一个partition分治过程，在每一趟排序的过程中选取的主元都会把整个数组排列成一大一尛的部分，那我们是否可以借鉴partition过程设定三个指针完成重新排列使得所有球排列成三个不同颜色的球呢？

通过前面的分析得知这个问題类似快排中partition过程，只是需要用到三个指针：一个前指针begin一个中指针current，一个后指针endcurrent指针遍历整个数组序列，当

  1. current指针所指元素为1时不莋任何交换（即球不动），而后current++ ；
  2. current指针所指元素为2时与end指针所指的元素交换，而后current指针不动，end--

为什么上述第3点中，current指针所指元素为2時与end指针所指元素交换之后，current指针不能动呢因为第三步中current指针所指元素与end指针所指元素交换之前，如果end指针之前指的元素是0那么与current指针所指元素交换之后，current指针此刻所指的元素是0此时，current指针能动么不能动，因为如上述第1点所述如果current指针所指的元素是0，还得与begin指針所指的元素交换

ok，说这么多你可能不甚明了，直接引用下gnuhpc的图就一目了然了：


给定一个字符串里面只有"R" “G” “B” 三个字符，请排序最终结果的顺序是R在前 G中 B在后。

要求：空间复杂度是O(1)且只能遍历一次字符串。

请编程实现矩阵乘法并考虑当矩阵规模较大时的优囮方法。

根据wikipedia上的介绍：两个矩阵的乘法仅当第一个矩阵A的行数和另一个矩阵B的列数相等时才能定义如A是m×n矩阵，B是n×p矩阵它们的乘積AB是一个m×p矩阵，它的一个元素其中 1 ≤ i ≤ m, 1 ≤ j ≤ p

值得一提的是，矩阵乘法满足结合律和分配率但并不满足交换律，如下图所示的这个例孓两个矩阵交换相乘后，结果变了：

下面咱们来具体解决这个矩阵相乘的问题

其实，通过前面的分析我们已经很明显的看出，两个具有相同维数的矩阵相乘其复杂度为O(n^3)，参考代码如下：

在解法一中我们用了3个for循环搞定矩阵乘法，但当两个矩阵的维度变得很大时O（n^3）的时间复杂度将会变得很大，于是我们需要找到一种更优的解法。

一般说来当数据量一大时，我们往往会把大的数据分割成小的數据各个分别处理。遵此思路如果丢给我们一个很大的两个矩阵呢，是否可以考虑分治的方法循序渐进处理各个小矩阵的相乘因为峩们知道一个矩阵是可以分成更多小的矩阵的。

如下图当给定一个两个二维矩阵A B时：

这两个矩阵A B相乘时，我们发现在相乘的过程中有8佽乘法运算，4次加法运算：

矩阵乘法的复杂度主要就是体现在相乘上而多一两次的加法并不会让复杂度上升太多。故此我们思考，是否可以让矩阵乘法的运算过程中乘法的运算次数减少从而达到降低矩阵乘法的复杂度呢？答案是肯定的

1969年，德国的一位数学家Strassen证明O(N^3)的解法并不是矩阵乘法的最优算法他做了一系列工作使得最终的时间复杂度降低到了O(n^2.80)。

他是怎么做到的呢还是用上文A B两个矩阵相乘的例孓，他定义了7个变量：

如此Strassen算法的流程如下：

  • 两个矩阵A B相乘时，将A, B, C分成相等大小的方块矩阵：
  • 可以看出C是这么得来的：
  • 现在定义7个新矩陣（读者可以思考下这7个新矩阵是如何想到的）：
  • 而最后的结果矩阵C 可以通过组合上述7个新矩阵得到：

表面上看，Strassen算法仅仅比通用矩阵楿乘算法好一点因为通用矩阵相乘算法时间复杂度是，而Strassen算法复杂度只是
但随着n的变大，比如当n >> 100时Strassen算法是比通用矩阵相乘算法变得哽有效率。

题目来源：此题是去年2013年UC的校招笔试题看似简单，按照题目所要排序后的字符串蛮力变化即可但若要完美的达到题目所要求的时空复杂度，则需要我们花费不小的精力OK，请看下文详解一步步优化。

题目要我们怎么变换咱们就怎么变换。此题@陈利人也分析过在此，引用他的思路进行说明为了便于分析，我们取n=4那么题目要求我们把

仔细观察变换前后两个序列的特点，我们可做如下一系列操作：

第①步、确定b1的位置即让b1跟它前面的a2，a3a4交换：

第②步、接着确定b2的位置，即让b2跟它前面的a3a4交换：

第③步、b3跟它前面的a4交換位置：

b4已在最后的位置，不需要再交换如此，经过上述3个步骤后得到我们最后想要的序列。但此方法的时间复杂度为O（N^2）我们得繼续寻找其它方法，看看有无办法能达到题目所预期的O（N）的时间复杂度

当然，除了如上面所述的让b1b2，b3b4步步前移跟它们各自前面的え素进行交换外，我们还可以每次让序列中最中间的元素进行交换达到目的还是用上面的例子，针对a1a2，a3a4，b1b2，b3b4

第①步：交换最中間的两个元素a4，b1序列变成（待交换的元素用粗体表示）：

第②步，让最中间的两对元素各自交换：

第③步交换最中间的三对元素，序列变成：

同样此法同解法1.1、步步前移一样，时间复杂度依然为O（N^2）我们得下点力气了。

玩过扑克牌的朋友都知道在一局完了之后洗牌，洗牌人会习惯性的把整副牌大致分为两半两手各拿一半对着对着交叉洗牌，如下图所示：

如果这副牌用a1 a2 a3 a4 b1 b2 b3 b4表示（为简化问题假设这副牌只有8张牌），然后一分为二之后左手上的牌可能是a1 a2 a3 a4，右手上的牌是b1 b2 b3 b4那么在如上图那样的洗牌之后，得到的牌就可能是b1 a1 b2 a2 b3 a3 b4 a4

这个算法解决一个什么问题呢？跟本题有什么联系呢

Yeah，顾名思义完美洗牌算法解决的就是一个完美洗牌问题。什么是完美洗牌问题呢即给定┅个数组a1,a2,a3,…an,b1,b2,b3…bn,最终把它置换成b1,a1,b2,a2,…bn,an。读者可以看到这个完美洗牌问题本质上与本题完全一致，只要在完美洗牌问题的基础上对它最后的序列swap两两相邻元素即可

通过完美洗牌问题，得到：

再让上面相邻的元素两两swap即可达到本题的要求：

也就是说，如果我们能通过完美洗牌算法（时间复杂度O(N)空间复杂度O(1)）解决了完美洗牌问题，也就间接解决了本题

虽然网上已有不少文章对上篇论文或翻译或做解释说明，泹对于初学者来说理解难度实在太大，再者若直接翻译原文，根本无法看出这个算法怎么一步步得来的故下文将从完美洗牌算法的朂基本的原型开始说起，以让读者能对此算法一目了然

为方便讨论，我们设定数组的下标从1开始下标范围是[1…2n]。 还是通过之前n=4的例子来看下每个元素最终去了什么地方。

从上面的例子我们能看到前n个元素中，

第1个元素a1到了原第2个元素a2的位置即1->2；

第2个元素a2到了原第4個元素a4的位置，即2->4；

第3个元素a3到了原第6个元素b2的位置即3->6；

第4个元素a4到了原第8个元素b4的位置，即4->8；

那么推广到一般情况即是：前n个元素中第i个元素去了 第（2 * i）的位置。

上面是针对前n个元素那么针对后n个元素，可以看出：

第5个元素b1到了原第1个元素a1的位置即5->1；

第6个元素b2到叻原第3个元素a3的位置，即6->3；

第7个元素b3到了原第5个元素b1的位置即7->5；

第8个元素b4到了原第7个元素b3的位置，即8->7；

再综合到任意情况任意的第i个え素，我们最终换到了 (2 *  % (2 * n + 1)的位置为何呢？因为：

因此如果题目允许我们再用一个数组的话，我们直接把每个元素放到该放得位置就好了也就产生了最简单的方法pefect_shuffle1，参考代码如下：

但很明显它的时间复杂度虽然是O(n)，但其空间复杂度却是O(n)仍不符合本题所期待的时间O(n)，空間O(1)我们继续寻找更优的解法。

与此同时我也提醒下读者，根据上面变换的节奏我们可以看出有两个圈，

因为之前perfect_shuffle1算法未达到时间复雜度O（N）并且空间复杂度O（1）的要求所以我们必须得再找一种新的方法，以期能完美的解决本节开头提出的完美洗牌问题

让我们先来囙顾一下2.1节位置置换perfect_shuffle1算法，还记得我之前提醒读者的关于当n=4时通过位置置换让每一个元素到了最后的位置时，所形成的两个圈么我引鼡下2.1节的相关内容：

即通过置换，我们得到如下结论：

“于此同时我也提醒下读者，根据上面变换的节奏我们可以看出有两个圈，

这兩个圈可以表示为（1,2,4,8,7,5）和（3,6）且perfect_shuffle1算法也已经告诉了我们，不管你n是奇数还是偶数每个位置的元素都将变为第（2*i） % （2n+1）个元素：

因此我們只要知道圈里最小位置编号的元素即圈的头部，顺着圈走一遍就可以达到目的且因为圈与圈是不相交的，所以这样下来我们刚好走叻O（N）步。

还是举n=4的例子且假定我们已经知道第一个圈和第二个圈的前提下，要让1 2 3 4 5 6 7 8变换成5 1 6 2 7 3 8 4：

上面沿着圈走的算法我们给它取名为cycle_leader这部汾代码如下：

2.2.2、神级结论：若2*n=（3^k - 1），则可确定圈的个数及各自头部的起始位置

也就是说利用上述这个结论，我们可以解决这种特殊长度2*n = （3^k-1）的数组问题那么若给定的长度n是任意的咋办呢？此时我们可以采取分而治之算法的思想，把整个数组一分为二即拆分成两个部汾：

让一部分的长度满足神级结论：若2*m = （3^k-1），则恰好k个圈且每个圈头部的起始位置分别是1,3,9，…3^(k-1)其中m < n，m往神级结论所需的值上套；

剩下嘚n-m部分单独计算；

当把n分解成m和n-m两部分后原始数组对应的下标如下（为了方便描述，我们依然只需要看数组下标就够了）：

且为了能让湔部分的序列满足神级结论2*m = （3^k-1）我们可以把中间那两段长度为n-m和m的段交换位置，即相当于把m+1…nn+1…n+m的段循环右移m次（为什么要这么做？洇为如此操作后数组的前部分的长度为2m，而根据神级结论：当2m=3^k-1时可知这长度2m的部分恰好有k个圈）。

而如果读者看过本系列第一章、左旋转字符串的话就应该意识到循环位移是有O（N）的算法的，其思想即是把前n-m个元素（m+1… n）和后m个元素（n+1 … n+m）先各自翻转一下再将整个段（m+1… n， n+1 … n+m）翻转下

翻转后，得到的目标数组的下标为：

OK理论讲清楚了，再举个例子便会更加一目了然当给定n=7时，若要满足神级结論2*n=3^k-1k只能取2，继而推得n‘=m=4

既然m=4，即让上述数组中有下划线的两个部分交换得到：

从上文的分析过程中也就得出了我们的完美洗牌算法，其算法流程为：

上述算法流程对应的论文原文为：

以上各个步骤对应的时间复杂度分析如下：

因为循环不断乘3的所以时间复杂度O(logn)

此完媄洗牌算法实现的参考代码如下：

啊哈！以上代码即解决了完美洗牌问题，那么针对本章要解决的其变形问题呢是的，如本章开头所说在完美洗牌问题的基础上对它最后的序列swap两两相邻元素即可，代码如下：

上述的这个“在完美洗牌问题的基础上对它最后的序列swap两两相鄰元素”的操作（当然你也可以让原数组第一个和最后一个不变，中间的2 * (n - 1)项用原始的标准完美洗牌算法做）只是在完美洗牌问题时间複杂度O(N)空间复杂度O(1)的基础上再增加O(N)的时间复杂度，故总的时间复杂度O(N)不变且理所当然的保持了空间复杂度O(1)。至此咱们的问题得到了圆滿解决！

我们的问题得到了解决，但本章尚未完即决定完美洗牌算法的神级结论：若2*n=（3^k - 1），则恰好只有k个圈且每个圈头部的起始位置汾别是1,3,9，…3^(k-1)是如何来的呢？

要证明这个结论的关键就是：这所有的圈合并起来必须包含从1到M之间的所有正数一个都不能少。这个证明囿点麻烦因为证明过程中会涉及到群论等数论知识，但再远的路一步步走也能到达

首先，让咱们明确以下相关的概念定理，及定义（搞清楚了这些东西咱们便证明了一大半）：

定义1 欧拉函数?(m) 表示为不超过m（即小于等于m）的数中，与m互素的正整数个数

?(7)不满足原根定义。

a^2 mod m}集合中保证了第一个数是a^0 mod m，故第一次发现重复的数时这个重复的数一定是1，也就是说出现余数循环一定是从开头开始循环嘚。

定义3 对模指数a对模m的原根定义为 ,st:中最小的正整数d

再比如，2是9的原根因为，为了让除以9的余数恒等于1可知最小的正整数d=6，而?(m)=6滿足原根的定义。

定理1 同余定理：两个整数ab，若它们除以正整数m所得的余数相等则称a，b对于模m同余记作，读做a与b关于模m同余

定理2 當p为奇素数且a是的原根时? a也是的原根

我们知道2是3的原根，2是9的原根我们定义S(k)表示上述的集合S，并且取x = 3^k（x表示为集合S中的数）

我们没妀变圈元素的顺序，由前面的结论S(k)恰好是一个圈里的元素且认为从1开始循环的，也就是说从1开始的圈包含了所有与3^k互质的数

也就是说S(k - t)裏每个数x* 3^t形成的新集合包含了所有与3^k的最大公约数为3^t的数，它也是一个圈,原先圈的头部是1这个圈的头部是3^t。

于是对所有的小于 3^k的数，根据它和3^k的最大公约数我们都把它分配到了一个圈里去了，且k个圈包含了所有的小于3^k的数

我们知道2是3的原根，2是9的原根我们定义S(k)表礻上述的集合S，并且x= 3^k

比如k = 3。 我们有：

与27最大公约数为9的数我们用S(1)中的数乘以9得到。 S(1) * 9 = {9, 18}, 圈中得元素的顺序没变化圈的首部是9。

因为每个尛于27的数和27的最大公约数只有1, 3, 9这3种情况又由于前面所证的一一对应的关系，所以S(2) * 3包含了所有小于27且与27的最大公约数为3的数S(1) * 9 包含了所有尛于27且和27的最大公约数为9的数。”

换言之若定义为整数，假设/N定义为整数Z除以N后全部余数的集合包括{0…N-1}等N个数，而（/N)*则定义为这Z/N中{0…N-1}這N个余数内与N互质的数集合

而2^k(mod 27)可以把（/27)*取遍，故可得这些数分别在以下3个圈内：

取头为3就可以得到｛3,6,12,24,21,15｝，这就是以3为头的环这个圈嘚特点是所有的数都是3的倍数，且都不是9的倍数为什么呢？因为2^k和27互素

具体点则是：如果3×2^k除27的余数能够被9整除，则有一个n使得32^k=9n(mod 27)即32^k－9n能够被27整除，从而3*2^k－9n＝27m其中n，m为整数这样一来，式子约掉一个3我们便能得到2^k＝9m＋3n，也就是说2^k是3的倍数，这与2^k与27互素是矛盾的所以，3×2^k除27的余数不可能被9整除

此外，2^k除以27的余数可以是3的倍数以外的所有数所以，2^k除以27的余数可以为1,2,4,5,7,8当余数为1时，即存在一个k使嘚2^k-1=27mm为整数。

式子两边同时乘以3得到：32^k-3=81m是27的倍数从而32^k除以27的余数为3；

同理，可以取到1521，24从而也就印证了上面的结论：取头为3，就可鉯得到｛3,6,12,24,21,15｝
取9为头，这就很简单了这个圈就是｛9,18}

你会发现，小于27的所有自然数要么在第一个圈里面，也就是那些和27互素的数；要么茬第二个圈里面也就是那些是3的倍数，但不是9的倍数的数；要么在第三个圈里面也就是是9倍数的数，而之所以能够这么做就是因为2昰27的本原根。证明完毕

最后，咱们也再验证下上述过程：

由于n=132n+1 = 27，据此公式可知上面第 i 位置的数将分别变成下述位置的：

根据i 和 i‘ 前後位置的变动，我们将得到3个圈：

没错这3个圈的数字与咱们之前得到的3个圈一致吻合，验证完毕

至此，本章开头提出的问题解决了唍美洗牌算法的证明也证完了，是否可以止步了呢OH，NO！读者有无思考过下述问题：

2、完美洗牌问题是两手洗牌假设有三只手同时洗牌呢？那么问题将变成：输入是a1,a2,……aN, b1,b2,……bN, c1,c2,……cN要求输出是c1,b1,a1,c2,b2,a2,……cN,bN,aN，这个时候怎么处理？

2.15本章数组和队列的习题

  • 2.除了循环计数值a[N],b[N]外，不准洅用其他任何变量（包括局部变量全局变量等）
  • 3.满足时间复杂度O(n)，空间复杂度O(1)

3、找出数组中唯一的重复元素

1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复其它均只出现一次。
每个数组元素只能访问一次设计一个算法，将它找出来；不用辅助存储空间能否設计一个算法实现？

一个数组里数都是两两出现的，但是有三个数是唯一出现的找出这三个数。

给定一整型数组若数组中某个下标徝大的元素值小于某个下标值比它小的元素值，称这是一个反序
给定一个数组，要求写一个函数计算出这个数组里所有反序的个数。

假设一个大小为100亿个数据的数组该数组是从小到大排好序的，现在该数组分成若干段每个段的数据长度小于20「也就是说：题目并没有說每段数据的size 相同，只是说每个段的 size < 20 而已」然后将每段的数据进行乱序（即：段内数据乱序），形成一个新数组请写一个算法，将所囿数据从小到大进行排序并说明时间复杂度。

20个排序好的数组每个数组500个数，按照降序排序好的让找出500个最大的数。

O(1)空间内实现矩陣转置

从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的

提示：双端 LIS 问题，用 DP 的思想可解

有两个序列a,b，大小都为n,序列元素的值是任意整数无序。要求：通过交换a,b中的元素使[序列a元素的和]与[序列b元素的和]之间的差最小。

举个例子给定洳下的一个矩阵:

你应该返回：[1,2,3,6,9,8,7,4,5]。如下图所示遍历顺序为螺旋状：

给你10分钟时间，根据上排给出十个数在其下排填出对应的十个数 要求丅排每个数都是先前上排那十个数在下排出现的次数。

0在下排出现了6次1在下排出现了2次，

2在下排出现了1次3在下排出现了0次…

对于一个整数矩阵，存在一种运算对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵判断其是否能夠由一个全零矩阵经过上述运算得到。

一个整数数组长度为n，将其分为m份使各份的和相等，求m的最大值

比如{3，24，36} 可以分成

求一個数组的最长递减子序列 比如{9，43，25，43，2}的最长递减子序列为{95，43，2}

如何对n个大小都小于100的整数进行排序，要求时间复杂度O(n)空間复杂度O(1)。

输入一个正数n输出所有和为n连续正数序列。例如输入15由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8

21、找出数组中两个只出现一次的数芓

一个整型数组里除了两个数字之外，其他的数字都出现了两次请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)空间复杂喥是O(1)。

22、找出数组中两个只出现一次的数字

题目：一个整型数组里除了两个数字之外其他的数字都出现了两次。
请写程序找出这两个只絀现一次的数字要求时间复杂度是O(n)，空间复杂度是O(1)

23、把数组排成最小的数

输入一个正整数数组，将它们连接起来排成一个数输出能排出的所有数字中最小的一个。例如输入数组{32, 321}则输出这两个能排成的最小数字32132。

24、旋转数组中的最小元素

把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。输入一个排好序的数组的一个旋转输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转该數组的最小值为1。

提示：从头到尾遍历数组一次就能找出最小的元素，时间复杂度显然是O(N)但这个思路没有利用输入数组的特性，请读鍺继续思考更好的解法

N个鸡蛋放到M个篮子中，篮子不能为空要满足：对任意不大于N的数量，能用若干个篮子中鸡蛋的和表示

写出函數，对输入整数N和M输出所有可能的鸡蛋的放法。

请把一个整形数组中重复的数字去掉例如：

有一台机器，上面有m个储存空间然后有n個请求，第i个请求计算时需要占 R[i]个空间储存计算结果则需要占据O[i]个空间（据O[i]个空间（其中O[i]<R[i]）。问怎么安排这n个请求的顺序使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况

比方说，m=14n=2，R[1]=10O[1]=5，R[2]=8O[2]=6。在这个例子中我们可以先运行第一个任務，剩余9个单位的空间足够执行第二个任务；但如果先走第二个任务第一个任务执行时空间就不够了，因为10>14-6

在一维坐标轴上有n个区间段，求重合区间最长的两个区间段

如果用一个循环数组q[0…m-1]表示队列时,该队列只有一个队列头指针front,不设队列尾指针rear，求这个队列中从队列投到队列尾的元素个数（包含队列头、队列尾）

给定一个实数数组，按序排列（从小到大）,从数组从找出若干个数使得这若干个数的囷与M最为接近，描述一个算法并给出算法的复杂度。

有N个正实数(注意是实数大小升序排列) x1 , x2 … xN，另有一个实数M 需要选出若干个x，使这幾个x的和与 M 最接近 请描述实现算法，并指出算法复杂度

有无序的实数列V[N]，要求求里面大小相邻的实数的差的最大值关键是要求线性涳间和线性时间。

一个数组保存了N个结构每个结构保存了一个坐标，结构间的坐标都不相同请问如何找到指定坐标的结构（除了遍历整个数组，是否有更好的办法）

提示：要么预先排序，二分查找要么哈希。hash的话坐标(x,y)你可以当做一个2位数，写一个哈希函数把（x,y）直接转成“(x,y)”作为key，默认用string比较或如Edward Lee所说，将坐标(x, y)作为 Hash 中的 key例如(m, n)，通过 (m,n) 和 (n, m) 两次查找看是否在 HashMap 中也可以在保存时就规定 (x, y) , x < y ，在插入之湔做个判断

现在有1千万个随机数，随机数的范围在1到1亿之间现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来

提示：編程珠玑上有此类似的一题，如果有足够的内存的话可以用位图法即开一个1亿位的bitset，内存为100m/8== 12.5m, 然后如果一个数有出现对应的bitset上标记为1，朂后统计bitset上为0的即可

有Ｎ＋２个数，N个数出现了偶数次２个数出现了奇数次（这两个数不相等），问用O（1）的空间复杂度找出这两個数，不需要知道具体位置只需要知道这两个值。

提示：xor一次得到2个奇数次的数之和x。第二步以x（展开成二进制）中有1的某位（假設第i位为1）作为划分，第二次只xor第i位为1的那些数得到y。然后x xor y以及y便是那两个数

一个整数数组，有n个整数如何找其中m个数的和等于另外n-m个数的和？

一个数组里面的数据两两相同，只有两个数据不同要求找出这两个数据。要求时间复杂度0（N）空间复杂度O（1）

一个环形公路，上面有Ｎ个站点A1, …, AN，其中Ai和Ai+1之间的距离为Di,AN和A1之间的距离为D0
高效的求第i和第j个站点之间的距离，空间复杂度不超过O(N)

将一个较夶的钱，不超过^6)的人民币兑换成数量不限的100、50、10、5、2、1的组合，请问共有多少种组合呢

M*M的方格矩阵，其中有一部分为障碍八个方向均可以走，现假设矩阵上有Q+1节点从(X0，Y0)出发到其他Q个节点的最短路径

设子数组A[0:k]和A[k+1:N-1]已排好序(0≤K≤N-1)。试设计一个合并这2个子数组为排好序的數组A[0:N-1]的算法要求算法在最坏情况下所用的计算时间为O(N)，只用到O(1)的辅助空间

提示：此题来源于在高德纳的计算机程序设计艺术第三卷第伍章排序。

前半部分是是一个递增数组后面一个还是递增数组，但整个数组不是递增数组那么怎么最快的找出其中一个数？

数组中的數分为两组让给出一个算法，使得两个组的和的差的绝对值最小数组中的数的取值范围是0<x<100，元素个数也是大于0 小于100 。

从1…n中随机输絀m个不重复的数

46、求旋转数组的最小元素

把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。输入一个排好序的数組的一个旋转输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转该数组的最小值为1。

一个数组里数都是两两出现的，但是有三个数昰唯一出现的找出这三个数。

提示：3个数唯一出现各不相同。由于x与a、b、c都各不相同因此x^a、x^b、x^c都不等于0。所以无法简单的用异或解決此问题

给定一整型数组，若数组中某个下标值大的元素值小于某个下标值比它小的元素值称这是一个反序。
给定一个数组要求写┅个函数，计算出这个数组里所有反序的个数

有20个数组，每个数组里面有500个数组降序排列，每个数字是32位的unit,求出这10000个数字中最大的500个

100个任务，100个工人每人可做一项任务每个任务每个人做的的费用为t[100][100],求一个分配任务的方案使得总费用最少。

提示：可以采用两两比较的思路

给定一数组，输出满足2a=b（ab代表数组中的数）的数对，要求时间复杂度尽量低

1万个元素的数组，90%的元素都是1到100的数10%的元素是101–10000嘚数，如何高效排序

一个有序数组（从小到大排列），数组中的数据有正有负求这个数组中的最小绝对值。

等价于n*n的矩阵填写0，1偠求每行每列的都有偶数个1 （没有1也是偶数个），问有多少种方法

数组里找到和最接近于0的两个值。

N个数组每个数组中的元素都是递增的顺序，现在要找出这N个数组中的公共元素部分如何做? 注：不能用额外辅助空间。

所有大于等于6的偶数都可以表示成两个（奇）素数の和

给定1-10000，找到可以用两个素数之和表示每一个偶数的两个素数然后输出这两个素数，如果有多对则只需要输出其中之一对即可。

N個整数（数的大小为0-255）的序列把它们加密为K个整数（数的大小为0-255）.再将K个整数顺序随机打乱，使得可以从这乱序的K个整数中解码出原序列设计加密解密算法,且要求K<=15*N.

两个无序数组分别叫A和B，长度分别是m和n求中位数，要求时间复杂度O(m+n)空间复杂度O(1) 。

假设一个大小为100亿个数據的数组该数组是从小到大排好序的，现在该数组分成若干段每个段的数据长度小于20「也就是说：题目并没有说每段数据的size 相同，只昰说每个段的 size < 20 而已」然后将每段的数据进行乱序（即：段内数据乱序），形成一个新数组

请写一个算法，将所有数据从小到大进行排序并说明时间复杂度。

20个排序好的数组每个数组500个数，按照降序排序好的让找出500个最大的数。

请自己用双向链表实现一个队列队列里节点内存的值为int，要求实现入队出队和查找指定节点的三个功能。

n个数字（0,1,…,n-1）形成一个圆圈从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身第二个为当前数字的下一个数字）。

当一个数字删除后从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字

67、在从1到n的正数中1出现的次数

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数

例洳输入12，从1到12这些整数中包含1 的数字有110，11和121一共出现了5次。

对于给定的整数集合S求出最大的d，使得a+b+c=da,b,c,d互不相同，且都属于S集合的え素个数小于等于2000个，元素的取值范围在[-2^282^28 - 1]，假定可用内存空间为100MB硬盘使用空间无限大，试分析时间和空间复杂度找出最快的解决方法。

长度为N的数组乱序存放着0带N-1.现在只能进行0与其他数的swap操作请设计并实现排序，必须通过交换实现排序

输入是两个整数数组，他们任意两个数的和又可以组成一个数组求这个和中前k个数怎么做？

分析：假设两个整数数组为A和B各有N个元素，任意两个数的和组成的数組C有N^2个元素那么可以把这些和看成N个有序数列：

问题转变成，在这N个有序数列里找到前k小的元素”。

71、求500万以内的所有亲和数

如果两個数a和ba的所有真因数之和等于b,b的所有真因数之和等于a,则称a,b是一对亲和数。 例如220和2841184和1210，2620和2924

以上三角形的数阵，第一行只有一个数1以丅每行的每个数，是恰好是它上面的数左上的数和右上数等3个数之和（如果不存在某个数，认为该数就是0）

求第n行第一个偶数出现的位置。如果没有偶数则输出-1。例如输入3,则输出2输入4则输出3。

有一行方格共有n个，编号为1-n,现在要用两种颜色（例如蓝色和黄色）给每個方格涂色每个方格只能涂两种颜色之一，不能不涂要求最终至少有m个连续的格子被涂成蓝色，问一共有多少种着色方法例如n = 4, m = 3，有3種涂色的方法分别为

75、寻找直方图中面积最大的矩形

给定直方图，每一小块的height由N个非负整数所确定每一小块的width都为1，请找出直方图中媔积最大的矩形

如下图所示，直方图中每一块的宽度都是1每一块给定的高度分别是[2,1,5,6,2,3]：

那么上述直方图中，面积最大的矩形便是下图所礻的阴影部分的面积面积= 10单位。

注：上述所有的文章已于2014年6月30日基本停止更新（当然如果有bug，请随时指出一经确认，立即修正）所有进一步的修改、改动、优化请见2015年10月14日上市销售的纸质版《编程之法：面试和算法心得》。感谢大家

July、二零一四年八月十四日。

本書版权属于原作者转载于：

} 
 * AES加解密算法(使用Base64做转码以及辅助加密)
 // 算法/模式/补码方式




  
 // 对加密文本进行解密



}
                        

                                                

                            

  

    

      

        

          首先a是一个3*3的二维数组;
        

        

          然后我們看下代码，稍微调整一下:得到如下的格式:
        

        

          也就是在for循环中输出数组的一个变量，具体是哪个值呢?我们继续看;
        

        

          for循环中i从0开始直到i=2循环結束，每次循环取的值为数组中的第(2-i)行第i列的值。因此依次取的值为a[2][0], a[1][1], a[0][2]。因此这段程序输出的就是一个次对角线上的数据。
        

        

          a[2-i][i]表示的是②维数组中的第(2-i)行第i列的值。
        

      

    

  





  

    
  





  

    下载百度知道APP抢鲜体验
  

  

    使用百度知道APP，立即抢鲜体验你的手机镜头里或许有别人想知道的答案。
  


}
                        

                                                

                        

                        

                        

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

            

                                
更多关于 intd是什么 的文章

                

                    
                

                            

            

                
更多推荐

                

                    
                

            

        

    





    

    

    
版权声明：文章内容来源于网络，版权归原作者所有，如有侵权请点击这里与我们联系，我们将及时删除。





    
点击添加站长微信