week 2019-07-21

寻找重复数

func findDuplicate(nums []int) int {
    left, right := 1, len(nums)-1
    mid := left + (right-left)/2
    for left < right {
        c := 0
        mid = left + (right-left)/2
        for i := 0; i < len(nums); i++ {
            if nums[i] <= mid {
                c++
            }
        }
        if c > mid {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

最佳买卖股票时机含冷冻期

/**
三种状态之间互相转移：持有，售出，休息
售出的收益等于持有加上当天价格
持有的收益等于max(前一天休息之后买入，前一天持有）
休息的收益等于max(前一天休息，前一天售出)
*/
func maxProfit(prices []int) int {
    sold, rest, hold := 0, 0, math.MinInt32
    for _, v := range prices {
        pre_sold := sold
        sold = hold + v
        hold = mymax(hold, rest-v)
        rest = mymax(rest, pre_sold)
    }
    return mymax(rest, sold)
}

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

左叶子之和

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func sumOfLeftLeaves(root *TreeNode) int {
    sum := 0
    if root != nil {
        if isLeaf(root.Left) {
            sum += root.Left.Val
        } else {
            sum += sumOfLeftLeaves(root.Left)
        }
        sum += sumOfLeftLeaves(root.Right)
    }
    return sum
}

func isLeaf(root *TreeNode) bool {
    if root == nil || root.Left != nil || root.Right != nil {
        return false
    }
    return true
}