Leetcode算法题解

记录一下Leetcode数组分类基础算法题解。一直想在平时不忙的时候回来练习一下自己的算法思维,毕竟在普通业务中是很少会直接用到算法的,但不可否认,算法于程序员而言,是一剂良药。

阅读指引

序号 类型 题目 链接
1 数组 T1: 从排序数组中删除重复项 leetcode
2 数组 T2: 买卖股票的最佳时机 II leetcode
3 数组 T3: 旋转数组 leetcode
4 数组 T4: 存在重复 leetcode
5 数组 T5: 只出现一次的数字 leetcode
6 数组 T6:两个数组的交集II leetcode
7 数组 T7: 加一 leetcode
8 数组 T8: 移动零 leetcode
9 数组 T9: 两数之和 leetcode
10 数组 T10: 有效的数独 leetcode
11 数组 T11 :旋转图像 leetcode
12 数学 T12: 罗马数字转整数 leetcode
13 数学 T13: 3的幂 leetcode
14 数学 T14: 计数质数 leetcode
15 数学 T15: Fizz Buzz leetcode
16 字符串 T16: 反转字符串 leetcode
17 字符串 T17: 整数反转 leetcode
18 字符串 T18:字符串中的第一个唯一字符 leetcode
19 字符串 T19: 有效的字母异位词 leetcode
20 字符串 T20: 验证回文字符串 leetcode
21 字符串 T21: 字符串转换整数 (atoi) leetcode
22 字符串 T22: 实现strStr() leetcode
23 字符串 T23:报数 leetcode
24 字符串 T24:最长公共前缀 leetcode
25 链表 T25:删除链表中的节点 leetcode
26 链表 T26:删除链表的倒数第N个节点 leetcode

T1: 从排序数组中删除重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/21/

func removeDuplicates(nums []int) int {
    x := len(nums) - 1
    for i := 0; i < x; i++ {
        if nums[i] == nums[i+1] {
            nums = append(nums[0:i], nums[i+1:]...)
            x--
            i--
        }
    }
    return len(nums)
}

T2: 买卖股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/22/

func maxProfit(prices []int) int {
    var profit = 0
    for i:=1;i<len(prices);i++ {
        if prices[i-1] < prices[i] {
            profit += (prices[i]-prices[i-1])
        } 
    }
    return profit
}

T3: 旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

//https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/23/

func rotate(nums []int, k int)  {
    for i:=0;i<k;i++ {
        x := nums[len(nums)-1]
        for j:=len(nums)-1;j>=1;j-- {
            nums[j] = nums[j-1]
        }
        nums[0] = x
    }
}

T4: 存在重复

给定一个整数数组,判断是否存在重复元素。如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/24/

func containsDuplicate(nums []int) bool {
    for i:=0;i<len(nums)-1;i++ {
        for j:=i+1;j<len(nums);j++ {
            if nums[i]==nums[j] {
                return true
            }
        }
    }
    return false
}

T5: 只出现一次的数字

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

// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/

func singleNumber(nums []int) int {
    ret := 0
    for _,v := range nums {
        ret ^= v
    }
    return ret
}

T6:两个数组的交集II

给定两个数组,编写一个函数来计算它们的交集。

// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/26/

func intersect(nums1 []int, nums2 []int) []int {
    ret := make([]int, 0)
    rmp := make(map[int]int, 0)
    for _, v := range nums1 {
        if count, ok := rmp[v]; ok {
            rmp[v] = count + 1
        } else {
            rmp[v] = 1
        }
    }

    for _, v := range nums2 {
        if count, ok := rmp[v]; ok {
            ret = append(ret, v)
            if count == 1 {
                delete(rmp, v)
            } else {
                rmp[v] = count - 1
            }
        }
    }
    return ret
}

T7: 加一

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

// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/27/

func plusOne(digits []int) []int {
    x := 0
    for i:=len(digits)-1;i>=0;i-- {
        y := digits[i] + x
        if i == len(digits)- 1 {
            y = digits[i]+1 + x
        }
        if y >= 10 {
            x = 1
            digits[i] = digits[i]+1 - 10
        }else {
            digits[i] = y
            x = 0
        }
    }
    ret := make([]int,0)
    if x > 0 {
        ret = append(ret,1)
    }
    ret = append(ret,digits...)
    return ret
}

T8: 移动零

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

// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/28/

