给定一个整数数组 nums 和一个目标值 target，
请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]Copy

# 暴力法: 2层循环遍历
func twoSum(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{}
}

# 两遍哈希遍历
func twoSum(nums []int, target int) []int {
    m := make(map[int]int,len(nums))
    for k, v := range nums{
        m[v] = k
    }

    for i := 0; i < len(nums); i++{
        b := target - nums[i]
        if num, ok := m[b]; ok && num != i{
            return []int{i,m[b]}
        }
    }
    return []int{}
}

# 一遍哈希遍历
func twoSum(nums []int, target int) []int {
    m := make(map[int]int, len(nums))
    for i, b := range nums {
        if j, ok := m[target-b]; ok {
            return []int{j, i}
        }
        m[b] = i
    }
    return nil
}Copy

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:输入: 123 输出: 321
示例 2:输入: -123 输出: -321
示例 3:输入: 120 输出: 21
注意:假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31,  2^31 − 1]。
请根据这个假设，如果反转后整数溢出那么就返回 0。Copy

// 使用符号标记，转成正数，循环得到%10的余数，再加上符号
func reverse(x int) int {
    flag := 1
    if x < 0 {
        flag = -1
        x = -1 * x
    }

    result := 0
    for x > 0 {
        temp := x % 10
        x = x / 10

        result = result*10 + temp
    }

    result = flag * result
    if result > math.MaxInt32 || result < math.MinInt32 {
        result = 0
    }
    return result
}

// 对x进行逐个%10取个位，一旦溢出，直接跳出循环
func reverse(x int) int {
    result := 0
    for x != 0 {
        temp := x % 10
        result = result*10 + temp
        if result > math.MaxInt32 || result < math.MinInt32 {
            return 0
        }
        x = x / 10
    }
    return result
}Copy

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:    输入: 121    输出: true
示例 2:输入: -121    输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:输入: 10      输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶: 你能不将整数转为字符串来解决这个问题吗？Copy

// 数学解法，取出后半段数字进行翻转，然后判断是否相等
func isPalindrome(x int) bool {
    if x < 0 || (x%10 == 0 && x != 0) {
        return false
    }

    revertedNumber := 0
    for x > revertedNumber {
        temp := x % 10
        revertedNumber = revertedNumber*10 + temp
        x = x / 10
    }
    // for example:
    // x = 1221  => x = 12 revertedNumber = 12
    // x = 12321 => x = 12 revertedNumber = 123
    return x == revertedNumber || x == revertedNumber/10
}

// 转成字符串，依次判断
func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }

    s := strconv.Itoa(x)
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true
}

// 转成byte数组，依次判断，同2
func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }
    arrs := []byte(strconv.Itoa(x))
    Len := len(arrs)
    for i := 0; i < Len/2; i++ {
        if arrs[i] != arrs[Len-i-1] {
            return false
        }
    }
    return true
}Copy

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 
27 写做  XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。
但也存在特例，例如 4 不写做 IIII，而是 IV。
数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。
同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
    I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
    X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
    C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:输入: "III" 输出: 3
示例 2:    输入: "IV" 输出: 4
示例 3:    输入: "IX"    输出: 9
示例 4:    输入: "LVIII"    输出: 58 解释: L = 50, V= 5, III = 3.
示例 5: 输入: "MCMXCIV"    输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.Copy

// 带标记位
func romanToInt(s string) int {
    m := map[byte]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }
    result := 0
    last := 0

    for i := len(s) - 1; i >= 0; i-- {
        current := m[s[i]]
        flag := 1
        if current < last {
            flag = -1
        }
        result = result + flag*current
        last = current
    }
    return result
}

// 不带标记位，小于则减去2倍数
func romanToInt(s string) int {
    m := map[byte]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }
    result := 0
    last := 0

    for i := len(s) - 1; i >= 0; i-- {
        current := m[s[i]]
        if current < last {
            result = result - current
        }else {
            result = result + current
        }
        last = current
    }
    return result
}Copy

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:输入: ["flower","flow","flight"] 输出: "fl"
示例 2:输入: ["dog","racecar","car"] 输出: ""
解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z 。Copy

// 先找最短的一个字符串，依次比较最短字符串子串是否是其他字符串子串
func longestCommonPrefix(strs []string) string {
    if len(strs) == 0{
        return ""
    }
    if len(strs) == 1{
        return strs[0]
    }

    short := strs[0]
    for _, s := range strs{
        if len(short) > len(s){
            short = s
        }
    }

    for i := range short{
        shortest := short[:i+1]
        for _,str := range strs{
            if strings.Index(str,shortest) != 0{
                return short[:i]
            }
        }
    }
    return short
}

// 暴力法:直接依次遍历
func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    if len(strs) == 1 {
        return strs[0]
    }

    length := 0

    for i := 0; i < len(strs[0]); i++ {
        char := strs[0][i]
        for j := 1; j < len(strs); j++ {
            if i >= len(strs[j]) || char != strs[j][i] {
                return strs[0][:length]
            }
        }
        length++
    }
    return strs[0][:length]
}

// 排序后，遍历比较第一个，和最后一个字符串
func longestCommonPrefix(strs []string) string {
    if len(strs) == 0{
        return ""
    }
    if len(strs) == 1{
        return strs[0]
    }

    sort.Strings(strs)
    first := strs[0]
    last := strs[len(strs)-1]
    i := 0
    length := len(first)
    if len(last) < length{
        length = len(last)
    }
    for i < length{
        if first[i] != last[i]{
            return first[:i]
        }
        i++
    }

    return first[:i]
}

// trie树
var trie [][]int
var index int

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    if len(strs) == 1 {
        return strs[0]
    }

    trie = make([][]int, 2000)
    for k := range trie {
        value := make([]int, 26)
        trie[k] = value
    }
    insert(strs[0])

    minValue := math.MaxInt32
    for i := 1; i < len(strs); i++ {
        retValue := insert(strs[i])
        if minValue > retValue {
            minValue = retValue
        }
    }
    return strs[0][:minValue]
}

func insert(str string) int {
    p := 0
    count := 0
    for i := 0; i < len(str); i++ {
        ch := str[i] - 'a'
        // fmt.Println(string(str[i]),p,ch,trie[p][ch])
        if value := trie[p][ch]; value == 0 {
            index++
            trie[p][ch] = index
        } else {
            count++
        }
        p = trie[p][ch]
    }
    return count
}

// 水平扫描法:比较前2个字符串得到最长前缀，然后跟第3个比较得到一个新的最长前缀，继续比较，直到最后
func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    if len(strs) == 1 {
        return strs[0]
    }

    commonStr := common(strs[0], strs[1])
    if commonStr == "" {
        return ""
    }
    for i := 2; i < len(strs); i++ {
        if commonStr == "" {
            return ""
        }
        commonStr = common(commonStr, strs[i])
    }
    return commonStr
}

func common(str1, str2 string) string {
    length := 0
    for i := 0; i < len(str1); i++ {
        char := str1[i]
        if i >= len(str2) || char != str2[i] {
            return str1[:length]
        }
        length++
    }
    return str1[:length]
}

// 分治法
func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    if len(strs) == 1 {
        return strs[0]
    }

    return commonPrefix(strs, 0, len(strs)-1)
}

func commonPrefix(strs []string, left, right int) string {
    if left == right {
        return strs[left]
    }

    middle := (left + right) / 2
    leftStr := commonPrefix(strs, left, middle)
    rightStr := commonPrefix(strs, middle+1, right)
    return commonPrefixWord(leftStr, rightStr)
}

