进一步有进一步惊喜

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    p,q,flag := l1,l2,&ListNode{Val: 0}
    current := flag
    carry := 0
    for p != nil || q != nil {
        x := 0
        y := 0
        if p != nil {
            x = p.Val
        }
        if q != nil {
            y = q.Val
        }
        // 相加,上一步的进位也要加上
        sum := carry + x + y
        // 重新计算进位
        carry = sum/10
        // 创建新的节点,节点里面放的是相加之后的个位数
        // current.Next里面可能已经有值了，但是不管.直接覆盖
        current.Next = &ListNode{Val: sum%10}
        current = current.Next
        if p != nil{
            p = p.Next
        }
        if q != nil {
            q = q.Next
        }
        // 有进位的话会往前创建一个node,如果后面还有数据的话这个节点会被丢弃
        if carry >0  {
            current.Next = &ListNode{Val: carry}
        }
    }
    return flag.Next
}

func deleteDuplicates(head *ListNode) *ListNode {
    cur := head
    for cur != nil && cur.Next != nil {
        if cur.Val == cur.Next.Val {
            // 删除重复节点
            // 跳过下一个节点
            cur.Next = cur.Next.Next
        }else{
            // 不相同到下一个
            cur = cur.Next
        }
    }
    return head
}

// 递归的方法
func deleteDuplicates2(head *ListNode) *ListNode{
    // 递归出口
    if head == nil || head.Next == nil {
        return head
    }
    // 递归条件
    head.Next = deleteDuplicates2(head.Next)
    if head.Val == head.Next.Val {
        head = head.Next
    }
    return head
}

func removeElements(head *ListNode, val int) *ListNode {
   flag := &ListNode{Val:0}
   flag.Next = head
   // 前置
   prev,cur := flag,head
   for cur != nil{
       if cur.Val == val {
           // 删除节点
           prev.Next = cur.Next
       }else{
           // 不相等,往前进发
           prev = cur
       }
       cur = cur.Next
   }
   return flag.Next
}

func hasCycle(head *ListNode) bool {
    cur := head
    m := make(map[*ListNode]interface{},1)
    for cur != nil{
        if _,ok := m[cur];ok {
            return true
        }
        m[cur] = nil
        cur = cur.Next
    }
    return false
}

func hasCycle(head *ListNode) bool {
  if head == nil || head.Next == nil {
        return false
    }
    slow,fast := head,head.Next
    for slow != fast {
        if fast == nil || fast.Next == nil {
            return false
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return true
}

func detectCycle(head *ListNode) *ListNode {
    cur := head
    m := make(map[*ListNode]interface{},1)
    for cur != nil{
        if _,ok := m[cur];ok {
            return cur
        }
        m[cur] = nil
        cur = cur.Next
    }
    return nil
}

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }
    slow,fast := head,head
    for {
        if fast == nil || fast.Next == nil {
            return nil
        }
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break
        }
    }

    // 相遇了,一个C从开始点出发,再相遇的点是相交点
    for cur := head; cur!=nil;{
        if slow == cur {
            return slow
        }
        slow = slow.Next
        cur = cur.Next
    }
    return slow
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    m := make(map[*ListNode]interface{})
    if headA == nil || headB == nil {
        return nil
    }
    cur := headA
    for cur != nil {
        m[cur] = true
        cur = cur.Next
    }
    // 遍历B的时候,判断
    cur = headB
    for cur != nil {
        if _,ok := m[cur];ok{
            return cur
        }
        cur = cur.Next
    }
    return nil
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    pA,pB := headA,headB
    //如果两个链表相交: A+B = B+A,两个指针走的路程都是一样的,会在汇合处相遇
    //不相交：最后都会变成nil,退出
    // 退出的条件为相等,要么找到相同节点,要么都为nil
    for pA != pB {
        if pA == nil {
            // 到达尾巴了,从B链表开始
            pA = headB
        }else {
            // 
            pA = pA.Next
        }
        // 同理
        if pB == nil {
            pB = headA
        }else{
            pB = pB.Next
        }
    }
    // 如果p
    return pA
}

