题目描述 对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。给定字符串A以及它的长度n，请返回最长回文子串的长度。 示例 输入 "abc1234321ab",12 返回值 7 解题思路 将大问题拆分成小问题，回文子串每每去掉头部和尾部，都会是一个回文子串，向卷心菜一样剥开还是一个小的卷心菜，所以我们要从回文子串最中心着手。 我们要做的就是遍历回文子串的“中心”，得到中心之后再向外扩散，直到最外层数值不相等。 因为回文子串的中心可能有 1 个，如 "aba"，也有可能是 2 个， 如 "abba"，所以我们每次遍历中心时都要计算这两种情况，取这两种情况中子串最长的那个数。 Ja...

题目描述 牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？ 示例 输入 [1,2,1] 返回值 2 说明 把第三个数字+2可以构成1，2，3 解题思路 使用贪心算法。遍历数组 arr[len] ，第 i 次区间为 [i, len]，若 arr[i] < arr[i-1]，那么区间所有数增加直到arr[i] = arr[i-1] + 1。不过本质就是数组第 i 个数需要比 i - 1 大 1，所以我们在 arr[i] < arr[i-1] 处直接求两个元素之间的差即可。 Java代码实现 public...

问题描述 给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。 示例 输入 "1AB2345CD","12345EF" 返回值 "2345" 解题思路 使用了正则表达式法和动态规划法，都自测通过，但是不知道为什么在这里都过不了；（2021/4/21补充：今天重新做这道题，发现可以通过了，果然是当时牛客系统有问题） 正则表达式方法，不多赘述； 典型的动态规划问题，解题思路与2021/1/21 藏宝图类似。系统传入两个字符串，所以我们首先可以考虑二维数组，再考虑滚动的一维数组； 我们可以设二维数组 dp[i][j] 的行表示原字符串的每一个字符，列表示...

题目描述 一个机器人在m×n大小的地图的左上角（起点）。机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？备注：m和n小于等于100,并保证计算结果在int范围内 示例1 输入 2,1 返回值 1 示例2 输入 2,2 返回值 2 解题思路 动态规划问题，将大任务拆分为小任务，每个小任务的目标与大任务一致，都是计算路径，只是规模缩小； 从小任务可知，每一格会被走到的次数 = 上面一格的次数 + 左边一格的次数。从左上到右下遍历数组即可； 因为只能往下或往右走，所以第一行和第一列只能为 1。 Java代码实现 public class Solu...

题目描述 给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。如果无解，请返回-1.【要求】时间复杂度O(n × aim)，空间复杂度On。 示例1 输入 [5,2,3],20 返回值 4 示例2 输入 [5,2,3],0 返回值 0 示例3 输入 [3,5],2 返回值 -1 解题思路 典型的动态规划问题，如果输入值为一个以上，可以考虑使用二维数组。输入值为面值数组 arr 和找零数 aim，所以我们可以创建一个二维数组 dp[m][n]，纵轴 m 表示所有面值，横轴 n 表...

题目描述 牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。 输入描述 每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10 的不包含空格的可见 ASCII 字符串。 输出描述 输出一行 “Yes” 或者 “No” 表示结果。 示例 输入 x.nowcoder.com ooo 输出 Yes 解题思路 方案一：使用...

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

题目描述 假设你有一个数组，其中第 i 个元素是股票在第 i 天的价格。你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。 示例1 输入 [1,4,2] 返回值 3 示例2 输入 [2,4,1] 返回值 2 解题思路 可知买入操作必定在卖出操作之前，数组可以一直往后推，不需要再回头； 本质是找最小值和最大值，可以使用暴力解法。 因为买入操作在卖出操作之前，前面的值无论如何都要比后来的值小才可以进行计算，所以可以忽略前大后小的情况，可以使用贪心算法，记录最小值以及 当前最小值后面的 最大值。 Java代码实现 // 暴力解法求最大差 publ...

题目描述 给定一个数组arr，返回子数组的最大累加和例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.题目保证没有全为负数的数据[要求]时间复杂度为O(n)，空间复杂度为O(1) 示例 输入 [1, -2, 3, 5, -2, 6, -1] 输出 12 解题思路 将问题拆解为最小问题，拿最上面的示例举例，假若数组只有 [1, -2]，当遍历到 -2 时，子数组和为 -1 ，最大和可以一眼看出是 1。假若数组增加一个元素 3，即 [1, -2, 3]，根据上面已得出的 [1, -2] 子数组和为 -...