func commonPrefixWord(leftStr, rightStr string) string {
    if len(leftStr) > len(rightStr) {
        leftStr = leftStr[:len(rightStr)]
    }

    if len(leftStr) < 1 {
        return leftStr
    }

    for i := 0; i < len(leftStr); i++ {
        if leftStr[i] != rightStr[i] {
            return leftStr[:i]
        }
    }
    return leftStr
}Copy

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1: 输入: "()" 输出: true
示例 2: 输入: "()[]{}" 输出: true
示例 3: 输入: "(]" 输出: false
示例 4: 输入: "([)]" 输出: false
示例 5: 输入: "{[]}" 输出: trueCopy

// 使用栈结构实现
func isValid(s string) bool {
    st := new(stack)
    for _, char := range s {
        switch char {
        case '(', '[', '{':
            st.push(char)
        case ')', ']', '}':
            ret, ok := st.pop()
            if !ok || ret != match[char] {
                return false
            }
        }
    }

    if len(*st) > 0 {
        return false
    }
    return true
}

var match = map[rune]rune{
    ')': '(',
    ']': '[',
    '}': '{',
}

type stack []rune

func (s *stack) push(b rune) {
    *s = append(*s, b)
}
func (s *stack) pop() (rune, bool) {
    if len(*s) > 0 {
        res := (*s)[len(*s)-1]
        *s = (*s)[:len(*s)-1]
        return res, true
    }
    return 0, false
}

// 借助数组实现栈
func isValid(s string) bool {
    if s == "" {
        return true
    }

    stack := make([]rune, len(s))
    length := 0
    var match = map[rune]rune{
        ')': '(',
        ']': '[',
        '}': '{',
    }

    for _, char := range s {
        switch char {
        case '(', '[', '{':
            stack[length] = char
            length++
        case ')', ']', '}':
            if length == 0 {
                return false
            }
            if stack[length-1] != match[char]{
                return false
            } else {
                length--
            }
        }
    }
    return length == 0
}

// 借助数组实现栈，使用数字表示来匹配
func isValid(s string) bool {
    if s == "" {
        return true
    }

    stack := make([]int, len(s))
    length := 0
    var match = map[rune]int{
        ')': 1,
        '(': -1,
        ']': 2,
        '[': -2,
        '}': 3,
        '{': -3,
    }

    for _, char := range s {
        switch char {
        case '(', '[', '{':
            stack[length] = match[char]
            length++
        case ')', ']', '}':
            if length == 0 {
                return false
            }
            if stack[length-1]+match[char] != 0 {
                return false
            } else {
                length--
            }
        }
    }
    return length == 0
}Copy

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4Copy

// 迭代遍历
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    var head, node *ListNode
    if l1.Val < l2.Val {
        head = l1
        node = l1
        l1 = l1.Next
    } else {
        head = l2
        node = l2
        l2 = l2.Next
    }

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            node.Next = l1
            l1 = l1.Next
        } else {
            node.Next = l2
            l2 = l2.Next
        }
        node = node.Next
    }
    if l1 != nil {
        node.Next = l1
    }
    if l2 != nil {
        node.Next = l2
    }
    return head
}

// 递归遍历
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    if l1.Val < l2.Val{
        l1.Next = mergeTwoLists(l1.Next,l2)
        return l1
    }else {
        l2.Next = mergeTwoLists(l1,l2.Next)
        return l2
    }
}

#
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    res := &ListNode{}
    temp := res
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            temp.Next = l1
            l1 = l1.Next
        } else {
            temp.Next = l2
            l2 = l2.Next
        }
        temp = temp.Next
    }
    if l1 != nil {
        temp.Next = l1
    } else {
        temp.Next = l2
    }
    return res.Next
}Copy

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1: 给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
说明: 为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}Copy

// 双指针法
func removeDuplicates(nums []int) int {
    i , j , length := 0, 1, len(nums)
    for ; j < length; j++{
        if nums[i] == nums[j]{
            continue
        }
        i++
        nums[i] = nums[j]
    }
    return i+1
}

// 计数法
func removeDuplicates(nums []int) int {
    count := 1
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] != nums[i+1] {
            nums[count] = nums[i+1]
            count++
        }
    }
    return count
}Copy

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
说明: 为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}Copy

// 双指针，数字前移
func removeElement(nums []int, val int) int {
    i := 0
    for j := 0; j < len(nums); j++{
        if nums[j] != val{
            nums[i] = nums[j]
            i++
        }
    }
    return i
}

// 双指针，出现重复最后数字前移
func removeElement(nums []int, val int) int {
    i := 0
    n := len(nums)
    for i < n{
        if nums[i] == val{
            nums[i] = nums[n-1]
            n--
        }else {
            i++
        }
    }
    return n
}

// 首位指针法
func removeElement(nums []int, val int) int {
    i, j := 0, len(nums)-1
    for {
        // 从左向右找到等于 val 的位置
        for i < len(nums) && nums[i] != val {
            i++
        }
        // 从右向左找到不等于 val 的位置
        for j >= 0 && nums[j] == val {
            j--
        }
        if i >= j {
            break
        }
        // fmt.Println(i,j)
        nums[i], nums[j] = nums[j], nums[i]
    }
    return i
}Copy

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，
在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。
如果不存在，则返回-1。
示例 1:输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。
这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。Copy

// Sunday算法
func strStr(haystack string, needle string) int {
    if needle == ""{
        return 0
    }
    if len(needle) > len(haystack){
        return -1
    }
    // 计算模式串needle的偏移量
    m := make(map[int32]int)
    for k,v := range needle{
        m[v] = len(needle)-k
    }

    index := 0
    for index+len(needle) <= len(haystack){
        // 匹配字符串
        str := haystack[index:index+len(needle)]
        if str == needle{
            return index
        }else {
            if index + len(needle) >= len(haystack){
                return -1
            }
            // 后一位字符串
            next := haystack[index+len(needle)]
            if nextStep,ok := m[int32(next)];ok{
                index = index+nextStep
            }else {
                index = index+len(needle)+1
            }
        }
    }
    if index + len(needle) >= len(haystack){
        return -1
    }else {
        return index
    }
}

// 
func strStr(haystack string, needle string) int {
    hlen, nlen := len(haystack), len(needle)
    for i := 0; i <= hlen-nlen; i++ {
        if haystack[i:i+nlen] == needle {
            return i
        }
    }
    return -1
}

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

//
func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }

    next := getNext(needle)

    i := 0
    j := 0
    for i < len(haystack) && j < len(needle) {
        if j == -1 || haystack[i] == needle[j] {
            i++
            j++
        } else {
            j = next[j]
        }
    }

    if j == len(needle) {
        return i - j
    }
    return -1
}

// 求next数组
func getNext(str string) []int {
    var next = make([]int, len(str))
    next[0] = -1

    i := 0
    j := -1

    for i < len(str)-1 {
        if j == -1 || str[i] == str[j] {
            i++
            j++
            next[i] = j
        } else {
            j = next[j]
        }
    }
    return next
}Copy

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1: 输入: [1,3,5,6], 5 输出: 2
示例 2: 输入: [1,3,5,6], 2 输出: 1
示例 3: 输入: [1,3,5,6], 7 输出: 4
示例 4: 输入: [1,3,5,6], 0 输出: 0Copy

// 二分查找
func searchInsert(nums []int, target int) int {
    low, high := 0, len(nums)-1
    for low <= high {
        mid := (low + high) / 2
        switch {
        case nums[mid] < target:
            low = mid + 1
        case nums[mid] > target:
            high = mid - 1
        default:
            return mid
        }
    }
    return low
}

// 顺序查找
func searchInsert(nums []int, target int) int {
    i := 0
    for i < len(nums) && nums[i] < target {
        if nums[i] == target {
            return i
        }
        i++
    }
    return i
}

