算法——字母异位词分组、最长连续序列、移动零、两数之和的实现
字母异位词分组
输入: 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 放入字典中
解法:
代码语言: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 []
}