func moveZeroes(nums []int)  {
    x := len(nums)
    for i:=0;i<x;i++ {
        if nums[i]==0 {
            for j:=i+1;j<len(nums);j++ {
                nums[j-1]= nums[j]
            }
            nums[len(nums)-1] = 0
            x --
            i -- 
        }
    }
}

T9: 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

func twoSum(nums []int, target int) []int {
    for i:=0;i<len(nums)-1;i++ {
        for j:=i+1;j<len(nums);j++ {
            if nums[i]+nums[j] == target {
                return []int{i,j}
            }
        }
    }
    return []int{}
}

T10: 有效的数独

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

//https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/30/

func isValidSudoku(board [][]byte) bool {
    for _, row := range board {
        x := [10]int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
        for _, col := range row {
            tmp := convert(col)
            if tmp == 0 {
                continue
            }
            if x[tmp] == 1 {
                return false
            }
            x[tmp] = 1
        }
    }

    for i := 0; i < len(board); i++ {
        y := [10]int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
        for j := 0; j < len(board); j++ {
            tmp := convert(board[j][i])
            if tmp == 0 {
                continue
            }
            if y[tmp] == 1 {
                return false
            }
            y[tmp] = 1

        }
    }

    for i := 0; i < len(board); i += 3 {
        for j := 0; j < len(board); j += 3 {
            xy := [10]int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
            if xy[convert(board[i][j])] == 1 && convert(board[i][j]) != 0 {
                return false
            }
            xy[convert(board[i][j])] = 1

            if xy[convert(board[i+1][j])] == 1 && convert(board[i+1][j]) != 0 {
                return false
            }
            xy[convert(board[i+1][j])] = 1

            if xy[convert(board[i+2][j])] == 1 && convert(board[i+2][j]) != 0 {
                return false
            }
            xy[convert(board[i+2][j])] = 1

            if xy[convert(board[i][j+1])] == 1 && convert(board[i][j+1]) != 0 {
                return false
            }
            xy[convert(board[i][j+1])] = 1

            if xy[convert(board[i+1][j+1])] == 1 && convert(board[i+1][j+1]) != 0 {
                return false
            }
            xy[convert(board[i+1][j+1])] = 1

            if xy[convert(board[i+2][j+1])] == 1 && convert(board[i+2][j+1]) != 0 {
                return false
            }
            xy[convert(board[i+2][j+1])] = 1

            if xy[convert(board[i][j+2])] == 1 && convert(board[i][j+2]) != 0 {
                return false
            }
            xy[convert(board[i][j+2])] = 1

            if xy[convert(board[i+1][j+2])] == 1 && convert(board[i+1][j+2]) != 0 {
                return false
            }
            xy[convert(board[i+1][j+2])] = 1

            if xy[convert(board[i+2][j+2])] == 1 && convert(board[i+2][j+2]) != 0 {
                return false
            }
            xy[convert(board[i+2][j+2])] = 1
        }
    }
    return true
}

func convert(b byte) int {
    switch b {
    case '1':
        return 1
    case '2':
        return 2
    case '3':
        return 3
    case '4':
        return 4
    case '5':
        return 5
    case '6':
        return 6
    case '7':
        return 7
    case '8':
        return 8
    case '9':
        return 9
    default:
        return 0
    }
    return 0
}

T11 :旋转图像

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/31/

func rotate(matrix [][]int)  {
    var length = len(matrix);

    for i:= 0; i < length; i++ {
        for j := 0; j < length - i; j++ {
             var tmp = matrix[i][j]
             matrix[i][j] = matrix[length - j - 1][length - i - 1]
             matrix[length - j - 1][length - i - 1] = tmp
         }
     }

    for i:= 0; i < length; i++ {
        for j := 0; j < length / 2; j++ {
             var tmp = matrix[j][i]
             matrix[j][i] = matrix[length - j - 1][i]
             matrix[length - j - 1][i] = tmp
         }
     }
}

T12: 罗马数字转整数

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

//https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/25/math/63/

