此系列博文记录自己的刷题过程，一些有意思或者精妙的解答将会被我整理成一篇博文

No.3 无重复字符的最长子串

给定一个字符串，找出不含有重复字符的最长子串的长度。

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

说明：在看到此题之后，菜鸡的我开始思考如何通过设置一临时字符指针对未重复数字进行复制求长，有了大致思路之后开始胡乱操作，写的代码涂涂改改愣是半天没有结果，我随手百度一手，看到了一个简洁与智慧并存的解决方案，让人五体投地，特来膜拜

算法来源：XDmonkey 的CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lengthOfLongestSubstring(char* s) {
    int i, idx = -1, max = 0;
    int p[256];
    memset(p, -1, sizeof(p));

    for (i = 0; s[i] != '\0'; i++) {
        if (p[s[i]] > idx)
            idx = p[s[i]];
        if (i - idx > max)
            max = i - idx;
        p[s[i]] = i;
    }

    return max;
}

说明：

  1. 其首先设置了一个 int 数组p，开辟256空间并初始为-1 ；idx 为辅助变量；max为最小子串的长
  2. 循环读入单个字符，判断字符是否出现重复，如果出现重复，也就是 p[s[i]] > idx ，就刷新 idx 值，也就是 i - idx 开始从0重新记录子串长度。不重复则在p数组对应的位置（字符对应ASCII码）更新为 i 的值，同时更新max的值

贴上提交后的分析图：

No.3
No.3

No.7 反转整数

给定一个 32 位有符号整数，将整数中的数字进行反转。

示例 1:

1
2
输入: 123
输出: 321

示例 2:

1
2
输入: -123
输出: -321

示例 3:

1
2
输入: 120
输出: 21

注意:

假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−\(2^{31}\), \(2^{31}\) − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

说明：此题作为一个简单题，重点就是后面的注意内容，作为一个菜鸡，我的代码是这样判断滴：

1
2
3
4
5
6
7
8
9
10
11
int reverse(int x) {
    int s = 0, i = 0;
    while (x){
        if (i == 9 && (s > 214748364 || s < -214748364))
            return 0;
        s = s * 10 + x % 10;
        x /= 10;
        i++;
    }
    return s;
}

也就是 if 部分，采用判断转换后的前九位与\(2^{31}\)的前九位进行比较，来判断是否return 0

提交后运行时间为20ms，之后我有幸看到了8ms的代码，如下：

1
2
3
4
5
6
7
8
9
10
11
int reverse(int x) {
    int y=0;
    while(x){
        int temp=y;
        y=y*10+x%10;
        if((y-x%10)/10!=temp)
            return 0;
        x/=10;    
    }
    return y;
}

嗯，很强，可不是嘛！如果转换后超出，y就会成一个奇怪的数，因此只需在每次y被赋值之后检验其对应位置是否还是x对应位置即可！！！学到了

贴上提交后的分析图：

No.7
No.7