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

迷南。 2023-03-02 04:54 18阅读 0赞

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

**难度** 中等

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

**示例1**

输入: "abcabcbb"
    输出: 3
    解释: 因为无重复字符的最长子串是"abc"，所以其长度为3。

**示例2**

输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是"b"，所以其长度为1。

**示例3**

输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是"wke"，所以其长度为3。
    请注意，你的答案必须是子串的长度，"pwke"是一个子序列，不是子串。

--------------------

**解法** 滑动窗口  
语言：C

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`，对其进行遍历，找出以每个字符最长无重复字符子串长度，再取这些长度的最大值，即为本题所求。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]  
那么，我们该如何找出以每个字符开头的最大子串呢？  
引入标记数组`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,4]
    解释: 输入数组表示数字123。

**示例2**

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

--------------------

**解法** 数学  
语言：C

/** * 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即可得到答案。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]: /images/20230208/884a8a7151f14c53badf8903222d9387.png