// 顺序查找
func searchInsert(nums []int, target int) int {
    for i := 0; i < len(nums); i++ {
        if nums[i] >= target {
            return i
        }
    }
    return len(nums)
}Copy

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
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 项。
注意：整数顺序将表示为一个字符串。
示例 1:输入: 1 输出: "1"
示例 2: 输入: 4 输出: "1211"Copy

// 递推+双指针计数
func countAndSay(n int) string {
    strs := []byte{'1'}
    for i := 1; i < n; i++ {
        strs = say(strs)
    }
    return string(strs)
}

func say(strs []byte) []byte {
    result := make([]byte, 0, len(strs)*2)

    i, j := 0, 1
    for i < len(strs) {
        for j < len(strs) && strs[i] == strs[j] {
            j++
        }
        // 几个几
        result = append(result, byte(j-i+'0'))
        result = append(result, strs[i])
        i = j
    }
    return result
}

// 递归+双指针计数
func countAndSay(n int) string {
    if n == 1 {
        return "1"
    }
    strs := countAndSay(n - 1)

    result := make([]byte, 0, len(strs)*2)

    i, j := 0, 1
    for i < len(strs) {
        for j < len(strs) && strs[i] == strs[j] {
            j++
        }
        // 几个几
        result = append(result, byte(j-i+'0'))
        result = append(result, strs[i])
        i = j
    }
    return string(result)
}Copy

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。Copy

// 贪心法
func maxSubArray(nums []int) int {
    result := nums[0]
    sum := 0
    for i := 0; i < len(nums); i++ {
        if sum > 0 {
            sum += nums[i]
        } else {
            sum = nums[i]
        }
        if sum > result {
            result = sum
        }
    }
    return result
}

// 暴力法
func maxSubArray(nums []int) int {
    result := math.MinInt32

    for i := 0; i < len(nums); i++ {
        sum := 0
        for j := i; j < len(nums); j++ {
            sum += nums[j]
            if sum > result {
                result = sum
            }
        }
    }
    return result
}

// 
func maxSubArray(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    result := nums[0]

    for i := 1; i < len(nums); i++ {
        if dp[i-1]+nums[i] > nums[i] {
            dp[i] = dp[i-1] + nums[i]
        } else {
            dp[i] = nums[i]
        }

        if dp[i] > result {
            result = dp[i]
        }
    }
    return result
}

// 动态规划
func maxSubArray(nums []int) int {
    dp := nums[0]
    result := dp

    for i := 1; i < len(nums); i++ {
        if dp+nums[i] > nums[i] {
            dp = dp + nums[i]
        } else {
            dp = nums[i]
        }

        if dp > result {
            result = dp
        }
    }
    return result
}

// 分治法
func maxSubArray(nums []int) int {
    result := maxSubArr(nums, 0, len(nums)-1)
    return result
}

func maxSubArr(nums []int, left, right int) int {
    if left == right {
        return nums[left]
    }

    mid := (left + right) / 2
    leftSum := maxSubArr(nums, left, mid)        // 最大子序在左边
    rightSum := maxSubArr(nums, mid+1, right)    // 最大子序在右边
    midSum := findMaxArr(nums, left, mid, right) // 跨中心
    result := max(leftSum, rightSum)
    result = max(result, midSum)
    return result
}

func findMaxArr(nums []int, left, mid, right int) int {
    leftSum := math.MinInt32
    sum := 0
    // 从右到左
    for i := mid; i >= left; i-- {
        sum += nums[i]
        leftSum = max(leftSum, sum)
    }

    rightSum := math.MinInt32
    sum = 0
    // 从左到右
    for i := mid + 1; i <= right; i++ {
        sum += nums[i]
        rightSum = max(rightSum, sum)
    }
    return leftSum + rightSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}Copy

给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。
示例: 输入: "Hello World" 输出: 5Copy

// 调用系统函数，切割为数组取最后一个值
func lengthOfLastWord(s string) int {
    arr := strings.Split(strings.Trim(s, " "), " ")
    return len(arr[len(arr)-1])
}

// 遍历统计
func lengthOfLastWord(s string) int {
    length := len(s)
    if length == 0 {
        return 0
    }

    result := 0
    for i := length - 1; i >= 0; i-- {
        if s[i] == ' ' {
            if result > 0 {
                return result
            }
            continue
        }
        result++
    }
    return result
}Copy

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1: 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。
示例 2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。Copy

// 模拟进位
func plusOne(digits []int) []int {
    length := len(digits)
    if length == 0 {
        return []int{1}
    }

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

    if digits[0] > 9 {
        digits[0] = digits[0] - 10
        digits = append([]int{1}, digits...)
    }

    return digits
}

// 模拟进位
func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] < 9 {
            digits[i]++
            return digits
        } else {
            digits[i] = 0
        }
    }
    return append([]int{1}, digits...)
}Copy

给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1: 输入: a = "11", b = "1" 输出: "100"
示例 2:输入: a = "1010", b = "1011" 输出: "10101"Copy

// 转换成数组模拟
func addBinary(a string, b string) string {
    if len(a) < len(b) {
        a, b = b, a
    }
    length := len(a)

    A := transToInt(a, length)
    B := transToInt(b, length)

    return makeString(add(A, B))
}

func transToInt(s string, length int) []int {
    result := make([]int, length)
    ls := len(s)
    for i, b := range s {
        result[length-ls+i] = int(b - '0')
    }
    return result
}

func add(a, b []int) []int {
    length := len(a) + 1
    result := make([]int, length)
    for i := length - 1; i >= 1; i-- {
        temp := result[i] + a[i-1] + b[i-1]
        result[i] = temp % 2
        result[i-1] = temp / 2
    }
    i := 0
    for i < length-1 && result[i] == 0 {
        i++
    }
    return result[i:]
}

func makeString(nums []int) string {
    bytes := make([]byte, len(nums))
    for i := range bytes {
        bytes[i] = byte(nums[i]) + '0'
    }
    return string(bytes)
}

// 直接模拟
func addBinary(a string, b string) string {
    i := len(a) - 1
    j := len(b) - 1
    result := ""
    flag := 0
    current := 0

    for i >= 0 || j >= 0 {
        intA, intB := 0, 0
        if i >= 0 {
            intA = int(a[i] - '0')
        }
        if j >= 0 {
            intB = int(b[j] - '0')
        }
        current = intA + intB + flag
        flag = 0
        if current >= 2 {
            flag = 1
            current = current - 2
        }
        cur := strconv.Itoa(current)
        result = cur + result
        i--
        j--
    }
    if flag == 1 {
        result = "1" + result
    }
    return result
}Copy

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:输入: 4 输出: 2
示例 2:输入: 8 输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。Copy

// 系统函数
func mySqrt(x int) int {
    result := int(math.Sqrt(float64(x)))
    return result
}

// 系统函数
func mySqrt(x int) int {
    result := math.Floor(math.Sqrt(float64(x)))
    return int(result)
}

// 牛顿迭代法
func mySqrt(x int) int {
    result := x
    for result*result > x {
        result = (result + x/result) / 2
    }
    return result
}

