/*
    插入排序

    时间 n^2, 稳定
    向前插入，先找位置再移动
*/
func InsertSort(arr []int) {
	length := len(arr)
	for i := 1; i < length; i++ {
		j := i - 1
		for j >= 0 {
			if arr[j] < arr[i] {
				break
			}
			j--
		}
		if j != i-1 {
			temp := arr[i]
			k := i - 1
			for ; k > j; k-- {
				arr[k+1] = arr[k]
			}
			arr[k+1] = temp
		}
	}
}

// 向前插入，边移动边找位置
func InsertSort2(arr []int) {
	length := len(arr)
	for i := 1; i < length; i++ {
		if arr[i-1] > arr[i] {
			temp := arr[i]
			j := i - 1
			for ; j >= 0 && arr[j] > temp; j-- {
				arr[j+1] = arr[j]
			}
			arr[j+1] = temp
		}
	}
}

// 向前插入，值向前冒泡
func InsertSort3(arr []int) {
	length := len(arr)
	for i := 1; i < length; i++ {
		for j := i - 1; j >= 0 && arr[j] > arr[j+1]; j-- {
			arr[j], arr[j+1] = arr[j+1], arr[j]
		}
	}
}

/*
    时间 n^2, 稳定
*/
func BubbleSort(arr []int) {
	length := len(arr)
	for i := 0; i < length; i++ {
		for j := 1; j < length-i; j++ {
			if arr[j-1] > arr[j] {
				arr[j-1], arr[j] = arr[j], arr[j-1]
			}
		}
	}
}

func BubbleSortSwapFlag(arr []int) {
	flag := true
	for i := len(arr); flag == true; i-- {
		flag = false
		for j := 1; j < i; j++ {
			if arr[j-1] > arr[j] {
				arr[j-1], arr[j] = arr[j], arr[j-1]
				flag = true
			}
		}
	}
}

func BubbleSortTailFlag(arr []int) {
	flag := len(arr)
	for flag > 1 {
		i := flag
		flag = 0
		for j := 1; j < i; j++ {
			if arr[j-1] > arr[j] {
				arr[j-1], arr[j] = arr[j], arr[j-1]
				flag = j
			}
		}
	}
}

/*
    时间 n^2, 不稳定
*/
func SelectSort(arr []int) {
	length := len(arr)
	for i := 0; i < length; i++ {
		ind := i
		for j := i + 1; j < length; j++ {
			if arr[ind] > arr[j] {
				ind = j
			}
		}
		arr[i], arr[ind] = arr[ind], arr[i]
	}
}

/*
	1 循环：选gap为一半长度
	2 循环：第一段gap
	3 循环gap间隔序列
	4 选择排序

	时间 n^(1.3-2), 不稳定
*/
func ShellSort(arr []int) {
	length := len(arr)
	for gap := length / 2; gap > 0; gap /= 2 {
		for i := 0; i < gap; i++ {
			for j := i + gap; j < length; j += gap {
				k := j - gap
				if arr[k] > arr[j] {
					temp := arr[j]
					for k >= 0 && arr[k] > temp {
						arr[k+gap] = arr[k]
						k -= gap
					}
					arr[k+gap] = temp
				}
			}
		}
	}
}

/*
	1 循环：选gap为一半长度
	2 循环：第一个gap之后每个元素为j
	3 j向前的gap间隔序列做选择排序
 */
func ShellSort2(arr []int) {
	length := len(arr)
	for gap := length / 2; gap > 0; gap /= 2 {
		for j := gap; j < length; j++ {
			k := j - gap
			if arr[k] > arr[j] {
				temp := arr[j]
				for k >= 0 && arr[k] > temp {
					arr[k+gap] = arr[k]
					k -= gap
				}
				arr[k+gap] = temp
			}
		}
	}
}

/*
	..
	最后用冒泡排序
*/
func ShellSort3(arr []int) {
	length := len(arr)
	for gap := length / 2; gap > 0; gap /= 2 {
		for i := gap; i < length; i++ {
			for j := i - gap; j >= 0 && arr[j] > arr[j+gap]; j -= gap {
				arr[j], arr[j+gap] = arr[j+gap], arr[j]
			}
		}
	}
}

