Merge pull request algorithm004-01#401 from tifazxy/master

melody-li · web-flow · commit 765703048bf3 · 2019-10-28T12:00:35.000+08:00
106-Week 02
diff --git a/Week 02/id_106/17.letter-combinations-of-a-phone-number.java b/Week 02/id_106/17.letter-combinations-of-a-phone-number.java
@@ -0,0 +1,85 @@
+import java.util.HashMap;
+import java.util.ArrayList;
+/*
+ * @lc app=leetcode id=17 lang=java
+ *
+ * [17] Letter Combinations of a Phone Number
+ *
+ * https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
+ *
+ * algorithms
+ * Medium (43.31%)
+ * Likes:    2720
+ * Dislikes: 343
+ * Total Accepted:    466.7K
+ * Total Submissions: 1.1M
+ * Testcase Example:  '"23"'
+ *
+ * Given a string containing digits from 2-9 inclusive, return all possible
+ * letter combinations that the number could represent.
+ * 
+ * A mapping of digit to letters (just like on the telephone buttons) is given
+ * below. Note that 1 does not map to any letters.
+ * 
+ * 
+ * 
+ * Example:
+ * 
+ * 
+ * Input: "23"
+ * Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
+ * 
+ * 
+ * Note:
+ * 
+ * Although the above answer is in lexicographical order, your answer could be
+ * in any order you want.
+ * 
+ */
+
+// @lc code=start
+class Solution {
+    
+    public List<String> letterCombinations(String digits) {
+        HashMap<Character,String> map = new HashMap<Character,String>();    
+        map.put('2', "abc");
+        map.put('3', "def");
+        map.put('4', "ghi");
+        map.put('5', "jkl");
+        map.put('6', "mno");
+        map.put('7', "pqrs");
+        map.put('8', "tuv");
+        map.put('9', "wxyz");
+
+        ArrayList<String> result = new ArrayList<String>();
+        
+        if("".equals(digits))
+            return result;
+        else{
+            _combaination(0,"",digits,map,result);
+        }
+        return result;
+    }
+
+    private void _combaination( int level, 
+                                String s,
+                                String digits, 
+                                HashMap<Character,String> map, 
+                                ArrayList<String> result){
+        //terminator
+        if(level==digits.length()){
+            result.add(s);
+            return;
+        }
+        //current process
+        String chars = map.get(digits.charAt(level));
+        for(int index = 0; index< chars.length();index++){
+            //drill down
+            _combaination(level+1,s+chars.charAt(index), digits, map, result);
+        }
+        
+        //reverse
+    }
+}
+// @lc code=end
+//定义代码表的对应关系，对每一位数字可能对应的字母进行递归的排列
diff --git a/Week 02/id_106/46.permutations.java b/Week 02/id_106/46.permutations.java
@@ -0,0 +1,41 @@
+/*
+ * @lc app=leetcode id=46 lang=java
+ *
+ * [46] Permutations
+ */
+
+// @lc code=start
+import java.util.ArrayList;
+import java.util.List;
+class Solution {
+    public List<List<Integer>> permute(int[] nums) {
+        List<List<Integer>> result = new ArrayList<List<Integer>>();
+        _permutations(new int[nums.length], nums, new ArrayList<Integer>(), result);
+        return result;
+    }
+
+    private void _permutations( int[] visited, 
+                                int[] nums, 
+                                ArrayList<Integer> current,
+                                List<List<Integer>> result){
+        //terminator
+        if (current.size() == nums.length){
+            result.add(new ArrayList<>(current));
+            return;
+        }
+        //current process
+        for(int i = 0; i < nums.length; i++){
+            if(visited[i]==1){continue;}
+            visited[i]=1;
+            current.add(nums[i]);
+            //drill down
+            _permutations(visited, nums, current, result);
+            //reverse
+            visited[i]=0;
+            current.remove(current.size()-1);
+        }
+        
+    }
+}
+// @lc code=end
+//全排列 回溯方式，每一位置一个标志位，如果是1 ，不在加入自己，如果不是加入自己并置为1
diff --git a/Week 02/id_106/NOTE.md b/Week 02/id_106/NOTE.md
@@ -1,4 +1,29 @@
 # NOTE
+20191021-1027 week2
+1.本周主要学习了hashmap tree等数据结构的基础概念。
+2.学习了递归的思想与编写模板，同时学习了分治回溯的问题解决思想。
+3.其中树作为二维数据结构，遍历方式主要使用递归的方式，递归编写是需要注意不能使用人脑递归的方式，同时要注意寻找重复子问题与数学归纳法的证明。
+4.递归的编写模板范式如下
+    public void recur(int level, int param) { 
 
+    // terminator 
+    if (level > MAX_LEVEL) { 
+        // process result 
+        return; 
+    } 
+
+    // process current logic 
+    process(level, param); 
+
+    // drill down 
+    recur( level: level + 1, newParam); 
+
+    // restore current status 
+    
+    }
+
+
+HashMap源码分析
+主要阅读了hashmap中put get 方法的实现方式
   
 