// 二分查找法
func mySqrt(x int) int {
    left := 1
    right := x
    for left <= right {
        mid := (left + right) / 2
        if mid == x/mid {
            return mid
        } else if mid < x/mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    if left * left <= x{
        return left
    }else {
        return left-1
    }
}

// 暴力法:遍历
func mySqrt(x int) int {
    result := 0
    for i := 1; i <= x/i; i++ {
        if i*i == x {
            return i
        }
        result = i
    }
    return result
}Copy

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 
1.  1 阶 + 1 阶
2.  2 阶
示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶Copy

// 递归
var arr []int

func climbStairs(n int) int {
    arr = make([]int, n+1)
    return climbStart(0, n)
}

func climbStart(i, n int) int {
    if i > n {
        return 0
    }
    if i == n {
        return 1
    }
    if arr[i] > 0 {
        return arr[i]
    }
    arr[i] = climbStart(i+1, n) + climbStart(i+2, n)
    return arr[i]
}

// 动态规划
func climbStairs(n int) int {
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

// 斐波那契
func climbStairs(n int) int {
    if n == 1 {
        return 1
    }
    first := 1
    second := 2
    for i := 3; i <= n; i++ {
        third := first + second
        first = second
        second = third
    }
    return second
}Copy

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:输入: 1->1->2 输出: 1->2
示例 2:输入: 1->1->2->3->3 输出: 1->2->3Copy

// 直接法
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    temp := head
    for temp.Next != nil {
        if temp.Val == temp.Next.Val {
            temp.Next = temp.Next.Next
        } else {
            temp = temp.Next
        }
    }
    return head
}

// 递归法
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil{
        return head
    }
    head.Next = deleteDuplicates(head.Next)
    if head.Val == head.Next.Val{
        head = head.Next
    }
    return head
}

// 双指针法
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil{
        return head
    }
    p := head
    q := head.Next
    for p.Next != nil{
        if p.Val == q.Val{
            if q.Next == nil{
                p.Next = nil
            }else {
                p.Next = q.Next
                q = q.Next
            }
        }else {
            p = p.Next
            q = q.Next
        }
    }
    return head
}Copy

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
    初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
    你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]Copy

// 合并后排序
func merge(nums1 []int, m int, nums2 []int, n int) {
    nums1 = nums1[:m]
    nums1 = append(nums1, nums2[:n]...)
    sort.Ints(nums1)
}

// 双指针法
func merge(nums1 []int, m int, nums2 []int, n int) {
    for m > 0 && n > 0 {
        if nums1[m-1] < nums2[n-1] {
            nums1[m+n-1] = nums2[n-1]
            n--
        } else {
            nums1[m+n-1] = nums1[m-1]
            m--
        }
    }
    if m == 0 && n > 0 {
        for n > 0 {
            nums1[n-1] = nums2[n-1]
            n--
        }
    }
}

// 拷贝后插入
func merge(nums1 []int, m int, nums2 []int, n int) {
    temp := make([]int, m)
    copy(temp, nums1)

    if n == 0 {
        return
    }
    first, second := 0, 0
    for i := 0; i < len(nums1); i++ {
        if second >= n {
            nums1[i] = temp[first]
            first++
            continue
        }
        if first >= m {
            nums1[i] = nums2[second]
            second++
            continue
        }
        if temp[first] < nums2[second] {
            nums1[i] = temp[first]
            first++
        } else {
            nums1[i] = nums2[second]
            second++
        }
    }
}Copy

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入:       1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
输出: true
示例 2:
输入:      1          1
          /           \
         2             2
        [1,2],     [1,null,2]
输出: false
示例 3:
输入:       1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
输出: falseCopy

// 递归(深度优先)
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }

    if p == nil || q == nil {
        return false
    }

    return p.Val == q.Val && isSameTree(p.Left, q.Left) &&
        isSameTree(p.Right, q.Right)
}

// 层序遍历(宽度优先)
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }

    var queueP, queueQ []*TreeNode
    if p != nil {
        queueP = append(queueP, p)
        queueQ = append(queueQ, q)
    }

    for len(queueP) > 0 && len(queueQ) > 0 {
        tempP := queueP[0]
        queueP = queueP[1:]

        tempQ := queueQ[0]
        queueQ = queueQ[1:]

        if tempP.Val != tempQ.Val {
            return false
        }

        if (tempP.Left != nil && tempQ.Left == nil) ||
            (tempP.Left == nil && tempQ.Left != nil) {
            return false
        }
        if tempP.Left != nil {
            queueP = append(queueP, tempP.Left)
            queueQ = append(queueQ, tempQ.Left)
        }

        if (tempP.Right != nil && tempQ.Right == nil) ||
            (tempP.Right == nil && tempQ.Right != nil) {
            return false
        }
        if tempP.Right != nil {
            queueP = append(queueP, tempP.Right)
            queueQ = append(queueQ, tempQ.Right)
        }
    }
    return true
}Copy

给出两个 非空 的链表用来表示两个非负的整数。
其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8
原因：342 + 465 = 807Copy

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    res := &ListNode{}
    cur := res
    carry := 0
    for l1 != nil || l2 != nil || carry > 0 {
        sum := carry
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }
        carry = sum / 10 // 进位
        cur.Next = &ListNode{Val: sum % 10}
        cur = cur.Next
    }
    return res.Next
}

#
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil && l2 == nil {
        return nil
    }
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    sum := l1.Val + l2.Val
    res := &ListNode{Val: sum % 10}
    if sum >= 10 {
        l1.Next = addTwoNumbers(l1.Next, &ListNode{Val: 1})
    }
    res.Next = addTwoNumbers(l1.Next, l2.Next)
    return res
}Copy

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:输入: "abcabcbb"输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:输入: "bbbbb" 输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:输入: "pwwkew" 输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
同剑指offer面试题48.最长不含重复字符的子字符串Copy

func lengthOfLongestSubstring(s string) int {
    arr := [256]int{}
    for i := range arr {
        arr[i] = -1
    }
    max, j := 0, 0
    for i := 0; i < len(s); i++ {
        if arr[s[i]] >= j {
            j = arr[s[i]] + 1
        } else if i+1-j > max {
            max = i + 1 - j
        }
        arr[s[i]] = i
    }
    return max
}

# 2
func lengthOfLongestSubstring(s string) int {
    max, j := 0, 0
    for i := 0; i < len(s); i++ {
        index := strings.Index(s[j:i], string(s[i]))
        if index == -1 {
            continue
        }
        if i-j > max {
            max = i - j
        }
        j = j + index + 1
    }
    if len(s)-j > max {
        max = len(s) - j
    }
    return max
}

# 3
func lengthOfLongestSubstring(s string) int {
    m := make(map[uint8]int)
    max, j := 0, 0
    for i := 0; i < len(s); i++ {
        if v, ok := m[s[i]]; ok && v >= j {
            j = v + 1
        } else if i+1-j > max {
            max = i + 1 - j
        }
        m[s[i]] = i
    }
    return max
}

# 4
func lengthOfLongestSubstring(s string) int {
    if len(s) < 1 {
        return 0
    }
    dp := make([]int, len(s))
    dp[0] = 1
    res := 1
    m := make(map[byte]int)
    m[s[0]] = 0
    for i := 1; i < len(s); i++ {
        index := -1
        if value, ok := m[s[i]]; ok {
            index = value
        }
        if i-index > dp[i-1] {
            dp[i] = dp[i-1] + 1
        } else {
            dp[i] = i - index
        }
        m[s[i]] = i
        if dp[i] > res {
            res = dp[i]
        }
    }
    return res
}

# 5
func lengthOfLongestSubstring(s string) int {
    arr := [256]int{}
    for i := range arr {
        arr[i] = -1
    }
    res, j := 0, -1
    for i := 0; i < len(s); i++ {
        if arr[s[i]] > j { // 出现重复了，更新下标
            j = arr[s[i]]
        } else {
            res = max(res, i-j) // 没有重复，更新长度
        }
        arr[s[i]] = i
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}Copy

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：输入: "babad"输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2：输入: "cbbd" 输出: "bb"Copy

// dp(l,r)=dp(l+1,r−1)&&(s[l]==s[r])
// dp[l,r]：字符串s从索引l到r的子串是否是回文串
func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }
    dp := make([][]bool, len(s))
    start := 0
    max := 1
    for r := 0; r < len(s); r++ {
        dp[r] = make([]bool, len(s))
        dp[r][r] = true
        for l := 0; l < r; l++ {
            if s[l] == s[r] && (r-l <= 2 || dp[l+1][r-1] == true) {
                dp[l][r] = true
            } else {
                dp[l][r] = false
            }
            if dp[l][r] == true {
                if r-l+1 > max {
                    max = r - l + 1
                    start = l
                }
            }
        }
    }
    return s[start : start+max]
}

