2019-12-08

Find Duplicate Number

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
}

Search Matrix

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    n := len(matrix)
    m := len(matrix[0])
    if target < matrix[0][0] || target > matrix[n-1][m-1] {
        return false
    }

    var mid int
    low, high := 0, n-1
    for low <= high {
        mid = (low + high) / 2
        if matrix[mid][0] > target {
            high = mid - 1
        } else if matrix[mid][0] < target {
            low = mid + 1
        } else {
            return true
        }
    }

    left, right := 0, m-1
    for left <= right {
        mid = (left + right) / 2
        if matrix[high][mid] > target {
            right = mid - 1
        } else if matrix[high][mid] < target {
            left = mid + 1
        } else {
            return true
        }
    }
    return false
}

Full permute

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