算法——两数之和、字母异位词分组、最长连续序列、移动零

2024-06-20

算法——两数之和、字母异位词分组、最长连续序列、移动零的实现

两数之和

给指定的数，找到数组中两数之和为给定数的 index

思路：

使用字典 dict 存储，key 为数组中 index 对应的值, value 为 index。然后遍历数组，

如果 target - value在数组中存在，则返回target-value 对应的字典的 value 即 index和当前 value 对应的 index；
如果不存在，则把当前 value 和 index 存入数组中。

解法：

/**

index, value 遍历数组

如果 target - value 在字典中，则返回字典中的index和当前index

如果不存在，则存储当前值和 index，dict[value] = index

*/

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var dict = [Int: Int]()
    for (index, value) in nums.enumerated() {
        if let lastIndex = dict[target - value] {
            return [lastIndex, index]
        } 
        dict[value] = index
    }
    return []
}

字母异位词分组

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

思路：

首先理解什么是异位词，是有相同字母组成，不同顺序的单词。所以异位词分组，就是把有相同字母组成的单词分成一个组。

理解了之后，再来看怎么实现？首先怎么判断是由相同字母组成的单词呢？很简单，对单词做个排序，比如”eat”、”tea”、”ate”，排序后都是”aet”；所有的异位词排序后相同的就可以分到一个组。

然后来看具体实现：

借助字典来存储，排序后的固定单词作为 key，value 是一个数组，存储的是相同异位词的原始单词

声明一个字典 [String: [String]]
遍历数组，排序后的单词作为 key
如果当前 key 存在，则说明之前有存储过，即前面有当前单词的异位词，把当前单词存储到字典的 value （数组）中
如果当前 key 不存在，则说明前面没有当前单词的异位词，把当前单词放入数组，作为 value 放入字典中

解法：


func groupAnagrams(_ strs: [String]) -> [[String]] {
  var dict = [String: [String]]()
  for str in strs {
      let key = String(str.sorted())
      if let _ = dict[key] {
          dict[key]?.append(str)
      } else {
          dict[key] = [str]
      }
  }
  return dict.values.map { $0 }
}

最长连续序列

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

思路：

理解最长连续序列的意思，我之前误以为，是数组中每个元素的每个数都要用于判断，但其实不是这样。是数组里每个元素判断，比如 100，要看做一个数，而不是拆分为 1 0 0；

然后，再来看连续序列的意思，比如上面的[100, 4, 200, 1, 3, 2]，最长的连续的序列就是[1, 2, 3, 4]; 因为 100 和 200 没有连续的数字。

再比如[1, 2, 4, 5, 6]，有两个连续序列[1, 2]、[4, 5, 6]，最长的连续序列就是[4, 5, 6]。这样就理解了题目意思

解法：

解法一：从小到大排序，然后放入 set 中，从小的开始，如果+1 在set 中，则最长序列+1，如果不在则重置，最后取出最长的那个序列即可。

解法二：将数组放入 set 中，遍历，如果当前值-1 不在数组中，则说明是起始值，开始+1 遍历；当前值-1 在 set 中，则忽略，因为判断中的当前值+1 会计算到这个值

func longestConsecutive(_ nums: [Int]) -> Int {
   let numSet = Set(nums)
   var longestStreak = 0
   for num in numSet {
      if !numSet.contains(num - 1) {
          var currentNum = num
          var currentStreak = 1
          while numSet.contains(currentNum + 1) {
              currentNum += 1
              currentStreak += 1 
          }
          longestStreak = max(longestStreak, currentStreak)
      }
   }
   return longestStreak
}

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]

思路：

有两种解法，一种是移动 0，一种是移动非 0 的元素

解法 1：遍历数组每一个元素，如果是 0，则删除，然后插入到数组末尾，然后继续遍历；
解法 2：把所有不是 0 的元素，从头依次放入数组中，并记录有多少不为 0 的元素；最后把数组剩余位置补 0；

下面是解法 2 的实现。

解法2：


func moveZeroes(_ nums: inout [Int]) {
    var index = 0
    for i in 0..<nums.count {
        if nums[i] != 0 {
            nums[index] = nums[i]
            index += 1
        }
    }
    for i in index..<nums.count {
        nums[i] = 0
    }
}

再来看下解法1 的实现，按照解法 1 的逻辑，直接实现如下：


func moveZeroes1_Wrong(_ nums: inout [Int]) {
    for i in 0..<nums.count {
        if nums[i] == 0 {
            nums.remove(at: i)
            nums.append(0)
        }
    }
}

但是解法 1 如果按照上面的写法就会发现结果不通过？为什么呢？乍一看逻辑没有问题，但是在 for 循环中，如果删除了某个元素，导致位置发生了变化，然后还是按照初始数组的顺序遍历，就会导致结果不对；

比如：起始数组为[0, 0, 1]

i = 0时，运行后数组变为了[0, 1, 0]
然后继续 i = 1 时，运行后数组还是[0, 1, 0]
然后 i = 2，运行后数组还是[0, 1, 0]
最终结果就不对了

所以如果想要按照解法 1，移动 0 来实现，需要每次遍历遇到 0 时，i 保持上一次 i 的值；遇到非 0 的值，i += 1；同时保证总共的遍历次数为数组的长度。修改后实现如下：


func moveZeroes1(_ nums: inout [Int]) {
    let count = nums.count
    var compareCount = 0
    var i = 0
    while compareCount < count {
        if nums[i] == 0 {
            nums.remove(at: i)
            nums.append(0)
        } else {
            i += 1
        }
        compareCount += 1
    }
}