实验室暑假学习第三周算法总结

2020-07-27

LeetCode 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"是一个子序列，不是子串。

解法 滑动窗口
语言：C 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLongestSubstring(char* s) {
    int i;
    int cnt = 0;
    int max = 0;
    int start = 0;                          /* 记录最长子串起点 */
    int flag[128] = {0};                    /* 标记数组 */
    for (i = 0; s[i] != '\0'; i++) {
        if (flag[s[i]] > start) {           /* 如果出现了重复字符 */
            cnt = i - start;                /* 记录当前子串的长度 */
            max = cnt > max ? cnt : max;    /* 刷新最长子串的长度 */
            start = flag[s[i]];             /* 重置起点 */
        }
        flag[s[i]] = i + 1;                 /* 刷新标记数组 */
    }
    cnt = i - start;                        /* 记录最后一子串的长度 */
    return cnt > max ? cnt : max;           /* 刷新最长子串的长度并返回结果 */
}

这道题采用滑动窗口的思想，大致思路如下图所示。对于给定的字符串s，对其进行遍历，找出以每个字符最长无重复字符子串长度，再取这些长度的最大值，即为本题所求。
在这里插入图片描述
那么，我们该如何找出以每个字符开头的最大子串呢？
引入标记数组flag，长度为128（因为ASCII码的十进制数范围为0-127），并将其所有元素初始化为0。初始化cnt变量为0，用于记录每个子串的长度。初始化max变量为0，每记录一个子串的长度，就刷新一次max，确保可以保留最长的子串长度。
遍历字符串s，找出以每个字符开头的最长无重复字符子串。首先判断子串中有没有出现重复字符，如果出现了重复字符，则必定有flag[s[i]] > start这一条件成立。如果没有出现重复字符，则刷新标记数组元素flag[s[i]] = i + 1；否则，记录当前子串的长度cnt = i - start，刷新max的值，并重置起点start为flag[s[i]]，最后刷新标记数组元素flag[s[i]] = i + 1。在遍历字符串的循环外，我们仍需记录最后一个子串的长度cnt并且刷新最长无重复字符子串长度max，再返回结果。
需要说明的一点是，当我们在遍历的过程中判断出子串中出现了重复字符时，寻找下一个字符开头的子串时并不需要再次从那个字符开始，而是可以从中断点处继续搜索，因为前面的那一部分子串必定不会包含重复元素。

LeetCode 66. 加一

难度 简单

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数0之外，这个整数不会以零开头。

示例1 

1
2
3
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字123。

示例2 

1
2
3
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字4321。

解法 数学
语言：C 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize) {
    for (int i = digitsSize - 1; i >= 0; i--) {
        if (digits[i] == 9) {
            digits[i] = 0;
        } else {
            digits[i]++;
            * returnSize = digitsSize;
            return digits;
        }
    }
    int* ret = (int*)malloc(sizeof(int) * (digitsSize + 1));
    memset(ret, 0, sizeof(int) * (digitsSize + 1));
    ret[0] = 1;
    * returnSize = digitsSize + 1;
    return ret;
}

这道题总体来说类似于数学的竖式计算，需要分情况来讨论。
最简单的情况就是不涉及进位操作，这样只需要把个位上的数字加1。稍微复杂一点，个位上的数字是9，这时候就要考虑到进位的情况，即让个位数字变为0，十位数字加1。同样地，如果十位数字也是9的话，进位操作就要将十位数字变为0，百位数字加1。百位、千位、万位……数字也是9的情况以此类推。最极端的情况，这个整数的所有位都是9，那么将其所有位的数字都置为0，再从前面添上1即可得到答案。