Merge pull request algorithm001#335 from ma451152002/20190415_58_maguangjun_week01

GeekUniversity · web-flow · commit bf259142d5ab · 2019-04-27T22:49:26.000+08:00
maguangjun: add week02
diff --git a/Week_01/id_58/NOTE.md b/Week_01/id_58/NOTE.md
@@ -1 +1,17 @@
-# 学习笔记
+# 学习笔记
+本周的学习总结：
+1、学会了GitHub的pull-requet的使用。平时我们都是直接用git提交，然后merge到master，
+对于github的pull-request的提交形式不太熟悉，通过微信群咨询和同学的帮助，我学会了
+这项功能的使用。
+2、另外感触比较深的如何结合工作和学习任务，本周共布置了16道题，我完成了3道题目。
+虽然完成了，但是还是与之前的心里目标相差很远，希望在接下来的一周，能够每天按质
+按量的完成学习任务。
+3、本周主要学习了链表的功能使用
+    83题:删除链表中的所有重复元素
+    21题:合并两个排序的链表的链表
+    24题:交换两个相邻的结点
+4、通过上面题目的训练，我对链表的题目有了新的认识，对于链表题目的解题方法就是要
+借助画图，拿出笔，简单的画出操作的关系，就可以很好的维护好各个结点关系，避免各种
+找不到后续结点错误。    
+5、对于后续的数组、栈、递归、排序的题目，在后续的过程中也要快速完成。
+
diff --git a/Week_02/id_58/LeetCode_242_058.java b/Week_02/id_58/LeetCode_242_058.java
@@ -0,0 +1,55 @@
+package algorithm.Week_02.id_58;
+
+/**
+ * 242. Valid Anagram
+ *
+ * Given two strings s and t , write a function to determine if t is an anagram of s.
+ *
+ * Example 1:
+ *
+ * Input: s = "anagram", t = "nagaram"
+ * Output: true
+ * Example 2:
+ *
+ * Input: s = "rat", t = "car"
+ * Output: false
+ * Note:
+ * You may assume the string contains only lowercase alphabets.
+ *
+ * Follow up:
+ * What if the inputs contain unicode characters? How would you adapt your solution to such case?
+ *
+ * 分析：
+ * 所谓有效的字母异位词，就是字母类型和大小都一致，但是是不同的单词，这样的两个单词互为字母异位词
+ * 分别用26个字母数组来存储两个字母串，最后对比两个数组即可，发现有不一致的则返回false，若同相同则返回true。
+ * @auther: guangjun.ma 
+ * @date: 2019/4/27 16:16
+ * @version: 1.0
+ */
+public class LeetCode_242_058 {
+    public boolean isAnagram(String s, String t) {
+        //1、这里用一个26位的字符串数字做为存储介质，转化公式为 ch - 'a'
+        int[] sCounts = new int[26];
+        int[] tCounts = new int[26];
+
+        //2、存储s字符串
+        for(char ch : s.toCharArray()){
+            sCounts[ch - 'a'] ++;
+        }
+
+        //3、存储t字符串
+        for(char ch : t.toCharArray()){
+            tCounts[ch - 'a'] ++;
+        }
+
+        //4、比较两个字符串
+        for (int i = 0; i < 26 ; i++){
+            if(sCounts[i] != tCounts[i]){
+                return false;
+            }
+        }
+
+        return true;
+
+    }
+}
diff --git a/Week_02/id_58/LeetCode_692_058.java b/Week_02/id_58/LeetCode_692_058.java
@@ -0,0 +1,69 @@
+package algorithm.Week_02.id_58;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.PriorityQueue;
+
+/**
+ * 692. Top K Frequent Words
+ *
+ * Given a non-empty list of words, return the k most frequent elements.
+ *
+ * Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
+ *
+ * Example 1:
+ * Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
+ * Output: ["i", "love"]
+ * Explanation: "i" and "love" are the two most frequent words.
+ *     Note that "i" comes before "love" due to a lower alphabetical order.
+ * Example 2:
+ * Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
+ * Output: ["the", "is", "sunny", "day"]
+ * Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
+ *     with the number of occurrence being 4, 3, 2 and 1 respectively.
+ * Note:
+ * You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
+ * Input words contain only lowercase letters.
+ * Follow up:
+ * Try to solve it in O(n log k) time and O(n) extra space.
+ *
+ * 分析 ： 这里是取最大的值，可以借助Java里的最大堆的数据结构  PriorityQueue
+ * @auther: guangjun.ma
+ * @date: 2019/4/27 17:07
+ * @version: 1.0
+ */
+public class LeetCode_692_058 {
+    public List<String> topKFrequent(String[] words, int k) {
+        Map<String,Integer> map = new HashMap();
+
+        //把元素都放入到map中
+        for(String s : words){
+            map.put(s,map.getOrDefault(s,0) + 1);
+        }
+
+        //优先队列  最大堆
+        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
+            @Override
+            public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
+                if(o1.getValue() .equals(o2.getValue()) ){
+                    return o1.getKey().compareTo(o2.getKey());
+                }
+                return o2.getValue() - o1.getValue();
+            }
+        });
+
+        //将map中的元素加入到队列中
+        queue.addAll(map.entrySet());
+
+        //依次取出k个值
+        List<String> res = new ArrayList<>(k);
+        for(int i = 0; i <k ; i++){
+            res.add(queue.poll().getKey());
+        }
+        return res;
+
+    }
+}
