AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

Golang每日一练(leetDay0042) 二叉树最大路径和、回文串、单词接龙II

2024-01-30 60
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Golang每日一练(leetDay0042) 二叉树最大路径和、回文串、单词接龙II

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 main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func maxPathSum(root *TreeNode) int {
  if root == nil {
    return 0
  }
  res := root.Val
  maxPathSumHelper(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 := 1
  for 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 main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func maxPathSum(root *TreeNode) int {
  if root == nil {
    return 0
  }
  res := root.Val
  stack := []*TreeNode{root}
  visited := make(map[*TreeNode]bool)
  visited[root] = true
  for 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 := 0
      if node.Left != nil {
        leftMax = max(0, node.Left.Val)
      }
      rightMax := 0
      if node.Right != nil {
        rightMax = max(0, node.Right.Val)
      }
      res = max(res, leftMax+rightMax+node.Val)
      node.Val = max(leftMax, rightMax) + node.Val
      if 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 := 1
  for 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 main
import (
  "fmt"
  "strings"
)
func isPalindrome(s string) bool {
  if len(s) == 0 {
    return true
  }
  s = strings.ToLower(s)
  left, right := 0, len(s)-1
  for 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 main
import (
  "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)-1
  for 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 main
import (
  "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 := 1
  levelMap := 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] = true
          newPath := 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/


文章标签：
Go
Python
Java
C++
canal
关键词：
Python循环
Python旋转
Python链表
链表python
链表旋转
HannYang
目录
相关文章
屿小夏
|
6月前
|
Python
使用Python绘制动态螺旋线：旋转动画效果
使用Python绘制动态螺旋线：旋转动画效果
屿小夏
86 1
bruce_xiaowei
|
2月前
|
算法 数据安全/隐私保护 开发者
马特赛特旋转算法：Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心，由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器，具有超长周期和高维均匀性，适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组，经状态更新和输出提取生成随机数，代码简单高效。
bruce_xiaowei
123 63
BetterBench
|
5月前
|
Python
【Leetcode刷题Python】21. 合并两个有序链表
介绍了几种不同的方法来合并多个已排序的链表，包括暴力求解、使用小顶堆以及分而治之策略。
BetterBench
51 2
BetterBench
|
5月前
|
索引 Python
【Leetcode刷题Python】328. 奇偶链表
在不使用额外空间的情况下，将链表中的奇数和偶数索引节点重新排序的方法，并提供了相应的Python实现代码。
BetterBench
44 0
BetterBench
|
5月前
|
Python
【Leetcode刷题Python】25.K 个一组翻转链表
解决LeetCode "K 个一组翻转链表" 问题的三种方法：使用栈、尾插法和虚拟节点顺序法，并提供了每种方法的Python实现代码。
BetterBench
39 0
bruce_xiaowei
|
3月前
|
Python
Python对PDF文件页面的旋转和切割
Python对PDF文件页面的旋转和切割
bruce_xiaowei
56 3
BetterBench
|
5月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现，通过先序遍历二叉树并调整节点的左右指针，将二叉树转换为先序遍历顺序的单链表。
BetterBench
33 3
【Leetcode刷题Python】114. 二叉树展开为链表
BetterBench
|
5月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案，使用双指针法找到并返回链表中倒数第k个节点。
BetterBench
61 5
BetterBench
|
5月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案，通过使用双指针法找到并删除链表中值为特定数值的节点，然后返回更新后的链表头节点。
BetterBench
49 4
BetterBench
|
5月前
|
Python
【Leetcode刷题Python】剑指 Offer 11. 旋转数组的最小数字
解决剑指Offer 11题 "旋转数组的最小数字" 的三种Python实现方法：直接使用min函数、线性查找分界点和二分查找法，以找出旋转数组中的最小元素。
BetterBench
65 2