func getK(x, y []int, k int) float64 {
	index1, index2 := 0, 0
	for {
		if len(x) == index1 {
			return float64(y[index2+k-1])
		}
		if len(y) == index2 {
			return float64(x[index1+k-1])
		}
		if k == 1 {
			return float64(min(x[index1], y[index2]))
		}
		half := k / 2
		// 算出新的 index，注意 k 不能直接变成 k/2，因为两个数组可能有的长度已经不足 k/2，要根据情况来缩短
		newIx, newIy := min(index1+half-1, len(x)-1), min(index2+half-1, len(y)-1) // 当长度不足时，使用最后一个元素
		xx, yy := x[newIx], y[newIy]
		if xx < yy {
			k -= newIx - index1 + 1 //k没有直接折半。而是减去不需要的元素。两个下标相减再+1，就是可以删掉的元素个数。
			index1 = newIx + 1
		} else {
			k -= newIy - index2 + 1
			index2 = newIy + 1
		}
	}
	return 0 //实际不会走到这
}

func nextPermutation(nums []int) {
	j := len(nums) - 1
	for ; j >= 1; j-- {
		// 从后往前找有找大哥的
		if nums[j-1] < nums[j] {
			break
		}
	}
	if j < 1 {
		// 目前是倒序排列
		reverse(nums)
		return
	}
	i := j - 1 // i,j 已就位，开始找 k
	k := len(nums) - 1
	for ; k > i; k-- {
		if nums[k] > nums[i] {
			break
		}
	}
	nums[i], nums[k] = nums[k], nums[i]
	reverse(nums[j:])
}

// SearchInts searches for x in a sorted slice of ints and returns the index
// as specified by Search. The return value is the index to insert x if x is
// not present (it could be len(a)).
// The slice must be sorted in ascending order.
func SearchInts(a []int, x int) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}

func jump(nums []int) int {
    ans := 0
 
    end := 0
    maxPos := 0
    for i := 0 ; i < len(nums)  - 1; i++{
        maxPos = max(nums[i]+i,maxPos)
        if i == end{
            end = maxPos
            ans++
        }
    }
    return ans
}

func TestMapKeyArray(t *testing.T) {
	m := map[[3]int]int{}
	a := [3]int{111, 222, 333}
	b := [3]int{111, 222, 333}
	m[a] = 1
	m[b]++
	println(m[b]) //结果为 2

	//	既然数组可以，试一下切片呢？

	// m2 := map[[]int]int{}
	// 声明 m 后就报错了，切片不能做等值比较，因此无法作为 map 的 key！
}

// This example demonstrates searching a list sorted in ascending order.
func ExampleSearch() {
	a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
	x := 6

	i := sort.Search(len(a), func(i int) bool { return a[i] >= x })
	if i < len(a) && a[i] == x {
		fmt.Printf("found %d at index %d in %v\n", x, i, a)
	} else {
		fmt.Printf("%d not found in %v\n", x, a)
	}
	// Output:
	// found 6 at index 2 in [1 3 6 10 15 21 28 36 45 55]
}

// This example demonstrates searching a list sorted in descending order.
// The approach is the same as searching a list in ascending order,
// but with the condition inverted.
func ExampleSearch_descendingOrder() {
	a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
	x := 6

	i := sort.Search(len(a), func(i int) bool { return a[i] <= x })
	if i < len(a) && a[i] == x {
		fmt.Printf("found %d at index %d in %v\n", x, i, a)
	} else {
		fmt.Printf("%d not found in %v\n", x, a)
	}
	// Output:
	// found 6 at index 7 in [55 45 36 28 21 15 10 6 3 1]
}

x.Right = cur.Right
cur.Left,cur.Right = nil,cur.Left

// 题目里算的结果可包含root也可不包含root
// 因此我需要封装一个计算函数，计算包含 root 的最大
maxPathSumWithRoot = func(root *TreeNode) int {
	if root == nil {
		return -1001
	}
	sum, l, r := root.Val, maxPathSumWithRoot(root.Left), maxPathSumWithRoot(root.Right)
	if l > 0 {
		sum += l
	}
	if r > 0 {
		sum += r
	}
	m[root] = sum
	if sum > ans {
		ans = sum
	}
	return max(root.Val, max(root.Val+l, root.Val+r))
}

if m[k-1] {
  continue
}

func canFinish(numCourses int, prerequisites [][]int) bool {
	if numCourses == 1 {
		return true
	}
	// x 的入度
	ruMap := make([]int, numCourses)
	// 以 x 为起点能到的点
	toMap := map[int][]int{}
	for _, x := range prerequisites {
		// x1 -> x0
		ruMap[x[0]]++
		if toMap[x[1]] != nil {
			toMap[x[1]] = append(toMap[x[1]], x[0])
		} else {
			toMap[x[1]] = []int{x[0]}
		}
	}
	ok := true
	list := []int{}
	for ok {
		// hasZero 是说是否有入度为 0 的点。如果整个 ruMap 都找不到入度为 0 的点，已经成为僵局。可以退出外层 for
		hasZero := false
		for k, v := range ruMap {
			if v == 0 {
				// k 的入度 v 为 0，说明 k 可以顺利完成无前置依赖。
				// 这时候以 k 出发的终点都可以 -1
				hasZero = true
				ruMap[k] = -1 // 标记为 -1，避免重复计算，也可以不标记，直接删除
				list = append(list, k)
				for _, item := range toMap[k] {
					ruMap[item]--
				}
			}
		}
		if !hasZero {
			//整个 ruMap 都找不到入度为 0 的点，已经成为僵局。可以退出外层 for
			ok = false
		}
	}
	// 能进入 list 的，都是入度为 0 的，也就是可达的点
	return len(list) >= numCourses
}

func quick(nums []int, i, j int) int {
  x := nums[i]
	for i < j {
		for i < j && x <= nums[j] {//注意这里一定要是带等于号，不然假如 a[2] = a[3]，就会反复地变成 a[2] = a[3]但是i也不会++，j也不会--，为了让i++、j--，必须再他们等于的时候也满足 if
			j--
		}
		nums[i] = nums[j]
		for i < j && x >= nums[i] {
			i++
		}
		nums[j] = nums[i]
	}
	nums[i] = x
}

func init() {
    debug.SetGCPercent(-1)
}

func findKthLargest(nums []int, k int) int {
    left, right := -10001, 10001
    check := func(m int) bool {
        cnt := 0
        for _, x := range nums {
            if x >= m {
                cnt++
            }
        }

        return cnt >= k
    }
    for left+1 < right {
        mid := (left+right) >> 1
        if check(mid) {
            left = mid
        } else {
            right = mid
        }
    }

    return left
}

for _, x := range coins {
    for i := x; i <= amount; i++ {
        ans[i] += ans[i-x]
        fmt.Printf("x=%v,ans[%v]=%v\n", x, i, ans[i])
    }
}
Output:
x=1,ans[1]=1
x=1,ans[2]=1
x=1,ans[3]=1
x=1,ans[4]=1
x=1,ans[5]=1
x=2,ans[2]=2
x=2,ans[3]=2
x=2,ans[4]=3
x=2,ans[5]=3
x=5,ans[5]=4
4

if ansJ == ansI {
		// 不可能挪自己
		// 除非
		// 从左往右找，max 越来越大，ansJ 没更新还是起点 -1
		// 这时候一定会出现
		// 从右往左找，min 越来越小，ansI 也没更新还是起点 -1
		return 0
}