题目(n 个骰子点数之和)

把 n 个骰子仍在地上，所有骰子朝上一面的点数之和为 s。输入 n，打印出 s 的所有可能的值出现的概率。

算法思路

首先，剑指offer上的本题题解过于晦涩，作者未明确指出其实这道题是一题dp(动态规划)题。
首先，扔 n 个骰子的解可以由扔 n-1 骰子的解推出，即原问题包含了子问题的解(状态转移)；其次，对于如果使用递归的话，那么必定存在重复的子问题；因此，本题适用于动态规划的解法。
那么，首先构造状态转移方程：设扔 n 个骰子时排列数之和为 s 的函数为f(n,s)，那么如果先扔了 n-1 个骰子，则扔最后一个骰子就有 6 种情况(最后一个投出1、2、3、4、5、6)来得到排列数之和 s(前面的 6 种状态(解)可以推出当前状态(解))。即，f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6),n<=s<=6n。而当 s6n，则f(n,s)=0。初始状态位 n=1，f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。

算法实现(递归版)

递归版的实现只需要对 N 个骰子遍历每种可能的排列数即可。(自顶向上递归下去，自底向上回溯到顶得解)

算法实现(循环版)

循环版首先需要遍历每个骰子的情况，然后针对每个骰子的，再遍历其可能的排列数范围。(自底向上求出所有解)

参考

[1] <<剑指offer2>>

题目一(滑动窗口的最大值)

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

算法思路

最简单的思路，就是遍历数组，找到所有的滑动窗口，耗时 O(n)，同时计算滑动窗口内的最大值，O(k)，那么总共需要 O(nk) 的时间复杂度。另一种思路是，引入队列，将滑动窗口内的数值存入，如果能够在 O(1) 内计算出队列中的最大值，那么算法也是可行的。
最后的思路是：不将滑动窗口内的每个数值都存入队列，而是将可能成为滑动窗口最大值的数值存入。那么，就要删掉那些队列中不可能成为滑动窗口最大值的元素。主要分为两类：一是队列中已有的数字小于待存入的数字；二是，队列中的队头如果滑出了窗口，也需要删除。那么，最终我们的队头就保存了滑动窗口的最大值。由于涉及了两段的删除，那么需要用到双端队列。并且我们需要知道当前队头的下标，以便知道滑动窗口的位置，因此队列中的元素不是数值而是数值的下标。

算法实现

题目二(队列的最大值)

定义一个队列并实现函数 max 得到队列里的最大值，要求函数 max、push_back 和 pop_front 的时间复杂度都是O(1)。

算法思路

思路类似题目一。在队列内部，除了一个保存原始数据的双端队列 data 外，还需要一个保存队列中最大值的双端队列 maxiums。当执行 push_back 时，maxiums仅保存可能成为队列最大值的元素，仍然需要比较待添加元素和 maxiums 队列中已有元素的大小关系。执行 pop_front 时，需要注意如果当前出队的元素恰好是当前队列中的最大值时(所以元素必须有个 index 值)，两个队列都必须出队头。
执行 max函数时，只需要返回最大值队列的队头即可。

算法实现

复杂度分析

算法一仅线性遍历数组，时间复杂度为 O(n)；利用了常数大小的队列，空间复杂度为 O(1)。

参考

[1] <<剑指offer2>>
[2] 牛客网

题目一(翻转单词顺序列)

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串 “I am a student.”，则输出 “student. a am I”。

算法思路

下面介绍两种思路，分为翻转法和后追加法。
翻转法：显然，我们可以先对整个句子翻转，然后再对每个单词进行翻转就可得到所求。单词的边界就通过空格来判断即可。
后追加法：从输出结果，可以看出这么一个规律。前一个单词需要追加到后一个单词的后面。因此，我们可以遍历字符串，通过空格，找出每个单词(除了最后一个)，然后将空格和单词进行拼接后的结果再和之前的结果顺序拼接得到新的结果。最后，还剩下最后尾巴的部分尚未拼接，将其这部分拼接到当前结果的前面即可。这样子，遍历依次就完成了整个单词顺序翻转的过程，整个过程没有采用翻转，而关键在于单词拼接顺序的改变。

算法实现

翻转法

后追加法

题目二(左旋转字符串)

在题目一的基础上，如果定义字符串的左旋转操作是把字符串的若干个字符转移到字符串的尾部。那么请实现一个函数实现此功能。比如，输入字符串 “abcdefg” 和 2，该函数将返回左旋转两位得到的结果 “cdefgab”。

算法思路

本题最简单的思路就是直接将前若干个数字拼接到后面的子串的后方即可。但本题实际考察的是字符串翻转的使用。
那么通过例子，我们发现对整个字符串翻转之后，得到 “gfedcba”，如果再对前5个字符和后两个字符分别进行字符串翻转之后，那么结果显而易见。总之，借助三次字符串翻转便可达到目的。

