algorithm001 · Water-DD · Apr 20, 2019 · Apr 20, 2019 · Apr 20, 2019 · Apr 20, 2019
diff --git a/Week_01/id_11/LeetCode1.cpp b/Week_01/id_11/LeetCode1.cpp
@@ -0,0 +1,106 @@
+#ifndef SOLUTION_H
+#define SOLUTION_H
+
+#include <vector>
+#include <string>
+
+#include <hash_map>
+#include <stack>
+
+#include <sstream>
+using namespace  __gnu_cxx;
+using namespace std;
+
+class Solution
+{
+public:
+    Solution();
+
+    static vector<int> twoSum(int a[], int len, int target);
+    static vector<int> twoSum2(int a[], int len, int target);
+    static vector<int> twoSum3(int a[], int len, int target);
+
+
+
+
+};
+
+vector<int> Solution::twoSum(int a[], int len,int target)
+{
+    //1 traverse the array
+    vector<int> res;
+    res.clear();
+    for(int i = 0; i < len; ++i)
+    {
+        for(int j = i+1; j < len; ++j)
+        {
+            if(a[i] + a[j] == target)
+            {
+                res.push_back(i);
+                res.push_back(j);
+
+                return res;
+
+            }
+        }
+    }
+    //
+    return res;
+}
+
+vector<int> Solution::twoSum2(int a[], int len, int target)
+{
+    //1 traverse the array
+    vector<int> res;
+    res.clear();
+    hash_map<int,int> val2Mark;
+
+    for(int i = 0; i < len; ++i)
+    {
+        val2Mark[a[i]] = i;
+    }
+
+    for(int i = 0; i < len; ++i)
+    {
+        auto it = val2Mark.find(target - a[i]);
+        if(it != val2Mark.end())
+        {
+            res.push_back(i);
+            res.push_back(it->second);
+
+            return res;
+
+        }
+    }
+
+    //
+    return res;
+}
+
+vector<int> Solution::twoSum3(int a[], int len, int target)
+{
+    //1 traverse the array
+    vector<int> res;
+    res.clear();
+
+
+    hash_map<int,int> val2Mark;
+    for(int i = 0; i < len; ++i)
+    {
+        val2Mark[a[i]] = i;
+        auto it = val2Mark.find(target - a[i]);
+        if(it != val2Mark.end())
+        {
+            res.push_back(i);
+            res.push_back(it->second);
+
+            return res;
+
+        }
+    }
+
+    //
+    return res;
+}
+
+#endif // SOLUTION_H
diff --git a/Week_01/id_11/LeetCode2.cpp b/Week_01/id_11/LeetCode2.cpp
@@ -0,0 +1,70 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode(int x) : val(x), next(NULL) {}
+ * };
+ */
+class Solution {
+public:
+    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
+
+        int s1 = len(l1);
+        int s2 = len(l2);
+
+        if(s1 < s2)
+        {
+            ListNode* temp = l1;
+            l1 = l2;
+            l2 = temp;
+        }
+
+        int add = 0;
+        ListNode* res = l1;
+        ListNode* prev = l1;
+        while(l2 != NULL)
+        {
+            int sum = l1->val+ l2->val + add;
+            add = sum / 10;
+            l1->val = sum %10;
+            prev = l1;
+            l1 = l1->next;
+            l2 = l2->next;
+        }
+
+
+        while(l1!= NULL)
+        {
+            int sum = l1->val + add;
+            add = sum / 10;
+            l1->val =  sum %10;
+            prev = l1 ;
+            l1 = l1->next;
+        }
+
+        if(add != 0)
+        {
+           prev->next = new ListNode(add);
+        }
+
+        return res;
+
+    }
+
+
+    int len(ListNode* l)
+    {
+        int size = 0;
+        ListNode* p = l;
+        while(p != NULL)
+        {
+            p = p->next;
+            size++;
+        }
+        return size;
+
+    }
+
+
+};
diff --git a/Week_01/id_11/LeetCode3.cpp b/Week_01/id_11/LeetCode3.cpp
@@ -0,0 +1,23 @@
+class Solution {
+public:
+    int lengthOfLongestSubstring(string s) {
+
+    string result;
+
+    int max = 0;
+    for(int i = 0; i < s.size(); ++i)
+    {
+        char str = s.at(i);
+        int pos = result.find_first_of(str);
+        if(pos != string::npos)
+            result.erase(0,pos+1);
+        result.push_back(str);
+        if(result.size() > max)
+        {
+            max = result.size();
+        }
+      }
+
+      return max; 
+    }
+};
diff --git a/Week_01/id_11/NOTE.md b/Week_01/id_11/NOTE.md
@@ -1 +1,7 @@
-# 学习笔记
+# 学习笔记
+
+1.思考过程，直接暴力破解，写出，O(n2)的解决方法，外测循环都是不可省略的，但是我们可以优化内层循环，来提高算法执行效率
+2.内层循环中使用的是继续遍历剩余数组看是否有符合条件的元素，遍历的时间复杂度事O(n),我们可以根据优化索引的效率
+3.我们可以使用hash这种索引效率为O(1)的数据结构来提高算法效率，可以提前遍历一遍数组将数组元素放入到hash_map中，在查找时可以使用，hash根据值查找索引
+  这里的是一共遍历了两遍数组，有没有可能只遍历一遍，可以的
+4.直接将hash_map中的数组在查找循环中存入数据，这样就可以的。
diff --git a/Week_02/id_11/LeetCode_242_011.cpp b/Week_02/id_11/LeetCode_242_011.cpp
@@ -0,0 +1,61 @@
+#include <string>
+#include <unordered_map>
+using namespace std;
+class Solution {
+public:
+ bool isAnagram_1(string s, string t) {
+        unordered_map<char,int> maps;
+        for(int i = 0; i < s.size(); i++)
+        {
+            auto it =  maps.find (s[i]);
+            if(it == maps.end())
+            {
+                maps[s[i]] = 0;
+                continue;
+            }
+            maps[s[i]]++;
+        }
+
+
+        unordered_map<char,int> mapt;
+        for(int i = 0; i < t.size(); i++)
+        {
+            auto  it = mapt.find (t[i]);
+            if(it == mapt.end())
+            {
+                mapt[t[i]] = 0;
+                continue;
+            }
+            mapt[t[i]]++;
+        }
+
+
+        for(auto it =maps.begin(); it != maps.end();++it)
+        {
+            auto f = mapt.find(it->first);
+            if(f == mapt.end() || f->second != it->second)
+            {
+                return false;
+            }
+        }
+
+        return true;
+
+    }
+    bool isAnagram_2(string s, string t) {
+
+        int i, x[26] = {0},y[26] = {0};
+        for(i = 0; s[i]!='\0';i++) x[s[i] - 'a']++;
+        for(i = 0; t[i]!='\0';i++) y[t[i] - 'a']++;
+        for(i = 0; i < 26; i++)
+        {
+            if(x[i] != y[i])
+            {
+                return false;
+            }
+        }
+
+        return true;
+
+    }
+};
diff --git a/Week_02/id_11/LeetCode_692_011.cpp b/Week_02/id_11/LeetCode_692_011.cpp
@@ -0,0 +1,112 @@
+
+ //自定义排序方式，单词出现的次数由高到低排序
+struct intComp {
+	bool operator() (const pair<int, string>& lhs, const pair<int, string>& rhs) const{
+		return lhs.first > rhs.first;
+	}
+};
+class Solution {
+public:
+    vector<string> topKFrequent(vector<string>& words, int k) {
+        vector<string> resVec(k);//存储结果
+		map<string, int> hashMap;
+        //用于统计各个单词出现的次数，并按照字母顺序排序
+		for (auto word : words) {
+			hashMap[word] += 1;
+		}
+        //然后按照单词出现的次数进行排序
+		multiset<pair<int, string>, intComp> mySet;
+		for (auto &item : hashMap) {
+			mySet.insert({ item.second, item.first });
+		}
+        //取出前k个
+		multiset<pair<int, string>>::iterator it = mySet.begin();
+		for (int i = 0; i < k; ++i, ++it) {
+			resVec[i] = it->second;
+		}
+		return resVec;
+    }
+
+	vector<string> topKFrequent_1(vector<string>& words, int k) {
+
+        vector<string> resVec(k);
+
+            map<string,int> hashMap;
+
+            for(auto it = words.begin(); it != words.end(); it++)
+            {
+                hashMap[*it]++;
+            }
+
+            vector<pair<string,int>> pairVec;
+            for(auto it = hashMap.begin(); it != hashMap.end();it++)
+            {
+                pairVec.push_back(std::make_pair(it->first,it->second));
+            }
+
+            QuickSort(pairVec,k);
+            for(int i = 0; i < k; i++)
+            {
+                resVec[i] = pairVec[i].first;
+            }
+
+            return resVec;
+    }
+private:
+    void QuickSort(vector<pair<string,int> >& pairVec,int k)
+    {
+        QuickSort_C(pairVec,0,pairVec.size()-1,k);
+    }
+
+    void QuickSort_C(vector<pair<string,int> >& pairVec,int s,int t,int k)
+    {
+        if(s >= t)
+            {
+                return ;
+            }
+
+            int m = Parition(pairVec,s,t);
+
+            QuickSort_C(pairVec,s,m-1,k);
+
+            QuickSort_C(pairVec,m+1,t,k);
+
+
+    }
+
+    int Parition(vector<pair<string,int> >& pairVec,int s,int t)
+    {
+       int pivot = t;
+            int i = s;  // <
+            int j = s;
+
+            for(;j < t;j++)
+            {
+                pair<string,int> item = pairVec[j];
+                if(item.second > pairVec[pivot].second)
+                {
+                    Swap(pairVec,i,j);
+                    i++;
+                }else if((item.second == pairVec[pivot].second)
+                         && item.first <pairVec[pivot].first)
+                {
+                    Swap(pairVec,i,j);
+                    i++;
+                }
+
+
+            }
+            Swap(pairVec,i,pivot);
+            return i;
+    }
+
+    void Swap(vector<pair<string,int> >& pairVec,int i,int j)
+    {
+        pair<string,int> tmp = pairVec[i];
+        pairVec[i] = pairVec[j];
+        pairVec[j] = tmp;
+    }
+
+
+
+};