LeetCode 刷题笔记 - 第一期

最近发现一个刷算法题目的网站，LeetCode ，回想一下毕业以后一直在写一些业务，并没有涉及到算法，对于算法的记忆还停留在上学时候的课程里面，所以之后会在这里慢慢回顾一下和算法相关的有关的知识，打好基础才是最重要的。

以后会在这里记录一下刷题时的一些笔记，和总结一些知识点在这里。

因为最近在学习Golang，所以这里的实现会主要以Golang和Node.js来实现。今天先上两道简单入门的算法题目。

Two Sum

题目描述

Two Sum 是一个比较经典算法，就是要求给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的数组下标。

比如给定的数组为 [3, 6, 8, 2]，然后给定的目标值为 9，则返回值为 [0, 1]，即 3 和 6 的下标。

思考

看到这个题目，首先想到的就是嵌套两个循环然后求和和目标值进行比对，具体如下：

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

OK，这段代码运行是没有问题的，但是，我们可以看到，这里面的两个循环是嵌套的，所以这个函数运行的时间复杂度为 O(n^2)，这个时间复杂度是比较不能够接受的，那我们就应该考虑一种更为效率的方法。

假设我们在第一遍遍历数组的时候，将遍历过的元素存入Hash表中，然后在后面遍历出的元素和Hash表中的元素做计算，因为Hash表的查询的时间复杂度为 O(1)，所以这样的方法最后的时间复杂度为遍历数组的时间复杂度，即为 O(n)。

改进方法

按照上面的思路，重新实现一下：

func twoSum(nums []int, target int) []int {
  var results []int
  mapping := make(map[int]int)
  for i, num := range nums {

    // 计算和目标值相差的数值
    sub := target - num

    // 查找Map中是否存在这个数值
    // 如果存在，和这个数值相加即为目标值
    // 如果不存在，将这个数值和下标存入Map
    if v, ok := mapping[sub]; ok {
      results = append(results, v, i)
    } else {
      mapping[num] = i
    }
  }
  return results
}

这里定义了一个 Map，KEY 值为数组中元素的值， VALUE 值为数组中元素的下标值，遍历时，计算出当前元素值和目标值的差，然后在 Map 中查找是否存在和这个差值相等的 Key，如果存在则返回当前元素在数组中的下标和 Map 中这个 Key 对应的 Value。

这样这个函数的时间复杂度为 O(n)，这个时间复杂度在在一个可以接受的范围内。

Reverse Integer

题目描述

这个题目的要求很简单，给定一个 32 位有符号整数，将整数中的数字进行反转。如果反转后的整数溢出，则返回 0。

比如：给定的数值为 123，反转后的结果为 321

比如：给定的数值为 -234，反转后的结果为 -432

比如：给定的数值为 340，反转后的结果为 43

解决方案

在给定整数中可以通过取余数来获取每一位的数值，然后在乘以对应的位数进行反转，所以可以按照这个思路实现：

func reverse(x int) int {
  result := 0
  for x != 0 {
    remainder := x % 10
    result = result * 10 + remainder    
    x = (x - remainder) / 10
  }
  if result > math.MaxInt32 - 1 || result < math.MinInt32 {
    return 0
  }
  return result
}

这里我们进行一个循环，然后每次循环对给定的数值除以 10 取余数，取到的余数追加到反转后的数值后面，即为之前反转后的数值扩大 10 倍加上这个数值，即增加一位，原数值减去余数再除以 10，即为减少一位。直到数值减少到 0。

最后由于数值为 int32 类型，所以我们需要判断如果超过 int32 类型所表示的范围，则返回0。

这样这个函数的时间复杂度为 O(n)。

总结

今天简单记录两个算法的实现过程，Two Sum 和 Reverse Integer，和对算法的时间复杂度优化。把这两个算法的实现记录下来也便于以后自己查阅，如果有人阅读到这篇文章，而且有更好，更高效的算法，欢迎指导。