淄博制作网站的公司,长沙知名网站建设,网站虚拟主机免备案,个人网站主页怎么做力扣每日四题 129. 求根节点到叶节点数字之和-中等130. 被围绕的区域-中等437. 路径总和 III-中等376. 摆动序列-中等总结 129. 求根节点到叶节点数字之和-中等
题目描述#xff1a; 给你一个二叉树的根节点 root #xff0c;树中每个节点都存放有一个 0 到 9 之间的数字。 … 力扣每日四题 129. 求根节点到叶节点数字之和-中等130. 被围绕的区域-中等437. 路径总和 III-中等376. 摆动序列-中等总结 129. 求根节点到叶节点数字之和-中等
题目描述 给你一个二叉树的根节点 root 树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字 例如从根节点到叶节点的路径 1 - 2 - 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 叶节点 是指没有子节点的节点。
题解 简单的深度优先搜索就可以解决
代码Go
func sumNumbers(root *TreeNode) int {return dfs(root,0)
}func dfs(root *TreeNode,sum int) int {if root nil {return sum}sum sum * 10 root.ValNewSum : 0if root.Left nil root.Right nil{return sum}if root.Left ! nil{NewSum dfs(root.Left,sum)}if root.Right ! nil{NewSum dfs(root.Right,sum)}return NewSum
}130. 被围绕的区域-中等
题目描述 给你一个 m x n 的矩阵 board 由若干字符 ‘X’ 和 ‘O’ 找到所有被 ‘X’ 围绕的区域并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
题解 没有被包围的O一定与边界上的O相连所以可以反过来从边界上的O开始找到所有相连的O并标记最后遍历矩阵被标记的O变回O没有被标记的O改为X
代码Go
func solve(board [][]byte) {for i : 0;i len(board);i{for j : 0;j len(board[0]);j{if (i 0 || j 0 || i len(board) - 1 || j len(board[0]) - 1) board[i][j] O{checkout(board,i,j)board[i][j] 1}}}for i : 0;i len(board);i{for j : 0;j len(board[0]);j{if board[i][j] 1{board[i][j] O}else{board[i][j] X}}}return
}func checkout(board [][]byte,x int,y int) {if x - 1 0 board[x - 1][y] O{board[x - 1][y] 1checkout(board,x - 1,y)}if y - 1 0 board[x][y - 1] O{board[x][y - 1] 1checkout(board,x,y - 1)}if x 1 len(board) board[x 1][y] O{board[x 1][y] 1checkout(board,x 1,y)}if y 1 len(board[0]) board[x][y 1] O{board[x][y 1] 1checkout(board,x,y 1)}return
}437. 路径总和 III-中等
题目描述 给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。
题解 代码写麻烦了官方题解更容易懂。我的思路是用一个flag变量标记此节点是否必选如果此节点的父节点已经被选中到路径中则该节点必须被选择然后就是常规的深度优先搜索统计即可
代码Go
func pathSum(root *TreeNode, targetSum int) int {return search(root,targetSum,0)
}func search(root *TreeNode,targetSum int,flag int) int {if root nil{return 0}if root.Val targetSum flag 0{return 1 search(root.Left,0,1) search(root.Right,0,1) search(root.Left,targetSum,0) search(root.Right,targetSum,0)}else if root.Val targetSum flag 1{return 1 search(root.Left,0,1) search(root.Right,0,1)}else if flag 0{return search(root.Left,targetSum,0) search(root.Right,targetSum,0) search(root.Left,targetSum - root.Val,1) search(root.Right,targetSum - root.Val,1)}else{return search(root.Left,targetSum - root.Val,1) search(root.Right,targetSum - root.Val,1)}
}376. 摆动序列-中等
题目描述 如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如 [1, 7, 4, 9, 2, 5] 是一个 摆动序列 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。 相反[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。 子序列 可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。 给你一个整数数组 nums 返回 nums 中作为 摆动序列 的 最长子序列的长度 。
题解 子序列问题直接想到动态规划整体思路和最长递增子序列问题基本一致但是因为每次判断dp[i]时都需要和前面所有的位置依次对比所以时间复杂度是On²官方题解使用了两个dp数组分别表示最后一个元素是上升状态的上升数组和最后一个元素是下降状态的下降数组两个数组的第n个状态都可以通过两个数组的n-1个状态共同得出这样既使时间复杂度降到了On也使空间复杂度降到了O1具体可以看下官方题解
代码Go
func wiggleMaxLength(nums []int) int {dp : make([]int,len(nums))sign : make([]int,len(nums))for i : 0;i len(nums);i{if i 0{dp[i] 1sign[i] 0}else if i 1{if nums[i] nums[0]{sign[i] 1dp[i] 2}else if nums[i] nums[0]{sign[i] -1dp[i] 2}else{sign[i] 0dp[i] 1}}else{max : 0for j : 0;j i;j{if sign[j] 1 nums[i] nums[j]{if dp[j] 1 max{max dp[j] 1sign[i] -1}}else if sign[j] -1 nums[i] nums[j]{if dp[j] 1 max{max dp[j] 1sign[i] 1}}else if sign[j] 0{if dp[j] 1 max nums[i] nums[j]{max dp[j] 1sign[i] 1}else if dp[j] 1 max nums[i] nums[j]{max dp[j] 1sign[i] -1}}}dp[i] max}}max : 0for i : 0;i len(nums);i{if dp[i] max{max dp[i]}}return max
}总结
终于忙完了一个大阶段正式回归但是因为现在还要上课而且两道简单两道中等现在变成了四道中等所以不一定能保证每天全靠自己做完四道题了只能说尽量完成如果时间不够的话就只能把没解出来看了题解的题也搬上来了
