提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  工具

当前栏目

Golang每日一练(leetDay0042)

Golang 每日
2023-09-14 09:01:28 时间

目录

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 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/ 

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

相关文章