算法实现

复杂度

算法的时间复杂度均为 O(n)，空间复杂度为 O(1)。

参考

[1] <<剑指offer2>>
[2] 牛客网1
[3] 牛客网2

题目一(和为 s 的两个数字)

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

算法思路

由于给定的数组是递增有序的，那么我们设置左右指针分别指向数组的首尾，然后从两端向中间夹逼。如果当前指针指向的两个数之和大于 S，那么说明右指针指向的数大了，应该后退一位；如果当前指针指向的两个数之和小于 S，那么说明左指针指向的数小了，应该前进一位。直到首次遇到两数之和恰好等于 S，即所求。 由于数组递增有序，那么首次遇到的两数之积必然最小。

算法实现

题目二

如果题目一去掉递增有序呢？

算法思路

那么题目一的思路便失效了。
我们取可能的一对数分析，我们发现对于这对数 a,b，用 S 减去 a 所得的数字 b 其实也在原数组中，那么当 S 减去 b 时又得到了 a，也就是当他们都被减的时候，a 一定会重复出现。而非所求的数字不会有此情况。那么我们可以利用哈希表，以原数组的值为键，以 S 与数组元素的差值为值，构造哈希表。如果新的差值是哈希表中的键，那么就可以确定这对数(哈希表中的键和值)是候选解，记录下来。最后从候选解中选出乘积最小的那对即可。

算法实现

题目三(和为 s 的连续正数序列)

输入一个正数 s，打印出所有和为 s 的连续正数序列(至少含有两个数)。例如，输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以打印出 3 个连续序列 1~5、4~6 和 7~8。

算法思路

题目意思就是从 1~s 的正数序列中，找到可能的连续序列，其和为 s。那么正数序列仍然可看成递增排序的，借鉴于题目一，我们仍然设置左右指针，左指针仍然指向第一个正数，右指针指向末位正数？我们发现，左指针的活动范围显然一定不会超过 (1+s)/2。那么其实最简单的思路是左指针每确定一个位置，右指针就移动到可能的位置进行判断，然后下一次左指针移动一位，右指针就后退到可能的位置进行判断，依次类推，直到左指针走到边界。那么这样必然需要重复计算两指针范围内的数之和。
其实，我们可以将右指针指向第二个正数，从最小的范围开始判断连续序列之和是否为 s，然后右指针不断前进，并随时统计连续序列之和。如果连续序列大于 s，并且左指针在合法范围内，那么连续序列之和先减去左指针指向的数字，然后左指针前进。如果此时情况满足，那么立即打印。否则右指针继续前进判断。

算法实现

复杂度

题目的时间复杂度为均为 O(n)复杂度，除了题目二的空间复杂度为O(n)，其他均为 O(1)。

参考

[1] <<剑指offer2>>
[2] 牛客网

题目一(数组中只出现一次的两个数字)

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

算法思路

题目限制了复杂度，因此常见的思路，如使用哈希表记录数字出现次数、或对每个数字遍历数组计算次数，都不可行。
那么，就要另寻思路。假设，题目变成，一个整形数组里除一个数字之外，其他数字都出现了两次。请找出这一个只出现一次的数字，那么如何求呢？我们想到了异或运算。因为0=a异或a，那么数组中出现两次的数字都会通过异或运算而抵消，所以最好仅留下一个数字，就是那个只出现一次的数字。

那么，回到本题。如果我们能够根据某种标准将数组划分为两个子数组，并且每个子数组中都含有唯一的一个只出现一次的数字，那么我们就可以利用上面的思路进行求解。当对原数组的所有元素进行异或运算后，得到一个结果数字，且由于这两个数字不同，因此异或得到的结果数字的二进制表示中至少有一位是 1，然后，我们找到结果数字中第一个为 1 的位置，记为第 n 位，再以第 n 位 是不是 1 为标准把原数组分成两个子数组。这样一来，数字相同的必然都分配到同一子数组中，因为，他们的二进制表示的每一位都是相同的。最后，对子数组分别进行异或运算就可以得到这两个所求的数字了。

算法实现

题目二(数组中唯一只出现一次的数字)

在一个数组中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

算法思路

现在题目是重复的数字出现了三次，那么异或运算就不行了，需要另寻它路。
如果仍然从位运算的角度考虑，可以发现：如果一个数字出现三次，那么它的二进制表示的每一位(0 或者 1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被 3 整除。如果每一位的和都能被 3 整除，那么那个只出现一次的数字的二进制表示中对应的那一位是0；否则就是 1 (不可能是 2，二进制位只有 0、1)。

算法实现

参考

[1] <<剑指offer2>>
[2] 牛客网