剑指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' ';
    }
};