2019-11-03

-1

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// 如果nums1>nums2，返回true；否则返回false
func compare(nums1, nums2 []int) bool {
    i := 0
    for ; i < len(nums1) && i < len(nums2); i++ {
        if nums1[i] > nums2[i] {
            return true
        } else if nums2[i] > nums1[i] {
            return false
        }
    }
    if i == len(nums1) {
        return false
    }
    return true
}

/*
思路： 2*greedy + 1*DP
子问题1：找到数组中由k个数组成的最大数的组合（不改变先后顺序）
    getMax(nums []int, k int) []int {}
子问题2：将长度为i和k-i的两个最大值组合进行合并(不改变先后顺序)
    mergeMax(max1, max2 []int) []int {}
子问题3：获取子问题2中所有合并所得结果的最大组合
    dpMax(max1, max2 []int) []int {}
*/
func getMax(nums []int, k int) []int {
    size := len(nums)
    res := make([]int, k)
    // j代表res的长度，不是index
    j := 0
    for i := 0; i < size; i++ {
        for j > 0 && nums[i] > res[j-1] && size-i > k-j {
            j--
        }
        if j < k {
            res[j] = nums[i]
            j++
        }
    }
    return res
}

func mergeMax(max1, max2 []int, k int) []int {
    res := make([]int, k)
    i1, i2 := 0, 0
    n1, n2 := len(max1), len(max2)
    for i := 0; i < k; i++ {
        if i1 == n1 {
            res[i] = max2[i2]
            i2++
            continue
        }
        if i2 == n2 {
            res[i] = max1[i1]
            i1++
            continue
        }
        //if max1[i1] > max2[i2] {
        if compare(max1[i1:], max2[i2:]) {
            res[i] = max1[i1]
            i1++
        } else {
            res[i] = max2[i2]
            i2++
        }
    }
    return res
}

func dpMax(max1, max2 []int, k int) []int {
    for i := 0; i < k; i++ {
        if max1[i] > max2[i] {
            return max1
        } else if max2[i] > max1[i] {
            return max2
        }
    }
    return max1
}

func maxNumber(nums1 []int, nums2 []int, k int) []int {
    n1, n2 := len(nums1), len(nums2)
    if n2 < n1 {
        return maxNumber(nums2, nums1, k)
    }
    iMax := min(n1, k)
    res := make([]int, k)
    for i := 0; i <= iMax; i++ {
        if k-i <= n2 {
            res = dpMax(res, mergeMax(getMax(nums1, i), getMax(nums2, k-i), k), k)
        }
    }
    return res
}

Missing Number

func missingNumber(nums []int) int {
    total := 0
    for _, v := range nums {
        total += v
    }
    l := len(nums)
    sum := l * (l + 1) / 2
    return sum - total
}

Find Difference

func findTheDifference(s string, t string) byte {

    m := make(map[int32]int, 256)

    var i int32
    for i = 0; i < 256; i++ {
        m[i] = 0
    }

    for _, v := range s {
        m[v]++
    }
    for _, v := range t {
        m[v]--
        if m[v] < 0 {
            return byte(v)
        }
    }
    return 0
}