week 2019-07-07

盛水最多的容器

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0
    for left < right {
        maxArea = max(maxArea, min(height[left], height[right])*(right-left))
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return maxArea
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}

全排列

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]
    }
}

Z字形变换

func convert(s string, numRows int) string {
    if numRows == 1 {
        return s
    }

    item_len := 2*numRows - 2 //循环的长度
    res := make([][]string, numRows, numRows)

    for index, v := range s {

        mod := index % item_len

        if mod < numRows {
            res[mod] = append(res[mod], string(v))
        } else {
            i := numRows - (mod - numRows) - 2
            res[i] = append(res[i], string(v))
        }
    }

    var str string

    for _, arr := range res {
        for _, v := range arr {
            str += v
        }
    }

    return str
}