Leetcode 1-5 | 欣欣然不知所以

1. 两数之和

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

解: 目的是要返回数组下标。

如果不考虑空间复杂度

如果考虑时间复杂度，就要保留一份数组备份，空间复杂度至少O(n),然后对数组进行排序，通过二分法查找，时间复杂度最优的是O(nlogn)

code

	func twoSum(nums []int, target int) []int {
m := make(map[int]int)
      for i := 0; i < len(nums); i++ {
          another := target - nums[i]
          if _, ok := m[another]; ok {
              return []int{m[another], i}
          }
          m[nums[i]] = i
      }
      return nil
  }

  func twoSum(nums []int, target int) []int {
      onum := make([]int, len(nums))
      copy(onum, nums) // 保留备份

      // Onlgn
      sort.Ints(nums) // 原数组排序

      var find = func(anum []int, dest int) int { // 二分查找数组中是否存在值为dest的元素
          start := 0
          end := len(anum) - 1
          var mid int
          for start < end-1 {
              mid = (start + end) / 2
              if anum[mid] == dest {
                  return mid
              }
              if anum[mid] > dest {
                  end = mid
              } else {
                  start = mid
              }
          }
          if anum[start] == dest {
              return start
          }
          if anum[end] == dest {
              return end
          }
          return -1
      }

      // 遍历数组匹配
      for i := range nums {
          if cj := find(nums[i+1:], target-nums[i]); cj != -1 {
              var ret = make([]int, 0)
              for j := range onum {
                  if onum[j] == nums[i] || onum[j] == nums[i+1+cj] {
                      ret = append(ret, j)
                  }
              }
              return ret
          }
      }
      return nil
  }

2. 两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字0之外，这两个数都不会以0开头。

解: 注意的只有两点

进位

链表遍历到最后做长度判断和拼接

code

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil{
        return l2
    }
    if l2 == nil{
        return l1
    }
    node := new(ListNode)
    sum := l1.Val + l2.Val
    node.Next = addTwoNumbers(l1.Next,l2.Next)
    if sum <10{
        node.Val = sum
    }else{
        node.Val = sum -10
        node.Next = addTwoNumbers(node.Next, &ListNode{Val:1})
    }

    return node
}

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度

code

func lengthOfLongestSubstring(s string) int {
    var bMap = make(map[rune]int) // 存储字符索引，用于判断重复
    var startInd = 0              // 有效点开始
    var maxLen = 0                // 长度
    for i, r := range s {
        ind,ok :=  bMap[r]
        if ok && ind >= startInd {  // 判断是否在有效区间内重复
             startInd = ind + 1     // 如果是，直接修改起始有效索引，没有比较的必要
        }else{
            l := i - startInd + 1   // 否则，每一步计算当前有效区间长度，避免临界问题
            if l > maxLen{          // 与已有最大长度比较，如果超过最大长度就更新
                maxLen = l
            }
        }
        bMap[r] = i                 // 赋值覆盖
    }
    return maxLen
}

4. 寻找两个有序数组的中位数

给定两个大小为m和n的有序数组nums1和nums2请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为O(log(m + n))。你可以假设nums1和nums2不会同时为空。

解：有序数组，要求时间复杂度是O(log)级别的，应该是要使用二分法的。但是直接的二分法似乎没有可行之路，逐步分析下，发现通过递归可以实现。

code

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    total := len(nums1) + len(nums2)
    if total%2 == 1 {
        return float64(findKthNum(nums1, nums2, total/2+1))
    } else {
        return 0.5 * float64(findKthNum(nums1, nums2, total/2)+findKthNum(nums1, nums2, total/2+1))
    }
}

// 查找第k个数
func findKthNum(nums1, nums2 []int, k int) int {
    l1, l2 := len(nums1), len(nums2)
    if l1 > l2 {
        return findKthNum(nums2, nums1, k)
    }
    if l1 == 0 {
        return nums2[k-1]
    }
    if k == 1 {
        if nums1[0] < nums2[0] {
            return nums1[0]
        } else {
            return nums2[0]
        }
    }

    var pa, pb int
    if l1 < k/2 {
        pa = l1
    } else {
        pa = k / 2
    }
    pb = k - pa
    // 比较较小端可以直接去除，不可能落在那里面，类二分
    if nums1[pa-1] < nums2[pb-1] {
        return findKthNum(nums1[pa:], nums2, k-pa)
    } else if nums2[pb-1] < nums1[pa-1] {
        return findKthNum(nums1, nums2[pb:], k-pb)
    } else {
        return nums1[pa-1]
    }
}

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

解: 硬算

code

 func longestPalindrome(s string) string {
    rs := []rune(s)
    l := len(rs)

    if l<=1{
        return s
    }

    mp := rs[0:1] // 最长子串

    for i := 0; i < l-1; i++ {
        temp1 := findPalindrome(rs, i, i)
        if len(temp1) > len(mp) {
            mp = temp1
        }
        if rs[i] == rs[i+1] {
            temp2 := findPalindrome(rs, i, i+1)
            if len(temp2) > len(mp) {
                mp = temp2
            }
        }
    }
    return string(mp)
}

func findPalindrome(rs []rune, si, ei int) []rune {
    for si > 0 && ei < len(rs)-1 {
        if rs[si-1] == rs[ei+1] {
            si--
            ei++
        } else {
            break
        }
    }
    return rs[si : ei+1]
}