func middleNode(head *ListNode) *ListNode {
    length := 0
    cur := head
    if head == nil {
        return head
    }
    for cur != nil {
        length ++
        cur = cur.Next
    }
    cur = head
    if length % 2 == 0{
        // 偶数 = (length+2)/2
        length = (length + 2)/2
    }else {
        // 奇数 = (length+1)/2
        length = (length + 1)/2
    }
    for ;length>1;length-- {
        cur = cur.Next
    }
    return cur
}

func middleNode(head *ListNode) *ListNode {
    length := 0
    cur := head
    if head == nil {
        return head
    }
    for cur != nil {
        length ++
        cur = cur.Next
    }
    cur = head
    for length = length/2 + 1;length>1;length-- {
        cur = cur.Next
    }
    return cur
}

func middleNode(head *ListNode) *ListNode {
    slow,fast := head,head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

func reachNumber(target int) int {
    if target < 0 {
        target = -target
    } 
    sum := 0
    i := 1
    for {
        sum = sum + i
        if sum == target {
            return i
        }else if sum > target {
            if (sum - target) %2 == 0 {
                return i
            }
        }
        i++
    }
    return i
}

func MovesToMakeZigzag(nums []int) int {
    /**
    锯齿状数据,只能递减,每次减1。步数最少。
    奇数位先减,操作的步数。
    偶数位再减,操作的步数。
    比较那个走得少。
    */
    oddStep := 0
    eventStep := 0
    length := len(nums)
    // 奇位数先减 1,3,5,7
    for i:=0;i < length; i = i +2{
        tmp := nums[i]
        // 处在头部,只比较右边的数据
        if i == 0 {
            if nums[i + 1] > tmp {
                // A < B 高过，不用管
                continue
            }else {
                // A >= B,下拉
                oddStep = oddStep + (tmp - nums[i+1] + 1)
                continue
            }
        }
        // 处在尾部
        if i == length -1 {
            // B > C
            if nums[i-1] > tmp {
                continue
            }else {
                // B < C
                oddStep = oddStep + (tmp - nums[i-1] + 1)
                continue
            }
        }
        
        // 处在中间,比两边。低过最低的便可
        if i > 0 && i < length-1 {
            // 比较两边,
            if nums[i-1] > tmp && tmp < nums[i+1] {
                continue
            }
            if nums[i-1] > nums[i+1] {
                // A > C 低过右边便可
                if nums[i + 1] > tmp {
                    continue
                }else {
                    oddStep = oddStep + (tmp - nums[i+1] + 1)
                    continue
                }
            }else{
                // A < C 低过左边便可
                if nums[i - 1] > tmp {
                    continue
                }else {
                    oddStep = oddStep + (tmp - nums[i-1] + 1)
                    continue
                }
            }
        }
    }
    
    // 偶数位先减 2,4,6,8
    for i:=1;i < length;i= i + 2{
        tmp := nums[i]
        // 尾部
        if i == length -1 {
            // B > C
            if nums[i-1] > tmp {
                continue
            }else {
                // B < C
                eventStep = eventStep + (tmp - nums[i-1] + 1)
                continue
            }
        }
        // 中间
        if i > 0 && i < length-1 {
            // 比较两边,
            if nums[i-1] > tmp && tmp < nums[i+1] {
                continue
            }
            if nums[i-1] > nums[i+1] {
                // A > C 低过右边便可
                if nums[i + 1] > tmp {
                    continue
                }else {
                    eventStep = eventStep + (tmp - nums[i+1] + 1)
                    continue
                }
            }else{
                // A < C 低过左边便可
                if nums[i - 1] > tmp {
                    continue
                }else {
                    eventStep = eventStep + (tmp - nums[i-1] + 1)
                    continue
                }
            }
        }
    }
    
    if oddStep > eventStep {
        return eventStep
    }
    return oddStep
}

func reverseList(head *ListNode) *ListNode {
   var tmp *ListNode = nil
   cur := head
   for cur != nil {
       tmpNode := &ListNode{
           Val: cur.Val,
       }
       tmpNode.Next = tmp
       tmp = tmpNode
       cur = cur.Next
   }
   return tmp
}

func ReverseList2(head *ListNode) *ListNode {
    var tmp *ListNode = nil
    cur := head
    for cur != nil {
        tmpNode := cur
        cur = cur.Next
        // 断开链表
        tmpNode.Next = nil
        // 重新连接
        tmpNode.Next = tmp
        tmp = tmpNode
    }
    return tmp
}

func isPalindrome(head *ListNode) bool {
    // 复制链表
    cp := []int{}
    cur := head
    for cur != nil {
        cp = append(cp,cur.Val)
        cur = cur.Next
    }
    // 逆序比较
    cur = head
    index := len(cp) - 1
    for cur != nil{
        if cur.Val != cp[index] {
            return false
        }
        index --
        cur = cur.Next
    }
    return true
}

// 判断链表是否是回文数
func isPalindrome(head *ListNode) bool {
    // 复制链表
    cp := []int{}
    cur := head
    for cur != nil {
        cp = append(cp,cur.Val)
        cur = cur.Next
    }
    // 逆序比较
    cur = head
    index := len(cp) - 1
    index2 := 0
    for index != index2 && index2 < index {
        if cp[index] != cp[index2] {
            return false
        }
        index --
        index2 ++
    }
    //for cur != nil{
    //    if cur.Val != cp[index] {
    //        return false
    //    }
    //    index --
    //    cur = cur.Next
    //}
    return true
}

func getDecimalValue(head *ListNode) int {
    // 读出来再进制运算
    arr := []int{}
    cur := head
    for cur != nil {
        arr = append(arr,cur.Val)
        cur = cur.Next
    }
    // 进制运算
    base := 1 << (len(arr) - 1)
    result := 0
    for _,v := range arr {
        result = result + v * base
        base /= 2
    }
    return result
}

func getDecimalValue(head *ListNode) int {
    // 读出来
    cur := head
    length := 0
    for cur != nil {
        cur = cur.Next
        length ++
    }
    // 按权重进行相加
    length --
    base := 1 << length
    result := 0
    for cur = head;cur!=nil;cur=cur.Next {
        result = result + cur.Val * base
        base /= 2
    }
    return result
}

func getKthFromEnd(head *ListNode, k int) *ListNode {
    // 第一遍算长度
    length := 0
    cur := head
    for ;cur != nil;cur= cur.Next {
        length ++
    }
    // 算前进步数
    length = length - k
    cur = head
    for i:=1; i <=length; i++{
        cur = cur.Next
    }
    return cur
}

func getKthFromEnd(head *ListNode, k int) *ListNode {
    fast,slow := head,head
    for i:=k;i>0;i--{
        fast = fast.Next
    }
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }
    return slow
}

