剑指offer刷题13——动态规划(中等)

剑指 Offer 48. 最长不含重复字符的子字符串

难度 中等

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 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" 是一个子序列,不是子串。

思路与题解

这是一道典型的动态规划题目。对于一个数 num[i],我们有两种选择:

  1. 只翻译自己;
  2. 和前面的数字组合翻译,前提是组合的数在 10−25 之间。

用F[i]表示前 i 个数字的翻译方法数。根据以上两种选择,我们进行如下分析:

  • 如果只翻译自己,比如 12345,如果 5 单独翻译,那么方法数与 1234 是一样的, dp(i)=dp(i-1)。
  • 如果和前面的数字组合,比如 1235,如果 35 组合翻译,从两方面考虑: 35 看成一个整体,虽然加了 5 但是和没加是一样的,状态 dp(i)=dp(i-1); 35 组合就意味着不能再组合了,相当于条件 11 中的单独翻译自己,方法数与 12 是一样的。这时 dp(i)=dp(i-2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int translateNum(int num) {
int a = 1, b = 1, x, y = num % 10;
while(num != 0) {
num /= 10;
x = num % 10;
int tmp = 10 * x + y;
int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
b = a;
a = c;
y = x;
}
return a;

}
};

剑指 Offer 48. 最长不含重复字符的子字符串

难度 中等

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 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" 是一个子序列,不是子串。

思路与题解

PS:这题剑指里归类为了动态规划,不过感觉好像滑动窗口更适合这个题点,解出来的时间也更快,不过可能主要是因为测试样例的原因把。。。

  1. 用一个字符串str来存储从s[0]到s[i]中最长的字符串,初始化为空
  2. 遍历s,如果str中含有此时的s[i],删除从第一位到重复位的字符串
  3. 每个遍历过程中更新最大值max
  4. 返回最大值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int Max = 0,i,j,index;
string str;
for(i = 0;i < s.size();i++)
{
index = str.find(s[i],0);
if(index != -1) str.erase(0,index+1);
str+=s[i];
Max = max((int)str.length(), Max);
}
return Max;
}
};