# 2
func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }
    start := 0
    end := 0
    for i := 0; i < len(s); i++ {
        left1, right1 := find(s, i, i)
        left2, right2 := find(s, i, i+1)
        if right1-left1 > end-start {
            start, end = left1, right1
        }
        if right2-left2 > end-start {
            start, end = left2, right2
        }
    }
    return s[start : end+1]
}

func find(s string, left, right int) (int, int) {
    for ; 0 <= left && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {
    }
    return left + 1, right - 1
}

# 3
func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }
    res := ""
    for i := 0; i < len(s); i++ {
        for j := i; j < len(s); j++ {
            str := s[i : j+1]
            if len(str) < len(res) && res != "" {
                continue
            }
            if judge(str) == true && len(res) < len(str) {
                res = str
            }
        }
    }
    return res
}

func judge(s string) bool {
    for i := 0; i < len(s)/2; i++ {
        if s[i] != s[len(s)-1-i] {
            return false
        }
    }
    return true
}

# 4
func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }
    str := add(s)
    length := len(str)
    max := 1
    begin := 0
    for i := 0; i < length; i++ {
        curLength := search(str, i)
        if curLength > max {
            max = curLength
            begin = (i - max) / 2
        }
    }
    return s[begin : begin+max]
}

func search(s string, center int) int {
    i := center - 1
    j := center + 1
    step := 0
    for ; i >= 0 && j < len(s) && s[i] == s[j]; i, j = i-1, j+1 {
        step++
    }
    return step
}

func add(s string) string {
    var res []rune
    for _, v := range s {
        res = append(res, '#')
        res = append(res, v)
    }
    res = append(res, '#')
    return string(res)
}

#
func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }
    str := add(s)
    length := len(str)
    temp := make([]int, length)
    maxRight := 0
    center := 0
    max := 1
    begin := 0
    for i := 0; i < length; i++ {
        if i < maxRight {
            mirror := 2*center - i
            temp[i] = min(maxRight-i, temp[mirror])
        }
        left := i - (1 + temp[i])
        right := i + (1 + temp[i])
        for left >= 0 && right < len(str) && str[left] == str[right] {
            temp[i]++
            left--
            right++
        }
        if i+temp[i] > maxRight {
            maxRight = i + temp[i]
            center = i
        }
        if temp[i] > max {
            max = temp[i]
            begin = (i - max) / 2
        }
    }
    return s[begin : begin+max]
}

func add(s string) string {
    var res []rune
    for _, v := range s {
        res = append(res, '#')
        res = append(res, v)
    }
    res = append(res, '#')
    return string(res)
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}Copy

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L   C   I   R
E T O E S I I G
E   D   H   N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN"
示例 2:输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG"
解释:
L     D     R
E   O E   I I
E C   I H   N
T     S     GCopy

func convert(s string, numRows int) string {
    if numRows == 1 {
        return s
    }
    arr := []rune(s)
    total := numRows*2 - 2
    res := make([]string, numRows)
    for i := 0; i < len(arr); i++ {
        index := i % total
        if index < numRows {
            res[index] = res[index] + string(arr[i])
        } else {
            res[total-index] = res[total-index] + string(arr[i])
        }
    }
    return strings.Join(res, "")
}

#
func convert(s string, numRows int) string {
    if numRows == 1 {
        return s
    }
    arr := []rune(s)
    res := make([]string, numRows)
    flag := -1
    index := 0
    for i := 0; i < len(arr); i++ {
        res[index] = res[index] + string(arr[i])
        if index == 0 || index == numRows-1 {
            flag = -flag
        }
        index = index + flag
    }
    return strings.Join(res, "")
}Copy

请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
   如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
   假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
   该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，
则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
    本题中的空白字符只包括空格字符 ' ' 。
    假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。
    如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:输入: "42" 输出: 42
示例 2:输入: "   -42" 输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:输入: "4193 with words" 输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:输入: "words and 987" 输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。
示例 5:输入: "-91283472332" 输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。Copy

func myAtoi(str string) int {
    i := 0
    for i < len(str) && str[i] == ' ' {
        i++
    }
    str = str[i:]
    arr := make([]byte, 0)
    isFlag := byte(' ')
    for j := 0; j < len(str); j++ {
        if str[j] >= '0' && str[j] <= '9' {
            arr = append(arr, str[j])
        } else {
            if len(arr) > 0 {
                break
            }
            if str[j] != ' ' && str[j] != '+' && str[j] != '-' {
                return 0
            }
            if isFlag != ' ' {
                return 0
            }
            isFlag = str[j]
        }
    }
    res := 0
    for i := 0; i < len(arr); i++ {
        value := int(arr[i] - '0')
        res = res*10 + value
        if isFlag == '-' {
            if -1*res < math.MinInt32 {
                return math.MinInt32
            }
        } else if isFlag == ' ' || isFlag == '+' {
            if res > math.MaxInt32 {
                return math.MaxInt32
            }
        }
    }
    if isFlag == '-' {
        return -1 * res
    }
    return res
}

#
func myAtoi(str string) int {
    re := regexp.MustCompile(`^[+-]?\d+`)
    arrS := re.FindAllString(strings.Trim(str, " "), -1)
    if len(arrS) == 0{
        return 0
    }
    arr := arrS[0]
    res := 0
    isFlag := byte(' ')
    if !(arr[0] >= '0' && arr[0] <= '9') {
        isFlag = arr[0]
        arr = arr[1:]
    }
    for i := 0; i < len(arr); i++ {
        value := int(arr[i] - '0')
        if isFlag == '-' {
            if res > 214748364 || (res==214748364 && value >= 8) {
                return math.MinInt32
            }
        } else if isFlag == ' ' || isFlag == '+' {
            if res > 214748364 || (res==214748364 && value >= 7) {
                return math.MaxInt32
            }
        }
        res = res*10 + value
    }
    if isFlag == '-' {
        return -1 * res
    }
    return res
}

#
func myAtoi(str string) int {
    str = strings.TrimSpace(str)
    result := 0
    flag := 1
    for i, v := range str {
        if v >= '0' && v <= '9' {
            result = result*10 + int(v-'0')
        } else if v == '-' && i == 0 {
            flag = -1
        } else if v == '+' && i == 0 {
            flag = 1
        } else {
            break
        }
        if result > math.MaxInt32 {
            if flag == -1 {
                return math.MinInt32
            }
            return math.MaxInt32
        }
    }
    return flag * result
}Copy

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：输入：[1,8,6,2,5,4,8,3,7] 输出：49Copy

