IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【剑指offer】股票的最大利润+最长不含重复字符的子字符串 -> 正文阅读

[数据结构与算法]【剑指offer】股票的最大利润+最长不含重复字符的子字符串

🔥题目

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

输入:[7, 1, 5, 3, 6, 4]
输出:5
解释:第2天买,第5天卖,获得最大利润 6 - 1 = 5

??解析

一共两个状态【不持股】【持股】
dp[i][0]的含义是 第i天不持股的最大资金
dp[i][1]的含义是 第i天持股的最大资金

戳这里:《【图解算法】经典而规整的动态规划——买卖股票的最佳时机》

🧊代码

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        return dp[len - 1][0];
    }
}

?
?
?
?
?

🔥题目

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

??解析

滑动指针的核心为:以右指针为驱动,拖着左指针向前走——右指针主动移动,探索新的区域;左指针被迫跟进,负责保证区间符合题意。

对于本题,可以使用哈希集合(HashSet)或哈希表(HashMap)来统计滑动窗口内的信息。

戳这里:《【图解算法】模板的优化与进阶——滑动窗口专题》

🧊代码

使用哈希集合:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        Set<Character> set = new HashSet<>();
        int L = 0, R = 0;
        int res = 0;
        while (R < len) {
            char c = s.charAt(R);
            while (set.contains(c)) {
                set.remove(s.charAt(L));
                L++;
            }
            set.add(c);
            res = Math.max(res, R - L + 1);
            R++;
        }
        return res;
    }
}

使用哈希表:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        Map<Character, Integer> map = new HashMap<>();
        int L = 0, R = 0;
        int res = 0;
        while (R < len) {
            char c = s.charAt(R);
            if (map.containsKey(c)) {
                L = Math.max(L, map.get(c) + 1);
            }
            map.put(c, R);
            res = Math.max(res, R - L + 1);
            R++;
        }
        return res;
    }
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-09 10:28:44  更:2021-08-09 10:29:08 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 18:54:50-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码