Valid Palindrome II
/**
greedy算法
从两边向中间搜索，如果对应位置不相等
则去掉左边的或者去掉右边的元素之后，剩余部分应该为回文
*/
func validPalindrome(s string) bool {
str := []byte(s)
l := len(s)
for i := 0; i < l/2; i++ {
if str[i] != str[l-i-1] {
j := l - i - 1
return isPalindrome(str, i+1, j) || isPalindrome(str, i, j-1)
}
}
return true
}
func isPalindrome(s []byte, l, r int) bool {
for i := l; i <= l+(r-l)/2; i++ {
if s[i] != s[r-i+l] {
return false
}
}
return true
}
Sum of Root To Leaf Binary Numbers
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
var ret int
func sumRootToLeaf(root *TreeNode) int {
ret = 0
helper(root, 0)
return ret
}
func helper(root *TreeNode, sum int) {
if root == nil {
return
}
sum = sum << 1
sum += root.Val
if root.Left == nil && root.Right == nil {
ret += sum
return
}
if root.Left != nil {
helper(root.Left, sum)
}
if root.Right != nil {
helper(root.Right, sum)
}
}
Repeated Substring Pattern
func repeatedSubstringPattern(s string) bool {
str := []byte(s)
if len(str) <= 1 {
return false
}
max := len(str) / 2
for i := 1; i <= max; i++ {
j := i
idx := 0
if len(str)%i > 0 {
continue
}
for ; j < len(str); j++ {
if str[j] != str[idx] {
break
}
idx++
if idx >= i {
idx = 0
}
}
if j == len(str) {
return true
}
}
return false
}
