fred-coder - 个人主页动态 - 牛客网

发布(153) 评论刷题收藏

2021-12-25 21:10

辽宁工程技术大学算法工程师

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

动态规划，定义 dp 数组, 其中 dp[i] 表示 array[0:i] 连续子数组的最大和; 转移方程为： (1) dp[i] = dp[i - 1] + array[i] 当 array[i] + dp[i - 1] >= array[i] (2) dp[i] = array[i] 当 array[i] + dp[i - 1] < dp[i - 1] 因为求的是连续子数组,则 dp[i] 的值与 dp[i - 1] 和 array[i] 有关, 即 dp[i - 1] + array[i] 较大时, dp[i] 由 dp[i - 1] 转移,否则 dp[i] 为当前值 再定义...

0 点赞评论收藏

分享

2021-12-24 00:47

辽宁工程技术大学算法工程师

题解 | #给单链表加一#

链表反转,末尾加 1 # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def reverse(self, head: ListNode) -> ListNode: if not head or not head.next: return head t = None whil...

0 点赞评论收藏

分享

2021-12-23 01:00

辽宁工程技术大学算法工程师

题解 | #对链表进行插入排序#

插入排序思想,当前值 <= val 时继续迭代,直到遇到较大值,由于链表结构,需要重置 next 节点,若是数组要进行移位操作 # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def insertionSortList(self , head: ListNode) -&gt...

0 点赞评论收藏

分享

2021-12-23 00:53

辽宁工程技术大学算法工程师

题解 | #加起来和为目标值的组合(三)#

dfs, 退出条件为 总数超过 k 或者总和超过 n # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param k int整型 # @param n int整型 # @return int整型二维数组 # class Solution: def combination(self , k: int, n: int) -> List[List[int]]: # write code here res = [] def dfs(s, t): nonlocal res if sum(t) > n or len(t) > k: retu...

0 点赞评论收藏

分享

2021-12-21 00:51

辽宁工程技术大学算法工程师

题解 | #字符串的全部子序列#

递归,将字符串的字符依次加入结果集中，在递归中将结果加入到集合中 # 按层递归, 递归 在 s > e 时结束, s == e 时操作 for i in range(s, e): dfs(s + 1, t) # 依次递归, 递归条件在 s > e 时结束, 在 s <= e 时操作 for i in range(s, e): dfs(i + 1, t)  # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @return string字符串一维数组 # class Solution: def ...

0 点赞评论收藏

分享

2021-12-21 00:24

辽宁工程技术大学算法工程师

题解 | #加起来和为目标值的组合(四)#

dfs， 由于数字可重复且顺序不同视为不同组合,则递归求解和为 target 的组合即可 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @param target int整型 # @return int整型 # class Solution: def combination(self , nums: List[int], target: int) -> int: # write code here res = 0 def dfs(t): nonlocal res if sum(t) > ...

0 点赞评论收藏

分享

2021-12-19 23:42

辽宁工程技术大学算法工程师

题解 | #加起来和为目标值的组合#

递归，可重复选取一个元素，由于不能有重复的数组出现，则当符合条件时，进行排序判断是否已在结果数组中 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param target int整型 # @param nums int整型一维数组 # @return int整型二维数组 # class Solution: def combinationCount(self , target: int, nums: List[int]) -> List[List[int]]: # write code here res = [] def dfs(t): n...

0 点赞评论收藏

分享

2021-12-18 23:37

辽宁工程技术大学算法工程师

题解 | #打家劫舍(二)#

动态规划,dp[i] = max(dp[i + 2] + nums[i], dp[i + 1]),由于围城了一个圈,第一家和最后一家算作相邻,即求 nums[1:] 和 nums[:-1] 上的最大 dp 值 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution: def rob(self , nums: List[int]) -> int: # write code here if len(nums) == 1: return nums[...

0 点赞评论收藏

分享

2021-12-18 00:09

辽宁工程技术大学算法工程师

题解 | #打家劫舍(一)#

dp，从后向前转移,直接赋初始值, 转移方程: dp[i] = max(dp[i + 2] + nums[i], dp[i + 1]) # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution: def rob(self , nums: List[int]) -> int: # write code here dp = [0 for _ in range(len(nums) + 2)] for i in range(len(nums) - 1,...

0 点赞评论收藏

分享

2021-12-16 00:35

辽宁工程技术大学算法工程师

题解 | #二叉树中和为某一值的路径(三)#

dfs + bfs, 由于题目中路径不以根节点开始、叶节点结束,设置全局变量保存路径数量 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 # @param sum int整型 # @return int整型 # class Solution: def __init__(self): self.path = 0 de...

0 点赞评论收藏

分享

2021-12-15 00:46

辽宁工程技术大学算法工程师

题解 | #矩阵最长递增路径#

记忆化搜索，根据题意可利用 dfs 进行求解,因为路径是递增的,已走过的路径可缓存,利用 递归 + 备忘录的方式求解 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 递增路径的最大长度 # @param matrix int整型二维数组 描述矩阵的每个数 # @return int整型 # class Solution: def solve(self , matrix: List[List[int]]) -> int: # write code here if not matrix: return 0 m, n = len(matrix), le...

0 点赞评论收藏

分享

2021-12-15 00:35

已编辑

辽宁工程技术大学算法工程师

题解 | #【模板】差分#

利用差分数组 diff 减少区间操作的时间复杂度, diff 生成如下: diff[0] = data[0] for i in range(1, len(data)): # 后一个元素与前一个元素相减 diff[i] = data[i] - data[i - 1]  之后可根据 diff 依次推算出 data 的值; data[0] = diff[0] for i in range(1, len(diff)): data[i] = data[i - 1] + diff[i]  这样在对 data[i:j + 1] 进行加减值操作时, 可对 diff[i] 和 diff[j + 1] 的值操作即...

0 点赞评论收藏

分享

2021-12-12 22:40

已编辑

辽宁工程技术大学算法工程师

题解 | #二叉树的最大宽度#

根据二插树的节点间的位置关系, left_child = root * 2, right_child = root * 2 + 1 利用层序遍历，进行判断处理 class Solution: def widthOfBinaryTree(self , root: TreeNode) -> int: """ {1,2,3,4,#,4,5,6,#,1} {1,#,1,#,1 #,1,#,1,#,1,#,4,2} """ # write code here if not root: return 0 q = [(root, 0, 0)] dept = l_pos = 0 res = 0 for ...

0 点赞评论收藏

分享

2021-12-12 16:41

辽宁工程技术大学算法工程师

题解 | #最长公共子数组#

利用二维 dp 求解，dp[i][j] 表示数组 A[i] 和 B[j] 内的最长公共子数组的长度 转移状态方程为: dp[i][j] = dp[i - 1][j - 1] + 1 A[i] = B[j] 因为公共子数组是连续的子数组,所以当 A[i] != B[j] 时的情况不用考虑 dp 的初始长度设置为 dp = [[len(B) + 1] len(A) + 1], 这样在遍历时将初值代入 设置 res 表示最终结果,在遍历中更新该值 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param A int整型一维数组 # @param B ...

0 点赞评论收藏

分享

2021-12-10 23:39

辽宁工程技术大学算法工程师

题解 | #最长公共子序列(一)#

两个字符串求公共子序列，利用二维 dp; 转移方程为 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) s1[i] != s2[j] dp[i][j] = dp[i - 1][j - 1] + 1 s1[i] == s2[j] dp 长宽为字符串长度 + 1 将 dp 基础赋值加在遍历中 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # s1和s2最长公共子序列的长度 # @param s1 string字符串 # @param s2 string字符串 # @return int整型 # class Solution...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务