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