【算法刷题】Day28

这篇具有很好参考价值的文章主要介绍了【算法刷题】Day28。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 买卖股票的最佳时机 III

【算法刷题】Day28,算法刷题,算法,java
原题链接


题干:

第 i 个元素是一支给定的股票在第 i 天的价格
最多可以完成 两笔 交易
注意:你不能同时参与多笔交易
【算法刷题】Day28,算法刷题,算法,java


算法原理:

1. 状态表示:

【算法刷题】Day28,算法刷题,算法,java
dp[i] 表示:第 i 天结束之后,所能获得的最大利润

f[i][j] 表示:第 i 天结束之后,完成了 j 次交易,此时处于“买入”状态下的,最大利润
g[i][j] 表示:第 i 天结束之后,完成了 j 次交易,此时处于“卖出”状态下的,最大利润

2. 状态转移方程

【算法刷题】Day28,算法刷题,算法,java
f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i])

g[i][j] = g[i - 1][j]
if(j - 1 >= 0) {
g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
}

3. 初始化

【算法刷题】Day28,算法刷题,算法,java
【算法刷题】Day28,算法刷题,算法,java

4. 填表顺序

从上往下填写每一行
每一行从左往右,两个表一起填

5. 返回值

g 表的最后一行里面的最大值


代码:

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int INF = 0x3f3f3f3f;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];

        for(int j = 0; j < 3; j++) {
            f[0][j] = g[0][j] = -INF;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++) {
            for(int j = 0; j < 3; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int ret = 0;
        for(int j = 0; j < 3; j++) {
            ret = Math.max(ret, g[n - 1][j]);
        }
        return ret;
    }
}

【算法刷题】Day28,算法刷题,算法,java


2. Z 字形变换

【算法刷题】Day28,算法刷题,算法,java
原题链接


题干:

字符串 s,给定的行数 numRows
从上往下、从左到右进行 Z 字形排列
输出需要从左往右逐行读取
【算法刷题】Day28,算法刷题,算法,java


算法原理:

1. 模拟

【算法刷题】Day28,算法刷题,算法,java

2. 找规律

【算法刷题】Day28,算法刷题,算法,java
第一行:0 到 0+d 到 0+2d…0+kd

第 k 行:(k, d-k) 到 (k+d, d-k+d) 到 (k+2d, d-k+2d)

第 n-1 行:n-1 到 n-1+d 到 n-1+2d…n-1+kd

当 n = 1 的时候特殊处理


代码:

class Solution {
    public String convert(String s, int numRows) {
        // 处理一下边界情况
        if(numRows == 1) {
            return s;
        }

        int d = 2 * numRows - 2;
        int n = s.length();
        StringBuilder ret = new StringBuilder();

        //1. 处理第一行
        for(int i = 0; i < n; i += d) {
            ret.append(s.charAt(i));
        }

        //2. 处理中间行
        for(int k = 1; k < numRows - 1; k++) {// 依次枚举中间行
            for(int i = k, j = d - i; i < n || j < n; j += d, i += d) {
                if(i < n) {
                   ret.append(s.charAt(i));
                }
                if(j < n) {
                   ret.append(s.charAt(j));
                }
            }
        }

        //3. 处理最后一行
        for(int i = numRows - 1; i < n; i += d) {
            ret.append(s.charAt(i));
        }

        return ret.toString();
    }
}

【算法刷题】Day28,算法刷题,算法,java文章来源地址https://www.toymoban.com/news/detail-786763.html

到了这里,关于【算法刷题】Day28的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法刷题day34:并查集

    今天写的题集是并查集,其实感觉有两个难点,一个是,要维护多余的信息和路径压缩,另一个难点则是抽象出来合并集合的这个操作,还是要不断地练习,看别人怎么去做,加油! 标签:并查集 思路: 模板题,没啥说的 题目描述: 示例代码: 标签:并查集 思路: 其实

    2024年03月21日
    浏览(64)
  • 【算法日志】贪心算法刷题:重叠区问题(day31)

    目录 前言 无重叠区间(筛选区间) 划分字母区间(切割区间)  合并区间 今日的重点是掌握重叠区问题。

    2024年02月12日
    浏览(47)
  • 力扣算法刷题Day59|单调栈

    力扣题目:# 503.下一个更大元素II  刷题时长:参考题解后2min 解题方法:单调栈 复杂度分析 时间O(n) 空间O(n) 问题总结 如何解决环的问题 本题收获 循环数组解决方案 思路一:将两个nums数组拼接在一起,使用单调栈计算出每一个元素的下一个最大值,最后再把结果集即res

    2024年02月13日
    浏览(83)
  • 算法刷题Day 60 柱状图中的最大矩阵

    暴力解法 超时了 分别找出当前位置左边 第一个 比自己小的索引(的后一个位置)和右边 第一个 比自己小的索引(的前一个位置),这个范围之内,就是以当前位置的高度所能达到的最大宽度。 单调栈 有了接雨水那道题的经验,这一道题可以模仿着做出了

    2024年02月14日
    浏览(55)
  • 算法刷题Day1 二分查找+移除元素

    代码随想录-数组-1.数组理论基础 数组是存放在 连续内存空间 上的 相同类型 数据的 集合 优点:常数时间复杂度访问元素 缺点: 在删除或者增添元素的时候,就难免要移动其他元素的地址 ,时间复杂度为O(n) 代码随想录-数组-2.二分查找 前提条件 二分查找前提条件: 数组

    2024年02月10日
    浏览(54)
  • 算法刷题Day 39 不同路径+不同路径II

    递归(深搜) 使用递归的方法超时(可以过37个case) 来分析一下时间复杂度,这个深搜的算法,其实就是要遍历整个二叉树。 这棵树的深度其实就是m+n-1(深度按从1开始计算)。 那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树(其实没

    2024年02月12日
    浏览(45)
  • 算法刷题营【Day1】:: 704.二分查找:二分法详谈与相关刷题

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:704. 二分查找 2. 题解参考(模板写法) - - 2.1 方法一:左闭右闭写法 - - 2.2 方法二:左闭右开写法 3. 模板解释:左闭右闭 - - 3.1 区间划定 - - 3.2 left 、right 移动问题 - - 3.3 循环条件

    2024年02月04日
    浏览(45)
  • 【算法日志】动态规划刷题:01背包问题,多重背包问题(day37,day38)

    目录 前言 目标和(01背包) 一和零(01背包) 零钱兑换(多重背包) 排列总和(多重背包) 这两天都是背包问题,其中的01背包的一些应用问题需要一定的数学建模能力,需要i将实际问题简化成我们熟悉的背包问题;而这两天的多重背包问题还算比较基础,但也要我明白了

    2024年02月11日
    浏览(56)
  • 算法刷题Day 30 重新安排行程+N皇后+解数独

    想了很久,最后还是放弃了 这道题目有几个难点: 一个行程中,如果航班处理不好容易变成一个圈,成为死循环 有多种解法,字母序靠前排在前面,让很多同学望而退步,如何该记录映射关系呢 ? 使用回溯法(也可以说深搜) 的话,那么终止条件是什么呢? 搜索的过程中

    2024年02月12日
    浏览(75)
  • 算法刷题Day 31 分发饼干+摆动序列+最大子序列和

    分发饼干其实有很多种写法,但是下面这种贪心的解法是最好理解,也最好解释的 我的其他解法 贪心算法 这道题用贪心算法要考虑的细节有很多。 动态规划 有点难(甚至涉及到了线段树),等后面二刷的时候再来学好了 暴力解法 超时了 贪心算法 贪心算法的代码写起来简

    2024年02月15日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包