第三阶段算法学习总结

脑图：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