week2作业提交

Jewons · Jewons · commit 7df719022144 · 2020-06-21T23:35:45.000+08:00
diff --git a/Week02/NOTE.md b/Week02/NOTE.md
@@ -1 +1,9 @@
-学习笔记
+学习笔记
+
+1.熟记二叉树遍历模板，并使用（前中后序，bfs dfs）
+2.二叉树的遍历一般用递归来实现即可，如果一定要用迭代来实现，那么可以考虑引用一个栈，将未遍历的节点存入栈中这种方式来实现。
+3.大顶堆：根节点大于所有子节点。
+  小顶堆：根节点小于所有子节点。
+4.对于堆的使用：可以利用堆来找出 第K个最大/最小的值。
+5.堆是一种比较抽象的数据结构，二叉堆不代表堆，只是堆的一种。
+6.二叉堆是堆中实现起来较为简单的一种堆。
diff --git a/Week02/binary-tree-preorder-traversal.cpp b/Week02/binary-tree-preorder-traversal.cpp
@@ -0,0 +1,49 @@
+ //递归
+class Solution {
+public:
+    void preOrder(TreeNode* root,std::vector<int> &result)
+    {
+        if(root == nullptr)
+            return;
+        result.push_back(root->val);
+        preOrder(root->left,result);
+        preOrder(root->right,result);
+    }
+    vector<int> preorderTraversal(TreeNode* root) {
+        std::vector<int> result;
+
+        preOrder(root,result);
+
+        return result;
+    }
+};
+//迭代 
+class Solution {
+public:
+    vector<int> preorderTraversal(TreeNode* root) {
+        std::vector<int> result;
+        std::stack<TreeNode*> st;
+
+        TreeNode* node = root;
+        while(1)
+        {
+            if(node != nullptr)
+            {
+                result.push_back(node->val);
+                if(node->right != nullptr)
+                    st.push(node->right);
+                node = node->left;
+            }
+            else if(st.empty())
+            {
+                break;
+            }
+            else
+            {
+                node = st.top();
+                st.pop();
+            }
+        }
+        return result;
+    }
+};
diff --git a/Week02/valid-anagram.cpp b/Week02/valid-anagram.cpp
@@ -0,0 +1,55 @@
+//利用map来实现，很耗时
+class Solution {
+public:
+    bool isAnagram(string s, string t) {
+        if(s.length() != t.length())
+            return false;
+
+        std::map<char,int> statisticMap1;
+        statisticMap1.clear();
+        for(int i = 0; i < s.length(); i++)
+        {
+            if(statisticMap1.find(s[i]) == statisticMap1.end())
+                statisticMap1[s[i]] = 1;
+            else
+                statisticMap1[s[i]]++;
+        }
+       // std::map<char,int> statisticMap2;
+       // statisticMap2.clear();
+        for(int i = 0; i < t.length(); i++)
+        {
+            if(statisticMap1.find(t[i]) == statisticMap1.end())
+                statisticMap1[t[i]] = 1;
+            else
+                statisticMap1[t[i]]--;
+        }
+        std::map<char,int>::iterator iter = statisticMap1.begin();
+        for(;iter != statisticMap1.end();++iter)
+        {
+            if(iter->second != 0)
+                return false;
+        }
+        return true;
+    }
+};
+//用数组实现的hash，效率要比上一个快
+class Solution {
+public:
+    bool isAnagram(string s, string t) {
+        if(s.length() != t.length())
+            return false;
+
+        int hash[26] = {0};
+
+        for(char n : s)
+            hash[n - 'a']++;
+        for(char n : t)
+            hash[n - 'a']--;
+        for(int n : hash)
+        {
+            if(n != 0)
+                return false;
+        }
+        return true;
+    }
+};