func removeDuplicateNodes(head *ListNode) *ListNode {
    // 向后读取,如果后面的数据和现在的一样,删除节点。不一样,指针前移
    if head == nil {
        return head
    }
    pre,cur := head,head.Next
    // 临时缓冲区
    buf := make(map[int]struct{})
    buf[pre.Val] = struct{}{}
    for cur != nil {
        if _,ok := buf[cur.Val];ok {
            // 相同,删除节点
            cur = cur.Next
            pre.Next = cur
        }else{
            // 不相同,继续
            buf[cur.Val] = struct{}{}
            pre = pre.Next
            cur = cur.Next
        }
    }
    return head
}

func removeDuplicateNodes(head *ListNode) *ListNode {
   if head == nil {
        return head
    }
    pre,cur := head,head.Next
    for pre != nil {
        preTmp := pre
        for cur != nil {
            if cur.Val == pre.Val {
                cur = cur.Next
                preTmp.Next = cur
            }else{
                preTmp = preTmp.Next
                cur = cur.Next
            }
        }
        pre = pre.Next
        if pre == nil {
            break
        }
        cur = pre.Next
    }
    return head
}

func removeDuplicateNodes(head *ListNode) *ListNode {
   if head == nil {
        return nil
    }
    index := head
    for index != nil {
        cur := index
        for cur.Next != nil {
            if cur.Next.Val == index.Val {
                // 删除节点
                cur.Next = cur.Next.Next
            }else{
                cur = cur.Next
            }
        }
        index = index.Next
    }
    return head
}

