使用golang解决LeetCode热题Hot100
1.两数之和
https://leetcode.cn/problems/two-sum/
题目
给定一个整数数组 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]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
解决方案
func twoSum(nums []int, target int) []int {
l := len(nums)
for i := 0; i < l; i++ {
for j := i + 1; j < l; j++ {
if nums[i] + nums[j] == target {
return []int{i, j} // 返回找到的满足条件的两个数的索引
}
}
}
return []int{} // 如果没有找到满足条件的两个数，则返回一个空数组
}
2.两数相加
https://leetcode.cn/problems/add-two-numbers/
题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
解决方案
package main
// ListNode 定义链表节点结构
type ListNode struct {
Val int
Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
current := dummy
carry := 0
// 遍历两个链表，直到两个链表都为空并且没有进位
for l1 != nil || l2 != nil || carry != 0 {
sum := carry
// 将l1的值加到sum，并将l1指向下一个节点
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
// 将l2的值加到sum，并将l2指向下一个节点
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
// 计算进位和当前节点的值
carry = sum / 10
current.Next = &ListNode{Val: sum % 10}
current = current.Next
}
return dummy.Next
}
3.无重复字符的最长字串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
解决方案
func lengthOfLongestSubstring(s string) int {
// 获取字符串长度
n := len(s)
// 建立哈希表记录字符出现的次数
freq := make(map[byte]int)
// 定义双指针
left, right := 0, 0
// 定义最大长度
maxLen := 0
// 当 right 指针小于字符串长度时，循环执行
for right < n {
// 如果当前字符在哈希表中已经存在，则将左指针右移，并更新哈希表中的值
if freq[s[right]] > 0 {
freq[s[left]]--
left++
} else { // 否则将右指针右移，并更新哈希表中的值
freq[s[right]]++
right++
// 计算当前窗口的长度，并取其中的最大值
maxLen = max(maxLen, right-left)
}
}
// 返回最大长度
return maxLen
}
// 定义一个求最大值的函数
func max(a, b int) int {
if a > b {
return a
}
return b
}
4.寻找两个正序数组的中位数
https://leetcode.cn/problems/median-of-two-sorted-arrays/
题目
给定两个大小分别为 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
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
解决方案
详解：https://mp.weixin.qq.com/s/FBlH7o-ssj_iMEPLcvsY2w来自公众号吴师兄学算法
package main
import "math"
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
// 获取两个数组的长度
n := len(nums1)
m := len(nums2)
// 将奇偶情况合并，求得左右两个位置
left := (n + m + 1) / 2
right := (n + m + 2) / 2
// 求得中位数，如果是奇数个元素，会计算两次同样的k。
return float64(getKth(nums1, 0, n-1, nums2, 0, m-1, left)+getKth(nums1, 0, n-1, nums2, 0, m-1, right)) * 0.5
}
func getKth(nums1 []int, start1, end1 int, nums2 []int, start2, end2 int, k int) int {
// 计算两个数组的长度
len1 := end1 - start1 + 1
len2 := end2 - start2 + 1
// 确保 len1 <= len2，简化逻辑
if len1 > len2 {
return getKth(nums2, start2, end2, nums1, start1, end1, k)
}
// 如果 nums1 为空数组，则直接返回 nums2 中的第 k 个元素
if len1 == 0 {
return nums2[start2+k-1]
}
// 当 k == 1 时，返回 nums1 和 nums2 中首个元素的较小值
if k == 1 {
return int(math.Min(float64(nums1[start1]), float64(nums2[start2])))
}
// 在 nums1 和 nums2 中分别找到当前搜索范围的中位数 i 和 j
// 使得 nums1[i] 和 nums2[j] 之前的元素都小于等于第 k 个元素
i := start1 + int(math.Min(float64(len1), float64(k/2))) - 1
j := start2 + int(math.Min(float64(len2), float64(k/2))) - 1
if nums1[i] > nums2[j] {
// 如果 nums1[i] > nums2[j]，说明第 k 个元素位于 nums1[i] 右侧或 nums2[j] 左侧
// 在 nums1 中缩小搜索范围，并更新 k 值
return getKth(nums1, start1, end1, nums2, j+1, end2, k-(j-start2+1))
}
// 否则，第 k 个元素位于 nums1[i] 左侧或 nums2[j] 右侧
// 在 nums2 中缩小搜索范围，并更新 k 值
return getKth(nums1, i+1, end1, nums2, start2, end2, k-(i-start1+1))
}
func main() {
// 测试该函数
nums1 := []int{1, 3}
nums2 := []int{2}
median := findMedianSortedArrays(nums1, nums2)
println(median) // 输出：2.0
}
5.最长回文子串
https://leetcode.cn/problems/longest-palindromic-substring/
题目
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
解决方案
解题思路：
对于一个子串而言,如果它是回文串,并且长度大于2,那么将它首尾的两个字母去除之后,它仍然是个回文串.例如对于字符串"ababa",如果我们已经知道"bab"是回文串,那么"ababa"一定是回文串,这是因为他的首尾两个字母都是"a".
动态规划:
P(i,j)表示字符串s的第i到第j个字母组成的串是否为回文串:
(1)如果子串si…sj是回文串----true
(2)其他情况----false
i.s[i,j]本身就不是一个回文串
ii.i>j,此时s[i,j]是 不合法的.
我们可以写出动态规划的状态转移方程:
P(i,j)=P(i+1,j-1)^(Si==Sj)
也就是说,只有s[i+1:j-1]是回文串,并且s的第i个和第j个字母相同时,s[i:j]才是回文串.
要注意的是,这是建立在子串长度大于2的前提下的,所以在此之前需要分析子串长度1或2.对于长度为1的子串,它本身就是一个回文串;对于长度为2的子串,只要它的两个字母相同,它就是一个回文串.
func longestPalindrome(s string) string {
n:=len(s)
res:=""
//声明一个二维数组并初始化
dp=make([][]int,n)
//对二维数组的每一行进行初始化
for i:=0;i<n;i++{
dp[i]=make([]int,n)
}
//遍历这个字符串
for m:=0;m<n;m++{
//行
for i:=0;i+m<n;i++{
//列
j:=i+m
//二维数组的对角线上,即每单个字符都是回文子串
if m==0{
dp[i][j]=1
}else if m==1{
//判断每相邻的两个字符是否相同,若相同则为回文子串
if s[i]==s[j]{
dp[i][j]=1
}
}else{
//当字符个数超过2个的时候,如果首尾字符相同,则需要看去掉首尾后里面的子串是否是回文串;
//在二维数组中即看下一行左一列是否是1
if s[i]==s[j]{
dp[i][j]=dp[i+1][j-1]
}
}
//首先dp[i][j]要是个回文串;其次必须长度大于之前找到的回文串的长度
if dp[i][j]>0&&m+1>len(res){
res=s[i:i+m+1]//slice截取数据的规则:左闭右开
}
}
}
return res
}
6.N字形变换
https://leetcode.cn/problems/zigzag-conversion/
题目
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
示例 3：
输入：s = "A", numRows = 1
输出："A"
解决方案
大致思路：
-
创建一个 numRows 行的二维数据结构（在 Python 中使用二维数组或列表的列表，而在 Go 中使用二维切片）用于模拟 Z 字形排列过程。
-
遍历输入字符串 s 的每个字符，按照 Z 字形的规则依次放入二维数据结构中。
-
在 Z 字形排列中，每一行对应 Z 字形的一个斜线。遍历过程中，按照顺序将字符依次放入每一行中，同时维护一个变量来表示当前所在的行数。
-
对于每个字符，需要判断当前行的位置，若在第一行，则下一个字符应该放入下一行；若在最后一行，则下一个字符应该放入上一行；否则按照当前方向继续放入相应的行。
-
最后，按照 Z 字形顺序读取二维数据结构中的字符，即从上到下，再从左到右，得到排列后的结果字符串。
-
特殊情况处理：如果 numRows 为 1 或者大于等于输入字符串 s 的长度，则不需要进行 Z 字形排列，直接返回原字符串。
总体来说，这个问题的关键是找到字符在 Z 字形排列中的规律，通过模拟过程来进行排列，最终得到 Z 字形排列后的结果。
package main
import "fmt"
func convert(s string, numRows int) string {
if numRows == 1 || numRows >= len(s) {
return s
}
// 创建一个 numRows 行的二维切片，用于模拟 Z 字形排列
result := make([][]byte, numRows)
for i := range result {
result[i] = make([]byte, 0)
}
row := 0 // 当前行数
direction := 1 // 方向，1 表示向下走，-1 表示向上走
for i := 0; i < len(s); i++ {
// 将当前字符放入对应的行
result[row] = append(result[row], s[i])
// 判断是否需要改变方向
if row == 0 {
direction = 1
} else if row == numRows-1 {
direction = -1
}
// 根据方向更新行数
row += direction
}
// 将二维切片中的字符拼接成一个字符串
var output string
for _, row := range result {
output += string(row)
}
return output
}
func main() {
inputString := "PAYPALISHIRING"
numRows := 3
output := convert(inputString, numRows)
fmt.Println(output)
}
7.整数反转
https://leetcode.cn/problems/reverse-integer/
题目
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
解决方案
解题思路：
- 初始化结果变量
result为0，表示反转后的整数。 - 初始化符号位
sign为1，表示输入整数的符号（正数为1，负数为-1）。 - 处理输入整数的符号：如果输入整数
x为负数，则将sign设置为-1，并将x取绝对值，这样我们可以将整数反转时当作正数来处理。 - 使用循环逐位反转整数
x：
a. 从原数字的最低位开始取出一位，可以通过取余操作x % 10来实现。
b. 将当前位添加到结果result中，可以通过将result乘以10再加上当前位来实现。
c. 检查是否会导致溢出，即检查result是否大于math.MaxInt32或小于math.MinInt32。
d. 继续处理下一位，即将x除以10。 - 返回
result乘以符号位sign作为最终结果。
这样，我们可以实现整数反转，并在反转时处理溢出的情况。
package main
import (
"fmt"
)
func reverse(x int) int {
// 定义结果变量和符号位
result := 0
sign := 1
// 处理符号位
if x < 0 {
sign = -1
x = -x
}
// 反转整数
for x > 0 {
// 从原数字的最低位开始取出一位
digit := x % 10
// 处理溢出情况
if result > (1<<31-1-digit)/10 {
return 0
}
// 将当前位添加到结果中
result = result*10 + digit
// 继续处理下一位
x /= 10
}
// 考虑符号位
return result * sign
}
func main() {
// 测试
fmt.Println(reverse(123)) // 输出：321
fmt.Println(reverse(-123)) // 输出：-321
fmt.Println(reverse(120)) // 输出：21
fmt.Println(reverse(1534236469)) // 输出：0（溢出情况）
}
8.字符串转换整数(atoi)
https://leetcode.cn/problems/string-to-integer-atoi/
题目
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
- 读入字符串并丢弃无用的前导空格
- 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
- 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为
0。必要时更改符号（从步骤 2 开始）。 - 如果整数数超过 32 位有符号整数范围
[−231, 231 − 1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于−231的整数应该被固定为−231，大于231 − 1的整数应该被固定为231 − 1。 - 返回整数作为最终结果。
注意：
- 本题中的空白字符只包括空格字符
' '。 - 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
示例 1：
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："42"（读入 "42"）
^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：
输入：s = " -42"
输出：-42
解释：
第 1 步：" -42"（读入前导空格，但忽视掉）
^
第 2 步：" -42"（读入 '-' 字符，所以结果应该是负数）
^
第 3 步：" -42"（读入 "42"）
^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：
输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
解决方案
- 去除前导空格：首先，函数会使用
strings.TrimSpace去除输入字符串开头的所有空格。 - 处理符号：接下来，函数会检查字符串的第一个非空字符。如果这个字符是正号
+或负号-，函数会根据正负号确定最终结果是正数还是负数。如果没有正负号，函数默认结果为正数。之后，函数会移动指针到下一个字符。 - 转换数字：接着，函数会遍历字符串中的字符，只处理数字字符。它会将字符转换为对应的数字，并将其累积到最终的结果中。这个过程会一直持续，直到遇到一个非数字字符或者到达输入字符串的末尾。
- 处理溢出：在转换数字的过程中，函数会检查每一步是否会导致整数溢出。如果当前的结果大于 32 位有符号整数范围的最大值除以 10，或者等于最大值除以 10 且当前数字大于最大值模 10，那么就会发生溢出。根据结果的正负性，函数会返回
math.MaxInt32或math.MinInt32，以避免溢出。 - 返回结果：最终，函数会将累积的结果乘以之前确定的符号，并将整数作为最终结果返回。
import (
"math"
"strings"
)
func myAtoi(s string) int {
// 去除字符串开头的所有空格
s = strings.TrimSpace(s)
// 若字符串为空，返回0
if len(s) == 0 {
return 0
}
var sign int = 1 // 符号，默认为正
var result int = 0 // 结果
var i int = 0 // 当前指针位置
// 处理符号
if s[i] == '+' || s[i] == '-' {
if s[i] == '-' {
sign = -1 // 若为负号，则修改符号为负
}
i++ // 移动指针到下一个字符
}
// 遍历字符串中的字符，处理数字
for i < len(s) && s[i] >= '0' && s[i] <= '9' {
digit := int(s[i] - '0') // 将字符转换为数字
// 检查是否会发生溢出
if result > math.MaxInt32/10 || (result == math.MaxInt32/10 && digit > math.MaxInt32%10) {
if sign == 1 {
return math.MaxInt32 // 正数溢出，返回最大值
} else {
return math.MinInt32 // 负数溢出，返回最小值
}
}
result = result*10 + digit // 更新结果
i++ // 移动指针到下一个字符
}
return result * sign // 返回最终结果，考虑符号
}
9.回文数
https://leetcode.cn/problems/palindrome-number/
题目
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
解决方案
func isPalindrome(x int) bool {
// 负数不可能是回文数，因为负号会导致数字的倒序与正序不同
if x < 0 {
return false
}
original := x // 保存原始数值
reversed := 0 // 用于存储倒序的数值
for x > 0 {
digit := x % 10 // 获取最后一位数字
reversed = reversed*10 + digit // 更新倒序数值
x /= 10 // 去掉最后一位数字
}
// 如果倒序数值与原始数值相等，则为回文数
return original == reversed
}
10.正则表达式匹配
https://leetcode.cn/problems/regular-expression-matching/
题目
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
解决方案
func isMatch(s string, p string) bool {
m := len(s)
n := len(p)
// 定义一个二维数组来保存匹配结果
dp := make([][]bool, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]bool, n+1)
}
// 空字符串和空正则表达式是匹配的
dp[0][0] = true
// 初始化首行，处理正则表达式中可能出现的连续 '*' 情况
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
dp[0][j] = dp[0][j-2]
}
}
// 填充二维数组
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if s[i-1] == p[j-1] || p[j-1] == '.' {
dp[i][j] = dp[i-1][j-1]
} else if p[j-1] == '*' {
// 处理 '*' 的情况
dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'))
}
}
}
return dp[m][n]
}