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

2024-06-26 17:06:05 浏览数 (1)

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

字母异位词分组

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

思路:

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

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

然后来看具体实现:

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

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

解法:

代码语言:Swift复制
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 会计算到这个值

代码语言:Swift复制
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:

代码语言:Swift复制
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 的逻辑,直接实现如下:

代码语言:Swift复制
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;同时保证总共的遍历次数为数组的长度。修改后实现如下:

代码语言:Swift复制
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
    }
}

两数之和

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

思路:

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

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

解法:

代码语言:Swift复制
/**

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 []
}

0 人点赞