脑图：http://naotu.baidu.com/file/3bc98871b57aa37136f7db9c7c603376?token=7a4113ffec3d8fba
239. 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
算法思路
- 暴力法
两层循环，外层循环遍历数组，内层循环遍历其中的窗口k个元素，找到最大值
// 伪代码：
for i in 0..<nums.count-k+1
max = nums[i]
for j in i..<i+k
max = Max(max, nums[j])
result.appent[max]
- 双端队列
利用一个单调递减的双端队列，队首保存最大值；当前值 小于 队尾，在队尾插入；否则，移除队尾元素。队列元素个数超出窗口k移除队首。
// 伪代码
for i in 0..<nums.count
while !deque.isEmpty && nums[i] >= deque.last {
deque.removeLast()
}
deque.append(i)
if i - deque.first > k {
deque.removeFirst()
}
result.append(nums[deque.first])
}
详细题解链接：https://www.jianshu.com/p/a879b0758d2c
242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
算法思路
- 排序
异位词排序之后相等
对两个异位词进排序，之后比较排序之后的两个字符串是否相等，相等 return true；否则 return false；
// 伪代码
sortS = s.sorted()
sortT = t.sorted()
sortS == sortT
- 字典
利用字典辅助存储字母出现的次数
key字母： value次数
最后判断两个字典是否相同
// 伪代码
for i in s {
if sMap.keys.contains(i) {
sMap[i] += 1
} else {
sMap[i] + 1
}
if tMap.keys.contains(i) {
tMap[i] += 1
} else {
tMap[i] + 1
}
sMap == tMap
}
- 辅助数组
利用字母表数组辅助
字母表数组的索引为 字母的ASCII值-a的ASCII值，value为字母出现的次数
遍历第一个字符串，字母表数组的次数++
遍历第二个字符串，字母表数组的次数--
最后查看字母表数组每个索引值是否为0
// 伪代码
for char in s {
alphabet[char.value - 'a'.value] += 1
}
for char in t {
alphabet[char.value - 'a'.value] -= 1
}
for i in alphabet {
if i != 0 {
return false
}
}
return true
详细题解：https://www.jianshu.com/p/f3fc2596edec
49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
算法思路
- 排序、字典
异位词，排序之后的字符串相同即为异位词
利用字典，key字符串排序之后，value异位词数组
// 伪代码
for s in nums {
if map.keys.contains(s.sorted()) {
map[s.sorted].append(s)
} else {
map[s.sorted] = s
}
}
return map.values
- 计数器、字典
异位词，每个字母出现次数相同的字符串即为异位词
字典，key字母表数组的字符串，value 异位词数组
// 伪代码
for s in nums {
for char in s {
alphabet[char.value - 'a'.value] += 1
}
if map.keys.contains(alphabet.description) {
map[alphabet.description].append(s)
} else {
map[alphabet.description] = s
}
}
return map.values
详细题解：https://www.jianshu.com/p/4050ac383902
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
算法思路
- 暴力解法
两次循环，判断两两元素相加是否等于target
// 伪代码
for i in 0..nums.count {
for j in i+1..<nums.count {
if target == nums[i] + nums[j] {
return [i, j]
}
}
}
- 双指针
数组排序，利用头尾指针，计算出相加等于target的两个元素，再遍历原始数组，找到两个元素的索引
// 伪代码
sortNums = nums.sorted()
while left < right {
if sortNums[left] + sortNums[right] == target {
return [sortNums[left], sortNums[right]]
} else if sortNums[left] + sortNums[right] < target {
left += 1
} else {
right -= 1
}
}
for i in 0..< nums.count {
if nums[i] == sortNums[left] {
result[0] = i
}
}
for i in 0..<nums.count {
if nums[i] == sortNums[right] && i != result[0] {
result[1] = i
}
}
详细题解：https://www.jianshu.com/p/656e37076047
GitHub：https://github.com/huxq-coder/LeetCode
欢迎star
网友评论