第三階段算法學(xué)習(xí)總結(jié)

腦圖：http://naotu.baidu.com/file/3bc98871b57aa37136f7db9c7c603376?token=7a4113ffec3d8fba

239. 滑動窗口最大值

給定一個數(shù)組 nums腺兴，有一個大小為 k 的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。你只可以看到在滑動窗口內(nèi)的 k 個數(shù)字刷袍『牧铮滑動窗口每次只向右移動一位冲泥。
返回滑動窗口中的最大值。
進(jìn)階：
你能在線性時間復(fù)雜度內(nèi)解決此題嗎？
示例:
輸入: 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

算法思路

暴力法
兩層循環(huán)刨晴，外層循環(huán)遍歷數(shù)組矛物，內(nèi)層循環(huán)遍歷其中的窗口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]

雙端隊(duì)列
利用一個單調(diào)遞減的雙端隊(duì)列，隊(duì)首保存最大值履羞；當(dāng)前值小于隊(duì)尾峦萎，在隊(duì)尾插入屡久；否則，移除隊(duì)尾元素爱榔。隊(duì)列元素個數(shù)超出窗口k移除隊(duì)首被环。

// 偽代碼
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])
}

詳細(xì)題解鏈接：http://www.reibang.com/p/a879b0758d2c

242. 有效的字母異位詞

給定兩個字符串 s 和 t ，編寫一個函數(shù)來判斷 t 是否是 s 的字母異位詞详幽。
示例 1:
輸入: s = "anagram", t = "nagaram"
輸出: true
示例 2:
輸入: s = "rat", t = "car"
輸出: false
說明:
你可以假設(shè)字符串只包含小寫字母筛欢。
進(jìn)階:
如果輸入字符串包含 unicode 字符怎么辦？你能否調(diào)整你的解法來應(yīng)對這種情況妒潭？
算法思路

排序
異位詞排序之后相等
對兩個異位詞進(jìn)排序悴能，之后比較排序之后的兩個字符串是否相等，相等 return true雳灾；否則 return false漠酿；

// 偽代碼
sortS = s.sorted()
sortT = t.sorted()
sortS == sortT

字典
利用字典輔助存儲字母出現(xiàn)的次數(shù)
key字母： value次數(shù)
最后判斷兩個字典是否相同

// 偽代碼
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
}

輔助數(shù)組
利用字母表數(shù)組輔助
字母表數(shù)組的索引為字母的ASCII值-a的ASCII值，value為字母出現(xiàn)的次數(shù)
遍歷第一個字符串谎亩，字母表數(shù)組的次數(shù)++
遍歷第二個字符串炒嘲，字母表數(shù)組的次數(shù)--
最后查看字母表數(shù)組每個索引值是否為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

詳細(xì)題解：http://www.reibang.com/p/f3fc2596edec

49. 字母異位詞分組

給定一個字符串?dāng)?shù)組，將字母異位詞組合在一起匈庭。字母異位詞指字母相同夫凸，但排列不同的字符串。
示例:
輸入: ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
說明：
所有輸入均為小寫字母阱持。
不考慮答案輸出的順序夭拌。
算法思路

排序、字典
異位詞衷咽，排序之后的字符串相同即為異位詞
利用字典鸽扁，key字符串排序之后，value異位詞數(shù)組

// 偽代碼
for s in nums {
  if map.keys.contains(s.sorted()) {
    map[s.sorted].append(s)
  } else {
    map[s.sorted] = s
  }
}
return map.values

計(jì)數(shù)器镶骗、字典
異位詞桶现，每個字母出現(xiàn)次數(shù)相同的字符串即為異位詞
字典，key字母表數(shù)組的字符串鼎姊，value 異位詞數(shù)組

// 偽代碼
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

詳細(xì)題解：http://www.reibang.com/p/4050ac383902

1. 兩數(shù)之和

給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target骡和，請你在該數(shù)組中找出和為目標(biāo)值的那兩個整數(shù)，并返回他們的數(shù)組下標(biāo)相寇。
你可以假設(shè)每種輸入只會對應(yīng)一個答案慰于。但是，數(shù)組中同一個元素不能使用兩遍唤衫。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
算法思路

暴力解法
兩次循環(huán)婆赠，判斷兩兩元素相加是否等于target

// 偽代碼
for i in 0..nums.count {
  for j in i+1..<nums.count {
    if target == nums[i] + nums[j] {
      return [i, j]
    }
  }
 }

雙指針
數(shù)組排序，利用頭尾指針战授，計(jì)算出相加等于target的兩個元素页藻，再遍歷原始數(shù)組桨嫁，找到兩個元素的索引

// 偽代碼
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
  }
}

詳細(xì)題解：http://www.reibang.com/p/656e37076047

GitHub：https://github.com/huxq-coder/LeetCode
歡迎star