目录

124. 二叉树中的最大路径和 Binary-tree-maximum-path-sum  🌟🌟🌟

125. 验证回文串 Valid Palindrome  🌟

126. 单词接龙 II Word Ladder II  🌟🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

124. 二叉树中的最大路径和 Binary-tree-maximum-path-sum

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

代码1： 递归

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func maxPathSum(root *TreeNode) int {if root == nil {return 0}res := root.ValmaxPathSumHelper(root, &res)return res
}func maxPathSumHelper(node *TreeNode, res *int) int {if node == nil {return 0}leftMax := max(0, maxPathSumHelper(node.Left, res))rightMax := max(0, maxPathSumHelper(node.Right, res))*res = max(*res, leftMax+rightMax+node.Val)return max(leftMax, rightMax) + node.Val
}func max(a, b int) int {if a > b {return a}return b
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func main() {nums := []int{1, 2, 3}root := buildTree(nums)fmt.Println(maxPathSum(root))nums = []int{-10, 9, 20, null, null, 15, 7}root = buildTree(nums)fmt.Println(maxPathSum(root))
}

 代码2： DFS

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func maxPathSum(root *TreeNode) int {if root == nil {return 0}res := root.Valstack := []*TreeNode{root}visited := make(map[*TreeNode]bool)visited[root] = truefor len(stack) > 0 {node := stack[len(stack)-1]if node.Left != nil && !visited[node.Left] {stack = append(stack, node.Left)visited[node.Left] = true} else if node.Right != nil && !visited[node.Right] {stack = append(stack, node.Right)visited[node.Right] = true} else {stack = stack[:len(stack)-1]leftMax := 0if node.Left != nil {leftMax = max(0, node.Left.Val)}rightMax := 0if node.Right != nil {rightMax = max(0, node.Right.Val)}res = max(res, leftMax+rightMax+node.Val)node.Val = max(leftMax, rightMax) + node.Valif len(stack) > 0 {parent := stack[len(stack)-1]if parent.Left == node {parent.Left = node} else {parent.Right = node}}}}return res
}func max(a, b int) int {if a > b {return a}return b
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func main() {nums := []int{1, 2, 3}root := buildTree(nums)fmt.Println(maxPathSum(root))nums = []int{-10, 9, 20, null, null, 15, 7}root = buildTree(nums)fmt.Println(maxPathSum(root))
}

输出：

6
42

125. 验证回文串 Valid Palindrome

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: "race a car"
输出: false
解释："raceacar" 不是回文串

提示：

• 1 <= s.length <= 2 * 10^5
• 字符串 s 由 ASCII 字符组成

代码1： 双指针

package mainimport ("fmt""strings"
)func isPalindrome(s string) bool {if len(s) == 0 {return true}s = strings.ToLower(s)left, right := 0, len(s)-1for left < right {if !isAlphanumeric(s[left]) {left++continue}if !isAlphanumeric(s[right]) {right--continue}if s[left] != s[right] {return false}left++right--}return true
}func isAlphanumeric(c byte) bool {return ('a' <= c && c <= 'z') || ('0' <= c && c <= '9')
}func main() {s := "A man, a plan, a canal: Panama"fmt.Println(isPalindrome(s))s = "race a car"fmt.Println(isPalindrome(s))
}

输出：

true
false

代码2： 正则表达式

package mainimport ("fmt""regexp""strings"
)func isPalindrome(s string) bool {if len(s) == 0 {return true}s = strings.ToLower(s)reg, _ := regexp.Compile("[^a-z0-9]+")s = reg.ReplaceAllString(s, "")return isPalindromeHelper(s)
}func isPalindromeHelper(s string) bool {left, right := 0, len(s)-1for left < right {if s[left] != s[right] {return false}left++right--}return true
}func main() {s := "A man, a plan, a canal: Panama"fmt.Println(isPalindrome(s))s = "race a car"fmt.Println(isPalindrome(s))
}

126. 单词接龙 II Word Ladder II

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：

• 每对相邻的单词之间仅有单个字母不同。
• 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
• sk == endWord

给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。

提示：

• 1 <= beginWord.length <= 5
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有单词 互不相同

代码：

package mainimport ("fmt"
)func findLadders(beginWord string, endWord string, wordList []string) [][]string {result, wordMap := make([][]string, 0), make(map[string]bool)for _, w := range wordList {wordMap[w] = true}if !wordMap[endWord] {return result}queue := make([][]string, 0)queue = append(queue, []string{beginWord})queueLen := 1levelMap := make(map[string]bool)for len(queue) > 0 {path := queue[0]queue = queue[1:]lastWord := path[len(path)-1]for i := 0; i < len(lastWord); i++ {for c := 'a'; c <= 'z'; c++ {nextWord := lastWord[:i] + string(c) + lastWord[i+1:]if nextWord == endWord {path = append(path, endWord)result = append(result, path)continue}if wordMap[nextWord] {levelMap[nextWord] = truenewPath := make([]string, len(path))copy(newPath, path)newPath = append(newPath, nextWord)queue = append(queue, newPath)}}}queueLen--if queueLen == 0 {if len(result) > 0 {break}for k := range levelMap {delete(wordMap, k)}levelMap = make(map[string]bool)queueLen = len(queue)}}return result
}func main() {beginWord, endWord := "hit", "cog"wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}fmt.Println(findLadders(beginWord, endWord, wordList))wordList = []string{"hot", "dot", "dog", "lot", "log"}fmt.Println(findLadders(beginWord, endWord, wordList))
}

输出：

[[hit hot dot dog cog] [hit hot lot log cog]]
[]

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