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

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

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

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

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

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