func maxArea(height []int) int {
    i := 0
    j := len(height) - 1
    res := 0
    for i < j {
        area := (j - i) * min(height[i], height[j])
        if area > res {
            res = area
        }
        // 移动较小的指针，尝试获取更大的面积
        if height[i] > height[j] {
            j--
        } else {
            i++
        }
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

#
func maxArea(height []int) int {
    res := 0
    for i := 0; i < len(height); i++ {
        for j := i + 1; j < len(height); j++ {
            area := (j - i) * min(height[i], height[j])
            if area > res {
                res = area
            }
        }
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}Copy

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 
27 写做  XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。
数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。
同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
    I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
    X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
    C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例 1:输入: 3输出: "III"
示例 2:输入: 4 输出: "IV"
示例 3:输入: 9 输出: "IX"
示例 4:输入: 58 输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:输入: 1994 输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.Copy

func intToRoman(num int) string {
    m := map[int]string{
        1:    "I",
        4:    "IV",
        5:    "V",
        9:    "IX",
        10:   "X",
        40:   "XL",
        50:   "L",
        90:   "XC",
        100:  "C",
        400:  "CD",
        500:  "D",
        900:  "CM",
        1000: "M",
    }
    arr := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    result := ""
    for i := 0; i < len(arr); i++ {
        if num == 0 {
            break
        }
        value := num / arr[i]
        for j := 0; j < value; j++ {
            result = result + m[arr[i]]
        }
        num = num - value*arr[i]
    }
    return result
}

#
func intToRoman(num int) string {
    res := ""
    arr1 := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
    arr2 := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
    arr3 := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
    arr4 := []string{"", "M", "MM", "MMM"}
    res = arr4[num/1000] + arr3[num%1000/100] + arr2[num%100/10] + arr1[num%10]
    return res
}Copy

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]Copy

func threeSum(nums []int) [][]int {
    res := make([][]int, 0)
    sort.Ints(nums)
    for i := 0; i < len(nums)-1; i++ {
        target := 0 - nums[i]
        left := i + 1
        right := len(nums) - 1
        if nums[i] > 0 || nums[i]+nums[left] > 0 {
            break
        }
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for left < right {
            if left > i+1 && nums[left] == nums[left-1] {
                left++
                continue
            }
            if right < len(nums)-2 && nums[right] == nums[right+1] {
                right--
                continue
            }
            if nums[left]+nums[right] > target {
                right--
            } else if nums[left]+nums[right] < target {
                left++
            } else {
                res = append(res, []int{nums[i], nums[left], nums[right]})
                left++
                right--
            }
        }
    }
    return res
}

#
func threeSum(nums []int) [][]int {
    res := make([][]int, 0)
    m := make(map[[2]int]int)
    p := make(map[int]int)
    sort.Ints(nums)
    for k, v := range nums {
        p[v] = k
    }
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if j != i+1 && nums[j] == nums[j-1] {
                continue
            }
            sum := nums[i] + nums[j]
            if sum > 0 {
                break
            }
            if value, ok := p[-sum]; ok && value > j {
                if _, ok2 := m[[2]int{nums[i], nums[j]}]; !ok2 {
                    res = append(res, []int{nums[i], nums[j], 0 - nums[i] - nums[j]})
                    m[[2]int{nums[i], nums[j]}] = 1
                }
            }
        }
    }
    return res
}Copy

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：输入：nums = [-1,2,1,-4], target = 1 输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
    3 <= nums.length <= 10^3
    -10^3 <= nums[i] <= 10^3
    -10^4 <= target <= 10^4Copy

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    res := nums[0] + nums[1] + nums[2]
    for i := 0; i < len(nums); i++ {
        left := i + 1
        right := len(nums) - 1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum > target {
                right--
            } else if sum < target {
                left++
            } else {
                return target
            }
            if abs(sum, target) < abs(res, target) {
                res = sum
            }
        }
    }
    return res
}

func abs(a, b int) int {
    if a > b {
        return a - b
    }
    return b - a
}

#
func threeSumClosest(nums []int, target int) int {
    res := nums[0] + nums[1] + nums[2]
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            for k := j + 1; k < len(nums); k++ {
                sum := nums[i] + nums[j] + nums[k]
                if abs(sum, target) < abs(res, target) {
                    res = sum
                }
            }
        }
    }
    return res
}

func abs(a, b int) int {
    if a > b {
        return a - b
    }
    return b - a
}Copy

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:输入："23"输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。Copy

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return nil
    }
    arr := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
    res := []string{""}
    for i := 0; i < len(digits); i++ {
        length := len(res)
        for j := 0; j < length; j++ {
            for k := 0; k < len(arr[digits[i]-'0']); k++ {
                res = append(res, res[j]+string(arr[digits[i]-'0'][k]))
            }
        }
        res = res[length:]
    }
    return res
}

#
var res []string
var arr = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return nil
    }
    res = make([]string, 0)
    dfs(digits, 0, "")
    return res
}

func dfs(digits string, index int, str string) {
    if index == len(digits) {
        res = append(res, str)
        return
    }
    for i := 0; i < len(arr[digits[index]-'0']); i++ {
        dfs(digits, index+1, str+string(arr[digits[index]-'0'][i]))
    }
}Copy

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，
使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]Copy

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    res := make([][]int, 0)
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i + 1; j < len(nums); j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            temp := target - nums[i] - nums[j]
            left := j + 1
            right := len(nums) - 1
            for left < right {
                if left > j+1 && nums[left] == nums[left-1] {
                    left++
                    continue
                }
                if right < len(nums)-2 && nums[right] == nums[right+1] {
                    right--
                    continue
                }
                if nums[left]+nums[right] > temp {
                    right--
                } else if nums[left]+nums[right] < temp {
                    left++
                } else {
                    res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
                    left++
                    right--
                }
            }
        }
    }
    return res
}

#
func fourSum(nums []int, target int) [][]int {
    m := make(map[[3]int]int)
    p := make(map[int]int)
    sort.Ints(nums)
    for k, v := range nums {
        p[v] = k
    }
    res := make([][]int, 0)
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            for k := j + 1; k < len(nums); k++ {
                sum := nums[i] + nums[j] + nums[k]
                if value, ok := p[target-sum]; ok && value > k {
                    if _, ok2 := m[[3]int{nums[i], nums[j], nums[k]}]; !ok2 {
                        res = append(res, []int{nums[i], nums[j], nums[k], target - nums[i] - nums[j] - nums[k]})
                        m[[3]int{nums[i], nums[j], nums[k]}] = 1
                    }
                }
            }
        }
    }
    return res
}

#
var res [][]int

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    res = make([][]int, 0)
    dfs(nums, target, []int{}, 0)
    return res
}

func dfs(nums []int, target int, arr []int, level int) {
    if len(arr) == 4 {
        sum := 0
        for i := 0; i < len(arr); i++ {
            sum = sum + arr[i]
        }
        if sum == target {
            tempArr := make([]int, len(arr))
            copy(tempArr, arr)
            res = append(res, tempArr)
        }
        return
    }
    prev := math.MaxInt32
    for i := level; i < len(nums); i++ {
        if nums[i] != prev {
            prev = nums[i]
            arr = append(arr, nums[i])
            dfs(nums, target, arr, i+1)
            arr = arr[:len(arr)-1]
        }
    }
}Copy

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？Copy

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    temp := &ListNode{Next: head}
    cur := temp
    total := 0
    for cur.Next != nil {
        cur = cur.Next
        total++
    }
    cur = temp
    count := 0
    for cur.Next != nil {
        if total-n == count {
            cur.Next = cur.Next.Next
            break
        }
        cur = cur.Next
        count++
    }
    return temp.Next
}

#
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    temp := &ListNode{Next: head}
    fast, slow := temp, temp
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return temp.Next
}

#
var count int

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head == nil {
        count = 0
        return nil
    }
    head.Next = removeNthFromEnd(head.Next, n)
    count = count + 1
    if count == n {
        return head.Next
    }
    return head
}Copy

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]Copy

var res []string

func generateParenthesis(n int) []string {
    res = make([]string, 0)
    dfs(0, 0, n, "")
    return res
}

func dfs(left, right, max int, str string) {
    if left == right && left == max {
        res = append(res, str)
        return
    }
    if left < max {
        dfs(left+1, right, max, str+"(")
    }
    if right < left {
        dfs(left, right+1, max, str+")")
    }
}