func romanToInt(s string) int {
    x := make([]int,0)
    for len(s) > 0 {
        if strings.Index(s,"CM") == 0 {
            x = append(x,900)
            s = s[2:]
            continue
        }
        if strings.Index(s,"CD") == 0 {
            x = append(x,400)
            s = s[2:]
            continue
        }
        if strings.Index(s,"XC") == 0 {
            x = append(x,90)
            s = s[2:]
            continue
        } 
        if strings.Index(s,"XL") == 0 {
            x = append(x,40)
            s = s[2:]
            continue
        } 
        if strings.Index(s,"IX") == 0 {
            x = append(x,9)
            s = s[2:]
            continue
        }
        if strings.Index(s,"IV") == 0 {
            x = append(x,4)
            s = s[2:]
            continue
        }
        if strings.Index(s,"M") == 0 {
            x = append(x,1000)
            s = s[1:]
            continue
        }
        if strings.Index(s,"D") == 0 {
            x = append(x,500)
            s = s[1:]
            continue
        }
        if strings.Index(s,"C") == 0 {
            x = append(x,100)
            s = s[1:]
            continue
        }
        if strings.Index(s,"L") == 0 {
            x = append(x,50)
            s = s[1:]
            continue
        }
        if strings.Index(s,"X") == 0 {
            x = append(x,10)
            s = s[1:]
            continue
        }
        if strings.Index(s,"V") == 0 {
            x = append(x,5)
            s = s[1:]
            continue
        }
        if strings.Index(s,"I") == 0 {
            x = append(x,1)
            s = s[1:]
            continue
        }
    }
    ret := 0 
    for _,v := range x {
        ret += v
    }
    return ret
}

T13: 3的幂

给定一个整数,写一个函数来判断它是否是 3 的幂次方。

func isPowerOfThree(n int) bool {
    return n > 0 && int64(math.Pow(3,19)) % int64(n) == 0
}

T14: 计数质数

统计所有小于非负整数 n 的质数的数量。

func countPrimes(n int) int {
    ret := 0
    if n > 2 {
        ret = 1
    }
    for i:=3;i<n;i++ {
        if i%2 == 0 {
            continue
        }
        t := math.Sqrt(float64(i)) + 1
        isP := true
        for j:=2;j<int(t);j++ {
            if i%j ==0 {
                isP = false
                break
            }
        }
        if isP {
            ret ++
        }
    }
    return ret
}

T15: Fizz Buzz

写一个程序,输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数,输出“Fizz”
  2. 如果 n 是5的倍数,输出“Buzz”
  3. 如果 n 同时是3和5的倍数,输出 “FizzBuzz”
func fizzBuzz(n int) []string {
    ret := make([]string,n)
    for i:=1;i<=n;i++ {
        var x = ""
        if i % 3 == 0 {
            x = "Fizz"
        }
        if i % 5 == 0 {
            x += "Buzz"
        }
        if x == "" {
            x = strconv.FormatInt(int64(i),10)
        }
        ret[i-1] = x
    }
    return ret
}

T16: 反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

func reverseString(s []byte)  {
    for i:=0;i<len(s)/2;i++ {
        s[i],s[len(s)-i-1] = s[len(s)-i-1],s[i]
    }
}

T17: 整数反转

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

func reverse(x int) int {

    if x > (1<<31 - 1) {
        return 0
    }

    if x < -(1<<31 - 1) {
        return 0
    }

    ret := 0

    s := make([]int, 0)
    var l = x

    for {
        if x == 0 {
            break
        }
        l = x % 10
        x = x / 10
        s = append(s, l)
    }

    t := 1
    for i := len(s) - 1; i >= 0; i-- {

        ret += t * s[i]
        t *= 10
    }

    if ret < -(1<<31-1) || ret > (1<<31-1) {
        return 0
    }

    return ret
}

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

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

func firstUniqChar(s string) int {
    var x rune
    var count = len(s)
    m := make(map[rune]int, 0)
    for _, c := range s {
        co, _ := m[c]
        m[c] = co + 1
    }
    for _, v := range m {
        if v < count {
            count = v
        }
    }

    if count != 1 {
        return -1
    }

    for _, c := range s {
        if m[c] == count {
            x = c
            break
        }
    }

    return strings.Index(s, string(x))
}

T19: 有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的一个字母异位词。你可以假设字符串只包含小写字母。

func isAnagram(s string, t string) bool {  
    for {
        if len(s) == 0 || len(t) == 0 {
            break
        }
        if len(s) != len(t) {
            return false
        }
        v := s[0]
        s = s[1:]
        idx := strings.Index(t,string(v))
        if idx == -1 {
            return false
        }
        t = t[0:idx] + t[idx+1:]
    }
    return true
}

T20: 验证回文字符串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

func isPalindrome(s string) bool {
    s = strings.ToLower(s)
    st := ""
    for _,v := range s {
        if (v >= '0' && v <= '9') || (v >= 'a' && v<= 'z'){
            st += string(v)
        }
    }
    for i:=0;i<len(st)/2;i++ {
        if st[i] != st[len(st)-i-1] {
            return false
        }
    }
    return true
}

