更新记录

1.1.0（2022-04-28）

此小程序是贴近生活

平台兼容性

1. 两数之和

难度简单14090收藏分享切换为英文接收动态反馈

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

func twoSum(nums []int, target int) []int {
        m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        another := target - nums[i]
        if _, ok := m[another]; ok {
                return []int{
                    m[another], i,
                }
        }
        m[nums[i]] = i
    }
    return nil
}

2. 两数相加

难度中等7859收藏分享切换为英文接收动态反馈

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := new(ListNode)
    curr := dummy
    carry := 0

    for (l1 != nil || l2 != nil || carry > 0) {
        curr.Next = new(ListNode)
        curr = curr.Next
        if l1 != nil {
            carry += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            carry += l2.Val
            l2 = l2.Next
        }
        curr.Val = carry % 10 
        carry /= 10
    }
    return dummy.Next
}

3. 无重复字符的最长子串

难度中等7336收藏分享切换为英文接收动态反馈

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

// 解法一
func lengthOfLongestSubstring(s string) int {
    // 哈希集合，记录每个字符是否出现过
    m := map[byte]int{}
    n := len(s)
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    rk, ans := -1, 0
    for i := 0; i < n; i++ {
        if i != 0 {
            // 左指针向右移动一格，移除一个字符
            delete(m, s[i-1])
        }
        for rk + 1 < n && m[s[rk+1]] == 0 {
            // 不断地移动右指针
            m[s[rk+1]]++
            rk++
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i + 1)
    }
    return ans
}

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

// 解法二
func lengthOfLongestSubstring(s string) int {
    var n = len(s)
    if n <= 1 {
        return n
    }
    var maxLen = 1
    var left, right, window = 0, 0, [128]int{}
    for right < n {
        var rightChar = s[right]
        var rightCharIndex = window[rightChar]
        if rightCharIndex > left {
            left = rightCharIndex
        }
        if right - left + 1 > maxLen {
            maxLen = right - left + 1
        }
        window[rightChar] = right + 1
        right++
    }
    return maxLen
}

4. 寻找两个正序数组的中位数

难度困难5302收藏分享切换为英文接收动态反馈

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
        return findMedianSortedArrays(nums2, nums1)
    }
    m, n := len(nums1), len(nums2)
    left, right := 0, m
    median1, median2 := 0, 0
    for left <= right {
        i := (left + right) / 2
        j := (m + n + 1) / 2 - i
        nums_im1 := math.MinInt32
        if i != 0 {
            nums_im1 = nums1[i-1]
        }
        nums_i := math.MaxInt32
        if i != m {
            nums_i = nums1[i]
        }
        nums_jm1 := math.MinInt32
        if j != 0 {
            nums_jm1 = nums2[j-1]
        }
        nums_j := math.MaxInt32
        if j != n {
            nums_j = nums2[j]
        }
        if nums_im1 <= nums_j {
            median1 = max(nums_im1, nums_jm1)
            median2 = min(nums_i, nums_j)
            left = i + 1
        } else {
            right = i - 1
        }
    }
    if (m + n) % 2 == 0 {
        return float64(median1 + median2) / 2.0
    }
    return  float64(median1)
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

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

5. 最长回文子串

难度中等5028收藏分享切换为英文接收动态反馈

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

// 1
func longestPalindrome(s string) string {
    start, end := 0, -1
    t := "#"
    for i := 0; i < len(s); i++ {
        t += string(s[i]) + "#"
    }
    t += "#"
    s = t
    arm_len := []int{}
    right, j := -1, -1
    for i := 0; i < len(s); i++ {
        var cur_arm_len int
        if right >= i {
            i_sym := j * 2 - i
            min_arm_len := min(arm_len[i_sym], right-i)
            cur_arm_len = expand(s, i-min_arm_len, i+min_arm_len)
        } else {
            cur_arm_len = expand(s, i, i)
        }
        arm_len = append(arm_len, cur_arm_len)
        if i + cur_arm_len > right {
            j = i
            right = i + cur_arm_len
        }
        if cur_arm_len * 2 + 1 > end - start {
            start = i - cur_arm_len
            end = i + cur_arm_len
        }
    }
    ans := ""
    for i := start; i <= end; i++ {
        if s[i] != '#' {
            ans += string(s[i])
        }
    }
    return ans
}

func expand(s string, left, right int) int {
    for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 { }
    return (right - left - 2) / 2
}

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

// 2
func longestPalindrome(s string) string {
    dp := make([][]bool,len(s))
    result := s[0:1]  //初始化结果(最小的回文就是单个字符)
    for i:=0;i<len(s);i++{
        dp[i] = make([]bool, len(s))
        dp[i][i] = true  // 根据case 1 初始数据
    }
    for length:=2;length<=len(s);length++{  //长度固定，不断移动起点
        for start:=0;start<len(s)-length+1;start++{  //长度固定，不断移动起点
            end := start + length - 1
            if s[start] != s[end]{  //首尾不同则不可能为回文
                continue
            }else if length < 3{
                dp[start][end] = true  //即case 2的判断
            }else {  
                dp[start][end] = dp[start+1][end-1]  //状态转移
            }
            if dp[start][end] && (end-start+1) > len(result){  //记录最大值
                result = s[start:end+1]
            }
        }
    }
    return result
}