牛客826462999号

题解

/ 注册

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

题解 | #最长上升子序列(一)#

采用动态规划的方式求解求解最长上升子列的问题，可以转化为求解输入的序列num中，分别以每一个元素作为结尾的序列的最长子列的问题。第i个元素的子列最长长度，等于满足nums[j] < nums[i]的子列的最长长度+1。具体求解步骤如下：取列表dp，长度等于输入的序列长度n。dp[i]...

Python3

2022-05-02

0 402

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

求解连续子数组的最大和，问题可以分解为如下步骤：数组长度为0，返回0 数组长度为1，返回数组第一个值数组长度大于1，从前往后，判断数组（第i个值+第i-1个值）于（第i个值）的大小，将其中较大值赋值给当前数组的第i个值。即计算数组从第一个值，到第i个值的最大子数组。 def max_sum...

Python3

2022-04-26

0 380

题解 | #三角形最小路径和#

利用一个数组dp来存储当前层的上一层元素，然后从前往后修改dp数组中的元素。 dp[j] = triangle[i][j] + min(dp[j],dp[j+1])，其中j表示当前层的第j个元素的下标。通过从后往前遍历每一层，就找到了每一个点的最小值的路径，最终遍历至一底层，最小值存储在dp[0]...

Python3

2022-04-25

2 458

题解 | #跳台阶#

从下往第n阶跳的方法数为F(n)，F(n)的前一步骤为F(n-1)或F(n-2) 故问题简化为斐波那契数列F(n) = F(n-1) + F(n-2) 使用动态规划的方式进行实现，用空间节约时间 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @p...

Python3

2022-04-25

0 402

题解 | #快速乘#

# @param q 询问次数 # @param a 乘数 # @param b 乘数 # @param p 除数 # @return res a*b对p取余数 def fast_add(a, b, p): res = 0 while b > 0: if b...

Python3

2022-04-25

0 404

题解 | #快速幂#

若采用循环直接实现幂指数计算时间复杂度为O(n) 使用快速幂的方式，即计算的幂指数的指数部分每次减半，底数变为平方。通过对折的方式，减少指数部分，从而减少循环的次数。（对指数奇偶性进行判断）当指数大于零的时候，对2取余数，余数为1的时候，此时计算的结果res乘一次底数，并将结果对p取余。指...

Python3

2022-04-25

0 552

题解 | #汉诺塔问题#

汉诺塔问题：将n个盘子从left柱，借助mid柱，放至right柱（大的盘子不能放在小的盘子上）可以分解为以下三个步骤：把n-1个盘子，从left，借助mid，放至right上把最大的盘子，从left，放至right上。把n-1个盘子从mid，借助left，放至right上 tips...

Python3

2022-04-17

2 627

题解 | #ranko的手表#

采用枚举的方式，将一天的时间转换为0 - 60 * 24 分钟并进行遍历，每个遍历值记为i 创建两个列表，分别存储两个输入时间的可能分钟数分别判断遍历值i能否满足两个输入值的格式，若满足，则将i添加到对应的列表中 s1 = input() s2 = input() # 创建两个空列表存储可能...

Python3

2022-04-17

19 1117

题解 | #删除链表的节点#

# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @para...

Python3

2022-04-16

0 344

题解 | #反转链表#

采用递归和非递归方式实现 # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可...

Python3

2022-04-16

0 348