week 2019-06-23

LeetCode 16[M]

/**
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
*/

func threeSumClosest(nums []int, target int) int {
    dist := math.MaxInt32
    ret := 0
    if len(nums) < 3 {
        return 0
    }
    sort.Ints(nums)
    l := len(nums)
    for i := 0; i < l-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        begin, end := i+1, l-1
        for begin < end {
            sum := nums[begin] + nums[end] + nums[i]
            if sum < target {
                if target-sum < dist {
                    dist = target - sum
                    ret = sum
                }
                begin++
            } else if sum > target {
                if sum-target < dist {
                    dist = sum - target
                    ret = sum
                }
                end--
            } else {
                return sum
            }
        }
    }
    return ret
}

LeetCode 17[M]

/**
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
*/
/*
回溯算法(不会写这个英文)
*/
func letterCombinations(digits string) []string {
    table := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
    ret := []string{}
    if len(digits) > 0 {
        help(&ret, digits, "", 0, table)
    }
    return ret
}

func help(ret *[]string, digits string, cur string, index int, table []string) {
    if index == len(digits) {
        *ret = append(*ret, cur)
        return
    }
    tmp := table[digits[index]-48]
    for _, t := range tmp {
        help(ret, digits, cur+string(t), index+1, table)
    }
}

LeetCode 926

package main

/**
dp解法
状态方程：
如果最后一位是0：
    dp[i][0] = dp[i-1][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1
如果最后一位是1：
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = min(dp[i-1][0], dp[i-1][1])
TODO 可以降维优化
*/

func minFlipsMonoIncr(S string) int {
    l := len(S)
    dp := make([][]int, l+1)
    //二维数组初始化方法
    for i := 0; i < l+1; i++ {
        dp[i] = make([]int, 2)
    }
    for i := 1; i <= l; i++ {
        if S[i-1] == '0' {
            dp[i][0] = dp[i-1][0]
            dp[i][1] = mymin(dp[i-1][0], dp[i-1][1]) + 1
        } else {
            dp[i][0] = dp[i-1][0] + 1
            dp[i][1] = mymin(dp[i-1][0], dp[i-1][1])
        }
    }
    return mymin(dp[l][0], dp[l][1])
}
func mymin(x, y int) int {
    if x > y {
        return y
    }
    return x
}