美文网首页
LeetCode 数组专题 6:其它数组问题

LeetCode 数组专题 6:其它数组问题

作者: 李威威 | 来源:发表于2019-05-27 23:05 被阅读0次

例题1:LeetCode 第 3 题:无重复字符的最长子串

传送门:英文网址:3. Longest Substring Without Repeating Characters ,中文网址:3. 无重复字符的最长子串

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

示例 1:

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

示例 2:

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

示例 3:

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

思路1:使用滑动窗口、“双指针”。

步骤1:首先试一试“右指针”能不能向右边“扩散”,即尝试“扩散”的元素在已经扫过的元素中还没有出现(字母频率为 0),可以向右“扩散”,则频率加 1

步骤2:如果不能扩散,把“左指针”向右移动一格,相应的字母频率减 1。然后继续步骤1。

在以上两个步骤中,记录下最长不重复的子串的长度。

Python 代码:滑动窗口、“双指针”典型的写法,在理解的基础上记住它

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        # 特判
        size = len(s)
        if size < 2:
            return size

        l = 0
        r = -1

        counter = [0 for _ in range(256)]

        res = 1
        while l < size:
            if r + 1 < size and counter[ord(s[r + 1])] == 0:
                # 表示没有重复元素,r 可以加 1
                counter[ord(s[r + 1])] += 1
                r += 1
            else:
                # 有重复元素,左边就要减 1
                counter[ord(s[l])] -= 1
                l += 1
            res = max(res, r - l + 1)
        return res

Java 代码:

public class Solution4 {

    // 定义成频率数组,刘宇波老师给出的思路,使用滑动窗口的思路
    // 不是很好理解,可以供参考

    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len == 0 || len == 1) {
            return len;
        }
        int[] freq = new int[128];
        int res = 1;

        int l = 0;
        int r = -1;

        // 只要左边不越界
        while (l < len) {
            // r + 1 最多到 len-1 表示没有越界
            // freq[s.charAt(r + 1)] == 0 表示下一个字母还没有出现过
            // 【这个分类标准是很关键的,r+1 表示接下来要考察的索引位置,=0 表示在 [l,r] 这个区间里没有出现】
            // 【这个分类标准是很关键的,r+1 表示接下来要考察的索引位置,=0 表示在 [l,r] 这个区间里没有出现】
            // 【这个分类标准是很关键的,r+1 表示接下来要考察的索引位置,=0 表示在 [l,r] 这个区间里没有出现】
            if (r + 1 < len && freq[s.charAt(r + 1)] == 0) {
                // 右边第 1 个字母加入频率数组,频数 + 1
                freq[s.charAt(++r)]++;
            } else {
                // 如果下一个字符已经越界了,或者右边第 1 个字母是频率数组是曾经出现过的
                // 把左边从频数数组中挪掉,即频数减1
                freq[s.charAt(l++)]--;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution4 solution4 = new Solution4();
        String s = "abcabcbb";
        int lengthOfLongestSubstring = solution4.lengthOfLongestSubstring(s);
        System.out.println(lengthOfLongestSubstring);
    }
}

Python 代码:另一种写法,我觉得更直接一些,不过 while 里面还有 while ,看过去不太简洁

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        # 特判
        size = len(s)
        if size < 2:
            return size
        l = 0
        r = -1
        counter = [0 for _ in range(256)]

        res = 1
        while l < size:
            # 首先"右指针"不断向右边尝试,走到出现重复的最右边
            while r + 1 < size and counter[ord(s[r + 1])] == 0:
                # 表示没有重复元素,r 可以加 1
                counter[ord(s[r + 1])] += 1
                r += 1
            # 此时,记录不重复子串是"左指针"固定时候最长
            res = max(res, r - l + 1)
            # 考虑移动"左指针"
            # 此时 s[r+1] 就是已经扫过的区间里重复的元素,要把它剔除出去
            while r + 1 < size and s[l] != s[r + 1]:
                # 有重复元素,左边就要减 1
                counter[ord(s[l])] -= 1
                l += 1
            # 出了上一个循环以后,还要再把左指针向右移动一格,否则右指针不能向右移动
            counter[ord(s[l])] -= 1
            l += 1
        return res

思路2:隔板法

Python 代码:

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        # 特判
        l = len(s)
        if l < 2:
            return l
        # 隔板法
        # key:字符,val 出现的索引
        map = dict()
        point = 0
        res = 1
        for i in range(l):
            # 关键1:map[s[i]] >= point,等于是可以的
            if s[i] in map and map[s[i]] >= point:
                # 先把隔板向后移动一位
                point = map[s[i]] + 1
            # 然后记录最长不重复子串的长度
            res = max(res, i - point + 1)
            # 关键2:无论如何都更新位置
            map[s[i]] = i
        return res

思路3:还可以使用“动态规划”完成。

Python 代码:

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 特判
        l = len(s)
        if l < 2:
            return l
        # dp[i] 表示以 s[i] 结尾的最长不重复子串的长度
        # 因为自己肯定是不重复子串,所以初始值设置为 1
        dp = [1 for _ in range(l)]
        map = dict()
        map[s[0]] = 0
        for i in range(1, l):
            if s[i] in map:
                if i - map[s[i]] > dp[i - 1]:
                    dp[i] = dp[i - 1] + 1
                else:
                    dp[i] = i - map[s[i]]
            else:
                dp[i] = dp[i - 1] + 1
            # 设置字符与索引键值对
            map[s[i]] = i
        # 最后拉通看一遍最大值
        return max(dp)

参考资料:LeetCode 第 3 题:最长不重复字符串

(本节完)

相关文章

  • LeetCode 数组专题 6:其它数组问题

    例题1:LeetCode 第 3 题:无重复字符的最长子串 传送门:英文网址:3. Longest Substri...

  • leetcode

    leetcode leetcode to practice leetcode ac code 数组专题 done ...

  • LeetCode 专题:数组

    知识点总结 二分查找法(二分查找法是弱点)**以及相关的操作:递归实现和非递归实现,floor 和 ceiling...

  • LeetCode 专题:查找表

    LeetCode 专题:查找表 LeetCode 第 349 题:计算两个数组的交集 LeetCode 第 350...

  • 数据结构之数组与字符串

    最近在刷 LeetCode 的数据结构,在此记录一下,欢迎大家提供其它解法! 一、数组 1. 寻找数组中心索引 给...

  • First Missing Positive

    标签: C++ 算法 LeetCode 数组 每日算法——leetcode系列 问题 First Missing...

  • Next Permutation

    标签: C++ 算法 LeetCode 数组 每日算法——leetcode系列 问题 Next Permuta...

  • Trapping Rain Water

    标签: C++ 算法 LeetCode 数组 每日算法——leetcode系列 问题 Trapping Rain...

  • Combination Sum

    标签: C++ 算法 LeetCode 数组 DFS 每日算法——leetcode系列 问题 Combinat...

  • 求连续子数组的最大和

    leetcode 53题 解题思路:动态规划问题。给出数组array[ ],假定 f(i)代表array数组中以a...

网友评论

      本文标题:LeetCode 数组专题 6:其它数组问题

      本文链接:https://www.haomeiwen.com/subject/grottctx.html