func reversePrint(head *ListNode) []int {
    arr := []int{}
    for cur := head;cur != nil;cur = cur.Next{
        arr = append([]int{cur.Val},arr...)
    }
    return arr
}

func reversePrint(head *ListNode) []int {
    length := 0
    for cur:=head;cur != nil;cur=cur.Next{
        length ++
    }
    arr := make([]int,length)
    for cur:=head;cur!=nil;cur=cur.Next{
        arr[length-1] = cur.Val
        length --
    }
    return arr
}

func deleteNode(head *ListNode, val int) *ListNode {
    if head == nil {
        return head
    }
    // 处理第一个节点为待删除节点
     cur:=head
    for;cur !=nil && cur.Val == val;{
        cur = cur.Next
    }
    head = cur
    for index:=head;index!=nil && index.Next !=nil ;{
        if index.Next.Val == val {
            index.Next = index.Next.Next
        }else{
            index = index.Next
        }
    }
    return head
}

func deleteNode(node *ListNode) {
    cur := node
    for cur.Next != nil {
        if cur.Next.Next == nil {
            // 删除最后节点
            cur.Val = cur.Next.Val
            cur.Next = nil
        }else{
            //
            cur.Val = cur.Next.Val
            cur = cur.Next
        }
    }
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head.Next == nil {
        return nil
    }
    length := 0
    for cur:=head;cur != nil;cur=cur.Next{
        length ++
    }
    // 得出待删除节点所处的位置
    length = length - n
    if length == 0 {
        // 删除头节点
        head = head.Next
        return head
    }
    // 定位节点并删除
    cur := head
    for ;length > 1;length--{
        cur = cur.Next
    }
    // 删除节点
    cur.Next = cur.Next.Next
    return head
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 快慢指针,快指针比慢指针先走n+1步.快指针到终点了慢指针就再到数第n为的前面,然后删除便可
    if head.Next == nil {
        return nil
    }
    slow,fast := head,head
    step := n + 1
    for ;fast != nil;fast=fast.Next {
        if step > 0 {
            step --  
        }else{
            slow = slow.Next
        }
    }
    // 快指针已经结束,但是还有剩余步数,说明删除的是第一个节点
    if step > 0 {
        head = head.Next
        return head
    }
    // 删除前面的节点
    slow.Next = slow.Next.Next
    return head
}

func swapPairs(head *ListNode) *ListNode {
    // 使用临时节点存放旧链表,节点短链重连
    oldHead := head
    newHead := &ListNode{}
    newLinkCur := newHead
    var n1,n2 *ListNode = nil,nil
    for oldHead != nil {
        if oldHead.Next == nil {
            // 最后一个节点了,将这个节点加入新链表尾巴
            newLinkCur.Next = oldHead
            break
        }
        // 处理节点
        n1,n2 = oldHead,oldHead.Next
        //newHead -> n2-> n1->
        oldHead = oldHead.Next.Next
        n1.Next = nil
        // n2 -> n1
        n2.Next = n1
        // tail-> n2
        newLinkCur.Next = n2
        // tail = n1
        // tail -> n2->n1 ->tail
        newLinkCur = n1
    }
    return newHead.Next
}

func swapPairs(head *ListNode) *ListNode {
    // 递归第一个出口
    if head == nil || head.Next == nil {
        return head
    }
    firstNode,secondNode := head,head.Next
    firstNode.Next = swapPairs(secondNode.Next)
    secondNode.Next = firstNode
    return secondNode
}

