week02_homework

xkluan · xkluan · commit 6df7198f9ab3 · 2020-06-21T23:33:56.000+08:00
diff --git a/Week02/1-两数之和.py b/Week02/1-两数之和.py
@@ -0,0 +1,25 @@
+# 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
+#
+#  你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
+#
+#
+#
+#  示例:
+#
+#  给定 nums = [2, 7, 11, 15], target = 9
+#
+# 因为 nums[0] + nums[1] = 2 + 7 = 9
+# 所以返回 [0, 1]
+#
+#  Related Topics 数组 哈希表
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def twoSum(self, nums: List[int], target: int) -> List[int]:
+        dic = {}
+        for k,v in enumerate(nums):
+            if target - v in dic:
+                return [dic[target-v], k]
+            dic[v] = k
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week02/NOTE.md b/Week02/NOTE.md
@@ -1 +1,19 @@
-学习笔记
+# 学习笔记
+## 哈希表
+### 概念
+#### 根据关键码值(Key value)而直接进行访问的数据结构。
+#### 通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
+### 哈希碰撞
+#### 不同的输入得到了同一个哈希值，就会发生"哈希碰撞"
+## 树、二叉树、搜索树
+### 概念
+#### 二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点
+####  Linked List 是特殊化的 Tree Tree 是特殊化的 Graph
+###  二叉树遍历 Pre-order/In-order/Post-order
+#### 1.前序(Pre-order):根-左-右 2.中序(In-order):左-根-右 3.后序(Post-order):左-右-根
+## 堆、二叉堆
+### 堆的概念
+#### 可以迅速找到一堆数中最大值或者最小值的结构
+### 二叉堆性质
+#### 通过完全二叉树来实现：
+#### 是一棵完全树；树中任一节点的值总是>=其子节点的值。
diff --git a/Week02/N叉树的前序遍历.py b/Week02/N叉树的前序遍历.py
@@ -0,0 +1,42 @@
+# 给定一个 N 叉树，返回其节点值的前序遍历。
+#
+#  例如，给定一个 3叉树 :
+#
+#
+#
+#
+#
+#
+#
+#  返回其前序遍历: [1,3,5,6,2,4]。
+#
+#
+#
+#  说明: 递归法很简单，你可以使用迭代法完成此题吗? Related Topics 树
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+"""
+# Definition for a Node.
+class Node:
+    def __init__(self, val=None, children=None):
+        self.val = val
+        self.children = children
+"""
+
+
+class Solution:
+    def preorder(self, root: 'Node') -> List[int]:
+        if root is None:
+            return []
+        stack = [root]  # 初始化一个数据
+        out = []
+        while stack:
+            temp = stack.pop()  # 先把栈顶的数据弹出来加入到 输出 集
+            out.append(temp.val)
+            if temp.children:  # 如果该元素有子节点children 则反转加入到 stack 里(因为是前序遍历)
+                for item in temp.children[::-1]:
+                    stack.append(item)
+        return out
+
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week02/字母易位词分组.py b/Week02/字母易位词分组.py
@@ -0,0 +1,31 @@
+# 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
+#
+#  示例:
+#
+#  输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
+# 输出:
+# [
+#   ["ate","eat","tea"],
+#   ["nat","tan"],
+#   ["bat"]
+# ]
+#
+#  说明：
+#
+#
+#  所有输入均为小写字母。
+#  不考虑答案输出的顺序。
+#
+#  Related Topics 哈希表 字符串
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+class Solution:
+    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
+        dict = {}
+        for item in strs:
+            key = tuple(sorted(item))
+            dict[key] = dict.get(key, []) + [item]
+        return list(dict.values())
+
+# leetcode submit region end(Prohibit modification and deletion)
