Merge pull request algorithm004-01#371 from z-wade/master

melody-li · web-flow · commit 3aaf5743fb48 · 2019-10-28T12:03:06.000+08:00
396-Week 02
diff --git a/Week 02/id_396/LeetCode_144_396.swift b/Week 02/id_396/LeetCode_144_396.swift
@@ -0,0 +1,58 @@
+//
+//  LeetCode_242_396.swift
+//  
+//
+//  Created by chenjunzhi on 2019/10/27.
+//
+
+import UIKit
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     public var val: Int
+ *     public var left: TreeNode?
+ *     public var right: TreeNode?
+ *     public init(_ val: Int) {
+ *         self.val = val
+ *         self.left = nil
+ *         self.right = nil
+ *     }
+ * }
+ */
+
+//二叉树前序遍历
+class Solution {
+    func preorderTraversal(_ root: TreeNode?) -> [Int] {
+        guard let tree = root else {
+            return []
+        }
+        
+        var current:TreeNode!
+        var result : [Int] = []
+        var stack: [TreeNode] = [tree]
+        while stack.count > 0 {
+            //遍历当前节点
+            current = stack.last
+            result.append(current.val)
+            stack.removeLast()
+            //右节点进入栈底
+            if let right = current.right {
+                stack.append(right)
+            }
+            //再左节点进入栈
+            if let left = current.left {
+                stack.append(left)
+            }
+        }
+        return result
+    }
+    
+    // func preorderTraversal(_ root: TreeNode?) -> [Int] {
+    //     guard let root = root else {
+    //         return []
+    //     }
+    //     let left = preorderTraversal(root.left)
+    //     let right = preorderTraversal(root.right)
+    //     return [root.val] + left + right
+    // }
+}
diff --git a/Week 02/id_396/LeetCode_242_396.swift b/Week 02/id_396/LeetCode_242_396.swift
@@ -0,0 +1,84 @@
+//
+//  LeetCode_242_396.swift
+//  
+//
+//  Created by chenjunzhi on 2019/10/27.
+//
+
+import UIKit
+
+class Solution {
+    
+    /// 思路：把每个字母变成Unicode编码。利用桶的思想，计算每个字符显示的次数。最后比较两个桶是否一样
+    func isAnagram(_ s: String, _ t: String) -> Bool {
+        guard s.count == t.count else { return false }
+        
+        let aUnicode = UnicodeScalar("a").value
+        
+        var counterS = Array(repeating: 0, count: 26)
+        for c in s.unicodeScalars {
+            counterS[Int(c.value - aUnicode)] += 1
+        }
+        
+        var counterT = Array(repeating: 0, count: 26)
+        for c in t.unicodeScalars {
+            counterT[Int(c.value - aUnicode)] += 1
+        }
+        
+        return counterS == counterT
+    }
+    
+    /// 把每个字母根据Ascii码进行桶排序，然后比较两个字符串是否相等
+    class Solution1 {
+        func isAnagram(_ s: String, _ t: String) -> Bool {
+            let charS = sort(Array(s))
+            let charT = sort(Array(t))
+            return charT == charS
+        }
+        
+         func sort(_ chars: [Character]) -> String {
+            let charVal = Character("a").asciiValue!
+            var buckets = Array(repeating: 0, count: 26)
+            for char in chars {
+                let index = char.asciiValue! - charVal
+                buckets[Int(index)] += 1
+            }
+            var result = [Character]()
+            for index in 0..<buckets.count {
+                let count = buckets[index]
+                for _ in 0..<count {
+                    result.append(Character(UnicodeScalar(index + Int(charVal))!))
+                }
+            }
+            return String(result)
+        }
+    }
+    
+    class Solution2 {
+        func isAnagram(_ s: String, _ t: String) -> Bool {
+            var dicS = [Character: Int]()
+            if s.count != t.count {
+                return false
+            }
+            
+            for sChar in s {
+                if let count = dicS[sChar] {
+                    dicS[sChar] = count + 1
+                } else {
+                    dicS[sChar] = 1
+                }
+            }
+            for tChar in t {
+                if let count = dicS[tChar] {
+                    if count == 0 {
+                        return false;
+                    }
+                    dicS[tChar] = count - 1
+                } else {
+                    return false;
+                }
+            }
+            return true;
+        }
+    }
+}
diff --git a/Week 02/id_396/LeetCode_598_396.java b/Week 02/id_396/LeetCode_598_396.java
@@ -0,0 +1,43 @@
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.List;
+
+public class NTreePreTraversal {
+
+    public List<Integer> preorder(Node root) {
+        ArrayList<Integer> result = new ArrayList();
+        LinkedList<Node> stack = new LinkedList();
+        if (root == null){
+            return  result;
+        }
+
+        stack.push(root);
+        while (!stack.isEmpty()) {
+            Node current  = stack.pop();
+            result.add(current.val);
+            if (current.children != null) {
+                for (int i = current.children.size() - 1; i >= 0; i--){
+                    stack.push(current.children.get(i));
+                }
+            }
+        }
+
+        return result;
+    }
+
+    public List<Integer> preorder2(Node root) {
+        ArrayList<Integer> result = new ArrayList();
+        LinkedList<Node> stack = new LinkedList();
+        if (root == null){
+            return  result;
+        }
+
+        result.add(root.val);
+        for (int i = 0; i < root.children.size(); i++) {
+            List<Integer> childResult = preorder(root.children.get(i));
+            result.addAll(childResult);
+        }
+        return result;
+    }
+}
diff --git a/Week 02/id_396/LeetCode_94_396.swift b/Week 02/id_396/LeetCode_94_396.swift
@@ -0,0 +1,57 @@
+//
+//  LeetCode_242_396.swift
+//  
+//
+//  Created by chenjunzhi on 2019/10/27.
+//
+
+import UIKit
+
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     public var val: Int
+ *     public var left: TreeNode?
+ *     public var right: TreeNode?
+ *     public init(_ val: Int) {
+ *         self.val = val
+ *         self.left = nil
+ *         self.right = nil
+ *     }
+ * }
+ */
+
+//基于栈的遍历
+class Solution {
+    func inorderTraversal(_ root: TreeNode?) -> [Int] {
+        var stack = [TreeNode]()
+        var currentNode = root;
+        var result = [Int]()
+        
+        while currentNode != nil || stack.count != 0 {
+            //左节点入栈
+            while currentNode != nil {
+                stack.append(currentNode!)
+                currentNode = currentNode!.left
+            }
+            //出栈并把右节点入栈
+            currentNode = stack.last
+            stack.removeLast();
+            result.append(currentNode!.val)
+            currentNode = currentNode?.right
+        }
+        return result
+    }
+}
+
+//递归 时间复杂度O(n)
+class Solution {
+    func inorderTraversal(_ root: TreeNode?) -> [Int] {
+        guard let root = root else {
+            return []
+        }
+        let left = inorderTraversal(root.left)
+        let right = inorderTraversal(root.right)
+        return left + [root.val] + right
+    }
+}
