2019-07-28

Longest Palindrome

func longestPalindrome(s string) int {
    count := make([]int, 128)
    for _, c := range s {
        count[c]++
    }
    ans := 0
    for _, v := range count {
        ans += v / 2 * 2
        if ans%2 == 0 && v%2 == 1 {
            ans++
        }
    }
    return ans
}

Partition Equal Subset Sum

func canPartition(nums []int) bool {
    sum := 0
    for _, v := range nums {
        sum += v
    }
    if sum%2 == 1 {
        return false
    }
    dp := make([]bool, sum+1)
    for k := range dp {
        dp[k] = false
    }
    dp[0] = true
    for _, v := range nums {
        //注意，这里是倒着循环，避免被覆盖
        for i := sum; i >= 0; i-- {
            if dp[i] {
                dp[i+v] = true
            }
        }
        if dp[sum/2] {
            return true
        }
    }
    return false
}

Permutations

func permute(nums []int) [][]int {
    var ret [][]int
    l := len(nums)
    if l == 0 {
        return ret
    }
    helper(nums, 0, l-1, &ret)
    return ret
}

func helper(nums []int, begin, end int, ret *[][]int) {
    if begin == end {
        t := make([]int, len(nums))
        copy(t, nums) //这里一定要copy
        *ret = append(*ret, t)
        return
    }

    for i := begin; i <= end; i++ {
        nums[begin], nums[i] = nums[i], nums[begin]
        helper(nums, begin+1, end, ret)
        nums[begin], nums[i] = nums[i], nums[begin]
    }
}