LeetCode题解

1.两数之和

func twoSum(nums []int, target int) []int {
    return hashMap(nums,target)
}
/**
暴力求解：
    使用嵌套循环，每次循环判断两数之和是否等于 target。
 */
func directly(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return []int{}
}
/**
哈希表：
    1.每次循环拿到 num，判断哈希表里面是否存在 target - num，
    2.如果不存在，就把 num 和 i 对应的下标存入哈希表，
    3.如果存在，则表示找到两个数，此时返回两个数的下标。
 */
func hashMap(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        _, ok := m[target-num]
        if ok {
            return []int{i, m[target-num]}
        }
        m[num] = i
    }
    return []int{}
}

9.回文数

func isPalindrome(x int) bool {
    if x == 0 {
        return true
    }
    if x < 0 {
        return false
    }
    return byString(x)
}


/**
转为字符串
    1.使用strconv把整数转为字符串
    2.使用双指针分别从头尾开始移动比较字符
*/
func byString(x int) bool {
    str := strconv.Itoa(x)
    length := len(str)
    i := 0
    j := length - 1

    for i < j {
        if str[i] != str[j] {
            return false
        }
        i++
        j--
    }
    return true
}


/**
数学方法
    1.对每位数进行取模操作 321 -> 1, 32 -> 2 , 3 -> 3
    2.对余数重新计算，在题目没有限制数字范围的情况下需要考虑反转的数字是否溢出
 */
func byMath(x int) bool {
    temp := x
    sum := 0
    for x != 0 {
        pop := x % 10
        x /= 10
        sum = sum*10 + pop
    }
    return sum == temp
}

13.罗马数字转整数

/**
    1.使用map来存储罗马字符
    2.拿出当前字符与下一个字符一起处理
    3.对最后一个字符单独处理
 */
func romanToInt(s string) int {
    m := map[string]int{"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}

    runes := []rune(s)
    res := 0
    for i := 0; i < len(runes); i++ {
        if i == len(runes)-1 {
            res += m[string(runes[i])]
            break
        }

        str1 := string(runes[i])
        str2 := string(runes[i+1])
        var1 := m[str1]
        var2 := m[str2]

        if funcName(str1, str2) {
            res += var2 - var1
            i++
        } else {
            res += var1
        }

    }
    return res
}

func funcName(str1 string, str2 string) bool {
    switch str1 {
    case "I":
        return str1 == "I" && (str2 == "V" || str2 == "X")
    case "X":
        return str1 == "X" && (str2 == "L" || str2 == "C")
    case "C":
        return str1 == "C" && (str2 == "D" || str2 == "M")
    default:
        return false
    }

}

14.最长公共前缀

import "strings"

//leetcode submit region begin(Prohibit modification and deletion)
/**
    1.截取首个元素的和其他元素进行比较
    2.当flag和数组长度相等的时候，当前截取的字符串即为最长公共前缀
 */
func longestCommonPrefix(strs []string) string {
    first := strs[0]
    flag := 1
    var prefix string

    if len(strs) == 1 {
        prefix = first
        return prefix
    }

    for i := 1; i <= len(first); i++ {
        prefix = first[0:i]
        for j := 1; j < len(strs); j++ {
            if strings.HasPrefix(strs[j],prefix) {
                flag++
            }
        }
        if len(strs) != flag {
            if i == 1 {
                prefix = ""
            }else {
                prefix = first[0:i-1]
            }
            break
        }
        flag = 1
    }

    return prefix
}

20.有序的括号

/**
    1.使用map存储对应的括号
 */
func isValid(s string) bool {
    length := len(s)

    if length%2 == 1 {
        return false
    }

    pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}

    var stack []byte

    for i := 0; i < length; i++ {
        left, ok := pairs[s[i]]
        //判断。右括号先取对应的左括号；左括号入栈
        if ok {
            //检查栈是否为空 || 检查是否栈顶元素（左括号）匹配，
            if len(stack) == 0 || stack[len(stack)-1] != left {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }

    }

    return len(stack) == 0
}有序的括号

21.合并两个有序链表（待完成）

26.删除有序数组中的重复项

func removeDuplicates(nums []int) int {
    return doublePointer(nums)
}

//比较法
func comparedNext(nums []int) int {
    length := len(nums)
    for i := 0; i < length-1; i++ {
        if nums[i] == nums[i+1] {
            nums = append(nums[:i], nums[i+1:]...)
            length--
            i--
        }
    }
    return length
}

//双指针
func doublePointer(nums []int) int {
    length := len(nums)

    if length == 0 {
        return 0
    }

    slow := 0
    fast := 0

    for fast < length {
        if nums[slow] != nums[fast] {
            slow++
            nums[slow] = nums[fast]
        }
        fast++
    }
    return slow + 1
}

27.移除元素

/**
双指针
    1.快指针查询出要保留的数据
    2.慢指针正常遍历把快指针指向的数据保存
 */
func removeElement(nums []int, val int) int {
    lg := 0
    for v := range nums {
        if v != val {
            nums[lg] = v
            lg++
        }
    }

    return lg
}

28.实现 strStr() 函数

/**
    1.切片比较
 */
func strStr(haystack string, needle string) int {
    if haystack == needle {
        return 0
    }

    LenHaystack, LenNeedle := len(haystack), len(needle)

    //进行循环遍历
    for i := 0; i <= LenHaystack-LenNeedle; i++ {
        if haystack[i:i+LenNeedle] == needle {
            return i
        }
    }
    return -1
}

35.搜索插入位置

func searchInsert(nums []int, target int) int {
    return binarySearch(nums, target, 0, len(nums)-1)
}

func binarySearch(nums []int, target int,left int,right int) int {
    if left > right {
        return left
    }
    mid := left + ((right - left) / 2)
    if target > nums[mid] {
        return binarySearch(nums, target, mid+1, right)
    } else if target < nums[mid] {
        return binarySearch(nums, target, left, mid-1)
    } else {
        return mid
    }
}

58.最后一个单词的长度

import (
    "strings"
)

func lengthOfLastWord(s string) int {
    new := strings.TrimSpace(s)
    split := strings.Split(new, " ")
    return len(split[len(split)-1])
}

59.加一

func plusOne(digits []int) []int {
    length := len(digits)

    for i := length - 1; i >= 0; i-- {
        if digits[i] == 9 {
            digits[i] = 0
            continue
        }
        digits[i] += 1
        break
    }

    if digits[0] == 0 {
        newDigits := make([]int, length+1)
        newDigits[0] = 1
        return newDigits
    }

    return digits
}

94.二叉树的中序遍历

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
    var res []int
    var middleOrder func(node *TreeNode)
    middleOrder = func(node *TreeNode) {
        if node == nil {
            return
        }
        middleOrder(node.Left)
        res = append(res, node.Val)
        middleOrder(node.Right)
    }
    middleOrder(root)
    return res
}