1.在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：

• 数组排序后找到重复数字，排序数组时间复杂度O(nlogmn)。
• 遍历数组建立哈希表，key存数组中的值，value存数组中值出现的次数。
• 遍历数组，当遍历到下标为i的数字（m）时，比较下标为i的数字是否等于i，如果不相等且下标m的数字和数字m相等则找到一个重复数字；如果不相等且下标m的数字和数字m不相等则互换数据；如果相等则扫描下一个数字。

代码：

func isExist(numbers []int, number int) bool {
	for _, value := range numbers {
		if value == number {
			return true
		}
	}
	return false
}
func duplicate(numbers []int) (bool, []int) {
	length := len(numbers)
	if length == 0 || numbers == nil {
		return false, nil
	}
	repeats := make([]int, 0)
	for _, value := range numbers {
		if value < 0 || value > length -1 {
			return false, nil
		}
	}
	for index, value := range numbers {
		for index != value {
			if value == numbers[value] {
				if !isExist(repeats, value) {
					repeats = append(repeats, value)
					break
				}
			}
			numbers[index], numbers[value] = numbers[value], numbers[index]
			break
		}
	}
	return true, repeats
}

2.在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：

• 首先选取数组中右上角额数字，如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列，如果该数字小于要查找的数字，则剔除这个数字所在的行，也就是说，如果要查找的数字不在数组的右上角，则每次都在数组的查找范围中删除一行或一列，这样每一步都可以缩小查找范围，直到找到要查找的数字或者范围为空。

代码：

func find(array [][]int, target int, rows int, columns int) bool {
	isFind := false
	if array == nil || rows <= 0 || columns <=0 {
		return isFind
	}
	row := 0
	column := columns -1
	for column >= 0 && row < rows {
		if array[row][column] == target {
			isFind= !isFind
			return isFind
		} else if array[row][column] > target {
			column--
		} else {
			row++
		}
	}
	return isFind
}

3.请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：

• 扫描字符串，碰到空格就替换，后面字节后移2字节。
• 计算替换后的总长度：原来的长度+2*空格数，从右向左遍历，遇到空格替换成“20%”，其余替换成原数组的位置。

代码：

func replaceBlank(strs []byte) []byte {
	length := len(strs)
	if length <= 0 || strs == nil {
		return nil
	}

	blankNum := 0
	for _, value := range strs {
		if value == ' ' {
			blankNum++
		}
	}

	newLength := length + 2 * blankNum
	j := newLength -1
	newStr := make([]byte, newLength)
	for i := length - 1; i >= 0; {
		if strs[i] == ' ' {
			newStr[j] = '0'
			j--
			newStr[j] = '2'
			j--
			newStr[j] = '%'


		} else {
			newStr[j] = strs[i]
		}
		j--
		i--
	}
	return newStr
}

4.输入一个链表，按链表从尾到头的顺序返回一个ArrayList

思路：

• 使用栈，遍历链表压栈，出栈打印。
• 递归实现，递归本质就是栈。

代码：

func printList(mElement *list.Element) {
	if mElement == nil {
		return
	}
	printList(mElement.Next())
	fmt.Println(mElement.Value)
}

5.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：

• 前序遍历的第一个数字1为根节点的值，中序遍历1左面的数为左子树；1右面的数为右子树。
• 递归调用建立二叉树。

代码：

package main

import (
    "fmt"
)

// 重建二叉树

type Node struct {
    value int64
    left *Node
    right *Node
}

func main() {
    preOrder := []int64{1,2,4,7,3,5,6,8}
    inOrder := []int64{4,7,2,1,5,3,8,6}

    tree := constructBTree(preOrder, inOrder)
    
    //将构建好的二叉树 输出先序遍历和中序遍历的结果 用于检验
    preCatTree(tree)
    inCatTree(tree)
}

//重建二叉树
func constructBTree(preOrder, inOrder []int64) *Node{
    l := len(preOrder)
    if l == 0{
        return nil
    }

    root := &Node{
        value:preOrder[0],
    }
    if l == 1{
        return root
    }

    leftLen := 0
    rightLen := 0
    for _,v := range inOrder{
        if v == root.value{
            break
        }
        leftLen++ //根节点之前的为左子树长度
    }
    rightLen = l - leftLen - 1 //右子树长度

    if leftLen > 0{
        //fmt.Println("左子树",preOrder[1:leftLen+1], inOrder[0:leftLen]) //可打开注释查看详细过程
        root.left = constructBTree(preOrder[1:leftLen+1], inOrder[0:leftLen])
    }
    if rightLen >0{
        //fmt.Println("右子树",preOrder[leftLen+1:], inOrder[leftLen+1:])
        root.right = constructBTree(preOrder[leftLen+1:], inOrder[leftLen+1:])
    }

    return root
}


func preCatTree(t *Node) {
    fmt.Println(t.value)
    if t.left!=nil{
        preCatTree(t.left)
    }
    if t.right!=nil{
        preCatTree(t.right)
    }
}
func inCatTree(t *Node) {
    if t.left!=nil{
        inCatTree(t.left)
    }
    fmt.Println(t.value)
    if t.right!=nil{
        inCatTree(t.right)
    }
}

6.给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：