func rotateRight(head *ListNode, k int) *ListNode {
    // 结环 -> 割环
    // step = length - k%length
    if k == 0 {
        return head
    }
    if head == nil {
        return nil
    }
    length := 0
    cur := head
    for cur != nil {
        if cur.Next == nil {
            // 结环,获得长度
            cur.Next = head
            length ++
            break
        }
        cur= cur.Next
        length ++
    }
    // 计算切割点
    // [1,2,3] 20000000 需要进行mod运算
    step := length - k%length
    // 定位切割点
    for ;step > 1;step-- {
        head = head.Next
    }
    // 切割
    tmp := head
    head = head.Next
    tmp.Next = nil
    return head
}

func deleteDuplicates(head *ListNode) *ListNode {
   if head == nil || head.Next == nil {
       return head
   }
   // map
    mp := make(map[int]int)
    for cur:=head;cur!=nil;cur=cur.Next{
        mp[cur.Val] += 1
    }
    dump := &ListNode{}
    dump.Next = head
    dup := false
    for cur := dump;cur!= nil&&cur.Next != nil;{
        // 判断重复 值大于2
        if v,_ := mp[cur.Next.Val]; !dup && v > 1 {
            dup = true
        }
        // 删除重复的节点
        if dup {
            if v,_ := mp[cur.Next.Val];v > 0{
                mp[cur.Next.Val] -= 1
                if v,_ := mp[cur.Next.Val];v == 0 {
                    dup = false
                }
                cur.Next = cur.Next.Next
            }
        }else{
            cur = cur.Next
        }
    }
    return dump.Next
}

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    // 先将待翻转的数据存下来,存完之后就翻转
    // 使用array存储
    // 哑节点
    if head == nil || head.Next == nil {
        return head
    }
    dummy := &ListNode{}
    dummy.Next = head
    pre,cur := dummy,head
    arr := []*ListNode{}
    sub := n - m
    step := 2
    i := 0
    for {
        if step == 2 {
            // 分析阶段
            if i < m -1 {
                // 定位
                pre = cur
                cur = cur.Next
                i ++
            }else if i >= m -1 && i <= n -1{
                // 赋值
                arr = append(arr,cur)
                cur = cur.Next
                i ++
            }else{
                step --
                continue
            }
        }else if step == 1{
            // 反转阶段
            if sub >= 0 {
                tmp := arr[sub]
                tmp.Next = nil
                pre.Next = tmp
                pre = tmp
                sub --
            }else{
                // 翻转完成,链表连接
                pre.Next = cur
                step --
            }
        }else{
            break
        }
    }
    return dummy.Next
}

if head == nil || head.Next == nil {
       return head
   }
   // 使用多指针，边走边翻转
   dummy := &ListNode{}
   dummy.Next = head
   // 新生成链表的尾巴
   dTail := dummy
   // 旧的数据
   var sHead *ListNode = nil
   var sTail *ListNode = nil
   i := 0
   cur := head
   for {
       if i < m -1 {
           dTail = cur
           cur = cur.Next
           i ++
       }else if i == m-1{
           // 切割点
           sTail = cur
           sHead = cur
           cur = cur.Next
           i ++
       }else if i > m -1 && i <= n -1 {
           // 翻转点
           tmp := cur
           cur = cur.Next
           tmp.Next = sHead
           sHead = tmp
           i ++
       }else if i == n {
           // 重新连接点
           dTail.Next = sHead
           sTail.Next = cur
           break
       }else{
           break
       }
   }
   
   return dummy.Next

