【开始刷题啦——Leetcode《初级算法》（Go语言）】

持续更新中…

删除排序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致

思路：
采用双指针的方法

func removeDuplicates(nums []int) int {
    length := len(nums)
    if length == 0{ // 排除特殊情况
        return 0
    }
    // 双指针实现
    low := 0
    for high := 1;high < length;high++{
        if nums[low] != nums[high]{  
            low ++
            nums[low] = nums[high]
        }
    }
    return low + 1
}

买卖股票的最佳时机 II

旋转数组

存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

思路：
字典

import "fmt"
func containsDuplicate(nums []int) bool {
    digitCount := make(map[int]int)

    for i := 0;i < len(nums);i++{
        if  _,ok := digitCount[nums[i]];ok{ // 说明这个数字之前出现过
            return true
        }else {
            digitCount[nums[i]] = 0
        }
    }
    return false
}

只出现一次的数字

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

思路：
字典

func singleNumber(nums []int) int {
    digitCount := make(map[int]int)

    for i := 0;i < len(nums);i++{
        if _,ok := digitCount[nums[i]];ok{ // 说明这个数字之前出现过
            digitCount[nums[i]] += 1
        }else{
            digitCount[nums[i]] = 1
        }
    }
    var ret int
    for k,v := range(digitCount){
        if v == 1{
            ret = k
            break
        }
    }
    return ret
}

两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

思路：
用字典记录数组中数字个数

func intersect(nums1 []int, nums2 []int) []int {
    // 用两个字典存储两个数组中数字的个数
    digitCount1 := make(map[int]int)
    digitCount2 := make(map[int]int)

    // 记录两个数组中数字的个数
    for i := 0;i < len(nums1);i++{
        if _,ok := digitCount1[nums1[i]];ok{
            digitCount1[nums1[i]] += 1
        }else{
            digitCount1[nums1[i]] = 1
        }
    }

    for i := 0;i < len(nums2);i++{
        if _,ok := digitCount2[nums2[i]];ok{
            digitCount2[nums2[i]] += 1
        }else{
            digitCount2[nums2[i]] = 1
        }
    }

    // 求交集
    ret := []int{}
    for k,v1 := range(digitCount1){
        if _,ok := digitCount2[k];ok{ // 说明k在nums1和nums2都存在
            v2 := digitCount2[k]
            if v1 < v2{
                for i := 0;i < v1;i++{
                    ret = append(ret,k)
                }
            }else{
                for i := 0;i < v2;i++{
                    ret = append(ret,k)
                }
            }
        }
    }
    return ret
}

加1

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

import "fmt"
func plusOne(digits []int) []int {
    i := len(digits) - 1 // 指针指向最后一位，而后往前移动
    
    flag := false // 进位标志位
    var tmp int

    numSum := []int{}

    // 将最后一位加入
    tmp = digits[i] + 1
    if tmp > 9{
        flag = true
        numSum = append(numSum,0)
    }else{
        numSum = append(numSum,tmp)
    }

    // 把剩余几位加入
    for i = i - 1;i > -1;i--{
        if flag{
            flag = false
            tmp = digits[i] + 1
            if tmp > 9{
                numSum = append(numSum,0)
                flag = true
            }else{
                numSum = append(numSum,tmp)
            }
        }else{
            //fmt.Println(digits[i])
            tmp = digits[i]
            if tmp > 9{
                numSum = append(numSum,0)
                flag = true
            }else{
                numSum = append(numSum,tmp)
            }
        }
    }

    
    if flag{ // 说明还需要进位
        numSum = append(numSum,1)
    }

    ret := []int{}
    for i := len(numSum) - 1;i > -1;i--{
        ret = append(ret,numSum[i])
    }

    return ret
}

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

思路：
双指针

func moveZeroes(nums []int)  {
    left,right,length := 0,0,len(nums)
    for right < length{
        if nums[right] != 0{
            nums[left],nums[right] = nums[right],nums[left]
            left ++
        }
        right ++
    }
    
}

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

思路：
哈希表

func twoSum(nums []int, target int) []int {
    countMap := make(map[int]int) // 采用字典，k-v：数字-下标

    ret := []int{}

    for i := 0;i < len(nums);i++{
        if _,ok := countMap[target - nums[i]];ok{ // 说明找到答案了
            ret = append(ret,countMap[target - nums[i]])
            ret = append(ret,i)
            break
        }else{
            countMap[nums[i]] = i
        }
    }
    return ret
}

有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

import "fmt"
func isValidSudoku(board [][]byte) bool {
   
   
    // 检查行
    for i := 0;i < 9;i++{
        row := make(map[byte]int)
        for j := 0;j < 9;j++{
            if board[i][j] == '.'{
                continue
            }
            if _,ok := row[board[i][j]];ok{ // 说明一行中有数字重复
                return false
            }else{
                row[board[i][j]] = 1
            }
        }
    }

    // 检查列
    for j := 0;j < 9;j++{
        column := make(map[byte]int)
        for i := 0;i < 9;i++{
            if board[i][j] == '.'{
                continue
            }
            if _,ok := column[board[i][j]];ok{
                return false
            }else{
                column[board[i][j]] = 1
            }
        }
    }

    // 检查3*3矩阵
    boardMatrix := make([]map[byte]int,9)
    for i := 0;i < 9;i++{
        boardMatrix[i] = make(map[byte]int)
    }
    // fmt.Println(boardMatrix)
    for i := 0;i < 9;i ++{
        for j := 0;j < 9;j ++{
            if board[i][j] == '.'{
                continue
            }
            index := (i / 3) * 3 + j / 3
            // fmt.Println(index)
            if _,ok := boardMatrix[index][board[i][j]];ok{
                return false
            }else{
                boardMatrix[index][board[i][j]] = 1
            }

        }
    }
    return true
}

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

