已注销

题解

排序(2)

/ 注册

全部文章 / 题解（共6篇）

剑指offer：85-42-题解 | #连续子数组的最大和（一）(二)#

题目描述：连续子数组的最大和（二）输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。 1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组 2.如果存在多个最大和的连续...

C++ 动态规划数组

2022-02-14

0 396

剑指offer：71-题解 | #跳台阶扩展问题#

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。题解1：动态规划当n = 1， f(1) = 1 = 2^0; 当n = 2， f(2) = 2 = 2^1; 当n = 3， f(3) = 4 =2^2...

C++ 动态规划

2022-02-11

0 419

剑指offer：70-题解 | #矩形覆盖#

题目描述可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2 * 1 的小矩形无重叠地覆盖一个 2 * n 的大矩形，从同一个方向看总共有多少种不同的方法？数据范围：0≤n≤38 进阶：空间复杂度O(1) ，时间复杂度O(n) 注意：约定 n == 0 时，输出 ...

C++ 动态规划

2022-02-11

0 402

剑指offer：69-题解 | #跳台阶#

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。数据范围：1≤n≤40 要求：时间复杂度：O(n)O(n) ，空间复杂度： O(1)O(1) 题解思路：该题是典型的斐波那契数列当n = 1时候，f(1...

C++ 动态规划

2022-02-11

0 335

剑指offer:48-题解 | #最长不含重复字符的子字符串#

题目描述请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。数据范围:s.length≤40000 题解:动态规划哈希表统计：遍历字符串 s 时，使用哈希表（记为 dic ）统计各字符最后一次出现的索引位置。左边界 i 获取方式：遍历到 s[j]时，可通过...

C++ 动态规划

2022-02-09

0 487

题解 | #连续子数组的最大和#

描述输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。数据范围: 要求:时间复杂度为 O(n)O(n)，空间复杂度为 O(n)O(n) 进阶:时间复杂度为 O(n)O(n)，空间复杂度为 O(1)O(1) 题解1：规律分析输入： [1...

C++ 动态规划

2022-02-08

0 346