难度中等163
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
1
2
3
| 输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
|
提示：
可以通过递归的方式实现，类似于上台阶问题，一次上一步一次上两步，有多少种走法。
这题也可以分成类似的，一次选一个或者两个去翻译，但是要注意有智能走一步的情况，这就是两个连在一起不在10~25范围内的数字，这时只能走一步。
1
2
3
4
5
6
7
| class Solution {
public:
int translateNum(int num) {
if(num < 10) return 1;
return (num % 100 >= 10 && num % 100 <= 25) ? translateNum(num/100) + translateNum(num/10) : translateNum(num/10);
}
};
|
难度中等85
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
1
2
3
4
5
6
7
8
| 输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
|
提示：
0 < grid.length <= 2000 < grid[0].length <= 200
二维的动态规划，感觉算很简单的动态规划了(原因是我竟然做得出)。
先初始化dp的第一行第一列。
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int temp = 0;
for(int i = 0; i < n; ++i)
{
temp += grid[0][i];
dp[0][i] = temp;
}
temp = 0;
for(int i = 0; i < m; ++i)
{
temp += grid[i][0];
dp[i][0] = temp;
}
for(int i = 1; i < m; ++i)
{
for(int j = 1; j < n; ++j)
{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
};
|
难度中等133
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
1
2
3
| 输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例 2:
1
2
3
| 输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例 3:
1
2
3
4
| 输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
提示：
滑动窗口+双指针，用hash表记录加入窗口的字母对应的下标，用于滑动。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char, int> m;
int ret = 0, l = 0, r = 0;
while (r < s.size()) {
if (m.find(s[r]) != m.end()) {
l = max(l, m[s[r]] + 1);
}
m[s[r++]] = r;
ret = max(r - l, ret);
}
return ret;
}
};
|
难度中等92
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
1
2
3
| 输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
|
说明:
1 是丑数。n 不超过1690。
注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/
又是一个动态规划，数学推导问题。第一个丑数是1，第二个是2*1=2 ,第三个是3*1=3。可以看到可以由上一步得到，推出动态规划。dp[i] 表示第i+1个丑数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int nthUglyNumber(int n) {
int two = 0, three = 0, five = 0;
vector<int> dp(n, 0);
dp[0] = 1;
for(int i = 1; i < n; ++i)
{
int temp1 = dp[two] * 2, temp2 = dp[three] * 3, temp3 = dp[five] * 5;
dp[i] = min(temp1, min(temp2, temp3));
if(dp[i] == temp1) ++two;
if(dp[i] == temp2) ++three;
if(dp[i] == temp3) ++five;
}
return dp[n-1];
}
};
|
难度简单63
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
1
2
3
4
5
| s = "abaccdeff"
返回 "b"
s = ""
返回 " "
|
限制：
通过次数64,266
提交次数106,776
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
char firstUniqChar(string s) {
if(!s.size()) return ' ';
unordered_map<char, bool> c2flag;
for(int i = 0; i < s.size(); ++i)
{
if(!c2flag.count(s[i]))
{
c2flag[s[i]] = true;
}
else
{
c2flag[s[i]] = false;
}
}
char res = ' ';
for(int i = 0; i < s.size(); ++i)
{
if(c2flag[s[i]])
{
res = s[i];
break;
}
}
return res;
}
};
|