• 如果有右子树，下一节点是右子树的最左子节点。
• 如果没有右子树，且该节点是父节点的左子节点，下一节点是父节点。
• 如节点既没有右子树，并且是父节点的右子节点；沿父亲节点向上遍历，直到找到一个是它父节点的左节点的节点，如果节点存在，该节点的父节点就是要找的节点。

代码：

func getNextNode (pNode *Node) *Node{
	if pNode == nil {
		return nil
	}

	var pNext *Node
	if pNode.right != nil {
		pRight := pNode.right
		for pRight.left != nil {
			pRight = pRight.left
		}
		pNext = pRight
	} else {
		for pNode.parent != nil {
			if pNode == pNode.parent.left {
				pNext = pNode.parent
			} else {
				pNode = pNode.parent
			}
		}


	}

	return pNext
}

7.用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型

type MyQueue struct {
	InStack []interface{}
	OutStack []interface{}
}

func initQueue() *MyQueue{
	return &MyQueue{
		InStack:make([]interface{}, 0),
		OutStack:make([]interface{}, 0),
	}
}

func (queue *MyQueue)Push(data interface{}) {
	queue.InStack = append(queue.InStack, data)
}

func (queue *MyQueue)Pop() interface{} {
	outQueueLength := len(queue.OutStack)
	if outQueueLength > 0 {
		data := queue.OutStack[outQueueLength -1]
		queue.OutStack = queue.OutStack[:outQueueLength -1]
		return data
	}

	inQueueLength := len(queue.InStack)
	if inQueueLength > 0 {
		for i := inQueueLength; i > 0; i-- {
			queue.OutStack = append(queue.OutStack, queue.InStack[i -1])
			queue.InStack = queue.InStack[:i-1]
		}
		data := queue.OutStack[len(queue.OutStack) -1]
		queue.OutStack = queue.OutStack[:len(queue.OutStack) -1]
		return data
	}

	return nil
}

8.大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

递归：

