剑指offer五道题，C++实现，看看自己能不能解出来。
第一道（剑指offer46 把数字翻译成字符串）
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例：
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”
代码实现：
用得是动态规划的思想。
class Solution {
public:
int translateNum(int num) {
int a = 1;
int b = 1; //滚动变量
int c = 0;
string str = to_string(num);
if(num <= 9) return 1;
for(int i = 2; i <= str.size(); i++)
{
int tem = 10 * (str[i-2] - '0') + (str[i - 1] - '0');
if(tem>= 10 && tem <= 25)
{
c = a + b; //动态规划的关系式，c表示有多少种方案，等于除去最后一位的方案 加上 如果除去最后两位组成的数合理的方案
}
else
{
c = b;
}
a = b;
b = c; //迭代
}
return c;
}
};
第二道（剑指offer47 礼物的最大价值）
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
代码实现：方法一
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int n = grid.size();//行
int m = grid[0].size();//列
vector< vector<int> > dp(n, vector<int>(m)); // dp的含义：表示第i,j位的最大价值为多少
dp[0][0] = grid[0][0];
for(int i = 1; i < n ; i++) //求出动态规划的初始值 dp[i][0] dp[0][j]
{
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for(int j = 1; j < m; j++)
{
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; //关系式 从右边 从上边 看谁大谁加入dp中
}
}
return dp[n - 1][m - 1];
}
};
方法二
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int n = grid.size();//行
int m = grid[0].size();//列
int* dp = new int[m]; //空间复杂度优化成m 还可以优化成O(1)
dp[0] = grid[0][0];
for(int j = 1; j < m; j++)
{
dp[j] = dp[j - 1] + grid[0][j];
}
for(int i = 1; i < n; i++)
{
dp[0] = dp[0] + grid[i][0];
for(int j = 1; j < m; j++)
{
dp[j] = max(dp[j], dp[j - 1]) + grid[i][j];
}
}
return dp[m - 1];
}
};
第三题（剑指offer48 最长不含重复字符的子字符串）
题目描述：
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例：
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
代码实现：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s == "") return 0;
if (s.length() == 1) return 1;
unordered_map<char, int> position;
vector<int> dp(s.length(), 0);
int res = 0, count = 0;
for (int i = 0; i < s.length(); i++) {
if (i != 0 && position.find(s[i]) == position.end()) {
dp[i] = dp[i - 1] + 1;
}
else if (i == 0) {
dp[i] = 1;
}
else {
int j = position[s[i]];
if (i - j <= dp[i - 1]) {
dp[i] = i - j;
}
else {
dp[i] = dp[i - 1] + 1;
}
}
position[s[i]] = i;
res = max(res, dp[i]);
}
return res;
}
};
第四题（剑指offer49 丑数）
题目描述：
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例：
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
代码实现：
class Solution {
public:
int nthUglyNumber(int n) {
int a=1, b=1, c=1;
int* dp = new int[n + 1];
dp[1] = 1;
for(int i = 2; i <= n; i++)
{
dp[i] = min(min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
if(dp[i] == dp[a] * 2) a++;
if(dp[i] == dp[b] * 3) b++;
if(dp[i] == dp[c] * 5) c++;
}
return dp[n];
}
};
第五题剑指offer50 第一个只出现一次的字符
题目描述：
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例：
输入：s = “abaccdeff”
输出：‘b’
输入：s = “”
输出：’ ’
代码实现：
class Solution {
public:
char firstUniqChar(string s) {
if(s.size() == 0) return' ';
unordered_map<int, int> map;
for(auto ch : s)
{
map[ch]++;
}
for(auto ch : s)
{
if(map[ch] == 1) return ch;
}
return' ';
}
};