T21:字符串转换整数 (atoi)

请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。 该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。 注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。 在任何情况下,若函数不能进行有效的转换时,请返回 0。

func myAtoi(str string) int {
    x := ""
    isBegin := false
    for _, v := range str {
        if ((v == '-' || v == '+') || (v >= '0' && v <= '9')) && !isBegin {
            isBegin = true
            x += string(v)
            continue
        } else if !isBegin && v != ' ' {
            break
        }
        if isBegin {
            if !(v >= '0' && v <= '9') {
                break
            }
            x += string(v)
        }
    }

    if x == "" {
        return 0
    }

    fator := 1
    if x[0] == '-' {
        fator = -1
        x = x[1:]
    } else if x[0] == '+' {
        x = x[1:]
    }

    ret := 0
    for i := 0; i < len(x); i++ {

        tmp := math.Pow(10, float64(len(x)-i-1)) * float64(x[i]-'0')
        if tmp*float64(fator) > 1<<31-1 {
            return (1<<31 - 1)
        }
        if tmp*float64(fator) < -(1 << 31) {
            return -(1 << 31)
        }

        ret += int(tmp)
    }

    ret = ret * fator

    if ret <= -(1<<31)-1 {
        return -1 << 31
    }
    if ret > 1<<31-1 {
        return 1<<31 - 1
    }
    return ret
}

T22:实现strStr()

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

func strStr(haystack string, needle string) int {
    return strings.Index(haystack,needle)
}

T23:报数

报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:

1.     1
2.     11
3.     21
4.     1211
5.     111221
1  被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"), 即 21。
21 被读作 "one 2",  "one 1" ("一个二" ,  "一个一") , 即 1211。
给定一个正整数 n(1 ≤ n ≤ 30),输出报数序列的第 n 项。
注意:整数顺序将表示为一个字符串。

这个题目要理解题意,千万不要被题目的解释给绕进去了。

func countAndSay(n int) string {
    if n == 1 {
        return "1"
    }
    x := "1"
    for i := 2; i <= n; i++ {
        tmpRet := ""
        count := 0
        tmpChar := ""
        for j := 0; j < len(x); j++ {
            flag := false
            if tmpChar == "" {
                tmpChar = string(x[j])
                count++
                flag = true
            }
            if tmpChar != string(x[j]) {
                if tmpChar != "" && count > 0 {
                    tmpRet += fmt.Sprintf("%d%s", count, tmpChar)
                    count = 1
                    tmpChar = string(x[j])
                }
            } else if j <= len(x)-1 && !flag {
                count++
            }
            if j == len(x)-1 {
                tmpRet += fmt.Sprintf("%d%s", count, tmpChar)
            }
        }
        x = tmpRet
    }
    return x
}

T24:最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ““。

func longestCommonPrefix(strs []string) string {
    if len(strs) == 1 {
        return strs[0]
    }
    prefix := ""
    for i := 0; i < len(strs)-1; i++ {
        if prefix == "" {
            prefix = strs[i]
        }
        for j := len(prefix); j >= 0; j-- {
            prefix = strs[i][0:j]
            if strings.Index(strs[i+1], prefix) == 0 {
                break
            }
        }       
        if prefix == "" {
            break
        }
    }
    return prefix
}

T25:删除链表中的节点

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(node *ListNode) {
    if node.Next != nil {
       node.Val = node.Next.Val    
    }
    if node.Next.Next != nil {
        node.Next = node.Next.Next    
    }else{
        node.Next = nil
    }       
}

T26:删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    var h *ListNode = head
    var c *ListNode = nil
    
    var length = 1
    var t *ListNode = head
    for t.Next != nil {
        length ++
        t = t.Next
    }
       
    n = length - n + 1  
            
    if n == length {
        if n - 1 > 0 {
            //not first one
            for i:=1;i<=n-1;i++{
                if c == nil {
                    c = h                    
                }else{
                    c = c.Next
                }
            }
            c.Next = nil
        }else{
            //first one and length > 1
            h = nil          
        }
    }else{
        //first one
        if n == 1 {
            if h.Next != nil {
                h.Val = h.Next.Val
                h.Next = h.Next.Next
            }else{
                //only one
                h = nil
            }
        }else{
            for i:=1;i<=n;i++ {
                if c == nil {
                    c = h
                }else{
                    c = c.Next
                }
            }
            c.Val = c.Next.Val
            c.Next = c.Next.Next
        }
    }
    
    
    
    return h
}
赞赏我吗