算法——两数之和、字母异位词分组、最长连续序列、移动零
原创算法——两数之和、字母异位词分组、最长连续序列、移动零
原创
算法——字母异位词分组、最长连续序列、移动零、两数之和的实现
字母异位词分组
输入: 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
}
}两数之和
给指定的数，找到数组中两数之和为给定数的 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 []
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