func reverseList(head *ListNode) *ListNode{
    var nHead *ListNode = nil
    cur := head
    for cur != nil {
        tmpNode := cur
        cur = cur.Next
        // 断开链表
        tmpNode.Next = nil
        // 重新连接
        tmpNode.Next = nHead
        nHead = tmpNode
    }
    return nHead
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 翻转链表,然后按照简单的方法做
    l1 = reverseList(l1)
    l2 = reverseList(l2)
    p,q,flag := l1,l2,&ListNode{Val: 0}
    current := flag
    carry := 0
    for p != nil || q != nil {
        x := 0
        y := 0
        if p != nil {
            x = p.Val
        }
        if q != nil {
            y = q.Val
        }
        // 相加,上一步的进位也要加上
        sum := carry + x + y
        // 重新计算进位
        carry = sum/10
        // 创建新的节点,节点里面放的是相加之后的个位数
        // current.Next里面可能已经有值了，但是不管.直接覆盖
        current.Next = &ListNode{Val: sum%10}
        current = current.Next
        if p != nil{
            p = p.Next
        }
        if q != nil {
            q = q.Next
        }
        // 有进位的话会往前创建一个node,如果后面还有数据的话这个节点会被丢弃
        if carry >0  {
            current.Next = &ListNode{Val: carry}
        }
    }
    return reverseList(flag.Next)
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    stack1 := []int{}
    stack2 := []int{}
    // 数据入栈
    for cur:=l1;cur!= nil;cur=cur.Next{
        stack1 = append(stack1,cur.Val)
    }
    for cur:=l2;cur!=nil;cur=cur.Next{
        stack2 = append(stack2,cur.Val)
    }
    // 出栈相加
    dummy := &ListNode{}
    top1,top2 := len(stack1),len(stack2)
    carray := 0
    for top1 > 0 || top2 > 0{
        a,b := 0,0
        if top1 == 0 {
            a = 0
        }else{
            a = stack1[top1 - 1]
            top1 --
        }
        if top2 == 0 {
            b = 0
        }else{
            b = stack2[top2 -1]
            top2 --
        }
        sum := a + b + carray
        carray = sum / 10
        val := sum % 10
        node := &ListNode{
            Val:val,
            Next:nil,
        }
        node.Next = dummy.Next
        dummy.Next = node
    }
    if carray > 0 {
        cNode := &ListNode{
            Val:1,
            Next:nil,
        }
        cNode.Next = dummy.Next
        dummy.Next = cNode
    }
    return dummy.Next
}

func searchInsert(nums []int, target int) int {
    i := 0
    if target < nums[0]{
        return 0
    }
    for ;i < len(nums);i++{
        if nums[i] == target {
            return i
        }
        if i + 1 < len(nums)  {
            if target > nums[i] && target < nums[i + 1]{
                return i + 1  
            }
        }
    }
    return i
}

func merge(A []int, m int, B []int, n int)  {
    // 从后向前移动,每次寻找最大值填入A
    index := m + n -1
    m,n = m-1,n-1
    for m >=0 || n >= 0 {
        if m < 0 {
            // A已经选取结束了,把B放入便可
            A[index] = B[n]
            index --
            n --
            continue
        }
        if n < 0 {
            A[index] = A[m]
            index --
            m --
            continue
        }
        if A[m] >= B[n] {
            A[index] = A[m]
            m --
            index --
        }else {
            A[index] = B[n]
            n--
            index --
        }
    }
}

func maxProfit(prices []int) int {
    // 最低点买入,最高点卖出,由于只能进行一次买入和卖出,就计算看看,每天的情况
    if len(prices) == 0 || len(prices) == 1 {
        return 0
    }
    minPrice := prices[0]
    maxProfit := 0
    for i:=1;i<len(prices);i++{
        if prices[i] < minPrice {
            // 今天的价格最低,今天买入吧
            minPrice = prices[i]
        }
        if prices[i] - minPrice > maxProfit {
            // 今天卖出比前一天好
            maxProfit = prices[i] - minPrice
        }
    }
    return maxProfit
}

func plusOne(digits []int) []int {
    carray := 1
    for i:=len(digits)-1;i>=0;i--{
        sum := digits[i] + carray
        carray = sum/10
        digits[i] = sum % 10
    }
    if carray > 0 {
        digits = append([]int{carray},digits...)
    }
    return digits
}

func majorityElement(nums []int) int {
    half := len(nums) / 2
    mp := make(map[int]int)
    for _,v := range nums{
        mp[v] += 1
    }
    for k,v := range mp {
        if v > half {
            return k
        }
    }
    return 0
}

func majorityElement(nums []int) int {
    candidate := 0
    count := 0
    for _,k := range nums {
        if count == 0 {
            candidate = k
        }
        if k == candidate {
            count ++ 
        }else {
            count --
        }
    }
    return candidate
}

