week 2019-07-14

四数之和

func fourSum(nums []int, target int) [][]int {
    var ret [][]int
    sort.Ints(nums)
    val := [...]int{0, 0, 0}
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i-1] == nums[i] {
            continue
        }
        for j := i + 1; j < len(nums); j++ {
            val[0] = nums[i] + nums[j]
            if val[0] > target && nums[j] > 0 { //后面不可能有解
                break
            }
            if j > i+1 && nums[j-1] == nums[j] { //相同元素
                continue
            }
            for k := j + 1; k < len(nums); k++ {
                val[1] = val[0] + nums[k]
                if val[1] > target && nums[k] > 0 {
                    break
                }
                if k > j+1 && nums[k-1] == nums[k] {
                    continue
                }
                for m := k + 1; m < len(nums); m++ {
                    val[2] = val[1] + nums[m]
                    if val[2] == target {
                        tmp := []int{nums[i], nums[j], nums[k], nums[m]}
                        ret = append(ret, tmp)
                        break
                    }
                    if val[2] > target {
                        break
                    }
                }
            }
        }
    }
    return ret
}

括号生成

var ret []string

func generateParenthesis(n int) []string {
    ret = []string{}
    helper("", n, n)
    return ret
}

func helper(item string, left, right int) {
    if left < 0 || right < 0 || left > right {
        return
    }
    if left == 0 && right == 0 {
        ret = append(ret, item)
        return
    }
    helper(item+"(", left-1, right)
    helper(item+")", left, right-1)

}

合并K个链表

/**
分治的方法，不停的两两merge
其中merge两个list的方法，就是#21
*/
type ListNode struct {
    Val  int
    Next *ListNode
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    begin, end := 0, len(lists)-1
    for begin < end {
        mid := (begin + end - 1) / 2
        for i := 0; i <= mid; i++ {
            lists[i] = mergeTwoLists(lists[i], lists[end-i])
        }
        end = (begin + end) / 2
    }
    return lists[0]
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val < l2.Val {
        l1.Next = mergeTwoLists(l1.Next, l2)
        return l1
    } else {
        l2.Next = mergeTwoLists(l1, l2.Next)
        return l2
    }

}