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))
}

输出：

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))
}