题目(丑数)

把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。 习惯上我们把 1当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。

算法思路一

逐个判断数是不是丑数，如果是丑数就计数，直到达到第 N 个丑数。而丑数是只含质因子 2，3，5的数。

算法思路二

算法实现二基于用前一个丑数求解下一个丑数的思想。即，对于一个有序的丑数数组，后面的丑数一定是前面的某个丑数乘以 2、3 或 5 的结果。
那么如何保证丑数数组有序呢？假设对于丑数 a，b，c(a,b,c 可相同)，下一个丑数可能为 2a、3b 或 5c 三种之一，那么我们就选取这三个数的最小丑数存入数组中，但是为了要继续更新下一个可能的丑数，我们必须记录这三种丑数对应的前一个丑数的位置(ps:每一种就是用前一个丑数乘以相应的质因子得到下一个丑数)，所以在我们将最小的那种丑数存入丑数数组时，还需要对那种丑数对应的指示器执行加 1 操作，即更新当前这种丑数的位置，以便继续求解下一个丑数。

算法实现一

算法实现二(优化版)

复杂度

算法思路一，尽管空间复杂度小，但由于需要对每个数判断丑数，因此浪费了很多时间再非丑数的判别上；而算法思路二，虽然额外建立了一个动态数组，但是它不需要对每个数判别丑数，大大提高了时间效率，也就是以空间换时间的解法。

参考

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

题目(最长不含重复字符的子字符串)

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含 ‘a’-‘z’的字符。例如，在字符串 “arabcacfr” 中，最长的不含重复字符的子字符串是 “acfr”，长度为 4。

算法思路

主要采用动态规划的思想。先自顶向下分析问题，首先定义函数 f(i) 表示以第 i 个字符为结尾的不包含重复字符的子字符串的最长长度。那么从左往右扫描字符，在求 f(i) 时，我们可以从已知的 f(i-1) 推得 f(i) 的大小。 那么下面分两种情况进行讨论：

1. 如果第 i 个字符之前未出现过，那么 f(i)=f(i-1)+1，也就是直接算进以第 i 个字符为结尾的不包含重复字符的子字符串中。
2. 如果第 i 个字符之前已出现过，那么又需要分两种情况：先设第 i 个字符和它上次出现在字符串中的位置距离为 d。
   a)、当距离 d 小于等于 f(i-1)时，即第 i 个字符出现在了 f(i-1) 对应的最长字符串之中了，那么 f(i)=d,那么 f(i) 对应的最长字符串长度一定不会超过 f(i) 对应的最长字符串长度；
   b)、若这个距离 d 大于了 f(i-1) ，意味着第 i 位置上的字符出现在了 f(i-1) 对应的最长字符串的前面，则第 i 位置上的字符可以加入当前最长的字符串中，所以，f(i)=f(i-1)+1。

算法实现

算法自底向上逐步求解问题

复杂度

算法仅遍历一次字符串，因此时间复杂度为 O(n)；定义了长度为 26 的数组，空间复杂度也为 O(26)。

参考

[1] <<剑指offer2>>

题目(礼物的最大价值或年终奖)

小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个 6*6 的棋盘上进行，上面放着 36 个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。

给定一个 6*6 的矩阵board，其中每个元素为对应格子的礼物价值,左上角为 [0,0],请返回能获得的最大价值，保证每个礼物价值大于 100 小于 1000。

注：剑指 offer 上的题目和牛客网上的题目有点小区别，仅在棋盘大小的区别，我们以牛客网的为准。

算法思路一

本题是经典的类似走迷宫，求最优解的问题，采用的方法是填表法，还有另一种叫刷表法，感兴趣可以了解一下。

这是经典的动态规划之填表法的应用。我们先定义函数 f(i,j) 表示到达坐标为 (i,j) 的位置时小东能拿到的最大礼物价值总和。根据题目要求，我们有两种可能的路径到达坐标 (i,j) 的位置：通过位置 (i-1,j) 或者 (i,j-1),所以可得到等式 f(i,j)=max(f(i-1,j),f(i,j-1))+board[i][j],其中 board[i][j] 为当前位置上的礼物价值。

