(动态规划) 剑指 Offer 48. 最长不含重复字符的子字符串 ——【Leetcode每日一题】

这篇具有很好参考价值的文章主要介绍了(动态规划) 剑指 Offer 48. 最长不含重复字符的子字符串 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❓剑指 Offer 48. 最长不含重复字符的子字符串

难度:中等

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

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

示例 2:

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

示例 3:

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

提示

  • s.length <= 40000

注意:本题与 3. 无重复字符的最长子串 相同。

💡思路:动态规划

定义 dp 数组,dp[i] 代表以字符 s[i] 为结尾的 “最长不重复子字符串” 的长度。

固定右边界 i ,设字符 s[i] 左边距离最近的相同字符为 s[j] ,即 s[j] = s[i]

  • i < 0 ,即 s[i] 左边无相同字符,则 dp[i] = dp[i−1] + 1
  • dp[i−1] < i - j,说明字符 s[i] 在子字符串 dp[i−1] 区间之外 ,则 dp[i] = dp[i−1] + 1
  • dp[i−1] ≥ i - j ,说明字符 s[j] 在子字符串 dp[i−1] 区间之中 ,则 dp[i] 的左边界由 s[j] 决定,即 dp[i] = i − j

所以 状态转移方程 为:
d p [ i ] = { d p [ i − 1 ] + 1 , i < 0 d p [ i − 1 ] + 1 , d p [ i − 1 ] < i − j i − j , d p [ i − 1 ] ≥ i − j dp[i]=\begin{cases}dp[i-1]+1&,i<0\\dp[i-1]+1&,dp[i-1]<i-j\\i-j&,dp[i-1]\geq i-j\end{cases} dp[i]= dp[i1]+1dp[i1]+1ij,i<0,dp[i1]<ij,dp[i1]ij

观察发现 dp[i] 只与 dp[i - 1] 有关,所以只需定义一个变量 curLen 记录上一个长度。

使用哈希表统计:

  • 遍历字符串 s 时,使用哈希表(记为 preIndexs )统计 各字符最后一次出现的索引位置
  • 遍历到 s[i] 时,可通过访问哈希表 preIndexs[s[i]] 获取最近上一个的相同字符的索引 pre

🍁代码:(C++、Java)

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int curLen = 0;
        int maxLen = 0;
        map<char, int> preIndexs;
        for(int i = 0; i < s.size(); i++){
            int pre = preIndexs.find(s[i]) == preIndexs.end() ? -1 : preIndexs[s[i]]; // 获取当前字符的索引
            curLen = curLen < i - pre ? curLen + 1 : i - pre; // dp[i - 1] -> dp[i]
            maxLen = max(maxLen, curLen);
            preIndexs[s[i]] = i;
        }
        return maxLen;
    }
};

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int curLen = 0;
        int maxLen = 0;
        Map<Character, Integer> preIndexs = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            int pre = preIndexs.getOrDefault(s.charAt(i), -1); // 获取当前字符的索引
            curLen = curLen < i - pre ? curLen + 1 : i - pre; // dp[i - 1] -> dp[i]
            maxLen = Math.max(maxLen, curLen);
            preIndexs.put(s.charAt(i), i);
        }
        return maxLen;
    }
}
🚀 运行结果:

(动态规划) 剑指 Offer 48. 最长不含重复字符的子字符串 ——【Leetcode每日一题】,LeetCode,动态规划,leetcode,算法

🕔 复杂度分析:
  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为字符串 s 的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1),字符的 ASCII 码范围为 0 ~ 127 ,哈希表 preIndexs 最多使用 O ( 128 ) = O ( 1 ) O(128)=O(1) O(128)=O(1) 大小的额外空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-679679.html

注: 如有不足,欢迎指正!

到了这里,关于(动态规划) 剑指 Offer 48. 最长不含重复字符的子字符串 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剑指 offer 动态规划算法题:丑数

    题目描述 :我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。 分析:         枚举法, 从 1 开始判断遍历,判断是否丑数(只有 2, 3, 5 作为因子),若是丑数 n 自减,直到 n 等于 1,返回即可。         动态规划法,

    2024年02月16日
    浏览(43)
  • Java 动态规划 剑指 Offer 47. 礼物的最大价值

     代码展示:         进行动态规划的五个步骤:         1.状态表示                 dp[i][j]表示从起点到[i][j]这个位置上能获得礼物的最大价值         2.状态转移方程                 我们分析距离[i][j]最近的位置,根据题意我们到达[i][j]位置只能从[i-1][j]向下移动或

    2024年02月13日
    浏览(39)
  • 【leetcode刷题之路】剑指Offer(4)——分治+排序算法+动态规划

    8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/   前序遍历是根左右,中序遍历是左根右,这也就意味着前序遍历的第一个节点是整棵树的根节点,顺着这个节点找到它在中序遍历中的位置,即为in_root,那么in_root左边的都在左子

    2024年02月11日
    浏览(54)
  • 剑指offer(C++)-JZ47:礼物的最大价值(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 在一个mtimes nm×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向

    2024年02月05日
    浏览(62)
  • ( 动态规划) 674. 最长连续递增序列 / 718. 最长重复子数组——【Leetcode每日一题】

    难度:简单 给定一个未经排序的整数数组,找到最长且 连续递增的子序列 ,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l r) 确定,如果对于每个 l = i r ,都有 nums[i] nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

    2024年02月05日
    浏览(49)
  • LeetCode | C++ 动态规划——300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

    300题目链接 dp 数组定义 dp[i] 表示 i 之前包括 i 的以 nums[i]结尾 的最长递增子序列的长度 需要包含nums[i]结尾,不然在做递增比较的时候,就没有意义了。 递推公式 位置 i 的最长递增子序列 等于 j 从 0 到 i - 1各个位置的最长递增子序列 + 1 的 最大值 if (nums[i] nums[j]) dp[i] = ma

    2024年02月16日
    浏览(44)
  • 剑指offer(C++)-JZ63:买卖股票的最好时机(一)(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 假设你有一个数组prices,长度为n,其中prices[i]是股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益 1.你可以买入一次股票和卖出一

    2024年02月04日
    浏览(39)
  • (动态规划) 剑指 Offer 60. n个骰子的点数 ——【Leetcode每日一题】

    难度:中等 把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s 。输入 n ,打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 示例 1: 输入: 1 输出: [0.16667,0.16667,0.16667,

    2024年02月11日
    浏览(41)
  • (动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】

    难度:简单 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n) 。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 提示 : 1 = a r r . l e n g t h = 1 0 5 1 = arr.length = 10^

    2024年02月11日
    浏览(49)
  • (动态规划) 剑指 Offer 10- I. 斐波那契数列 ——【Leetcode每日一题】

    难度:简单 写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N) )。斐波那契数列的定义如下: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7(1000000007),如计

    2024年02月12日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包