fred-coder

分类

题解(149)

/ 注册

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

32篇文章 625人学习

全部文章（共139篇）

题解 | #二叉搜索树的第k个节点#

由于是二插搜索树，进行中序遍历得到有序数组，再对特殊值进行判断 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right ...

Python3 二叉树

2021-11-24

2 616

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

dp 解法，定义 dp 数组，转移方程为 dp[i] = max(dp[i], dp[j] + 1) j < i and arr[j] < arr[i] 因为每个数字算一位，初始值 dp = [1] * len(arr) 代码如下 # # 代码中的类名、方法名、参数名已经指定，请勿修改，...

Python3 动态规划

2021-11-23

2 690

题解 | #压缩字符串(一)#

一、利用一个字符变量 s 和一个计数变量 c 表示当前字符和数量,再用一个结果变量 res 记录最终结果二、利用栈进行存储,最终过滤 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param param string字符串 # @return ...

Python3 栈

2021-11-19

4 670

题解 | #二进制求和#

方法一: 两个字符串长度补0，从右至左依次相加，注意进位 >= 2 即进位方法二: 利用 Python 二进制转化十进制，相加后再转二进制 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param A string字符串 # @param...

Python3 字符串

2021-11-17

0 414

题解 | #字母收集#

本题可利用动态规划进行求解，数据是 n * m 的矩阵，利用二维 dp，每次移动只能向右或向下，初始值 dp[0][0] = v00，第一行 dp[i][j] = dp[i - 1][j] + vij, 第一列 dp[i][j] = dp[i][j - 1] + vij, 当 i > 0 且...

Python3 动态规划

2021-11-13

0 401

题解 | #【模板】完全背包#

同上题类似,由于物品的数量有任意多个，则压缩 dp 后遍历时不采用逆序; 代码如下: n, v = map(int, input().strip().split()) dp_1 = [0 for _ in range(v + 1)] dp_2 = [float('-inf') for _ in ra...

Python3 动态规划

2021-11-12

2 444

题解 | #【模板】01背包#

01背包问题可用二维 dp，在遍历状态转移时，由于状态只与其中一个维度有关，可进行压缩;注意恰好装满，初始数组值为 -inf。代码如下: n, v = map(int, input().strip().split()) dp_1 = [0 for _ in range(v + 1)] dp_2 =...

Python3 动态规划

2021-11-12

1 520

题解 | #寻找峰值#

根据题意峰值是相邻左侧和右侧数据均小于索引数据的值，则建立左右前缀数组，对左侧和右侧的值先行判断,最终左侧和右侧都符合的值即为峰值索引,代码如下 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @ret...

Python3 数组前缀和

2021-11-07

0 518

题解 | #【模板】前缀和#

根据题意，每次询问取数据 [l: r + 1]的总和，由于 n 的范围在 1 <= n <= 10 ** 5，则每次询问计算一次结果可能会超时，利用前缀数组 pre , 每次[l : r + 1] 即为前缀数组中的 pre[r] - pre[l] +data[l] 注意索引范围代码如下...

Python3 前缀和数组

2021-11-03

0 445

题解 | #nico和niconiconi#

利用动态规划思路求解，构建 dp 数组，设置初始值，根据转移状态方程进行遍历，dp[i] 表示字符串 s[:i + 1] 内的最有价值值，则当 i >= 3 时, 若 s[i - 3: i + 1] == "nico" 时，有价值即 dp[i] = max(dp[i], dp[i - 3] +...

Python3 动态规划

2021-11-03

0 475