算法(一)

移动零

func moveZeroes(nums []int)  {
    length := len(nums)
    if length <= 1 {
        return
    }

    j := 0
    for i := 0;i < length; i++ {
        if nums[i] != 0 {
            nums[j] = nums[i]
            j++
        }
    }

    for ;j < length;j++ {
        nums[j] = 0
    }
}

爬楼梯

实际上是一个斐波拉契数列优化问题

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    f1,f2,f3 := 1,2,3
    for i := 3;i <= n;i++ {
        f3 = f1 + f2
        f1 = f2
        f2 = f3
    }

    return f3
}

反转链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    return prev
}

有效的括号

符合“最近相关性”用栈解决：

func isValid(s string) bool {
    n := len(s)
    if n % 2 == 1 {
        return false
    }
    pairs := map[byte]byte{
        ')':'(',
        '}':'{',
        ']':'[',
    }
    stack := []byte{}
    for i := 0;i < n;i++ {
        if pairs[s[i]] > 0 {
            if len(stack) == 0 ||  stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            stack = stack[:len(stack)-1]
        }else{
            stack = append(stack,s[i])
        }
    }

    return len(stack) == 0
}

最小栈

type MinStack struct {
    stack []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{
        stack: []int{},
        minStack: []int{math.MaxInt64},
    }
}

func (this *MinStack) Push(x int)  {
    this.stack = append(this.stack, x)
    top := this.minStack[len(this.minStack)-1]
    this.minStack = append(this.minStack, min(x, top))
}

func (this *MinStack) Pop()  {
    this.stack = this.stack[:len(this.stack)-1]
    this.minStack = this.minStack[:len(this.minStack)-1]
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}


/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */