leetcode刷题日记-1

20241019刷题

1. 两数之和

func twoSum(nums []int, target int) []int {
    // 直接算加法，需要走循环两次，也就是你未知后续出现的数字
    // 逆向思维，走减法，因为遍历的过程中，前面的数字是已知的，存前面的数字A，然后用target-后面的数字B
    // 如果target-B的值=A，也就是在前面出现过，就输出下标
    subMap := make(map[int]int, 0)
    for i, val := range nums {
        subVal := target - val
        indexVal, ok := subMap[subVal]
        if ok {
            return []int{indexVal, i}
        } else {
            subMap[val] = i
        }
    }
    return []int{}
}

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

方法一：最容易想到的

func mergeSlice(nums1 []int, nums2 []int) []int {
nums1 = append(nums1, nums2...)
sort.Ints(nums1)
return nums1
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
nums := mergeSlice(nums1, nums2)
n := len(nums)
if n%2 == 0 {
return float64(nums[n/2-1]+nums[n/2]) / 2
} else {
return float64(nums[n/2])
}
}

简单优化一下，可以把合并两个有序数组的写成双指针【归并排序】

func mergeSortedArrays(arr1 []int, arr2 []int) []int {
// 创建一个结果数组，其长度为两个数组的总和
merged := make([]int, len(arr1)+len(arr2))
i, j, k := 0, 0, 0

// 使用双指针法合并两个有序数组
for i < len(arr1) && j < len(arr2) {
if arr1[i] < arr2[j] {
merged[k] = arr1[i]
i++
} else {
merged[k] = arr2[j]
j++
}
k++
}

// 将剩余的元素添加到结果数组中
for i < len(arr1) {
merged[k] = arr1[i]
i++
k++
}

for j < len(arr2) {
merged[k] = arr2[j]
j++
k++
}

return merged
}

方法二：二分查找

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
// 以长度小的作为二分查找的基准, 防止出现[5, 6, 7, 8, 9]和[1, 2, 3, 4]这种情况，无法划分
if len(nums1) > len(nums2) {
nums1, nums2 = nums2, nums1
}
// 对于偶数长度的数组， 划分就是左右两边相等， 比如 2， 4， 9， 15 和 3， 6， 8， 11划分就是左边是2 4 | 9 15 和 3 6 | 8 11
// 对于奇数长度的数组， 划分就是左边比右边多一个， 比如 2， 4， 9， 15， 21 和 3， 6， 8， 11划分就是左边是2 4 | 9 15 21 和 3 6  8 | 11 13
// 为了方便处理， 让左边多一个
// 如果是偶数：左边的长度就是(m+n)/2= (m+n+1)/2
// 如果是奇数：左边的长度就是(m+n+1)/2
// 为了方便处理， 综上， 左边的长度就是(m+n+1)/2
m, n := len(nums1), len(nums2)
totalLeft := (m + n + 1) / 2
// 二分查找的左右边界
left, right := 0, m
for left < right {
i := left + (right-left+1)/2
j := totalLeft - i
// 划分后的数组，需要满足左边的最大值小于右边的最小值， 所以这里需要判断nums1[i-1] <= nums2[j]和nums2[j-1] <= nums1[i]
// 我们只需要取其中一个判断即可
if nums1[i-1] > nums2[j] {
right = i - 1
} else {
left = i
}
}
i, j := left, totalLeft-left
// 判断奇偶
var nums1LeftMax, nums1RightMin, nums2LeftMax, nums2RightMin int
if i == 0 {
nums1LeftMax = math.MinInt64
} else {
nums1LeftMax = nums1[i-1]
}
if i == m {
nums1RightMin = math.MaxInt64
} else {
nums1RightMin = nums1[i]
}
if j == 0 {
nums2LeftMax = math.MinInt64
} else {
nums2LeftMax = nums2[j-1]
}
if j == n {
nums2RightMin = math.MaxInt64
} else {
nums2RightMin = nums2[j]
}
if (m+n)%2 == 1 {
return math.Max(float64(nums1LeftMax), float64(nums2LeftMax))
} else {
// 偶数的话， 需要取左边的最大值和右边的最小值
return (math.Max(float64(nums1LeftMax), float64(nums2LeftMax)) + math.Min(float64(nums1RightMin), float64(nums2RightMin))) / 2
}
}

原文地址：https://blog.csdn.net/qq_40840571/article/details/143000597

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！