go编码练习

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 函数用于将两个有序链表合并为一个新的有序链表。
// 参数 l1 和 l2 分别为两个有序链表的头节点。
// 返回值为合并后新链表的头节点。
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    // 创建一个虚拟头节点，用于简化边界条件的处理，最终返回 dummy.Next 作为合并后链表的头节点
    dummy := &ListNode{}
    // 如果链表 l1 为空，直接返回链表 l2
    if l1 == nil {
        return l2
    }
    // 如果链表 l2 为空，直接返回链表 l1
    if l2 == nil {
        return l1
    }
    // cur 指针用于遍历并构建合并后的链表，初始指向虚拟头节点
    cur := dummy
    // 当 l1 和 l2 都不为空时，比较它们当前节点的值
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            // 如果 l1 当前节点的值小于 l2 当前节点的值，将 l1 当前节点接入合并后的链表
            cur.Next = l1
            // l1 指针后移一位
            l1 = l1.Next
        } else {
            // 否则，将 l2 当前节点接入合并后的链表
            cur.Next = l2
            // l2 指针后移一位
            l2 = l2.Next
        }
        // cur 指针后移一位，准备接入下一个节点
        cur = cur.Next
    }
    // 如果 l1 还有剩余节点，将 l1 剩余部分直接接入合并后的链表
    if l1 != nil {
        cur.Next = l1
    } else {
        // 否则，将 l2 剩余部分直接接入合并后的链表
        cur.Next = l2
    }
    // 返回虚拟头节点的下一个节点，即合并后链表的头节点
    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++ {
        // 初始化二维数组，单个字符为回文串，所以定义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
            // 如果我们已经知道 “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]
}