Golang leetcode刷题记录【一】

📒 笔记 · 02-19

Golang学习过程中leetcode刷题笔记。。。

罗马数字转整数

leetcode:13:https://leetcode.cn/problems/roman-to-integer/description/

题目描述：

思路：

  • 罗马数字中，当左边的数字小于右边的数字时，则需要减去小的数字，比如：“IV” => 5-1=4
  • 当左边的数字大于右边时，则是相加。比如:"VI" => 5+1=6
  • 所以，将输入的字符串使用 strings.Split 切片处理，并循环遍历，当第一个字符对应的值小于后一个时，总数就减去第一个字符对应的数字，否则就相加。但是只遍历到倒数第二个字符，因为在循环中需要比较每个字符和其后一个字符的值
  • 最后一个字符没有和其后一个字符进行比较，因为它是最后一个字符了，没有后续字符了。因此，在循环结束后需要将最后一个字符对应的整数值加到 nums 中，
func romanToInt(s string) int {
    var values = map[string]int{"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    n := len(s)
    nums := 0
    slice := strings.Split(s, "")

    for i := 0; i < n-1; i++ {
        if values[slice[i]] < values[slice[i+1]] {
            nums -= values[slice[i]]
        } else {
            nums += values[slice[i]]
        }
    }
    nums += values[slice[n-1]]
    return nums
}

找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

  1. 自己的暴力解法思路：
  • 循环遍历haystack ，如果遍历到的字符和needle的第一个字符相同，则继续遍历needle，看是否needle后面的字符是否和haystack相等。并设置一个标志位来表示是否相等。
  • 当出现不相等时，跳出循环，标志位置于false
  • 当第二个循环结束时，判断标志位是否为真，为真时表示遍历完needle发现全部匹配，则返回索引值。为false时则是由于不相等才跳出的循环。则继续遍历haystack中的字符串。

直接索引字符串得到的是该字符串中相应位置的字节值（即 ASCII 码值）。

如果有一个字符串 str := "hello"，那么 str[0] 将返回 104，对应 ASCII 码值为 'h'；str[1] 将返回 101，对应 ASCII 码值为 'e'，以此类推。

func strStr(haystack string, needle string) int {
    for i := 0; i < len(haystack)-len(needle)+1; i++ {
        if haystack[i] == needle[0] {
            found := true // 设置标志位来表示是否找到匹配
            for j := 1; j < len(needle); j++ {
                if haystack[i+j] != needle[j] {
                    found = false
                    break
                }
            }
            if found {
                return i
            }
        }
    }
    return -1
}
  1. 使用内置函数strings.Index
func strStr(haystack string, needle string) int {
    return strings.Index(haystack, needle)
}

Index 函数会返回子串在主字符串中第一次出现的位置索引。如果子串不存在于主字符串中，则返回 -1。

有效的字母异位词

leetcode242

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true
示例 2:

输入: s = "rat", t = "car"
输出: false

  1. 自己的方法

思路：

  • 如果s和t长度不一样，一定不是字母异位词，直接返回 false
  • 长度一样时：新建映射，循环遍历第一个，循环到的字符的键值加一
  • 遍历循环第二个，循环到的字符的键值减一
  • 当出现某个元素的键值小于0时，则说明两个字符串中这个字符的数量不同，直接返回false。如果检查完键值都归0，则说明两个字符串是字母异位词，返回true
func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    count := make(map[rune]int)
    for _, item := range s {
        count[item]++
    }
    for _, item := range t {
        count[item]--
        if count[item] < 0 {
            return false
        }
    }
    return true
}
新建映射的rune的含义：用于表示 Unicode 字符（Unicode code point）。rune 类型实际上是 int32 类型的别名。

移动零

leetcode283

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

个人思路:

  • 初始化zeros为0，记录当前已经处理了多少个非零元素，并且也作为下一个非零元素应该放置的位置索引。

  • 在第一个循环中，我们遍历原始数组 nums，对于每个元素：

    • 如果当前元素不为零，则将其移动到数组的前面，并更新 zeros 的值，使其指向下一个位置。
    • 如果当前元素为零，则不做任何操作。
  • 这样，在第一个循环结束后，所有的非零元素都被移动到了数组的前面，并且 zeros 的值表示了非零元素的个数，同时也表示了数组的前面几个位置都已经被填充了非零元素。
  • 在第二个循环中，我们将数组中剩余的位置都填充为零，从 zeros 的位置开始到数组的末尾。因为在第一个循环中，已经将所有的非零元素移动到了数组的前面，所以剩余的位置就应该都填充为零，以保持原始数组的长度不变。
func moveZeroes(nums []int)  {
    zeros := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] != 0 {
            nums[zeros] = nums[i]
            zeros++
        }
    }
    for i := zeros; i < len(nums); i++ {
        nums[i] = 0
    }
}

x 的平方根

leetcode69

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

个人思路：

  • 循环找到数i，这个数的平方小于x，但是i+1的平方大于x。i就是x的平方根的整数部分
func mySqrt(x int) int {
    i := 0
    for {
        if i*i <= x {
            if (i+1)*(i+1) > x {
                return i
            }
        }
        i++
    }
}

合并两个有序数组

leetcode88

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

个人思路：

  • 遍历nums2，将元素的值覆盖nums1
  • 最后使用标准库 sort.Ints() 对数组从小到大排序。
func merge(nums1 []int, m int, nums2 []int, n int)  {
    for index, value := range nums2 {
        fmt.Println(index, value)
        nums1[m+index] = value
    }
    sort.Ints(nums1)
}

只出现一次的数字

leetcode136

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

  1. 方法1：循环遍历

(空间复杂度超标,使用了变量额外空间，不合题意)

  • 新建空映射，循环遍历nums，元素出现一次就在映射元素对应的值上加一
  • 循环遍历新建的映射，找到键值为1的元素返回
func singleNumber(nums []int) int {
    result := make(map[int]int)
    for _,value := range nums {
        result[value] += 1
    }
    num := 0
    for index, value := range result {
        if value == 1 {
            num = index
        }
    }
    return num
}
  1. 方法2：位运算

使用异或运算 ⊕ 。异或运算有以下三个性质:

  • 任何数和 0 做异或运算，结果仍然是原来的数
  • 任何数和其自身做异或运算，结果是 0 。
  • 异或运算满足交换律和结合律。
func singleNumber(nums []int) int {
    single := 0
    for _, num := range nums {
        single ^= num
    }
    return single
}

验证回文串

leetcode

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

自己的思路：

  • 首先正则表达式去除字符串中的其他字符，只保留字母和数字
  • 将所有字符转为小写，使用 strings.ToLower()
  • 遍历，第 i 个字符和第 -i 个字符是否相等，如果出现不相等直接返回 false 。只需要遍历字符的一半即可。
func isPalindrome(s string) bool {
    if s == "" {
        return true
    }
    reg := regexp.MustCompile("[^a-zA-Z0-9]+")
    result := reg.ReplaceAllString(s, "")
    result = strings.ToLower(result)
    for i := 0; i < len(result)/2; i++ {
        if result[i] != result[len(result)-i-1] {
            return false
        }
    }
    return true
}
Go
2021 - 2024 Echo's Blog. All Rights Reserved.
Theme Jasmine by Kent Liao