func generate(numRows int) [][]int {
   reNums := make([][]int,numRows)
   for i:=0;i<numRows;i++{
       if i == 0 {
           reNums[i] = []int{1}
       }else{
           subNum := make([]int,i+1)
           for j:=0;j < i + 1;j++ {
                pre1,pre2 := 0,0
                if j-1 <0 {
                    pre1 = 0
                }else{
                    pre1 = reNums[i-1][j-1]
                }
                
                if j >= i {
                    pre2 = 0
                }else{
                    pre2 = reNums[i-1][j]
                }
                subNum[j] = pre1 + pre2
           }
           reNums[i] = subNum
       }
   }
   return reNums
}

func getRow(rowIndex int) []int {
   numRows := rowIndex+1
   reNums := make([][]int,numRows)
   for i:=0;i<numRows;i++{
       if i == 0 {
           reNums[i] = []int{1}
       }else{
           subNum := make([]int,i+1)
           for j:=0;j < i + 1;j++ {
                pre1,pre2 := 0,0
                if j-1 <0 {
                    pre1 = 0
                }else{
                    pre1 = reNums[i-1][j-1]
                }
                
                if j >= i {
                    pre2 = 0
                }else{
                    pre2 = reNums[i-1][j]
                }
                subNum[j] = pre1 + pre2
           }
           reNums[i] = subNum
       }
   }
   return reNums[rowIndex]
}

func factorial(n int64) int64{
    if n == 0 {
        return 1
    }
    return factorial(n-1)*n
}
func combination(n1, m1 int) int64 {
    n := int64(n1)
    m := int64(m1)
    if m == 0 {
        return 1
    }
    return factorial(n)/(factorial(m)*factorial(n-m))
}
func getRow(rowIndex int) []int {
    // 只要计算一半便可
    half := rowIndex/2
    nums := make([]int,rowIndex + 1)
    for i:=0;i<=half;i++{
        nums[i] = int(combination(rowIndex,i))
    }
    for i:= half+1;i < rowIndex + 1;i++{
        nums[i] = nums[rowIndex - i]
    }
    return nums
}

func getRow(rowIndex int) []int {
	// 第0行
	nums := []int{1}
	for i := 1; i <= rowIndex; i++ {
		// 尾部追加1
		nums = append(nums, 1)
		// 倒序计算杨辉三角当前行
		for j:=i-1;j>0;j--{
			nums[j]+=nums[j-1]
		}
	}
	return nums
}
作者：revelationofturing
链接：https://leetcode-cn.com/problems/pascals-triangle-ii/solution/zhi-xing-yong-shi-0-ms-zai-suo-you-golang-ti-jia-8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

func moveZeroes(nums []int)  {
    cur,length := 0,len(nums)
    for i:=0;i<length;i++{
       if nums[i] != 0 {
           if cur != i {
                nums[cur] = nums[i]
                nums[i] = 0
                cur ++
           }else{
               cur ++
           }
       }
    }
}

func findRepeatNumber(nums []int) int {
    // 使用map存储数据
    mp := make(map[int]struct{})
    for _,v := range nums {
        if _,ok := mp[v];ok{
            return v
        }else{
            mp[v] = struct{}{}
        }
    }
    return 0
}

func maxProfit(prices []int) int {
    maxProfit := 0
    for i:=1;i<len(prices);i++{
        if prices[i-1] < prices[i] {
            // 今天相比昨天高了,卖出。
            maxProfit = maxProfit + prices[i] -prices[i-1]
        }
    }
    return maxProfit
}

func twoSum(numbers []int, target int) []int {
    // 一个从头开始，一个从末尾开始。如果和大于target,末尾指针左移，减小和。如果和小于target,头指针往前，增大sum.
    index1,index2 := 0,len(numbers)-1
    for numbers[index1] + numbers[index2] != target {
        if numbers[index1] + numbers[index2] == target {
            break
        }else if numbers[index1] + numbers[index2] > target {
            index2 --
        }else{
            index1 ++
        }
    }
    return []int{index1+1,index2+1}
}