colie

题解

未归档(29)

/ 注册

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

题解 | #丑数#

【剑指offer】丑数（python）我们只用比较3个数：用于乘2的最小的数、用于乘3的最小的数，用于乘5的最小的。 # -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): ...

动态规划

2021-04-14

0 496

题解 | #年终奖#

【剑指offer】礼物的最大价值（python）使用动态规划求解，DFS过于复杂，不是最优解。每次都求到达相邻的两个列中的最大值。 # -*- coding:utf-8 -*- class Bonus: def getMost(self, board): # write ...

动态规划

2021-04-14

0 657

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

【剑指offer】连续子数组的最大和（python） python初始化整数的最大值和最小值这是聪明法，这个sum的设置，想不到 # -*- coding:utf-8 -*- import sys class Solution: def FindGreatestSumOfSubArr...

动态规划分治

2021-04-14

0 431

题解 | #跳台阶扩展问题#

【剑指offer】变态跳台阶（python）动态规划，跳上n阶台阶可以从n-1跳1，也可以从n-2跳2，。。。f(n)=f(n-1)+f(n-2)+...+f(0)其实就是算了一个等比数列。 # -*- coding:utf-8 -*- class Solution: def jumpFl...

动态规划

2021-04-14

0 482

题解 | #矩形覆盖#

【剑指offer】矩形覆盖（python）覆盖n为1时，只有一种覆盖方法。覆盖n为2时，有两种覆盖方法。要覆盖2xn的大矩形，可以先覆盖2x1的矩形，再覆盖2x(n-1)的矩形；或者先覆盖2x(n-2)的矩形。而覆盖2x(n-1)的矩形和2x(n-2)的矩形可以看成子问题。递推公式就有了。 # -...

动态规划

2021-04-14

0 477

题解 | #斐波那契数列#

【剑指offer】裴波那契数列（Python）动态规划是“自下而上”求解，从最基础的base解到最终解。这里基础解就是第0项和第1项，第2项=第0项+第1项，从第2项开始往上。时间复杂度：O（n）空间复杂度：O（1） # -*- coding:utf-8 -*- class Solution: ...

动态规划

2021-04-14

0 484

题解 | #剪绳子#

【剑指offer】剪绳子（Python） 1. 聪明解法绳子拆成 1 和 n-1， 1*(n-1) - n = -1 < 0，乘积变小，所以不能出现长度为 1 的绳子绳子拆成 2 和 n-2， 2*(n-2) - n = n-4 >= 0(n>=4)，当n&g...

动态规划

2021-04-14

0 593