Merge pull request algorithm004-01#394 from uniquenaer/master

melody-li · web-flow · commit 1aaf20f77c1a · 2019-10-28T11:55:39.000+08:00
181-Week 02
diff --git a/.DS_Store b/.DS_Store
diff --git a/Week 01/id_181/PriorityQueue.md b/Week 01/id_181/PriorityQueue.md
@@ -1,4 +1,9 @@
 ## PriorityQueue 优先队列
 
 > 优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序
-> PriorityQueue 是一个无界队列，但是初始的容量(实际是一个Object[])，随着不断向优先级队列添加元素，其容量会自动扩容，无需指定容量增加策略的细节。
+> PriorityQueue 是一个无界队列，但是初始的容量(实际是一个Object[])，随着不断向优先级队列添加元素，其容量会自动扩容，无需指定容量增加策略的细节。
+
+参考文献：
+
+[《Java源码分析》：PriorityQueue - wojiushimogui的博客 - CSDN博客](https://blog.csdn.net/u010412719/article/details/52355557)
+[Source for java.util.PriorityQueue (GNU Classpath 0.99.1-pre Documentation)](http://fuseyism.com/classpath/doc/java/util/PriorityQueue-source.html#line.231)
diff --git a/Week 02/id_181/105.construct-binary-tree-from-preorder-and-inorder-traversal.py b/Week 02/id_181/105.construct-binary-tree-from-preorder-and-inorder-traversal.py
@@ -0,0 +1 @@
+# [Python 递归详解 - 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal)
diff --git a/Week 02/id_181/236.lowest-common-ancestor-of-a-binary-tree.py b/Week 02/id_181/236.lowest-common-ancestor-of-a-binary-tree.py
@@ -0,0 +1,78 @@
+# [236. 二叉树的最近公共祖先 - 力扣（LeetCode）](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
+
+# Definition for a binary tree node.
+# class TreeNode:
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+# 递归
+class Solution:
+    def __init__(self):
+        self.ans = None
+        
+    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
+        """
+        :type root:TreeNode
+        :type p:TreeNode
+        :type q:TreeNode
+        :rtype:TreeNode
+        """
+        def recurse_tree(curr_node):
+            if not curr_node:
+                return False
+            
+            left  = recurse_tree(curr_node.left)
+            
+            right = recurse_tree(curr_node.right)
+            
+            mid = curr_node == p or curr_node == q
+            
+            if(mid + left + right >=2):
+                self.ans = curr_node
+            
+            return mid or left or right
+        
+        recurse_tree(root)
+        
+        return self.ans
+
+    
+    # 父指针迭代 
+
+    def lowestCommonAncestor(self,root,p,q):
+        stack = [root]
+        
+        parent = {root:None}
+        
+        while p not in parent or q not in parent:
+            node = stack.pop()
+            
+            if node.left:
+                parent[node.left] = node
+                stack.append(node.left)
+                
+            if node.right:
+                parent[node.right] = node
+                stack.append(node.right)
+                
+            anccestors = set()
+            
+        while p:
+            anccestors.add(p)
+            p = parent[p]
+            
+        while q not in anccestors:
+            q = parent[q]
+        
+        return q
+        
+    ## 不明觉厉
+    def lowestCommonAncestor(self, root, p, q):
+        if root in (None, p, q): return root
+        left, right = (self.lowestCommonAncestor(kid, p, q)
+                   for kid in (root.left, root.right))
+        return root if left and right else left or right
+
+
diff --git a/Week 02/id_181/242.valid-anagram.js b/Week 02/id_181/242.valid-anagram.js
@@ -0,0 +1,78 @@
+// [242. 有效的字母异位词 - 力扣（LeetCode）](https://leetcode-cn.com/problems/valid-anagram/)
+
+/**
+   借鉴一下使用map实现，
+   0 s 和 t 的长度判断
+   1 对s中每个字母进行统计
+   2 在t时 如果不存在，直接返回false,存在则删除
+   3 最后判断map的size
+   
+   ps 非空判断
+   
+ * @param {string} s
+ * @param {string} t
+ * @return {boolean}
+ */
+var isAnagram = function(s, t) {
+    if(s.length!==t.length) return false;
+      if(s.length===0) return true;
+    const map = new Map();
+    for(let i =0;i<s.length;i++) {
+        const getMap = map.get(s[i])+1 || 1;
+        map.set(s[i],getMap)
+    }
+    
+    for(let j = 0;j<t.length;j++) {
+        const getMap = map.get(t[j]);
+        if(getMap == undefined ) return false;
+         console.log(getMap,t[j])
+        if(getMap===1) { 
+            map.delete(t[j])
+        }else {
+            map.set(t[j],getMap-1);
+        }
+        
+    }
+   
+    return !map.size
+};
+
+/*
+* 排序
+**/
+
+var isAnagram = function(s,t){
+    if(s.length!=t.length) return false;  
+    var str1 = s.split('').sort();
+    var str2 = t.split('').sort();
+    return str1.join('') === str2.join('');
+}
+
+/**
+* 哈希实现
+**/
+
+var isAnagram = function(s,t) {
+  if(s.length!=t.length) return false;  
+  var result = [];  // 数组
+  var aCode = 'a'.charCodeAt();
+  for(var i = 0;i<s.length;i++) {
+      var sIndex = s[i].charCodeAt()-aCode,tIndex = t[i].charCodeAt()-aCode;
+      result[sIndex]=(result[sIndex]||0) + 1;
+      result[tIndex]=(result[tIndex]||0) - 1;
+  }
+  
+  if(result.length===0) return true;
+  
+   for(var r = 0;r<result.length;r++){
+      if(!!result[r]){
+          return false;
+      }     
+  }
+  return true;
+  
+}
+
+
+
+
diff --git a/Week 02/id_181/590.n-ary-tree-postorder-traversal.js b/Week 02/id_181/590.n-ary-tree-postorder-traversal.js
@@ -0,0 +1,27 @@
+/**
+ * // Definition for a Node.
+ * function Node(val,children) {
+ *    this.val = val;
+ *    this.children = children;
+ * };
+ */
+/**
+ * @param {Node} root
+ * @return {number[]}
+ */
+
+// 后序遍历 根 左 右
+var postorder = function(root) {
+  const result = [];
+  function pushRoot(root) {
+      if(root.val===null) return result;    
+      if(root.children.length>0) {
+         for(var i = 0; i<root.children.length;i++) {
+             pushRoot(root.children[i]);
+         }
+      }
+      result.push(root.val)
+  }
+  root && pushRoot(root);
+  return result;
+};
diff --git a/Week 02/id_181/590.n-ary-tree-postorder-traversal.py b/Week 02/id_181/590.n-ary-tree-postorder-traversal.py
@@ -0,0 +1,18 @@
+# [590. N叉树的后序遍历 - 力扣（LeetCode）](https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/)
+class Solution:
+    def postorder(self, root: 'Node'):
+        res = []
+        if root == None: return res
+        stack = [root]
+        
+        while stack:
+            curr = stack.pop()
+            res.append(curr.val)
+            stack.extend(curr.children)
+            print(stack)
+       
+            
+        return res[::-1]
+
+
+# 前序排列后的倒序输出
diff --git a/Week 02/id_181/94.binary-tree-inorder-traversal.js b/Week 02/id_181/94.binary-tree-inorder-traversal.js
@@ -0,0 +1,48 @@
+/**
+ * [94. 二叉树的中序遍历 - 力扣（LeetCode）](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/)
+ * Definition for a binary tree node.
+ * function TreeNode(val) {
+ *     this.val = val;
+ *     this.left = this.right = null;
+ * }
+ */
+/**
+ * @param {TreeNode} root
+ * @return {number[]} 
+ 中序排序 先拍左子树 再排根节点 最后 右子树
+ */
+
+var inorderTraversal = function(root) {
+    const result = [];
+    function pushRoot(root){ 
+        if(root) {
+          // 以前写的判断 root.left 为真 才执行加入，发现很耗性能
+         root.left !== null && pushRoot(root.left)
+         result.push(root.val);
+         root.right !== null && pushRoot(root.right)
+        }
+     }
+    pushRoot(root)
+    
+    return result;
+};
+
+// 基于栈的遍历
+
+var inorderTraversal = function(root){
+  var result = [];
+  var tmpStack = [];
+  var currNode = root;
+  
+  while(currNode!=null || tmpStack.length!=0) {
+      while(currNode != null) {
+          tmpStack.push(currNode);
+          currNode = currNode.left;
+      }
+      currNode = tmpStack.pop();
+      result.push(currNode.val);
+      currNode = currNode.right;
+  }
+  
+  return result;
+}

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1 @@`
	`1`	`+# [Python 递归详解 - 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal)`