LeetCode题目：
散列表
class Solution {
// // 排序然后对比解法
// func isAnagram(_ s: String, _ t: String) -> Bool {
// let sortedS = s.sorted()
// let sortedT = t.sorted()
// return sortedS == sortedT ? true : false
// }
// hashMap
func isAnagram(_ s: String, _ t: String) -> Bool {
if s.count != t.count { return false }
var dictC = Dictionary<Character, Int>()
var dictT = Dictionary<Character, Int>()
for c in s {
if let count = dictC[c] {
dictC[c] = count + 1
} else {
dictC.updateValue(1, forKey: c)
}
}
for c in t {
if let count = dictT[c] {
dictT[c] = count + 1
} else {
dictT.updateValue(1, forKey: c)
}
}
for c in s {
if dictC[c] != dictT[c] { return false }
}
return true
}
}
class Solution {
func groupAnagrams(_ strs: [String]) -> [[String]] {
var res = Array<Array<String>>()
var dict = Dictionary<Array<Int>, String>()
for (index, str) in strs.enumerated() {
let a: String = "a"
let aNum = a.unicodeScalars.first!.value
var key = Array(repeating: 0, count: 26)
for c in str {
key[Int(c.unicodeScalars.first!.value - aNum)] += 1
}
if dict[key] != nil {
dict[key]! += "\(index),"
} else {
dict[key] = "\(index),"
}
}
for (_, var value) in dict {
value.removeLast()
let indexArray = value.components(separatedBy: ",")
var finalArray = Array<String>()
for i in indexArray {
finalArray.append(strs[Int(i)!])
}
res.append(finalArray)
}
return res
}
}
二叉树
class Solution {
func preorderTraversal(_ root: TreeNode?) -> [Int] {
var res = Array<Int>()
preOrder(root, res: &res)
return res
}
func preOrder(_ root: TreeNode?, res: inout Array<Int>) {
// terminator
if root == nil { return }
// process current logic
res.append(root!.val)
// drill down
preOrder(root?.left, res: &res)
preOrder(root?.right, res: &res)
}
}
class Solution {
func preorder(_ root: Node?) -> [Int] {
var res = Array<Int>()
preorder(root, res: &res)
return res
}
func preorder(_ root: Node?, res: inout Array<Int>) {
if root == nil { return }
res.append((root!.val))
for i in 0..<(root?.children.count)! {
preorder(root?.children[i], res: &res)
}
}
}
class Solution {
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var res = Array<Int>()
inorder(root, res: &res)
return res
}
func inorder(_ root: TreeNode?, res: inout Array<Int>) {
if root == nil { return }
inorder(root?.left, res: &res)
res.append(root!.val)
inorder(root?.right, res: &res)
}
}
class Solution {
func postorder(_ root: Node?) -> [Int] {
var res = Array<Int>()
postOrder(root, res: &res)
return res
}
func postOrder(_ root: Node?, res: inout Array<Int>) {
// terminator
if root == nil { return }
// process current logic
for i in 0..<(root?.children.count)! {
// drill down
postOrder(root?.children[i], res: &res)
}
res.append(root!.val)
}
}
class Solution {
// 递归解法
// func levelOrder(_ root: Node?) -> [[Int]] {
// var res = Array<Array<Int>>()
// var level = 0
// processOrder(root, res: &res, level: level)
// return res
// }
// func processOrder(_ root: Node?, res: inout Array<Array<Int>>, level: Int) {
// if root == nil { return }
// if res.count <= level {
// res.append([])
// }
// res[level].append(root!.val)
// let newLevel = level + 1
// for i in 0..<(root?.children.count)! {
// processOrder(root?.children[i], res: &res, level: newLevel)
// }
// }
//BFS解法
func levelOrder(_ root: Node?) -> [[Int]] {
guard let root = root else { return []}
var queue = Array<Node?>()
var res = Array<Array<Int>>()
queue = [root]
while !queue.isEmpty {
let levelCount = queue.count
var temp = Array<Int>()
for _ in 0..<levelCount {
let node = queue.removeFirst()
temp.append(node!.val)
node!.children.forEach { queue.append($0) }
}
res.append(temp)
}
return res
}
}
class Solution {
func invertTree(_ root: TreeNode?) -> TreeNode? {
if root == nil { return nil}
let left = invertTree(root?.left)
let right = invertTree(root?.right)
root?.left = right
root?.right = left
return root
}
}
class Solution {
func isValidBST(_ root: TreeNode?) -> Bool {
var res = true
var lower = Int64.min
backTrack(root: root, lower: &lower, res: &res)
return res
}
func backTrack(root: TreeNode?, lower: inout Int64, res: inout Bool) {
// 左根右
if root == nil {
return }
backTrack(root: root?.left, lower: &lower, res: &res)
if lower >= root!.val {
res = false
}
lower = Int64(root!.val)
backTrack(root: root?.right, lower: &lower, res: &res)
}
}
class Solution {
func maxDepth(_ root: TreeNode?) -> Int {
if root == nil { return 0 }
let maxLeft = maxDepth(root?.left)
let maxRight = maxDepth(root?.right)
return max(maxLeft, maxRight) + 1
}
}
class Solution {
func minDepth(_ root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
var minLevel = 0
var queue = [root]
while !queue.isEmpty {
minLevel += 1
for _ in 0..<queue.count {
let currentNode = queue.removeFirst()
if currentNode.left == nil && currentNode.right == nil {
return minLevel
}
if let right = currentNode.right {
queue.append(right)
}
if let left = currentNode.left {
queue.append(left)
}
}
}
return minLevel
}
}
class Codec {
func serialize(_ root: TreeNode?) -> String {
guard let nonNilRoot = root else {
return ""
}
return BFS(root: nonNilRoot)
}
func deserialize(_ data: String) -> TreeNode? {
if data == "" {return nil}
let NodeValueArray = data.split(separator: ",")
// 构造一个TreeNode数组
var treeNodeArray = Array<TreeNode?>()
for i in NodeValueArray {
if i == "Null" {
treeNodeArray.append(nil)
} else {
treeNodeArray.append(TreeNode(Int(i)!))
}
}
let resRoot:TreeNode? = treeNodeArray.first!
var queue = Array<TreeNode?>()
queue = [resRoot]
var i = 1
while !queue.isEmpty {
if let currentRoot = queue.removeFirst() {
if let left = treeNodeArray[i] {
currentRoot.left = left
queue.append(left)
}
if let right = treeNodeArray[i + 1] {
currentRoot.right = right
queue.append(right)
}
i += 2
}
}
return resRoot
}
func BFS(root: TreeNode?) -> String {
guard let root = root else {
return ""
}
var queue: [TreeNode?] = [root]
var res = "\(root.val),"
while !queue.isEmpty {
for _ in 0..<queue.count {
let currentNode = queue.removeFirst()
if let left = currentNode?.left {
queue.append(left)
res += "\(left.val),"
} else {
res += "Null,"
}
if let right = currentNode?.right {
queue.append(right)
res += "\(right.val),"
} else {
res += "Null,"
}
}
}
res.removeLast()
return res
}
}
// Your Codec object will be instantiated and called as such:
// var ser = Codec()
// var deser = Codec()
// deser.deserialize(ser.serialize(root))
class Solution {
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode?{
if root == nil || root?.val == p?.val || root?.val == q?.val {
return root
}
let left = lowestCommonAncestor(root?.left, p, q)
let right = lowestCommonAncestor(root?.right, p, q)
if left == nil { return right }
if right == nil { return left }
return root
}
}
class Solution {
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
var mPreorder = preorder
var mInorder = inorder
return backTrack(preorderNodeArray: &mPreorder, inorderNodeArray: &mInorder)
}
func backTrack(preorderNodeArray: inout [Int], inorderNodeArray: inout [Int]) -> TreeNode? {
guard let rootVal = preorderNodeArray.first else {
return nil
}
let root = TreeNode(rootVal)
if preorderNodeArray.count == 1 {
return root
}
var inorderLeftTree = Array(inorderNodeArray[0..<inorderNodeArray.firstIndex(of: root.val)!])
var inorderRighTree = Array(inorderNodeArray[inorderNodeArray.firstIndex(of: root.val)! + 1..<inorderNodeArray.count])
var preorderLeftTree = Array(preorderNodeArray[1..<inorderLeftTree.count + 1])
var preorderRightTree = Array(preorderNodeArray[(inorderLeftTree.count + 1)..<preorderNodeArray.count])
root.left = backTrack(preorderNodeArray: &preorderLeftTree, inorderNodeArray: &inorderLeftTree)
root.right = backTrack(preorderNodeArray: &preorderRightTree, inorderNodeArray: &inorderRighTree)
return root
}
}
递归
class Solution {
func generateParenthesis(_ n: Int) -> [String] {
var res = Array<String>()
backTrack(n: n, left: 0, right: 0, res: &res, cur: "")
return res
}
func backTrack(n: Int, left: Int, right: Int, res: inout Array<String>, cur: String) {
// terminator
if cur.count == n * 2 {
// process result
res.append(cur)
return
}
if left < n {
backTrack(n: n, left: left + 1, right: right, res: &res, cur: cur + "(")
}
if right < left {
backTrack(n: n, left: left, right: right + 1, res: &res, cur: cur + ")")
}
}
}
class Solution {
func combine(_ n: Int, _ k: Int) -> [[Int]] {
var res = Array<Array<Int>>()
var cur = Array<Int>()
backTracking(n: n, k: k, res: &res, cur: &cur, curNum: 1)
return res
}
func backTracking(n: Int, k: Int, res: inout Array<Array<Int>>, cur: inout Array<Int>, curNum: Int) {
if cur.count + (n - curNum + 1) < k {
return
}
if cur.count == k {
res.append(cur)
return
}
cur.append(curNum)
backTracking(n: n, k: k, res: &res, cur: &cur, curNum: curNum + 1)
cur.removeLast()
backTracking(n: n, k: k, res: &res, cur: &cur, curNum: curNum + 1)
}
}
class Solution {
func permute(_ nums: [Int]) -> [[Int]] {
var path = Array<Int>()
var res = Array<Array<Int>>()
var used = Array(repeating: false, count: nums.count)
dfs(path: &path, res: &res, used: &used, nums: nums, depth: 0)
return res
}
func dfs(path: inout Array<Int>, res: inout Array<Array<Int>>, used: inout Array<Bool>, nums: Array<Int>, depth: Int) {
if depth == nums.count {
res.append(path)
return
}
for i in 0..<nums.count {
if used[i] { continue }
path.append(nums[i])
used[i] = true
dfs(path: &path, res: &res, used: &used, nums: nums, depth: depth + 1)
path.removeLast()
used[i] = false
}
}
}
class Solution {
func permuteUnique(_ nums: [Int]) -> [[Int]] {
var res = Array<Array<Int>>()
var path = Array<Int>()
var used = Array(repeating: false, count: nums.count)
dfs(nums: nums.sorted(by: <), res: &res, path: &path, level: 0, used: &used)
return res
}
func dfs(nums: [Int], res: inout [[Int]], path: inout [Int], level: Int, used: inout [Bool]) {
if level == nums.count {
res.append(path)
return
}
for i in 0..<nums.count {
// !used[i - 1] 保证在填【i】这个数的时候重复数字只会被填入一次,只要最左边的。所以如果两个数字相同，并且前一个还没有用过，那么是不符合规则（用最左侧）的。要continue跳过
if used[i] == true || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue
}
used[i] = true
path.append(nums[i])
dfs(nums: nums, res: &res, path: &path, level: level + 1, used: &used)
path.removeLast()
used[i] = false
}
}
}