但是，这里要特殊处理的是，除了第一个位置，第一行和第一列的每个位置只有一种到达路径，所以我们先对第一行和第一列进行填表。

其实本题，由于输入数组是由题目给定的，因此，我们不改动输入数组,否则我们可以给输入数组的第一行和第一列之前全补0，那么就把所有情况统一了，意味着不需要上述的特殊处理了，请注意此处的补 0 技巧。

填表法：所谓的填表法就是我们每达到表中的一个位置，就确定下该位置的最优解，然后走遍整个表，即填完整张表。

算法实现二

由于到达坐标为 (i,j) 的位置时，能够拿到的礼物的最大价值只依赖坐标为 (i-1,j)和 (i,j-1) 的两个位置，因此此第 i-2 行及更上面的所有位置上的礼物的最大价值实际上没有必要存储下来。我们用一维数组来记录足以。

算法实现一

算法实现二(优化版)

复杂度

算法一的时间复杂度和空间复杂度均为O(n^2)，优化后的算法，时间复杂度降为 O(n)。

参考

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

题目(把数字翻译成字符串)

给定一个数字，我们按照如下的规则把它翻译为字符串：将 0-25 分别对应翻译到 a-z 字符，如 0 翻译成 a，以此类推。一个数字可能有多少种翻译。例如，12258 有 5 种不同的翻译,分别是 “bccfi”、”bwfi”、”bczi”、”mcfi”、”mzi”。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

算法思路

以 12258 为例，显然，从 1 开始翻译的种数包括了从第二个 2 开始翻译的种数，以及从第三个 2 开始翻译的总数，但是后者是有条件的，如果此例子中的 12 所在的位置是其他两位不在 10-25 之间的数字，那么此种情况无法翻译，那么该翻译方式就不统计了。显然，对于从 1 开始翻译，包含了两个递归子问题。那么对子问题的分析以此类推。这其实就是自顶向上分析问题。
那么既然是递归有无重叠子问题呢？从上述例子中，如果先翻译 1，再翻译 2，最后要翻译 258；如果先翻译 12，最后还是要翻译 258，这里就出现了重叠的子问题。

那么为了避免重叠子问题的计算，我们可以采用自底向上的计算方式，从后面开始翻译，因为从前面开始翻译的翻译总数可以由从后面开始翻译的翻译总数得到。

那么动态转移方程就是：
f(i)=f(i+1)+g(i,i+1)*f(i+2); g(i,i+1) 表示 i 和 i+1 位置上拼接的数字是否在 10-25 之内，因此其取值为 0 或者 1。

本题其实也是动态规划的一种，类似动态规划经典题青蛙跳台阶。

算法实现

复杂度

算法仅遍历一次输入数字对应的字符串，因此时间复杂度为 O(n)；定义了记录翻译总数的数组，空间复杂度也为 O(n)。

参考

[1] <<剑指offer2>>

题目(把数组排成最小的数)

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组 {3，32，321}，则打印出这三个数字能排成的最小数字为 321323。

算法思路

最简单的思路是对数组进行全排列，然后判断出最小的一个即可，但是这样的时间复杂度为 O(n!)，显然不能这么做。

本题其实只要找到数组的正确排序，即可按照数组顺序自然拼接每个数字。但是，要注意的是对于数字的拼接，我们需要考虑到整数的表示范围问题，因此，为了避免出现大数问题，我们需要将数字转为字符串然后进行拼接。那么既然是排序，我们只需确定一个排序规则即可。
对于给定的两个整数 m ，n，谁在前谁在后呢？那么只要 mn 组成的字符串小于 nm 组成的字符串，那么我们就让 m 在前，n 在后，反之也成立。

算法实现

复杂度分析

本题其实使用的是 c++ STL 中的 sort函数，所以时间复杂度为 O(nlogn)。

参考

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