go編碼練習(xí)

func replaceSpace(s string) string{
    return strings.Replace(s," ","%200",-1)
}

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    ans := 0
    for left < right {
        if height[left] < height[right] {
            ans = max(ans, height[left]*(right-left))
            left++
        } else {
            ans = max(ans, height[right]*(right-left))
            right--
        }
    }
    return ans
}

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

func main() {
    var head *ListNode
    // create a cycle listNode
    // head -> 2 -> 3 -> 4 -> 5 -> head
    head = &ListNode{Val: 2}
    node2 := &ListNode{Val: 3}
    node3 := &ListNode{Val: 4}
    node4 := &ListNode{Val: 5}
    head.Next = node2
    node2.Next = node3
    node3.Next = node4
    node4.Next = node2
    fmt.Println(hasCycle(head))
}

func canJamp(arr []int) bool {
    mx := 0
    for i := 0; i < len(arr); i++ {
        if i > mx {
            return false
        }
        mx = max(mx, i+arr[i])
    }
    return true
}

// mergeTwoLists 函數(shù)用于將兩個有序鏈表合并為一個新的有序鏈表。
// 參數(shù) l1 和 l2 分別為兩個有序鏈表的頭節(jié)點。
// 返回值為合并后新鏈表的頭節(jié)點。
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    // 創(chuàng)建一個虛擬頭節(jié)點，用于簡化邊界條件的處理，最終返回 dummy.Next 作為合并后鏈表的頭節(jié)點
    dummy := &ListNode{}
    // 如果鏈表 l1 為空，直接返回鏈表 l2
    if l1 == nil {
        return l2
    }
    // 如果鏈表 l2 為空，直接返回鏈表 l1
    if l2 == nil {
        return l1
    }
    // cur 指針用于遍歷并構(gòu)建合并后的鏈表，初始指向虛擬頭節(jié)點
    cur := dummy
    // 當 l1 和 l2 都不為空時，比較它們當前節(jié)點的值
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            // 如果 l1 當前節(jié)點的值小于 l2 當前節(jié)點的值，將 l1 當前節(jié)點接入合并后的鏈表
            cur.Next = l1
            // l1 指針后移一位
            l1 = l1.Next
        } else {
            // 否則，將 l2 當前節(jié)點接入合并后的鏈表
            cur.Next = l2
            // l2 指針后移一位
            l2 = l2.Next
        }
        // cur 指針后移一位，準備接入下一個節(jié)點
        cur = cur.Next
    }
    // 如果 l1 還有剩余節(jié)點，將 l1 剩余部分直接接入合并后的鏈表
    if l1 != nil {
        cur.Next = l1
    } else {
        // 否則，將 l2 剩余部分直接接入合并后的鏈表
        cur.Next = l2
    }
    // 返回虛擬頭節(jié)點的下一個節(jié)點，即合并后鏈表的頭節(jié)點
    return dummy.Next
}

func longestPalindrome(s string) string {
    n := len(s)
    //  dp[left][right]為true表示"從left到right的子串為回文串"，false表示不是回文串
    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)
    }
    start, end := 0, 0
    for i := 0; i < len(s); i++ {
        // 初始化二維數(shù)組，單個字符為回文串，所以定義dp[i][i] = true
        dp[i][i] = true
    }
    for right := 1; right < len(s); right++ {
        for left := 0; left < right; left++ {
            // dp[left][right] =
            //(s[right]==s[left] && (right-left==1 || dp[left+1][right-1])) ? true : false
            // s[right]==s[left] && (right-left==1)       情況一：bb 這種
            // s[right]==s[left] && dp[left+1][right-1]   情況二：bab
            // 如果我們已經(jīng)知道 “bab” 是回文，那么很明顯，“ababa” 一定是回文，因為它的左首字母和右尾字母是相同的。
            if s[right] == s[left] && (right-left == 1 || dp[left+1][right-1]) {
                dp[left][right] = true
                if right-left > end-start {
                    start = left
                    end = right
                }
            } else {
                dp[left][right] = false
            }
        }
    }
    return s[start : end-start+1]
}