func fibonacci(n int) int{
	if n <= 0 {
		return 0
	}
	if n ==1 {
		return 1
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

非递归：

func fibonacci(n int) int{
	if n <= 0 {
		return 0
	}
	if n ==1 {
		return 1
	}

	a, b := 0, 1
	for i := 2; i < n; i ++ {
		c := a + b
		a = b
		b = c
	}
	return a + b
}

9.把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思考：

 

• 计算数组是排序的，再线性地查找就显得不高效了。排序数组，自然要想到二分查找。只是这里的操作和常规二分查找不同。
• 二分查找的 mid 如果落在左半边，那么就 lo=mid+1，如果落在右半边，就减小 hi=mid。不断缩小范围，最终，lo 一定会掉到最低点。
• 但是要如何判断 mid 落在那一边呢。因为左半边 >= 右半边，如果原数组是严格递增的，你可以说，当 a[mid] > a[0] 那就是左半边。但是考虑下面这幅图：

 

 

• 如果原数组只有开始部分递增，之后很长一段都是平坦的，那么旋转后可能是上图的样子。a[mid] == a[lo] == a[hi]，根本没法判断 mid 在那边。解决的方法很简单：

1 2 3 4

while(a[lo] == a[hi]){     ++lo;     --hi; }

• 这样操作以后，一定有 a[lo] > a[hi]，一旦 lo 掉到了最低点，这个条件就不成立了。判断 mid 在左在右也很简单了，如果 a[mid] >= a[lo] 那就是左边。如果 a[mid] <= a[hi] 那就是右边。
• 如果在左边，那就 lo=mid+1，这样把 lo 向右边推进。如果在右边，为了避免 hi 爬到了左边去 hi=mid 即可。最终终止条件，就是 lo 落到了最低点。

代码：

func minNumberInRotateArray(arrays []int) int {
	length := len(arrays)
	if length <= 0 {
		return 0
	}
	low := 0
	high := length -1
	for arrays[low] == arrays[high] {
		low++
		high--
	}

	for arrays[low] > arrays[high] {
		mid := (low + high) / 2
		if arrays[low] <= arrays[mid] {
			low = mid +1
		} else if arrays[mid] <= arrays[high]{
			high = mid
		}
	}
	return arrays[low]
}

10.给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

代码：

func power(base float64, exponent int) float64 {
   result := 1.0
   //指数为0
   if exponent == 0 && base != 0 {
      return 1
   }
   //指数为负
   if exponent < 0 && base != 0 {
      for ; exponent != 0; exponent++ {
         result *= base
      }
      result = 1 / result
      return result
   }
   //指数为正
   if exponent > 0 {
      for ; exponent != 0; exponent-- {
         result *= base
      }
      return result
   }
   return -1
}

11.输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，打印1,2,3一直到最大的3位数即999。

思路：

• 不考虑n的范围，直接打印。
• 如果n很大，能表示范围超出了int 或者long long的范围，那么就需要考虑大数问题。最常用也是最容易的方法就是用字符串或者数组来表示大数。

代码：

func Print1ToMaxOfDigits(n int) {
	//附负数就退出
	if n <= 0 {
		return
	}

	number := make([]int, n)
	for i := 0; i < 10; i++ {
		//高位设置为0
		number[0] = i
		//低位从0-9设置一遍
		print1ToMaxOfDigitsRecursively(number, n, 0)
	}
}

func print1ToMaxOfDigitsRecursively(number []int, length int, index int) {
	//判断当前位是否是最后一位，是的话就输出
	if index == length-1 {
		printNumber(number)
		return
	}

	//如果不是最后一位，则需要跳到下一位并从0到9设置，如果下一位满9则高位加1
	for i := 0; i < 10; i++ {
		//当前位下一位设置为0
		number[index+1] = i
		//将当前位从0-9设置一遍
		print1ToMaxOfDigitsRecursively(number, length, index+1)
	}
}

func printNumber(number []int) {
	//前面的0不打印
	index := 0
	for index < len(number) && number[index]==0 {
		index++
	}
	for index < len(number) {
		fmt.Printf("%d", number[index])
		index = index + 1
	}
	fmt.Println()
}

12.在O(1)时间内删除链表节点。

思路：

可以将删除节点的后下一个节点的内容复制到删除节点，即覆盖原有内容，然后删除删除节点的下一个节点。

13.请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

思路：

• 首先，考虑特殊情况：

1.  两个字符串都为空，返回true
2.  当第一个字符串不空，而第二个字符串空了，返回false（因为这样，就无法匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成功的，比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次，所以有可能匹配成功）

• 之后就开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。但考虑到pattern 下一个字符可能是‘*’， 这里我们分两种情况讨论：pattern下一个字符为‘*’或 不为‘*’：

1.  pattern下一个字符不为‘*’：这种情况比较简单，直接匹配当前字符。如果 匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的 “匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的当前字符为‘.’,同时str的当前字符不为‘’。
2. pattern下一个字符为‘*’时，稍微复杂一些，因为‘*’可以代表0个或多个。 这里把这些情况都考虑到：

               a>当‘*’匹配0个字符时，str当前字符不变，pattern当前字符后移两位，跳过这个‘*’符号；
               b>当‘*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符不变。（这里匹配1个或多个可以看成一种情况，                   因为：当匹配一个时，由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况a；当匹配多于一个字符                     时，相当于从str的下一个字符继续开始匹配）

•     之后再写代码就很简单了

代码：

func match(str []byte, pattern []byte) bool {
	if len(str) == 0 && len(pattern) == 0 {
		return true
	}
	if len(str) != 0 && len(pattern) == 0 {
		return false
	}
	strCount, patternCount := 0, 0
	if pattern[patternCount + 1] != 0 {
		if str[strCount] ==  pattern[patternCount] || (strCount + 1 != len(str) && pattern[patternCount] != byte('.')) {
			return match(str[strCount+1:], pattern[patternCount+1:])
		}  else {
			return false
		}
		
	} else {
		if str[strCount] ==  pattern[patternCount] || (strCount != len(str) + 1 && pattern[patternCount] != byte('.')) {
			return match(str[strCount:], pattern[patternCount+2:]) || match(str[strCount+1:], pattern[patternCount:])
		} else {
			return match(str[strCount:], pattern[patternCount+2:])
		}
	}

}

14.输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路： 

第一个标记初始化数组的第一个位置，它只向前移动； 第二个标记指向初始化数组最后一个位置，它只向后移动；在两个标记位置相遇之前，如果第一个标记指向的是偶数，第二个标记指向的是奇数，则交换这两个数字。

代码:

func recorder(data []int, f func(int) bool) {
	length := len(data)
	if length <= 0 {
		return
	}
	begin, end := 0, length -1
	for begin < end {

		//向后移动begin，直到条件结束
		for begin < end && !f(data[begin]) {
			begin++
		}
		for begin < end && f(data[end]) {
			end--
		}
		if begin < end {
			data[begin], data[end] = data[end], data[begin]
		}
	}
}


func isEven(num int) bool {
	return num & 1 == 0
}

15.输入一个链表，输出该链表中倒数第k个结点。

思路：
定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

代码：

func findKtoTail(myList list.List, k int) interface{} {
	length := myList.Len()
	if length <= 0 || k < 0 || length - k < 0 {
		return nil
	}
	fastList , lowList := myList.Front(), myList.Front()
	for i := 0; i < k; i ++ {
		fastList = fastList.Next()
	}
	for fastList != nil {
		fastList = fastList.Next()
		lowList = lowList.Next()
	}
	return lowList.Value
}

16.给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：

1.判断链表中有环 -> 2.得到环中节点的数目 -> 3.找到环中的入口节点

代码：

func EntryNodeOfLoop(head *list.Element) *list.Element {
	if head == nil {
		return nil
	}

	//1.判断链表是否有环
	flag := false
	pSlow, pFast := head, head
	for pSlow != nil && pSlow.Next() != nil {
		pSlow = pSlow.Next()
		pFast = pSlow.Next().Next()
		if pSlow == pFast {
			flag = true
			break
		}
	}
	if !flag {
		return nil
	}
	//2.计算环中节点数目
	n := 1
	pFast = pFast.Next()
	for pSlow != pFast {
		pFast = pFast.Next()
		n++
	}

	//3.找到环入口节点
	pNode1, pNode2 := head, head
	for i := 0; i < n;  i ++ {
		pNode1 = pNode1.Next()
	}
	for pNode1 != pNode2 {
		pNode1 = pNode1.Next()
		pNode2 = pNode2.Next()
	}
	return pNode1
}

17.输入一个链表，反转链表后，输出新链表的表头。

思路：

1. 保存当前节点的next节点。
2. 修改当前节点next节点为pre（初值为null，因为反转后第一个节点的next节点为null）。
3. 将当前节点存进pre。
4. 进入next节点并循环。

代码：

func ReverseList(head *list.Element) *list.Element {
	if head == nil || head.Next() == nil {
		return nil
	}
	var preNode, nextNode *list.Element
	for head != nil {
		nextNode = head.Next()
		head.Next() = preNode
		preNode = head
		head = head.Next()
	}
	return preNode
}

18.输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路：

将两个链表结点挨个进行比较，插入到一个新表中。

代码：

func merge(pHead1 *list.Element, pHead2 *list.Element) *list.Element {
	if pHead1 == nil {
		return pHead2
	} else if pHead2 == nil {
		return pHead1
	}
	var pMergeHead *list.Element
	if pHead1.Value < pHead2.Value {
		pMergeHead = pHead1
		pMergeHead.Next() = merge(pHead1.Next(), pHead2)
	} else {
		pMergeHead = pHead2
		pMergeHead.Next() = merge(pHead1, pHead2.Next())
	}
	return pMergeHead
}

19.输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：

• 先写一个方法，传入两棵根节点值相同的树，判断tree1是否和tree2结构一样。
• 再写一个方法来遍历大树，找到一个和小树根节点值相等的节点，以该节点和小树根节点的值为参数调用上面的方法即可。

代码： 

func doesTree1HasTree2(tree1 *TreeNode, tree2 *TreeNode) bool {
	if tree2 == nil {
		return true
	}
	if tree1 == nil {
		return false
	}

	if tree1.val != tree2.val {
		return false
	}
	return doesTree1HasTree2(tree1.left, tree2.left) && doesTree1HasTree2(tree1.right, tree2.right)
}

func HasSubtree(root1 *TreeNode, root2 *TreeNode) bool {
	if root2 == nil || root1 == nil {
		return false
	}
	return doesTree1HasTree2(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2)
}

20.操作给定的二叉树，将其变换为源二叉树的镜像。

思路：

交换左右子树的节点。

代码：

func Mirror(root TreeNode) {
	if root == nil {
		return
	}
	root.left, root.right = root.right, root.left
	Mirror(root.left)
	Mirror(root.right)
}

21.请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：

比较二叉树的前序遍历序列和对称前序遍历序列来判断二叉树是不是对称的。如果两个序列是一样的，那么二叉树就是对称的。

代码：

func isSymmetrical(pRoot *BinaryTreeNode) bool {
	return jude(pRoot, pRoot)
}

func jude(pRoot1 *BinaryTreeNode, pRoot2 *BinaryTreeNode) bool {
	if pRoot1 == nil && pRoot2 == nil {
		return true
	}
	if pRoot1 == nil && pRoot2 == nil {
		return false
	}
	if pRoot1.value != pRoot2.value {
		return false
	}
	return jude(pRoot1.left, pRoot2.right) && jude(pRoot1.right, pRoot2.left)
}

22.输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路：

• 循环打印，每次都是打印矩阵中的一个圈。
• 向右->向下->向左->向上->向右->向下->向左->... 

代码：

func printMatrix(array *[][]int) []int {
	if array == nil {
		return nil
	}
	arrayList := make([]int, 0)
	low, high, left, right := 0, len(*array) - 1, 0, len((*array)[0]) - 1
	for low <= high && left <= right {
		//向右
		for i := left; i <= right; i++ {
			arrayList = append(arrayList, (*array)[low][i])
		}
		//向下
		for j := low + 1; j <= high; j++ {
			arrayList = append(arrayList, (*array)[j][right])
		}
		//向左,有可能出现特殊的情况只有一行，为了避免重复访问
		if low < high {
			for i := right - 1; i >= left; i-- {
				arrayList = append(arrayList, (*array)[high][i])

			}
		}
		//向上,有可能出现特殊的情况只有一列，为了避免重复访问
		if left < right {
			for j := high - 1; j >= low + 1; j-- {
				arrayList = append(arrayList, (*array)[j][left])

			}
		}
		low++
		high--
		left++
		right--
	}
	return arrayList
}

23.定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

思路：

每次都把最小元素压入辅助栈，那么就能保证辅助栈的栈顶一直都是最小元素。当最小元素从数据栈内被弹出之后，同时弹出辅助栈的栈顶元素，此时辅助栈的新的栈顶元素就是下一个最小值。

代码：

var stackTotal,  stackLittle *list.List

func Init() {
	stackTotal = list.New()
	stackLittle = list.New()
}

func Push(data int) {
	stackTotal.PushBack(data)
	if stackLittle.Len() <=0 {
		stackLittle.PushBack(data)
	} else {
		stackPeekValue := stackLittle.Back().Value
		stackPeekInt, ok := stackPeekValue.(int)
		if ok {
			if data < stackPeekInt {
				stackLittle.PushBack(stackPeekInt)
			} else {
				stackLittle.PushBack(stackLittle.Back())
			}
		}
	}
}

func Pop() {
	stackTotal.Remove(stackTotal.Back())
	stackLittle.Remove(stackTotal.Back())
}

func Top() interface{}{
	return stackTotal.Back().Value
}

func Min() interface{}{
	return stackLittle.Back().Value
}

24.输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：

需要一个辅助栈，来模拟出入栈的过程，流程如下：

• 取压入队列的首元素，将其压入辅助栈
• 检查辅助栈顶元素是否和弹出队列的首元素相等：
  • 若相等，则辅助栈弹出栈顶元素，弹出队列取出队首元素，重复检查
  • 若不相等，回到第一步

最后，检查辅助栈和弹出队列是否均为空。

代码：

func IsPopOrder(stackA []int, stackB []int) bool {
	stackTemp := list.New()
	count := 0
	for i := 0; i < len(stackA); i++ {
		stackTemp.PushBack(stackA[i])
		for stackTemp.Len() > 0 && reflect.DeepEqual(stackTemp.Back().Value, stackB[count]) {
			stackTemp.Remove(stackTemp.Back())
			count++
		}
	}
	return count == len(stackA)
}

25.从上往下打印出二叉树的每个节点，同层节点从左至右打印。 

思路：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

代码：

func PrintFromTopToBottom(pTreeRoot *BinaryTreeNode) {
	if pTreeRoot == nil {
		return
	}
	queueOfList := list.New()
	queueOfList.PushBack(pTreeRoot)
	for queueOfList.Len() > 0 {
		pNode := queueOfList.Front()
		queueOfList.Remove(queueOfList.Front())
		fmt.Println(pNode.Value)
		if pTreeRoot.pLeft != nil {
			queueOfList.PushBack(pTreeRoot.pLeft)
		}
		if pTreeRoot.pRight != nil {
			queueOfList.PushBack(pTreeRoot.pRight)
		}
	}
}

26.输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路：

当前用前序遍历的方式访问到某一节点时，我们把该节点添加到路径上，并累加该节点的值。如果该节点为叶节点，并且路径中节点值的和刚好等于输入的整数，则该路径符合要求。如果当前节点不是叶子节点，则继续访问它的子节点，当前访问结束后，递归函数继续调用回到它的父节点，在函数退出前删除当前节点并减去当前节点的值。

代码：

func FindPath(pRoot *BinaryTreeNode, expectedSum int) []int {
	if pRoot == nil {
		return nil
	}

	path.PushBack((*pRoot).value)
	expectedSum -= (*pRoot).value
	if expectedSum == 0 && pRoot.pLeft == nil && pRoot.pRight == nil {
		pathList = append(pathList, (*pRoot).value)

	}
	FindPath(pRoot.pLeft, expectedSum)
	FindPath(pRoot.pRight, expectedSum)
	path.Remove(path.Back())
	return pathList
}

27.输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：

• 从旧链表中创建新链表，不处理新节点的特殊指针。
• 处理新新链表的特殊指针。
• 从旧链表中拆分新链表。

代码：

type ComplexListNode struct {
	value int
	next *ComplexListNode
	sibling *ComplexListNode
}

func Clone(pHead *ComplexListNode) *ComplexListNode{
	if pHead == nil {
		return nil
	}
	currentNode := pHead
	//1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
	for currentNode != nil {
		nextNode := currentNode.next
		cloneNode := &ComplexListNode{
			value:currentNode.value,
			next:currentNode.next,
			sibling:currentNode.sibling,
		}
		currentNode.next = cloneNode
		cloneNode.next = nextNode
		currentNode = nextNode
	}
	//2、重新遍历链表，复制老结点的随机指针给新结点，如A1.sibling = A.sibling.next;
	currentNode = pHead
	for currentNode != nil {
		if currentNode == nil {
			currentNode.next.sibling = nil
		} else {
			currentNode.next.sibling = currentNode.sibling.next
		}
	}
	//3、拆分链表，将链表拆分为原链表和复制后的链表
	currentNode = pHead
	pCloneList := pHead.next
	for currentNode != nil {
		cloneNode := currentNode.next
		currentNode.next = cloneNode.next
		if cloneNode.next != nil {
			cloneNode.next = cloneNode.next.next
		} else {
			cloneNode.next = nil
		}
		currentNode = currentNode.next
	}
	return pCloneList
}

28.输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：

• 虽然不能创建新的结点，但可以利用额外的数据结构来存储
• 二叉排序树：左孩子 < 根结点 < 右孩子，所以根据中序遍历，左中右，可以遍历到一个有序的序列

       那么：

• 第一步：利用递归 / 非递归中序遍历，存在一个数组 or 一个队列
• 第二部：更新队列里的结点的 left and right 两个字段的引用，连成一条链表

代码：

func convertNode(pNode *BinaryTreeNode, pLastNode **BinaryTreeNode) {
	if pNode == nil {
		return
	}
	pCurrent := pNode
	if pCurrent.pLeft != nil {
		convertNode(pCurrent.pLeft, pLastNode)
	}
	pCurrent.pLeft = *pLastNode
	if *pLastNode != nil {
		(*pLastNode).pRight = pCurrent
	}
	*pLastNode = pCurrent
	if  pCurrent.pRight != nil {
		convertNode(pCurrent.pRight, pLastNode)
	}
}

func convert(pRoot *BinaryTreeNode) *BinaryTreeNode{
	var pLastNode *BinaryTreeNode
	convertNode(pRoot, &pLastNode)
	//此时，pLastNode指向为尾节点，需要指向头节点
	pFirstNode := pLastNode
	for pFirstNode != nil && pFirstNode.pLeft != nil {
		pFirstNode = pFirstNode.pLeft
	}
	return pFirstNode
}

29.请实现两个函数，分别用来序列化和反序列化二叉树。二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

代码：

func Serialize(pRoot *BinaryTreeNode, pString string)  {
	if pRoot == nil {
		pString += "$"
		return
	}
	pString += strconv.Itoa(pRoot.value) + ","
	Serialize(pRoot.pLeft, pString)
	Serialize(pRoot.pRight, pString)
}

var index int = -1
func Deserialize(pString string) *BinaryTreeNode{
	if pString == "" {
		return nil
	}
	index++
	if string(pString[index]) != "$" {
		node := &BinaryTreeNode{
			value:int(pString[index]),
		}
		node.pLeft = Deserialize(pString)
		node.pRight = Deserialize(pString)
		return node
	}
	return nil
}

30.输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路：

• 递归法，问题转换为先固定第一个字符，求剩余字符的排列；求剩余字符排列时跟原问题一样。
• 遍历字符串，固定可能出现在第一个位置的字符，作为第一个字符，后面剩下的字符串的组合用递归使用本函数的方式得到。

代码：

func Permutation(pString string) {
	if pString == "" {
		return
	}
	PermutationHelp(&pString, &pString)
}

func PermutationHelp(pString *string, pBegin *string) {
	if len(*pBegin) == 0 {
		fmt.Println(*pString)
	} else {
		for _, value := range *pBegin {
			sByte := []byte(*pBegin)
			sByte[0] , value = uint8(value), int32(sByte[0])
			newStr := (*pBegin)[1:]
			PermutationHelp(pString, &newStr)
			sByte1 := []byte(*pBegin)
			sByte1[0] , value = uint8(value), int32(sByte1[0])
		}
	}
}

31.数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：
用preValue记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count--，减到0的时候就要更换新的preValue值了，因为如果存在超过数组长度一半的值，那么最后preValue一定会是该值。

代码：

func MoreThanHalfNum(array []int) int {
	length := len(array)
	if array == nil || length <= 0 {
		return 0
	}
	preValue , count := array[0], 0
	for _, value := range array {
		if value == preValue {
			count++
		} else {
			count--
			if count < 0 {
				preValue = value
			}
		}
	}

	//判断是否是大于一半的那个数
	num := 0
	for _, value := range array {
		if value == preValue {
			num++
		}
	}
	if num > length / 2 {
		return preValue
	}
	return 0
}

32.如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路：

数据流小于大根堆根节点则插入大根堆，否则插入小根堆，这样大根堆维护小的那一半，小根堆维护大的那一半。

代码：

func Insert(num int) {
	if bigRootQueue.empty() || num <= bigRootQueue.top() {
		bigRootQueue.push(num)
	} else {
		littleRootQueue.push(num)
	}

	if bigRootQueue.size() > littleRootQueue.size() + 1 {
		littleRootQueue.push(bigRootQueue.top())
		bigRootQueue.pop()
	}
	if (littleRootQueue.size() > bigRootQueue.size()) {
		bigRootQueue.push(littleRootQueue.top())
		littleRootQueue.pop()
	}
}

func GetMedian() float64 {
	len := littleRootQueue.size() + bigRootQueue.size()
	if len % 2 {
		return float64(bigRootQueue.top())
	} else {
		return float64(bigRootQueue.top() + littleRootQueue.top() / 2)
	}
}

33.求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

思路：

根据当前位置为各位1 十位10 百位100等 来计算

• 如果当前位为0，则1的个数仅有高位来计算=高位*当前位
• 如果当前位为1，则=高位*当前位+低位+1
• 如果当前位为2-9：则=（高位+1）*当前位

func NumOf1Between1AndN(num int) int {
	current, before, after, count := 0, 0, 0, 0
	i := 1
	for num / i != 0 {
		//计算当前位、高位、低位
		current = (num / i) & 10
		before = num / (i * 10)
		after = num - (num / i) * i
		if current == 0 {
			count += before * i
		} else if current == 1 {
			count = count + before*i + after + 1
		} else {
			count = count + (before + 1) * i
		}
		i = i * 10
	}
	return count
}

34.输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路：
将数组中的数字连接起来，排成一个最小的数字。将'大数'往后放'小数'往前放，如何定义'大数'和'小数'？比如说有两个数a和b，如果ab>ba则a是'大数'b是'小数'，要排成ba。于是，这道题目变成了一个排序问题，将能把组合出来的数字变大的数字往后排。我们这里需要自己定义一个比大小的比较方法。

代码：

func PrintMinNumber(numbers  []int) string {
	if numbers == nil || len(numbers) == 0 {
		return ""
	}
	length := len(numbers)
	for i := 0; i < length; i++ {
		for j := i + 1; j < length; j++ {
			 str1 := strconv.Itoa(numbers[j]) + strconv.Itoa(numbers[i])
			 str2 := strconv.Itoa(numbers[i]) + strconv.Itoa(numbers[j])
			num1,_:=strconv.Atoi(str1)
			num2,_:=strconv.Atoi(str2)
			 if  num1 > num2 {
			 	numbers[j], numbers[i] = numbers[i], numbers[j]
			}
		}
	}
	str := ""
	for value, _ := range numbers {
		str += strconv.Itoa(value)
	}
	return str
}

35.把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路：

• 定义一个resualt数组保存的是从小到大的丑数。
• 定义3个指针p2,p3,p5 resualt[p2] resualt[p3] resualt[p5]分别对应*2 *3 *5能得到的最小的数。
• 这3者取最小就是下一位置上的丑数。

代码：

func min(number1, number2, number3 int) int {
	var min int
	if number1 < number2 {
		min = number1
	} else {
		min = number2
	}
	if min >= number3 {
		min = number3
	}
	return min
}
func GetUglyNumber(index int) int {
	if index <= 0 {
		return 0
	}
	resualt := make([]int, 0)
	resualt[0] = 1
	p2, p3, p5 := 0, 0, 0
	for i := 0; i < index; i++ {
		resualt[i] = min(resualt[p2] * 2, resualt[p3] * 3, resualt[p5] * 5)
		if resualt[i] == resualt[p2] * 2 {
			p2++
		}
		if resualt[i] == resualt[p3] * 3 {
			p3++
		}
		if resualt[i] == resualt[p5] * 5 {
			p5++
		}
	}
	return resualt[index -1]
}

36.在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它, 如果没有则返回 -1（需要区分大小写。

思路：使用hash，先统计出现次数，再返回index。

func FirstNotRepeatingChar(strs string) string {

	if len(strs) == 0 {
		return ""
	}
	count := make([] int, 256)
	for _, value := range strs {
		count[value]++
	}
	for _, value := range count {
		if value == 1 {
			return string(strs[value])
		}
	}
	return ""
}

37.在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。

思路：

• 二路归并即merge，是将两个有序的序列合并为一个有序的序列，在两个子序列left、right合并过程中，当left中当前元素A小于right中当前元素B时，因为right序列已经有序，所以不用比较，A一定是left、right两个子序列当前剩余元素中最小的元素，这省去了A与B后其他元素比较的操作。
• [A，B]中的逆序对=[A]的逆序对+[B]中的逆序对+将A，B混排在一起的逆序对。

代码：

var count int = 0
func MergeSort(array []int, start, end int) {
	if start >= end {
		return
	}
	mid := (start + end) / 2
	MergeSort(array, start, mid)
	MergeSort(array, mid, end)
}

func MergeOne(array []int, start, mid, end int) {
	temp := make([]int, end - start + 1)
	k, i, j := 0, start, mid + 1
	for i <= mid && j <= end {
		//如果前面的元素小于后面的元素，不能构成逆序对
		if array[i] <= array[j] {
			temp[k] = array[i]
			k++
			i++
		} else {
			k++
			j++
			//前面元素大于后面的，那么前面元素都能和后面元素组成逆序对
			count = count + (mid - i + 1)
		}
	}
	for i <= mid {
		temp[k] = array[i]
		k++
		i++
	}
	for j <= end {
		temp[k] = array[j]
		k++
		j++
	}
	for l := 0; l < k; l++ {
		array[start + l] = temp[l]
	}
}
 func InversePairs(array [] int) int {
	 MergeSort(array, 0, len(array) - 1)
	 return count
 }

38.输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的） 

思路：
双指针法。创建两个指针p1和p2,分别指向两个链表的头结点，然后依次往后遍历。如果某个指针到达末尾，则将该指针指向另一个链表的头结点；如果两个指针所指的节点相同，则循环结束，返回当前指针指向的节点。比如两个链表分别为：1->3->4->5->6和2->7->8->9->5->6。短链表的指针p1会先到达尾部，然后重新指向长链表头部，当长链表的指针p2到达尾部时，重新指向短链表头部，此时p1在长链表中已经多走了k步(k为两个链表的长度差值)，p1和p2位于同一起跑线，往后遍历找到相同节点即可。其实该方法主要就是用链表循环的方式替代了长链表指针先走k步这一步骤。

代码：

func FindFirstCommonNode(pHead1 *list.Element, pHead2 *list.Element) *list.Element {
	if pHead1 == nil || pHead2 == nil {
		return nil
	}
	p1, p2 := pHead1, pHead2
	for p1.Value != p2.Value {
		if p1.Next() == nil {
			p1 = pHead2
		} else {
			p1 = p1.Next()
		}
		if p2.Next() == nil {
			p2 = pHead1
 		} else {
 			p2 = p2.Next()
		}
	}
	return p1
}

39.统计一个数字在排序数组中出现的次数。

思路：

二分查找要找到数的位置，向前向后遍历。

代码：

func Find(array []int, value int) int {
	left, right, mid := 0, len(array) - 1, -1
	for left <= right {
		mid = (left + right) / 2
		if value == array[mid] {
			return mid
		} else if value > array[mid] {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

func GetNumberOfK(array []int, value int) int {
	count := 0
	if len(array) <= 0 {
		return count
	}
	index := Find(array, value)
	if index < 0 {
		return 0
	}
	count++
	for i := index + 1; i < len(array) && array[i] == value; i++ {
		count++
	}
	for j := index - 1; j >= 0 && array[j] == value; j-- {
		count++
	}
	return count
}

40.给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

思路：

树的中序遍历是正好是数组的从小到大排序，计数。

代码：

func KthNode(pRoot *BinaryTreeNode, k int) *BinaryTreeNode {
	if pRoot == nil {
		return nil
	}
	return dfs(pRoot, k)
}

func dfs(pRoot *BinaryTreeNode, k int) *BinaryTreeNode {
	var target *BinaryTreeNode = nil

	//走到了最左边结点,到空不继续递归，该节点左右走完了回溯上一层
	if pRoot.pLeft != nil {
		target = dfs(pRoot.pLeft, k)
	}

	if target == nil {
		if k == 1 {
			target = pRoot
		}
		k--
	}

	if target == nil && pRoot.pRight != nil {
		target = dfs(pRoot.pRight, k)
	}
	return target
}

41.输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

思路：

• 如果根节点只有左子树没有右子树，树的深度为左子树的深度+1；
• 如果根节点只有右子树，没有左子树，树的深度为右子树的深度+1；
• 如果既有左子树又有右子树，树的深度应该是其左右子树深度较大者+1。

代码：

func TreeDepth(pRoot *BinaryTreeNode) int {
	if pRoot == nil {
		return 0
	}
	left := TreeDepth(pRoot.left)
	right := TreeDepth(pRoot.right)
	if left > right {
		return left + 1
	} else {
		return right + 1
	}
}

42.一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路：

• 我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。
• 假设输入数字为{2，4，3，6，3，2，5，5}，让我们对每个数字异或之后为0010，异或得到的结果中倒数第二位是1；根据这位进行分组，第一个子数组{2，3，6，3，2}中倒数第二位是1，第二个子数组{4，5，5}中倒数第二位是0；接下载分别对这两个子数组求异或，找到第一个子数组中的6，第二个子数组中的4 。

代码：

func FindNumsAppearOnce(array []int) (int, int) {
	xor1 := 0
	for _, value := range array {
		xor1 = xor1 ^ value
	}
	//在xor1中找到第一个不同的位对数据进行分类，分类为两个队列对数据进行异或求和找到我们想要的结果
	index := 1
	for (index & xor1) == 0 {
		index = index << 1
	}
	result1, result2 := 0, 0
	for _, value := range array {
		if (index & value) == 0{
			result1 = result1 ^ value
		} else {
			result2 = result2 ^ value
		}
	}
	return result1, result2
}

43.输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

思路：

双指针，一个指针从头开始，一个从尾开始，向内移动，直到找到数字和S。

代码：

func FindNumbersWithSum(array []int, num int) []int {
	length := len(array)
	if length < 2 {
		return nil
	}
	left, right := 0, length - 1
	list := make([]int, 0)
	for left < right {
		current := array[left] + array[right]
		if current < num {
			left++
		} else if current > num {
			right--
		} else {
			list = append(list, array[left], array[right])
			break
		}
	}
	return list
}

44.新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

代码：

func reverseWords(s string) string {
	var ret []string
	//strings.TrimSpace(s) 去除字符串前后的空格
	//strings.Split 分割字符串存为一个[]string
	slice:=strings.Split(strings.TrimSpace(s)," ")
	//字符串翻转
	for i := 0; i < len(slice) - 1; i++{
		slice[i], slice[len(slice)-1-i] = slice[len(slice)-1-i], slice[i]
	}
	//遍历翻转后的字符串，将不为""的字符串加入 ret 字符串切片中
	for i,_:=range slice{
		if slice[i] !="" {
			ret = append(ret,slice[i])
		}
	}
	//将字符串切片连接为一个字符串，之间用 " " 来分隔。
	return strings.Join(ret," ")
}

45.给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

代码:

func maxInWindows(num []int, size int) []int {
	res := make([]int, 0)
	length := len(num)
	if length == 0 || size <= 0 || size > length {
		return res
	}
	for i := 0; i < length - size + 1; i++ {
		max := num[i]
		for j := i; j < i + size; j++ {
			if num[j] > max {
				max = num[j]
			}
		}
		res = append(res, max)
	}
	return res
}

46.从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。

思路:

• 1.数组中不能有重复数据
• 2.排序之后的数组最大差值<5

代码:

func isStraight(nums []int) bool {
	//nums 转化为递增序列
	sort.Ints(nums)
	//记录每个数字之间差值的和
	sub:=0
	for i:=0;i<4;i++{
		if nums[i]==0{
			//continue 不进行下面的代码，进入下一次循环
			continue
		}
		//如果扑克牌（非0数字）重复，不是顺子
		if nums[i] == nums[i+1] {
			return false
		}
		sub+=nums[i+1]-nums[i]
	}
	return sub<5
}

47.求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路：

sum=(a1+an)n/2=>(1+n)n/2=>(n+n^2)/2；Math.pow(a,b)表示a^b；右移一位相当于除以2。

代码：

func Sum_Solution(n int) int {
	sum := math.Pow(float64(n), 2) + float64(n)
	return int(sum) >> 1
}