Merge pull request algorithm004-01#428 from jie96169/master

melody-li · web-flow · commit 7060d508e8b1 · 2019-10-28T11:52:54.000+08:00
611-Week 02
diff --git a/Week 02/id_611/LeetCode_105_611.java b/Week 02/id_611/LeetCode_105_611.java
@@ -0,0 +1,47 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    
+    HashMap<Integer,Integer> map = new HashMap();
+    int[] preorder ;
+    
+    //使用hashset保存前序遍历，加快查询效率
+    public TreeNode buildTree(int[] preorder, int[] inorder) {
+        int preLen = preorder.length;
+        int inLen = inorder.length;
+        if(preLen != inLen){
+            return null;
+        }
+        this.preorder = preorder;
+        for(int i = 0; i < inorder.length; i++){
+            map.put(inorder[i],i);
+        }
+        return buildTree(0,preLen-1,0,inLen);
+    }
+    
+    public TreeNode buildTree( int preLeft, int preRight, int inLeft, int inRight){
+        //终止条件
+        if(preLeft > preRight || inLeft > inRight){
+            return null;
+        }
+        
+        //根据前序遍历,找到跟节点位置,并生成跟节点
+        int rootVal = preorder[preLeft];
+        TreeNode rootNode = new TreeNode(rootVal);
+        //找到下一层级的跟节点位置
+        int nextRootIdx = map.get(rootVal);
+        
+        rootNode.left = buildTree(preLeft + 1, nextRootIdx + preLeft -inLeft, inLeft, nextRootIdx -1);
+        rootNode.right = buildTree(nextRootIdx + preLeft -inLeft +1, preRight, nextRootIdx + 1,inRight );
+            
+        return rootNode;
+    }
+    
+}
diff --git a/Week 02/id_611/LeetCode_17_611.java b/Week 02/id_611/LeetCode_17_611.java
@@ -0,0 +1,40 @@
+class Solution {
+    
+    //初始化数据
+    HashMap<String,String> map = new HashMap(){{
+      put("2", "abc");
+      put("3", "def");
+      put("4", "ghi");
+      put("5", "jkl");
+      put("6", "mno");
+      put("7", "pqrs");
+      put("8", "tuv");
+      put("9", "wxyz");
+    }};
+    
+    
+    public List<String> letterCombinations(String digits) {
+        if(digits.length() != 0){
+            digits("",digits);
+        }
+        return output;
+    }
+    
+    //先用回溯实现
+    public void digits(String combition,String next_digits){
+        if(next_digits.length() == 0){
+            output.add(combition);
+            return;
+        } else {
+            String num = next_digits.substring(0,1);
+            String letters = map.get(num);
+            for(int i = 0; i < letters.length(); i++){
+                String letter = letters.substring(i,i+1);
+                digits(combition + letter, next_digits.substring(1));
+            }
+            
+        }
+    }
+    
+    List<String> output = new ArrayList();
+}
diff --git a/Week 02/id_611/LeetCode_236_611.java b/Week 02/id_611/LeetCode_236_611.java
@@ -0,0 +1,27 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    //传说中的递归
+    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+        //终止条件
+        //向上回溯条件
+        if(root == null || root.val ==p.val || root.val == q.val) return root;
+        
+        TreeNode left = lowestCommonAncestor(root.left,p,q);
+        TreeNode right = lowestCommonAncestor(root.right,p,q);
+        
+        //判断是否到底
+        if(left == null) return right;
+        if(right == null) return left;
+        //
+        return root;
+
+    }
+}
diff --git a/Week 02/id_611/LeetCode_46_611.java b/Week 02/id_611/LeetCode_46_611.java
@@ -0,0 +1,40 @@
+class Solution {
+    //回溯+剪枝+状态重置
+    public List<List<Integer>> permute(int[] nums) {
+        int len = nums.length;
+        List<List<Integer>> resList = new ArrayList();
+        if(len == 0){
+            return resList;
+        }
+       
+        //状态记忆
+        boolean[] used = new boolean[nums.length+1];
+        //路径记忆
+        Stack<Integer> path = new Stack();
+        
+        geneatePermute( nums, resList, 0, len, used, path);
+        return resList;
+    }
+    
+    
+    public void geneatePermute(int[] nums,List<List<Integer>> resList,int curSize,int len,boolean[] used,Stack<Integer> path){
+        if(curSize == len){
+            resList.add(new ArrayList(path));
+            return ;
+        }
+        
+        for(int i = 0; i < len; i++){
+            //根据状态，判断分支是否已经记忆
+            if(!used[i]){
+                used[i] = true;
+                path.add(nums[i]);
+                //curSize 为每层独立空间中的数据
+                geneatePermute(nums,resList,curSize + 1,len,used,path);
+                //状态重置
+                used[i] = false;
+                path.pop();
+            }
+        }
+    }
+    
+}
diff --git a/Week 02/id_611/LeetCode_47_611.java b/Week 02/id_611/LeetCode_47_611.java
@@ -0,0 +1,33 @@
+class Solution {
+    
+    boolean[] used ;
+    List<List<Integer>> resList = new ArrayList();
+    public List<List<Integer>> permuteUnique(int[] nums) {
+        int n = nums.length;
+        if(n == 0) return resList;
+        Arrays.sort(nums);
+        
+        used = new boolean[n];
+        findpermuteUnique(nums,0,new Stack<Integer>());
+        return resList;
+    }
+    
+    public void findpermuteUnique(int[] nums,int dept, Stack<Integer> path){
+        if(dept == nums.length){
+            resList.add(new ArrayList(path));
+            return;
+        }
+        
+        for(int i = 0; i < nums.length; i++){
+            if(!used[i]){
+                //复合剪枝操作
+                if(i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
+                used[i] = true;
+                path.add(nums[i]);
+                findpermuteUnique(nums,dept + 1,path);
+                used[i] = false;
+                path.pop();
+            }
+        }
+    }
+}
diff --git a/Week 02/id_611/LeetCode_77_611.java b/Week 02/id_611/LeetCode_77_611.java
@@ -0,0 +1,24 @@
+class Solution {
+    List<List<Integer>> res = new LinkedList();
+    int n;
+    int k;
+	//最普通的回溯解法，肝不动了，先撸出来再说。。。
+    public List<List<Integer>> combine(int n, int k) {
+        this.n = n;
+        this.k = k;
+        backtrack(new LinkedList(),1);
+        return res;
+    }
+    
+    public void backtrack(LinkedList<Integer> list,int first){
+        if(list.size() == k){
+           res.add(new LinkedList(list)); 
+        }
+        
+        for(int i = first; i <= n; ++i){
+            list.add(i);
+            backtrack(list,i+1);
+            list.removeLast();
+        }
+    }
+}