#
/*
dp[i]表示n=i时括号的组合
dp[i]="(" + dp[j] + ")"+dp[i-j-1] (j<i)
dp[0] = ""
*/
func generateParenthesis(n int) []string {
    dp := make([][]string, n+1)
    dp[0] = make([]string, 0)
    if n == 0 {
        return dp[0]
    }
    dp[0] = append(dp[0], "")
    for i := 1; i <= n; i++ {
        dp[i] = make([]string, 0)
        for j := 0; j < i; j++ {
            for _, a := range dp[j] {
                for _, b := range dp[i-j-1] {
                    str := "(" + a + ")" + b
                    dp[i] = append(dp[i], str)
                }
            }
        }
    }
    return dp[n]
}

#
type Node struct {
    str   string
    left  int
    right int
}

func generateParenthesis(n int) []string {
    res := make([]string, 0)
    if n == 0 {
        return res
    }
    queue := make([]*Node, 0)
    queue = append(queue, &Node{
        str:   "",
        left:  n,
        right: n,
    })
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.left == 0 && node.right == 0 {
            res = append(res, node.str)
        }
        if node.left > 0 {
            queue = append(queue, &Node{
                str:   node.str + "(",
                left:  node.left - 1,
                right: node.right,
            })
        }
        if node.right > 0 && node.left < node.right {
            queue = append(queue, &Node{
                str:   node.str + ")",
                left:  node.left,
                right: node.right - 1,
            })
        }
    }
    return res
}Copy

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:给定 1->2->3->4, 你应该返回 2->1->4->3.Copy

func swapPairs(head *ListNode) *ListNode {
    temp := &ListNode{Next: head}
    prev := temp
    for head != nil && head.Next != nil {
        first, second := head, head.Next
        prev.Next = second
        first.Next, second.Next = second.Next, first
        prev, head = first, first.Next
    }
    return temp.Next
}

#
func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    first, second := head, head.Next
    first.Next, second.Next = swapPairs(second.Next), first
    return second
}Copy

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，
例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:输入: dividend = 10, divisor = 3输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:输入: dividend = 7, divisor = -3 输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示：
    被除数和除数均为 32 位有符号整数。
    除数不为 0。
    假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31,  2^31 − 1]。
    本题中，如果除法结果溢出，则返回 2^31 − 1。Copy

func divide(dividend int, divisor int) int {
    if divisor == 0 || dividend == 0 {
        return 0
    }
    if divisor == 1 {
        return dividend
    }
    flag, count := 1, 1
    if dividend < 0 {
        flag = -flag
        dividend = -dividend
    }
    if divisor < 0 {
        flag = -flag
        divisor = -divisor
    }
    a, b, c := dividend, divisor, 0
    temp := b
    for a-b >= 0 {
        for a-b >= 0 {
            a = a - b
            c = c + count
            b = b + b
            count = count + count
        }
        b = temp
        count = 1
    }
    if c > math.MaxInt32 {
        return math.MaxInt32
    }
    if flag < 0 {
        return -c
    }
    return c
}

#
func divide(dividend int, divisor int) int {
    res := dividend / divisor
    if res > math.MaxInt32 {
        return math.MaxInt32
    }
    return res
}Copy

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1Copy

func nextPermutation(nums []int) {
    n := len(nums)
    left := n - 2
    // 以12385764为例，从后往前找到5<7 的升序情况，目标值为左边的数5
    for left >= 0 && nums[left] >= nums[left+1] {
        left--
    }
    if left == -1 {
        sort.Ints(nums)
        return
    }
    right := n - 1
    // 从后往前，找到第一个大于目标值的数，如6>5，然后交换
    for right >= 0 && nums[right] <= nums[left] {
        right--
    }
    nums[left], nums[right] = nums[right], nums[left]
    count := 0
    // 后面是降序状态，让它变为升序
    for i := left + 1; i <= (left+1+n-1)/2; i++ {
        nums[i], nums[n-1-count] = nums[n-1-count], nums[i]
        count++
    }
}

# 2
func nextPermutation(nums []int) {
    n := len(nums)
    left := n - 2
    // 以12385764为例，从后往前找到5<7 的升序情况，目标值为左边的数5
    for left >= 0 && nums[left] >= nums[left+1] {
        left--
    }
    if left >= 0 { // 存在升序的情况
        right := n - 1
        // 从后往前，找到第一个大于目标值的数，如6>5，然后交换
        for right >= 0 && nums[right] <= nums[left] {
            right--
        }
        nums[left], nums[right] = nums[right], nums[left]
    }
    reverse(nums, left+1, n-1)
}

func reverse(nums []int, left, right int) {
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}Copy

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4
示例 2:输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1Copy

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }
        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]
示例 2:输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]Copy

func searchRange(nums []int, target int) []int {
    left := 0
    right := len(nums) - 1
    for left <= right {
        if nums[left] != target {
            if target > nums[left] {
                left++
            }
        }
        if nums[right] != target {
            if target < nums[right] {
                right--
            }
        }
        if left < len(nums) && right >= 0 &&
            nums[left] == nums[right] && nums[left] == target {
            break
        }
    }
    if right < left {
        return []int{-1, -1}
    }
    return []int{left, right}
}

#
func searchRange(nums []int, target int) []int {
    left := -1
    right := -1
    for i := 0; i < len(nums); i++ {
        if nums[i] == target {
            right = i
        } else if nums[i] > target {
            break
        }
    }
    for i := len(nums) - 1; i >= 0; i-- {
        if nums[i] == target {
            left = i
        } else if nums[i] < target {
            break
        }
    }
    return []int{left, right}
}

# 3
func searchRange(nums []int, target int) []int {
    if len(nums) == 0 || nums[0] > target || nums[len(nums)-1] < target {
        return []int{-1, -1}
    }
    left := leftSearch(nums, target)
    right := rightSearch(nums, target)
    return []int{left, right}
}

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

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

#
func searchRange(nums []int, target int) []int {
    left := -1
    right := -1
    for i, j := 0, len(nums)-1; i <= j; {
        mid := i + (j-i)/2
        if nums[mid] < target {
            i = mid + 1
        } else if nums[mid] > target {
            j = mid - 1
        } else {
            for temp := mid; temp >= 0; temp-- {
                if target == nums[temp] {
                    left = temp
                } else {
                    break
                }
            }
            for temp := mid; temp < len(nums); temp++ {
                if target == nums[temp] {
                    right = temp
                } else {
                    break
                }
            }
            break
        }
    }
    return []int{left, right}
}Copy

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
    一个有效的数独（部分已被填充）不一定是可解的。
    只需要根据以上规则，验证已经填入的数字是否有效即可。
    给定数独序列只包含数字 1-9 和字符 '.' 。
    给定数独永远是 9x9 形式的。Copy

func isValidSudoku(board [][]byte) bool {
    var row, col, arr [9][9]int
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] != '.' {
                num := board[i][j] - '1'
                index := (i/3)*3 + j/3
                if row[i][num] == 1 || col[j][num] == 1 || arr[index][num] == 1 {
                    return false
                }
                row[i][num] = 1
                col[j][num] = 1
                arr[index][num] = 1
            }
        }
    }
    return true
}Copy

给定一个无重复元素的数组 candidates 和一个目标数 target ，
找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
    所有数字（包括 target）都是正整数。
    解集不能包含重复的组合。 
示例 1:输入: candidates = [2,3,6,7], target = 7, 所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:输入: candidates = [2,3,5], target = 8, 所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]Copy

var res [][]int

func combinationSum(candidates []int, target int) [][]int {
    res = make([][]int, 0)
    sort.Ints(candidates)
    dfs(candidates, target, []int{}, 0)
    return res
}

func dfs(candidates []int, target int, arr []int, index int) {
    if target == 0 {
        temp := make([]int, len(arr))
        copy(temp, arr)
        res = append(res, temp)
        return
    }
    if target < 0{
        return
    }
    for i := index; i < len(candidates); i++ {
        arr = append(arr, candidates[i])
        dfs(candidates, target-candidates[i], arr, i)
        arr = arr[:len(arr)-1]
    }
}