import "fmt"
func rotate(matrix [][]int)  {
    n := len(matrix)

    // 转换公式
    // matrix[i][j] --> matrix[j][n-i-1]

    for i := 0;i < n / 2;i ++{
        for j := 0;j < (n + 1) / 2;j++{
            matrix[i][j],matrix[n - j - 1][i],matrix[n - i - 1][n - j - 1],matrix[j][n - i - 1] = matrix[n - j - 1][i],matrix[n - i - 1][n - j - 1],matrix[j][n - i - 1],matrix[i][j]
        }
    }

}

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

func reverseString(s []byte)  {
    n := len(s)

    for i := 0;i < n / 2;i++{
        s[i],s[n - i - 1] = s[n - i - 1],s[i]
    }

}

整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。

感觉这一题的测试用例有点问题

// import "fmt"
func reverse(x int) int {
    // 首先判断数字是否为负
    flag := false
    if x < 0{
        x = -x
        flag = true
    }
    

    digit := []int{}
    for x != 0{
        digit = append(digit,x % 10)
        x = x / 10
    }

    var ret int
    for i := 0;i < len(digit);i++{
        ret  = ret * 10 + digit[i]
    }

    if flag{
        ret = -ret
    }

    
    if (ret >= (-1 * (2<<31))) && (ret <= (2<<31 - 1)){
        return ret
    }else{
        return 0
    }

}

字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

func firstUniqChar(s string) int {
    // 对string中的字母进行统计
    charCount := make(map[byte][]int)
    for i := 0;i < len(s);i++{
        if _,ok := charCount[s[i]];ok{
            charCount[s[i]] = append(charCount[s[i]],i)
        }else{
            charCount[s[i]] = []int{}
            charCount[s[i]] = append(charCount[s[i]],i)
        }
    }
    
    min_index := len(s)
    // 找到其中出现过一次的
    for _,v := range(charCount){
        if len(v) == 1{ // 说明只出现一次
            if v[0] < min_index{
                min_index = v[0]
            }
        }
    }
    if min_index == len(s){
        return -1
    }else{
        return min_index
    }
}

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

func isAnagram(s string, t string) bool {

    if len(s) != len(t){
        return false
    }
    charCount := make(map[byte]int)

    for i := 0;i < len(s);i++{
        if _,ok := charCount[s[i]];ok{
            charCount[s[i]] += 1
        }else{
            charCount[s[i]] = 1
        }
    }

    for i := 0;i < len(t);i++{
        if _,ok := charCount[t[i]];ok{
            charCount[t[i]] -= 1
        }else{
            charCount[t[i]] = -1
        }
    }
    
    for _,v := range(charCount){
        if v != 0{
            return false
        }
    }
    return true
}

验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

func isPalindrome(s string) bool {
    s = strings.ToLower(s)
    for low,high := 0,len(s) - 1;low <= high;{
        // 首先需要排除指向不是字母的情况
        if !isDigit(s[low]){
            low++
            continue
        } 
        if !isDigit(s[high]){
            high--
            continue
        }

        if s[high] != s[low]{
            return false
        }else{
            high--
            low++
        }
    }
    return true
}

func isDigit(b byte) bool{
    return (b >= 'a' && b <= 'z') || (b >= 'A' && b <= 'Z') || (b >= '0' && b <= '9')
}

字符串转换整数 (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 。
返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

import "math"
func myAtoi(s string) int {
    index := 0
    // 读取前置空格
    for index < len(s){
        if s[index] == ' '{
            index ++
        }else{
            break
        }
    }

    
    flag := false // 负数标志位

    // 读取符号位
    if index < len(s){
        if s[index] == '-'{
            flag = true
            index ++
        }else if s[index] == '+'{
            index ++
        }
    }

    ret := 0
    tmp := 0

    // 读取数字
    for index < len(s){
        if s[index] >= '0' && s[index] <= '9'{
            tmp = ret
            ret = ret * 10 + int(s[index] - '0')
            if ret / 10 != tmp{ // 说明越界了
                ret = math.MaxInt
                break
            }
            index ++
        }else{
            break
        }
    }

    
    
    if flag{
        ret = -ret
    }

    

    if ret > int(math.MaxInt32){
        ret =  int(math.MaxInt32)
    }else if ret < int(math.MinInt32){
        ret = int(math.MinInt32)
    }
    return ret
}

实现 strStr()

实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

func strStr(haystack string, needle string) int {
    // KMP算法
    if len(needle) == 0{
        return 0
    }
    next := getNext(needle)
    j := 0
    for i := 0;i < len(haystack);i++{
        for j > 0 && haystack[i] != needle[j]{
            j = next[j - 1]
        }
        if haystack[i] == needle[j]{
            j ++
        }
        if j == len(needle){
            return i - j + 1
        }
    }
    return -1
}

func getNext(needle string) []int{
    next := make([]int,len(needle))
    k := 0
    for i := 1;i < len(needle);i++{
        for k > 0 && needle[k] != needle[i]{
            k = next[k - 1]
        }
        if needle[k] == needle[i]{
            k++
        }
        next[i] = k
    }
    return next
}