/*
	分割，快排左右
	分割：
	1 取轴
	2 中位为start（轴本身占1位），循环除轴的节点
	2.1 节点值小时，中位后移，交换节点和中位的值
	3 交换轴与中位的值

	时间 n^2, 平均时间 nlog(n), 不稳定
*/
func QuickSort(arr []int, start int, end int) {
	swap := func(i int, j int) {
		arr[i], arr[j] = arr[j], arr[i]
	}
	partition := func(start int, end int) int {
		pivot := start
		val := arr[start]

		pos := start
		for i := start + 1; i <= end; i++ {
			if arr[i] < val {
				pos++
				swap(pos, i)
			}
		}
		swap(pivot, pos)
		return pos
	}
	if start < end {
		pivot := partition(start, end)
		QuickSort(arr, start, pivot-1)
		QuickSort(arr, pivot+1, end)
	}
}

/*
	..
	双指针法分割
	1 取轴为开头（或交换到开头），开头为左点，缓存值
	2 向中循环
	2.1 找到右点，向左点赋值
	2.2 找到左点，向右点赋值
	3. 找到中点，赋缓存值
*/
func QuickSort2(arr []int, start int, end int) {
	partition := func(start int, end int) int {
		i := start
		j := end
		val := arr[start]

		for i < j {
			for i < j && arr[j] >= val {
				j--
			}
			if i < j {
				arr[i] = arr[j]
				i++
			}
			for i < j && arr[i] < val {
				i++
			}
			if i < j {
				arr[j] = arr[i]
				j--
			}
		}
		arr[i] = val
		return i
	}
	if start < end {
		pivot := partition(start, end)
		QuickSort2(arr, start, pivot-1)
		QuickSort2(arr, pivot+1, end)
	}
}

/*
	数组表示大顶堆，pos为父节点时, pos*2+1为第一个子节点
	调整堆：父值非最大时下降
	1 给出父节点pos,找到儿子child。
	2 循环直到child越界
	2.1 找大儿子下降，更新pos，计算child

	构建堆: 默认给出数组为堆，从最后一个父节点pos=halfLen开始，向前一个个父节点调整堆

	堆排序:
	1 构建堆，重复2
	2 循环堆节点
	2.1 交换堆顶与末节点叶子, 下降堆顶

	时间 nlog(n), 不稳定
*/
func HeapSort(elements []int) {
	swap := func(i int, j int) {
		elements[i], elements[j] = elements[j], elements[i]
	}
	headAdjust := func(pos int, len int) {
		val := elements[pos]
		child := pos*2 + 1

		for child < len {
			if child+1 < len && elements[child] < elements[child+1] {
				child++
			}
			if elements[pos] >= elements[child] {
				break
			}

			elements[pos] = elements[child]
			pos = child
			child = pos*2 + 1
			elements[pos] = val
		}
	}

	buildHeap := func() {
		halfLen := len(elements) / 2
		for i := halfLen; i >= 0; i-- {
			headAdjust(i, len(elements))
		}

	}

	buildHeap()
	for i := len(elements) - 1; i > 0; i-- {
		swap(0, i)
		headAdjust(0, i)
	}
}

func HeapSort2(arr []int) {
	length := len(arr)
	swap := func(i int, j int) {
		arr[i], arr[j] = arr[j], arr[i]
	}
	parentPos := func(pos int) int {
		return (pos - 1) / 2
	}
	child1Pos := func(pos int) int {
		return pos*2 + 1
	}
	fixDown := func(pos int, l int) {
		val := arr[pos]
		child := child1Pos(pos)
		for child < l {
			if child+1 < l && arr[child+1] > arr[child] {
				child++
			}
			if arr[child] <= val {
				break
			}
			arr[pos] = arr[child]
			pos = child
			child = child1Pos(pos)
		}
		arr[pos] = val
	}
	buildHeap := func() {
		lastParentPos := parentPos(length - 1)
		for i := lastParentPos; i >= 0; i-- {
			fixDown(i, length)
		}
	}

	buildHeap()
	for i := length - 1; i > 0; i-- {
		swap(0, i)
		fixDown(0, i)
	}

	//fixUp := func(child int) {
	//	val := arr[child]
	//	pos := parentPos(child)
	//	for pos >= 0 && child > 0 {
	//		if arr[pos] >= val {
	//			break
	//		}
	//		arr[child] = arr[pos]
	//		child = pos
	//		pos = parentPos(child)
	//	}
	//	arr[child] = val
	//}
}