#
var res [][]int

func combinationSum(candidates []int, target int) [][]int {
    res = make([][]int, 0)
    sort.Ints(candidates)
    dfs(candidates, target, []int{}, 0)
    return res
}

func dfs(candidates []int, target int, arr []int, index int) {
    if target == 0 {
        temp := make([]int, len(arr))
        copy(temp, arr)
        res = append(res, temp)
        return
    }
    for i := index; i < len(candidates); i++ {
        if target < candidates[i] {
            return
        }
        dfs(candidates, target-candidates[i], append(arr, candidates[i]), i)
    }
}Copy

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
    所有数字（包括目标数）都是正整数。
    解集不能包含重复的组合。 
示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2:输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]Copy

var res [][]int

func combinationSum2(candidates []int, target int) [][]int {
    res = make([][]int, 0)
    sort.Ints(candidates)
    dfs(candidates, target, []int{}, 0)
    return res
}

func dfs(candidates []int, target int, arr []int, index int) {
    if target == 0 {
        temp := make([]int, len(arr))
        copy(temp, arr)
        res = append(res, temp)
        return
    }
    if target < 0 {
        return
    }
    for i := index; i < len(candidates); i++ {
        origin := i
        for i < len(candidates)-1 && candidates[i] == candidates[i+1] {
            i++
        }
        arr = append(arr, candidates[i])
        dfs(candidates, target-candidates[i], arr, origin+1)
        arr = arr[:len(arr)-1]
    }
}

#
var res [][]int

func combinationSum2(candidates []int, target int) [][]int {
    res = make([][]int, 0)
    sort.Ints(candidates)
    dfs(candidates, target, []int{}, 0)
    return res
}

func dfs(candidates []int, target int, arr []int, index int) {
    if target == 0 {
        temp := make([]int, len(arr))
        copy(temp, arr)
        res = append(res, temp)
        return
    }
    for i := index; i < len(candidates); i++ {
        if i != index && candidates[i] == candidates[i-1] {
            continue
        }
        if target < 0 {
            return
        }
        arr = append(arr, candidates[i])
        dfs(candidates, target-candidates[i], arr, i+1)
        arr = arr[:len(arr)-1]
    }
}Copy

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，
它们的乘积也表示为字符串形式。
示例 1:输入: num1 = "2", num2 = "3"输出: "6"
示例 2:输入: num1 = "123", num2 = "456"输出: "56088"
说明：
    num1 和 num2 的长度小于110。
    num1 和 num2 只包含数字 0-9。
    num1 和 num2 均不以零开头，除非是数字 0 本身。
    不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。Copy

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }
    arr := make([]int, len(num1)+len(num2))
    for i := len(num1) - 1; i >= 0; i-- {
        a := int(num1[i] - '0')
        for j := len(num2) - 1; j >= 0; j-- {
            b := int(num2[j] - '0')
            value := a*b + arr[i+j+1]
            arr[i+j+1] = value % 10
            arr[i+j] = value/10 + arr[i+j]
        }
    }
    res := ""
    for i := 0; i < len(arr); i++ {
        if i == 0 && arr[i] == 0 {
            continue
        }
        res = res + string(arr[i]+'0')
    }
    return res
}

# 2
func multiply(num1 string, num2 string) string {
    a, b := new(big.Int), new(big.Int)
    a.SetString(num1, 10)
    b.SetString(num2, 10)
    a.Mul(a, b)
    return a.String()
}Copy

给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:输入: [1,2,3]输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]Copy

var res [][]int

func permute(nums []int) [][]int {
    res = make([][]int, 0)
    arr := make([]int, 0)
    visited := make(map[int]bool)
    dfs(nums, 0, arr, visited)
    return res
}

func dfs(nums []int, index int, arr []int, visited map[int]bool) {
    if index == len(nums) {
        temp := make([]int, len(arr))
        copy(temp, arr)
        res = append(res, temp)
        return
    }
    for i := 0; i < len(nums); i++ {
        if visited[i] == false {
            arr = append(arr, nums[i])
            visited[i] = true
            dfs(nums, index+1, arr, visited)
            arr = arr[:len(arr)-1]
            visited[i] = false
        }
    }
}

#
func permute(nums []int) [][]int {
    if len(nums) == 1 {
        return [][]int{nums}
    }
    res := make([][]int, 0)
    for i := 0; i < len(nums); i++ {
        tempArr := make([]int, len(nums)-1)
        copy(tempArr[0:], nums[:i])
        copy(tempArr[i:], nums[i+1:])
        arr := permute(tempArr)
        for _, v := range arr {
            res = append(res, append(v, nums[i]))
        }
    }
    return res
}

#
var res [][]int

func permute(nums []int) [][]int {
    res = make([][]int, 0)
    arr := make([]int, len(nums))
    dfs(nums, 0, arr)
    return res
}

func dfs(nums []int, index int, arr []int) {
    if index == len(nums) {
        temp := make([]int, len(arr))
        copy(temp, arr)
        res = append(res, temp)
        return
    }
    for i := index; i < len(nums); i++ {
        arr[index] = nums[i]
        nums[i], nums[index] = nums[index], nums[i]
        dfs(nums, index+1, arr)
        nums[i], nums[index] = nums[index], nums[i]
    }
}Copy

给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:输入: [1,1,2] 输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]Copy

var res [][]int

func permuteUnique(nums []int) [][]int {
    res = make([][]int, 0)
    sort.Ints(nums)
    dfs(nums, 0, make([]int, len(nums)), make([]int, 0))
    return res
}

func dfs(nums []int, index int, visited []int, arr []int) {
    if len(nums) == index {
        temp := make([]int, len(arr))
        copy(temp, arr)
        res = append(res, temp)
        return
    }
    for i := 0; i < len(nums); i++ {
        if visited[i] == 1 {
            continue
        }
        // visited[i-1] == 0 或者 visited[i-1] == 1都可以
        if i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0 {
            // if i > 0 && nums[i] == nums[i-1] && visited[i-1] == 1 {
            continue
        }
        arr = append(arr, nums[i])
        visited[i] = 1
        dfs(nums, index+1, visited, arr)
        visited[i] = 0
        arr = arr[:len(arr)-1]
    }
}

# 2
var res [][]int

func permuteUnique(nums []int) [][]int {
    res = make([][]int, 0)
    sort.Ints(nums)
    dfs(nums, 0)
    return res
}

func dfs(nums []int, index int) {
    if index == len(nums) {
        temp := make([]int, len(nums))
        copy(temp, nums)
        res = append(res, temp)
        return
    }
    m := make(map[int]int)
    for i := index; i < len(nums); i++ {
        if _, ok := m[nums[i]]; ok {
            continue
        }
        m[nums[i]] = 1
        nums[i], nums[index] = nums[index], nums[i]
        dfs(nums, index+1)
        nums[i], nums[index] = nums[index], nums[i]
    }
}

# 3
var res [][]int

func permuteUnique(nums []int) [][]int {
    res = make([][]int, 0)
    sort.Ints(nums)
    dfs(nums, make([]int, 0))
    return res
}

func dfs(nums []int, arr []int) {
    if len(nums) == 0 {
        temp := make([]int, len(arr))
        copy(temp, arr)
        res = append(res, temp)
        return
    }
    for i := 0; i < len(nums); i++ {
        if i != 0 && nums[i] == nums[i-1] {
            continue
        }
        tempArr := make([]int, len(nums))
        copy(tempArr, nums)
        arr = append(arr, nums[i])
        dfs(append(tempArr[:i], tempArr[i+1:]...), arr)
        arr = arr[:len(arr)-1]
    }
}Copy