馒头2020

分类

学习笔记(3) 文章(4) 题解(65)

/ 注册

TA的专栏 4篇文章 0人订阅

Program魔法国与馒头小铺

1篇文章 319人学习

【入门级】初探动态规划

3篇文章 774人学习

全部文章（共71篇）

2021/1/26 最长回文子串

题目描述对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。给定字符串A以及它的长度n，请返回最长回文子串的长度。示例输入 "abc1234321ab",12 返回值 7 解题思路将大问题拆分成小问题，回文子串每每去掉头部和尾部，都会是一个回文子串，向卷心菜一样剥开还是一个小的...

2021-01-26

0 797

2021/1/26 递增数组

题目描述牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？示例输入 [1,2,1] 返回值 2 说明把第三个数字+2可以构成1，2，3 解题思路使用贪心算法。遍历数组 arr[len] ，第 i 次区间为 [...

2021-01-26

0 829

2021/1/25 最长公共子串

问题描述给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。示例输入 "1AB2345CD","12345EF" 返回值 "2345" 解题思路使用了正则表达式法和动态规划法，都自测通过，但是不知道为什么在这里都过不了；（2021/4/21补充：今...

Java 动态规划题解算法

2021-01-25

0 606

2021/1/25 求路径

题目描述一个机器人在m×n大小的地图的左上角（起点）。机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？备注：m和n小于等于100,并保证计算结果在int范围内示例1 输入 2,1 返回值 1 示例2 输入 2,2 返回值 2 解题思路动态规划...

2021-01-25

0 745

2021/1/22 换钱最少的货币数

题目描述给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。如果无解，请返回-1.【要求】时间复杂度O(n × aim)，空间复杂度On。示例1 输入 [5,2,3],20 返回值...

2021-01-22

2 903

2021/1/21 藏宝图

题目描述牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ...

2021-01-21

0 747

2021/1/21 股票(无限次交易)

题目描述假定你知道某只股票每一天价格的变动。你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。解题思路其实只要把每一天和前一天的股价相减，为正整数则统计即可。 Java代码实现 public int maxProfit (i...

2021-01-21

1 764

2021/1/20 买卖股票的最好时机

题目描述假设你有一个数组，其中第 i 个元素是股票在第 i 天的价格。你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。示例1 输入 [1,4,2] 返回值 3 示例2 输入 [2,4,1] 返回值 2 解题思路可知买入操作必定在卖出操作之前...

2021-01-20

0 428

2021/1/19 子数组的最大累加和

题目描述给定一个数组arr，返回子数组的最大累加和例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.题目保证没有全为负数的数据[要求]时间复杂度为O(n)，空间复杂度为O(1) 示例输入 [1, -2...

2021-01-19

0 460

2021/1/18 斐波那契数列

1 解题思路声明定义一个由-1填充的数组arr，在索引为n的地方存储f(n)，-1表示尚未存储数据；若n = 0或1，直接返回n本身；若不满足2，判断arr[n]若不是-1，说明已经存储过f(n)，不需要再进行计算，直接返回arr[n]；若不满足3，进行计算f(n) = f(n - 1) ...

2021-01-18

0 508