algorithm019 · kangkangkim · Nov 8, 2020 · Nov 9, 2020 · Nov 9, 2020 · Nov 14, 2020
diff --git a/Week_01/.README.md.swp b/Week_01/.README.md.swp
diff --git a/Week_01/Git command.pdf b/Week_01/Git command.pdf
diff --git a/Week_01/README.md b/Week_01/README.md
@@ -1 +1,31 @@
-学习笔记
+学习笔记
+For this week, I have learned three topics in terms of Array, Linekd list, Stack, Queue.
+
+Topic 1: Array 
+array学的还是可以的之前，这次主要通过练习leetcode的题目，发现其实array也可以很难。
+以前我只会暴力求解，而且没意识自己用的是暴力求解
+这次学到了一种很好用的双指针
+常见就是一个快慢指针，或者一个头尾指针
+
+Topic 2: Linked list
+学校教的链表把，感觉每个人都写的不一样，老师每次写的也都不一样，导致我一开始就没学好
+这兴趣感觉学的还可以，不过这个东西超哥说了，东西基本上都是固定的，所以考练习就好了。
+也是有了一个学习思路，会在下周继续去练习linked list的singular, double, circule etc.
+然后我觉得最重要对我而言，还是画图把，不画图，脑子空想很难想
+这个就想超哥说的，很多时候脑子超过了人脑的维度概念，就比较难以figure out.
+
+Topic 3: Stack
+先进后出的特性 Last in First out
+然后主要我觉得超哥是教会我们则么去看一些文件把，这个其实蛮重要的，之前学的时候，老师其实也给了很多资料，
+但是不知道是干什么用的，这次稍微明确一些了。
+
+
+Topic 4: Queue
+First in First out
+也学习了priority queue,不过我还要研究研究，我还是学生，之前没学好，所以感觉时间花的要久一点，而且有些太基础的内容，
+需要我自己去查阅。
+
+本周感悟：
+就像超哥说的，第一周坚持一下很容易，有激情，希望自己以后也能保持好吧。good luck to myself
+这个学习笔记不知道写什么老实说，我会附带上传xmind 做的课程导图.
+
diff --git a/Week_01/leetcode21.java b/Week_01/leetcode21.java
@@ -0,0 +1,26 @@
+class leetcode21 {
+    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+        // l1 is empty,return l2
+        if(l1 == null ) return l2;
+        //l2 is empty, return l1
+        if(l2 == null) return l1;
+        ListNode dummyHead = new ListNode(-99);
+        ListNode ptr =dummyHead;
+
+        while(l1 != null && l2 != null) {
+            if(l1.val <= l2.val) {
+                ptr.next = l1;
+                l1=l1.next;
+                ptr=ptr.next;
+            }else{
+                ptr.next =l2;
+                l2=l2.next;
+                ptr=ptr.next;
+            }
+        }
+        //合并完以后可能还有一个没有合并完的，最多一个，所以就指向未完的链表
+        ptr.next = l1 == null ? l2 : l1;
+        return dummyHead.next;
+
+    }
+}
diff --git a/Week_01/leetcode26.java b/Week_01/leetcode26.java
@@ -0,0 +1,15 @@
+class leetcode26 {
+    public int removeDuplicates(int[] nums) {
+        //two pointer method
+        //i is fatser pointer
+        //j is a slow pointer
+        int i = 0;
+        for(int j = 1; j < nums.length; j++) {
+            if(nums[j] != nums[i]) {
+                i++;
+                nums[i] = nums[j];
+            }
+        }
+        return i + 1;
+    }
+}
diff --git a/Week_01/第三课（数组、链表跳）.pdf b/Week_01/第三课（数组、链表跳）.pdf
diff --git a/Week_01/第四课Stack and Queue.pdf b/Week_01/第四课Stack and Queue.pdf
diff --git a/Week_01/算法训练营（方法论）.pdf b/Week_01/算法训练营（方法论）.pdf
diff --git a/Week_02/README.md b/Week_02/README.md
@@ -1 +1,64 @@
-学习笔记
+学习笔记
+还是一样，主要的内容我都做了思维导图，这里就简写一些把
+
+For hash table:
+1.每个key会通过hashing functioin然后最后去到hash table的
+eg: lies ,每个字母之和为429， 然后通过hash function,放到hash table
+2.如果碰到两个一样的值，那么hashtable就会在后面开始延长，以链表的形式
+3.如果设计的比较差的hash table,其实和链表差不多了就，O(n）
+4.好的hash table可以有效的避免冲突，达到O（1）
+Average
+Search: O(1)
+Insertion: O(1)
+Access: O(1)
+
+
+For tree:
+其实linked list就是特殊化的Tree
+Tree就算是特殊化的Graph, 当有cycle的时候其实就是graph了
+然后学习了二叉树的遍历：
+pre-order: root, left, right
+in-order: left, root, right
+post-order:left right root
+这一块的内容对于递归用的非常多，然后老师强调了其实递归并不是一定是效率低的一个内容
+
+BST：
+简单来说就是一个有序的二叉树
+三个特点
+1. 左子树上 所有结点 的值 均小于它根结点； 
+2. 右子树上 所有结点 的值 均大于它根结点； 
+3. 以此类推：左、右子树 也分别为二叉查找。 （这就是 重复性 ！）
+然后对于删除有一个需要注意：
+如果删掉以后需要选择一个节点去替换：那么选择右边的最小的那个来替换
+Average
+Search: O(logn)
+Insertion: O(logn)
+Access: O(logn)
+
+
+For heap:
+主要特点：可以迅速找到一堆数中的最大/最小的数据结构
+比如大顶堆，这样子find-max:O(1)
+但是你会发现这个java实现方式就是用的priorityQueue去实现的，这个在本周作业里面常常用到，很实用
+
+二叉堆性质：
+1.一个完全二叉树full binary tree
+2.数中任意节点的值>=其子节点的值
+一般通过数组实现
+关于Index关系：
+left children : 2*i +1;
+right children: 2*i +2；
+partent floor((i-1)/2);
+
+Insert需要特别强调：
+新元素都加到heap的尾部，这个和实现有关系
+然后heapifyup
+
+Delete max：跟insert类似
+先把最后一个元素替换到顶部
+然后heapifyDown,具体还是看图理解和复习
+
+for Studying:
+这周感觉还可以把，比上周感觉时间分配的更均匀一点，希望下周继续努力，不过由于自己基础感觉有些内容还没学过，可能需要再去学一下
+不然有些lamda函数，有点懵，还要这个有一些老师写的什么操作感觉有点看不懂，什么Map.Entry，不知道在干嘛
+有空我会在研究一下
diff --git a/Week_02/leetcode1.java b/Week_02/leetcode1.java
@@ -0,0 +1,16 @@
+class leetcode1 {
+    public int[] twoSum(int[] nums, int target) {
+        //先做一个hashtable
+        //利用target -nums[i]
+        Map<Integer, Integer> hashtable = new HashMap<Integer,Integer>();
+        for(int i = 0; i < nums.length ;i++) {
+            if(hashtable.containsKey(target- nums[i])) {
+                return new int[]{hashtable.get(target-nums[i]),i};
+            }
+            hashtable.put(nums[i],i);
+        }
+        return new int[0];
+
+
+    }
+}
diff --git a/Week_02/leetcode242.java b/Week_02/leetcode242.java
@@ -0,0 +1,26 @@
+class leetcode242 {
+    public boolean isAnagram(String s, String t) {
+        if(s.length() != t.length()) return false;
+
+        int counter[] = new int[26];
+        for(int i = 0 ; i< s.length(); i++) {
+            counter[s.charAt(i)-'a']++;
+            counter[t.charAt(i)-'a']--;
+        }
+        boolean p=true;
+        for(int i=0 ; i< counter.length ;i++) {
+            if(counter[i] !=0){
+                p=false;
+            }
+
+        }
+        return p;
+
+
+
+
+
+
+
+    }
+}
diff --git a/Week_02/leetcode347.java b/Week_02/leetcode347.java
@@ -0,0 +1,35 @@
+class leetcode347 {
+    public int[] topKFrequent(int[] nums, int k) {
+        //思路: 
+        //1.hashmap --> 统计次数
+        //2.heap -->output
+Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
+        for (int num : nums) {
+            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
+        }
+
+        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
+        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
+            public int compare(int[] m, int[] n) {
+                return m[1] - n[1];
+            }
+        });
+        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
+            int num = entry.getKey(), count = entry.getValue();
+            if (queue.size() == k) {
+                if (queue.peek()[1] < count) {
+                    queue.poll();
+                    queue.offer(new int[]{num, count});
+                }
+            } else {
+                queue.offer(new int[]{num, count});
+            }
+        }
+        int[] ret = new int[k];
+        for (int i = 0; i < k; ++i) {
+            ret[i] = queue.poll()[0];
+        }
+        return ret;
+
+    }
+}
diff --git a/Week_02/leetcode589.java b/Week_02/leetcode589.java
@@ -0,0 +1,24 @@
+class leetcode589 {
+    public List<Integer> preorder(Node root) {
+        LinkedList<Node> stack = new LinkedList<>();
+        LinkedList<Integer> output = new LinkedList<>();
+        if(root == null) return output;
+        //把根节点放进去
+        stack.add(root);
+        while(!stack.isEmpty()) {
+
+            Node node = stack.pollLast();
+            System.out.println(node.val);
+            output.add(node.val);
+            //这布很关键，根据stack先入后出来的
+            //1后面想出3，就得最后放3，这样子就算先出来
+            //所以需要这一步
+            Collections.reverse(node.children);//集合中的值反转，
+            for(Node item: node.children) {//直接把子节点的集合遍历加入栈中
+                stack.add(item);
+            }
+        }
+        return output;
+
+    }
+}
diff --git a/Week_02/第五课-哈希表、映射、集合的实现与特性.pdf b/Week_02/第五课-哈希表、映射、集合的实现与特性.pdf
diff --git a/Week_02/第六课-树、二叉树、二叉搜索树,堆，图.pdf b/Week_02/第六课-树、二叉树、二叉搜索树,堆，图.pdf
diff --git a/Week_03/README.md b/Week_03/README.md
@@ -1 +1,82 @@
-学习笔记
+# 学习笔记
+
+看了前几周别人总的总结，发现自己好像写的不是很到位，下周好好改进自己，这周时间来不及了！
+这周内容其实对我而言有点不太理解，练leetcode时候感觉很差，特别是回溯，分支，这些大学里面都没讲过，其实发现自己大三的话，其实基础可能的确就是差一点。
+感觉还是要多花点时间先去理解一下底层的东西。我会加油的！
+这周学校的大作业比较多，这上面时间花的就少一点，下周感恩节放假了，可以好好研究一下！
+
+## For 递归呢：
+按照四步法:
+1.terminator
+2.process logic in the current logic 处理当前逻辑
+3.drill down 下探到下一层
+4.reverse the current level status if needed 清理当前层（这个不是每次都用得到）
+
+
+### 回顾到之前的树，用的都是递归的思路：
+ ``` 
+ def preorder(self, root):
+  if root:
+  self.traverse_path.append(root.val)
+  self.preorder(root.left)
+  self.preorder(root.right)
+def inorder(self, root):
+  if root:
+  self.inorder(root.left)
+  self.traverse_path.append(root.val)
+  self.inorder(root.right)
+def postorder(self, root):
+  if root:
+  self.postorder(root.left)
+  self.postorder(root.right)
+  self.traverse_path.append(root.val)
+ ``` 
+
+### Java 代码模版for recursion
+ ``` 
+ 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
+}
+ ``` 
+
+## For 分治:
+本质上就是先divide 变成sub-problem,
+然后conquer,去给出sub-solution
+最后merge在一起，就是solution
+原理很简单，但是实操有点难,我还需要多练习去理解一下逻辑
+
+### 分治代码模板（可以理解为比recursion多了一步）
+ ``` 
+ def divide_conquer(problem, param1, param2, ...):
+    //recursion terminator
+    if problem is None:
+    print_result
+    return
+    // prepare data
+    data = prepare_data(problem)
+    subproblems = split_problem(problem, data)
+    //conquer subproblems
+    subresult1 = self.divide_conquer(subproblems[0], p1, ...)
+    subresult2 = self.divide_conquer(subproblems[1], p1, ...)
+    subresult3 = self.divide_conquer(subproblems[2], p1, ...)
+    ...
+    // process and generate the final result
+    result = process_result(subresult1, subresult2, subresult3, …)
+    // revert the current level states
+ ``` 
+
+## For 回溯：
+利用试错的思想，分别解决问题
+通常就是用递归方法来实现的
+在反复重复上述的步骤后可能出现两种情况：
+• 找到一个可能存在的正确的答案；
+• 在尝试了所有可能的分步方法后宣告该问题没有答案。
diff --git a/Week_03/leetcode105.java b/Week_03/leetcode105.java
@@ -0,0 +1,35 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class leetcode105 {
+    public TreeNode buildTree(int[] preorder, int[] inorder) {
+        int preLen = preorder.length;
+        int inLen = inorder.length;
+
+        Map<Integer, Integer> map = new HashMap<>(preLen);
+        for(int i=0 ; i< inLen; i++) {
+            map.put(inorder[i], i);
+        }
+        return helper(preorder,0, preLen-1, map, 0, inLen-1);
+
+
+    }
+    private TreeNode helper(int[] preorder, int preLeft, int preRight, Map<Integer, Integer> map, int inLeft, int inRight) {
+        if(preLeft > preRight || inLeft > inRight) return null;
+
+        int rootVal = preorder[preLeft];
+        TreeNode root=new TreeNode(rootVal);
+        int pIndex = map.get(rootVal);
+
+        root.left = helper(preorder,preLeft+1, pIndex-inLeft+preLeft, map, inLeft, pIndex-1);
+        root.right = helper(preorder,pIndex-inLeft+preLeft+1,preRight,map,pIndex+1, inRight);
+        return root;
+
+    }
+}