/*
    时间 nlog(n)
*/
func MergeSort(arr []int) {
	length := len(arr)
	temp := make([]int, length)

	merge := func(start int, mid int, end int) {
		i := start
		j := mid + 1
		m := mid
		n := end
		k := 0
		for i <= m && j <= n {
			if arr[i] <= arr[j] {
				temp[k] = arr[i]
				k++
				i++
			} else {
				temp[k] = arr[j]
				k++
				j++
			}
		}
		for i <= m {
			temp[k] = arr[i]
			k++
			i++
		}
		for j <= n {
			temp[k] = arr[j]
			k++
			j++
		}
		for r := 0; r < k; r++ {
			arr[start+r] = temp[r]
		}
	}

	recurse := func(start int, end int) {}
	recurse = func(start int, end int) {
		if start < end {
			mid := (start + end) / 2
			recurse(start, mid)
			recurse(mid+1, end)
			merge(start, mid, end)
		}
	}

	recurse(0, length-1)

}

/*
    时间 log(n)
*/
func BinarySearch(nums []int, low int, high int, val int) int {
	for low <= high {
		mid := (low + high) / 2
		if nums[mid] == val {
			return mid
		} else if nums[mid] > val {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

/*
    递归
*/
func BinarySearch2(nums []int, low int, high int, val int) int {
	if low > high {
		return -1
	}
	mid := (low + high) / 2
	if nums[mid] == val {
		return mid
	} else if nums[mid] > val {
		return BinarySearch2(nums, low, mid-1, val)
	} else {
		return BinarySearch2(nums, mid+1, high, val)
	}
}

/*
	第k大数

	用快排划分

	时间 n, 空间 n
*/
func topK(arr []int, low int, high int, k int) {
	start, end, mid := low, high, arr[low]
	for low < high {
		for low < high && arr[high] <= mid {
			high--
		}
		if low < high {
			arr[low] = arr[high]
			low++
		}
		for low < high && arr[low] >= mid {
			low++
		}
		if low < high {
			arr[high] = arr[low]
			high--
		}
	}
	arr[low] = mid
	if low > k {
		topK(arr, start, low-1, k)
	} else if low < k {
		topK(arr, low+1, end, k)
	}
}

/*
	大顶堆
	时间 nlog(k), 空间k
*/
func topK2(arr []int, k int) []int {
	heap := make([]int, k)
	for i := 0; i < k; i++ {
		heap[i] = arr[i]
	}

	adjust := func(start int, end int) {
		parent := start
		child := parent*2 + 1
		for child <= end {
			if child+1 <= end && heap[child+1] < heap[child] {
				child++
			}

			if heap[parent] <= heap[child] {
				return
			}
			heap[parent], heap[child] = heap[child], heap[parent]
			parent = child
			child = parent*2 + 1
		}
	}
	buildHeap := func() {
		for i := k / 2; i >= 0; i-- {
			adjust(i, k-1)
		}
	}

	buildHeap()
	for i := k; i < len(arr); i++ {
		if arr[i] > heap[0] {
			heap[0] = arr[i]
			adjust(0, k-1)
		}
	}
	return heap
}

/*
	返回第n个斐波那契数

	时间 n
*/
func Fibonacci(n int) int {
	if n < 3 {
		return 1
	}
	a, b := 1, 1
	for i := 3; i <= n; i++ {
		r := a + b
		a, b = b, r
	}
	return b
}

/*
	时间 n
*/
func Fibonacci2(n int) int {
	if n < 3 {
		return 1
	}
	return Fibonacci2(n-2) + Fibonacci2(n-1)
}

/*
	正整数和
	递归
*/
func CommonSum(n int) int {
	if n == 1 {
		return 1
	}
	return CommonSum(n-1) + n
}

/*
	最大公约数

	每执行一次循环, m或n至少缩小了2倍，故时间复杂度上限为log(2)(M),M是循环次数
	对于大量随机测试样例, 每次循环能便m与n值缩小一个10进位，所以平均复杂度为O(lgM)
*/
func GCD(m int, n int) int {
	var max, min int
	if m > n {
		max, min = m, n
	} else {
		max, min = n, m
	}
	for max%min != 0 {
		r := max % min
		max = min
		min = r
	}
	return min
}

/*
	..

	递归

	时间 logM 空间 logM
*/
func GCD2(m int, n int) int {
	var max, min int
	if m > n {
		max, min = m, n
	} else {
		max, min = n, m
	}

	if max%min == 0 {
		return min
	}
	return GCD2(min, max%min)
}

/*
	最小公倍数
*/
func LCM(m int, n int) int {
	return m * n / GCD(m, n)
}

/*
	最大子序列和

	时间 n
*/
func SumArr(arr []int) int {
	tmp := arr[0]
	max := tmp

	for i := 1; i < len(arr); i++ {
		if tmp >= 0 {
			tmp += arr[i]
		} else {
			tmp = arr[i]
		}

		if max < tmp {
			max = tmp
		}
	}
	return max
}

/*
	判断素数
	合数一定有因子小于sqrt(n)

	时间 n
*/
func isPrime(n int) bool {
	if n < 2 {
		return false
	}

	m := int(math.Sqrt(float64(n)))
	for i := 2; i <= m; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

/*
	arr中false的是素数
	j从i开始, 因小于i的数已筛过

	时间 n*loglog(n)
		n(1/2 + 1/3 + ... 1/n)
*/
func filterPrime(n int) {
	if n < 2 {
		return
	}

	arr := make([]bool, n+1)
	m := int(math.Sqrt(float64(n)))
	for i := 2; i <= m; i++ {
		for j := i; i*j <= n; j++ {
			arr[i*j] = true
		}
	}
}

/*
	描述：给正整数s, 写出连续正整数和为s的所有序列

	双指针法
	由等差数列求和公式知，数列最开始不能过一半
	移end加sum, 移start减sum
	sum找到后，只能同时加减sum，即同时移start、end
*/
func SeriesSum(s int) {
	half := (s + 1) / 2
	start := 1
	end := 2
	sum := 0

	for start < half {
		sum = (start + end) * (end - start + 1) / 2
		if sum == s {
			println(start, end)
			start++
			end++
		} else if sum < s {
			end++
		} else {
			start ++
		}
	}
}

/*
	升序不重复数组中，所有两个元素和为s的组合
	时间 n^2
*/
func TwoSum(arr []int, s int) {
	n := len(arr)

	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if arr[i]+arr[j] == s {
				println(i, j)
				break
			}
		}
	}
}

/*
	二分查找

	时间 nlog(n)
*/
func TwoSum2(arr []int, s int) {
	n := len(arr)
	for i, j := 0, 0; i < n-1; i++ {
		another := s - arr[i]
		j = sort.SearchInts(arr, another)
		if j > i {
			println(i, j)
		}
	}
}

/*
	双指针

	移i加sum, 移j减sum
	sum找到后，只能同时加减sum，即同时移i,j

	时间 n
*/
func TwoSum3(arr []int, s int) {
	i := 0
	j := len(arr) - 1
	for i < j {
		if arr[i]+arr[j] == s {
			println(i, j)
			i++
			j--
		} else if arr[i]+arr[j] < s {
			i++
		} else {
			j--
		}
	}
}

/*
	猴子吃桃：每天吃一半加1个，第n天剩1个，一共几个
*/
func MonkeyEat(n int) int {
	if n == 1 { //指倒数第一天
		return 1
	}
	return MonkeyEat(n-1)*2 + 2
}

/*
	滑动平均数
	先算sum数组
	隔n位的两sum之差即此n位的sum
	除位数取均值
*/
func movingAverage(arr []float64, n int) {
	sum := 0.0
	for i, _ := range arr {
		arr[i] += sum
		sum = arr[i]
	}

	result := make([]float64, len(arr))
	for i, v := range arr {
		start := i - n
		count := n
		if start < 0 {
			count += start + 1
			start = 0
		}
		result[i] = (v - arr[start]) / float64(count)
	}
}

/*
	爬楼梯问题：一次走1或2级，爬上n级有多少走法

	要走到n+1层，只能从n层或n-1层走。n+1层方法数为n层与n-1层方法数的和。所以是个斐波那契数列问题
*/
func ClimbStairs(n int) int {
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
	return ClimbStairs(n-1) + ClimbStairs(n-2)
}

/*
	1元两瓶水, 两空瓶一瓶水, n元几瓶水
*/
func sodaBottle(n int) int {
	if n == 0 {
		return 0
	}

	bottle := 0
	sum := 0
	for i := 1; i <= n; i++ {
		sum++
		bottle += 1
	}
	return sodaBottle(bottle/2) + sum
}

/*
	翻转数组

	双指针
	时间 n，空间 1
*/
func Inverse(arr []int) {
	for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
		arr[i], arr[j] = arr[j], arr[i]
	}
}

/*
	单指针
*/
func Inverse2(arr []int) {
	length := len(arr)
	for i, half := 0, length/2; i < half; i++ {
		j := length - 1 - i
		arr[i], arr[j] = arr[j], arr[i]
	}
}

/*
	轮换，如：[1,2,3,4,5],指定2时，结果[4,5,1,2,3]

	翻转前段，翻转后段，再整体翻转

	时间 n，空间 1
*/
func Rotate(arr []int, k int) {
	if k == 0 {
		return
	}

	length := len(arr)
	if k >= length {
		k = k % length
	}

	inverse := func(start int, end int) {
		for i, j := start, end; i < j; i, j = i+1, j-1 {
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	inverse(0, length-1-k)
	inverse(length-k, length-1)
	inverse(0, length-1)
}

/*
	洗牌(shuffle) Fisher-Yates
	随机选择, 删除, 插入新数组
*/
func shuffle(arr []int) {
	rand.Seed(time.Now().UnixNano())
	length := len(arr)
	result := make([]int, length)

	for i := 0; i < length; i++ {
		k := rand.Intn(len(arr))
		result[i] = arr[k]
		arr = append(arr[:k], arr[k+1:]...)
	}
}

/*
	洗牌 Knuth-Durstenfeld
	随机选择, 放尾部
*/
func shuffle2(arr []int) {
	rand.Seed(time.Now().UnixNano())
	length := len(arr)

	for i := length - 1; i >= 0; i-- {
		k := rand.Intn(i + 1)
		arr[k], arr[i] = arr[i], arr[k]
	}
	fmt.Print(arr)
}

/*
	洗牌 Inside-Out Algorithm
	复制到新数组
	遍历原数组位置i, 随机插入新数组(新数组位置i存插入前数据)
*/
func shuffle3(arr []int) {
	rand.Seed(time.Now().UnixNano())
	length := len(arr)
	result := make([]int, length)

	for i, v := range arr {
		result[i] = v
	}

	for i := 0; i < length; i++ {
		k := rand.Intn(i + 1)
		result[i] = result[k]
		result[k] = arr[i]
	}
	fmt.Print(result)
}

/*
	有序数组去重

	时间 n，空间 n
*/
func RemoveDuplicates(arr []int) int {
	if arr == nil || len(arr) == 0 {
		return 0
	}
	if len(arr) == 1 {
		return 1
	}

	end := len(arr) - 1
	list0 := list.New()

	for i := 0; i <= end; {
		if i == end {
			list0.PushBack(arr[i])
			i++
		} else {
			j := i + 1
			if arr[i] == arr[j] {
				for j <= end && arr[i] == arr[j] {
					j++
				}
			}
			list0.PushBack(arr[i])
			i = j
		}
	}

	eleInd := 0
	for ele := list0.Front(); nil != ele; ele = ele.Next() {
		arr[eleInd] = ele.Value.(int)
		eleInd++
	}
	return eleInd
}

/*
	..
	时间 n，空间 1
*/
func RemoveDuplicates2(arr []int) int {
	if arr == nil || len(arr) == 0 {
		return 0
	}
	if len(arr) == 1 {
		return 1
	}

	length := len(arr)
	num := 1
	for i, tmp := 1, arr[0]; i < length; i++ {
		if arr[i] != tmp {
			arr[num] = arr[i]
			tmp = arr[i]
			num++
		}
	}
	return num
}

// 无论中间多少高低柱子，当前点积水量都是min(最左, 最右)高度
func savewater(arr []int) int {
	point_l := 0
	max_l := arr[0]

	point_r := len(arr) - 1
	max_r := arr[len(arr)-1]

	volume := 0
	for point_l < point_r {
		if max_l < max_r {
			point_l++
			if max_l < arr[point_l] {
				max_l = arr[point_l]
			} else {
				volume = volume + max_l - arr[point_l]
			}
		} else {
			point_r--
			if max_r < arr[point_r] {
				max_r = arr[point_r]
			} else {
				volume = volume + max_r - arr[point_r]
			}
		}
	}
	return volume
}

/*
	字符统计
*/
func charSum(s string) {
	sumMap := make([]int, 26)
	for _, c := range s {
		sumMap[c-97]++
	}
	fmt.Print(sumMap)
}

func LastWordLen(s string) int {
	isLetter := func(c uint8) bool {
		if (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') {
			return true
		} else {
			return false
		}
	}
	length := len(s)
	if length < 1 {
		return 1
	}
	pos := length - 1
	for pos >= 0 {
		if isLetter(s[pos]) {
			break
		} else {
			pos--
		}
	}
	retLen := 0
	for pos >= 0 {
		if !isLetter(s[pos]){
			break
		} else {
			pos--
			retLen++
		}
	}
	return retLen
}

/*
	翻转词序
*/
func ReverseWords(s []rune) {
	reverse := func(start int, end int) {
		for start < end {
			s[start], s[end] = s[end], s[start]
			start++
			end--
		}
	}

	if s == nil || len(s) <= 1 {
		return
	}
	n := len(s)
	i := 0
	for i < n {
		j := i
		for j < n {
			if s[j] == ' ' {
				break
			} else {
				j++
			}
		}
		reverse(i, j-1)
		for j < n && s[j] == ' ' {
			j++
		}
		i = j
	}
	reverse(0, n-1)
}

const ALPHABET_LENGHT = 26
/*
	是否同字异序, 如eel, lee
*/
func Anagram(source string, target string) bool {
	if len(source) != len(target) {
		return false
	}
	length := len(source)
	table1 := make([]int, ALPHABET_LENGHT)
	table2 := make([]int, ALPHABET_LENGHT)

	for i := 0; i < length; i++ {
		table1[source[i]-'a']++
		table2[target[i]-'a']++
	}
	for i := 0; i < ALPHABET_LENGHT; i++ {
		if table1[i] != table2[i] {
			return false
		}
	}
	return true
}

/*
	题目解释：原题的意思就是用一个新的字符串描述上一个字符串，用数字表示上一个：
	当n=1时：输出1；
	当n=2时，解释1，1读作1个 ，表示为11；
	当n=3时，解释上一个11，读作2个1，表示为21；（注意相同数字的描述）
	当n=4时，解释上一个21，读作1个2，一个1，表示为1211；
	当n=5时，解释上一个1211，读作1个1，1个2，2个1，表示为111221；
	当n=6时，解释上一个111221，读作3个1，2个2，1个1，表示为312211；

	时间 n^3, 空间 n^2, n是输入的值
*/
func CountAndSay(n int) string {
	if n <= 0 {
		return ""
	}
	if n == 1 {
		return "1"
	}
	if n == 2 {
		return "11"
	}
	s := "11"
	result := ""
	for i := 3; i <= n; i++ {
		temp := s[0]
		count := 1
		for j := 1; j < len(s); j++ { // len的时间复杂度在for中越来越接近n^2
			if s[j] == temp {
				count++
			} else {
				// result的长度越来越接近n^2
				result += strconv.Itoa(count) + strconv.Itoa(int(temp-48))
				count = 1
				temp = s[j]
			}
		}
		result += strconv.Itoa(count) + strconv.Itoa(int(temp-48))
		s = result
		result = ""
	}
	return s
}

/*
	回文
*/
func IsPalindrome(s string) bool {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}

/*
	回文数
	1. 计算位
	2. 循环到half
	2.1 判断高低位余数。
		如 num = 12321, 则 t = 10000
		第一步 1 == (12321 / 10000) % 10 == 12321 % 10
		t /= 10 , 12321 /= 10
		第二步 2 == (12321 ／ 1000) % 10 == 1232 % 10
		判断成功
*/
func IsPalindromeNum(num int) bool {
	if num < 10 {
		return true
	}

	countWei := func() int {
		num := num
		count := 0
		for num > 0 {
			num /= 10
			count++
		}
		return count
	}

	wei := countWei()
	t := math.Pow(10, float64(wei-1))
	half := wei / 2
	n := num
	for i := 0; i < half; i++ {
		if (num/int(t))%10 == n%10 {
			t /= 10
			n /= 10
		} else {
			return false
		}
	}
	return true
}
/*
	最长回文子串

	时间 n^3
*/
func LongestPalindrome(s string) string {
	isPalindrome := func(start int, end int) bool {
		for start < end {
			if s[start] != s[end] {
				return false
			}
			start++
			end--
		}
		return true
	}

	length := len(s)
	from, to, max := 0, 0, 0
	for i := 0; i < length; i++ {
		for j := i; j < length; j++ {
			if isPalindrome(i, j) && (j-i) > max {
				from, to = i, j
				max = to - from
			}
		}
	}

	return s[from : to+1]
}

/*
	中心扩展法

	1 循环所有元素i（i为中心）
	2 循环向两边扩展 start, end。(start=i, end=i+1查找偶数串)
	2.1 记录left, right回文子串
	3 记录此i中心边缘子串是否最大
	*2 ..(start=i-1, end=i+1查找奇数串)
	*3 ..

	时间 n^2，空间 1
 */
func LongestPalindrome2(s string) string {
	maxLeft, maxRight, max := 0, 0, 1
	length := len(s)
	for i := 0; i < length; i++ {
		start, end, length1 := i, i+1, 0
		left, right := start, end
		for start >= 0 && end < length {
			if s[start] == s[end] {
				left, right, length1 = start, end, length1+2
				start, end = start-1, end+1
			} else {
				break
			}
		}
		if length1 > max {
			maxLeft, maxRight, max = left, right, length1
		}

		start, end, length1 = i-1, i+1, 1
		left, right = start, end
		for start >= 0 && end < length {
			if s[start] == s[end] {
				left, right, length1 = start, end, length1+2
				start, end = start-1, end+1
			} else {
				break
			}
		}
		if length1 > max {
			maxLeft, maxRight, max = left, right, length1
		}
	}
	return s[maxLeft : maxRight+1]
}

/*
	模式匹配，brute force法
	时间 m*n，空间1
*/
func BruteForce(s string, matcher string) int {
	m := len(s)
	n := len(matcher)
	for i := 0; i < m; i++ {
		count := 0
		for j := 0; j < n && i+j < m; j++ {
			if s[i+j] != matcher[j] {
				break
			} else {
				count++
			}
		}
		if count == n {
			return i
		}
	}
	return -1
}

/*
	时间m+n
*/
func KMP() {

}

/*
    检测方向 -> 走 -> 递归 -> 回退
*/
const (
	UP = iota
	DOWN
	LEFT
	RIGHT
)

const MAX = 10

type Direction int

var m = [MAX][MAX]int{
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
	{1, 0, 0, 0, 1, 0, 1, 1, 1, 1},
	{1, 0, 1, 0, 1, 0, 1, 1, 1, 1},
	{1, 0, 1, 0, 0, 0, 0, 0, 1, 1},
	{1, 0, 1, 0, 1, 1, 0, 1, 1, 1},
	{1, 0, 1, 0, 0, 1, 0, 1, 1, 1},
	{1, 0, 1, 1, 0, 1, 0, 0, 0, 1},
	{1, 0, 1, 1, 1, 1, 1, 1, 0, 1},
	{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
	{1, 0, 1, 1, 1, 1, 1, 1, 0, 1},
}

func printM() {
	emt := " #R"
	print(" ")
	for j := 0; j < MAX; j++ {
		fmt.Printf(" %d", j)
	}
	fmt.Println()
	for i := 0; i < MAX; i++ {
		fmt.Printf("%d", i)
		for j := 0; j < MAX; j++ {
			fmt.Printf("%c ", emt[m[i][j]])
		}
		fmt.Println()
	}
}
func move(x *int, y *int, d Direction) {
	switch d {
	case UP:
		*x--
		break
	case DOWN:
		*x++
		break
	case LEFT:
		*y--
		break
	case RIGHT:
		*y++
		break
	}
}

func inspect(x int, y int, d Direction) bool {
	move(&x, &y, d)
	if x < 0 || y < 0 || x >= MAX || y >= MAX || m[x][y] != 0 {
		return false
	}
	return true
}

func printProcess(n int) {
	fmt.Printf("步数:%d\n", n)
	printM()
}

func maze(s [2]int, e [2]int, n int) {
	if s[0] == e[0] && s[1] == e[1] {
		printProcess(n)
	}
	for i := Direction(0); i < 4; i++ {
		if inspect(s[0], s[1], i) {
			tmpX, tmpY := s[0], s[1]
			move(&tmpX, &tmpY, i)

			m[tmpX][tmpY] = 2
			maze([2]int{tmpX, tmpY}, e, n+1)
			m[tmpX][tmpY] = 0
		}
	}
}

func main() {
	s, e := [2]int{9, 1}, [2]int{9, 8}
	m[s[0]][s[1]] = 2
	maze(s, e, 0)
	println()
}

/*
    重量不同多个小球，合并用力为重量和。两两合并到剩一个，总用力最小。写代码求最优

    公式 max[n] = max[n-1] + min2(arr)
    每次捏重量最小两球，都达到全局最优
*/
func cutMin(arr []int) (int, []int) {
	min := 0
	for ind := range arr {
		if arr[ind] < arr[min] {
			min = ind
		}
	}
	v := arr[min]
	return v, append(arr[:min], arr[min+1:]...)
}

func pinch(arr []int) int {
	if len(arr) == 1 {
		return 0
	}
	v1, arr := cutMin(arr)
	v2, arr := cutMin(arr)
	return v1 + v2 + pinch(append(arr, v1+v2))
}

func main() {
	print(pinch([]int{2, 3, 1, 4}))
}

/*
    统计二进制串置位(位值是1)数

    8位全1数为255, 缓存0-255数的置位数到pc。值为0,1,1,2,1,2,...
    byte()会截断8位，如byte(256) = 0
    byte(x>>(0*8))得到x低8位截断数值，byte(x>>(1*8))得到x低9-16位截断数值
    累加8段数值在pc中映射的置位数，得到x的置位数

    时间 n/8
*/
func Count(x uint64) int {
    var pc [256]byte
	for i := range pc {
		pc[i] = pc[i/2] + byte(i&1)
	}
	count := int(pc[byte(x>>(0*8))] +
        pc[byte(x>>(1*8))] +
        pc[byte(x>>(2*8))] +
        pc[byte(x>>(3*8))] +
        pc[byte(x>>(4*8))] +
        pc[byte(x>>(5*8))] +
        pc[byte(x>>(6*8))] +
        pc[byte(x>>(7*8))])
    return count
}