algorithm007-class02 · melody-li · Mar 24, 2020 · Mar 15, 2020 · Mar 15, 2020 · Mar 22, 2020
diff --git a/Week_01/G20200343040334/project/one/main.go b/Week_01/G20200343040334/project/one/main.go
@@ -0,0 +1,84 @@
+package main
+
+import "fmt"
+
+// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
+// 26. 删除排序数组中的重复项
+//给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
+//
+// 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
+//
+//
+//
+// 示例 1:
+//
+// 给定数组 nums = [1,1,2],
+//
+//函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
+//
+//你不需要考虑数组中超出新长度后面的元素。
+//
+// 示例 2:
+//
+// 给定 nums = [0,0,1,1,1,2,2,3,3,4],
+//
+//函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
+//
+//你不需要考虑数组中超出新长度后面的元素。
+//
+//
+//
+//
+// 说明:
+//
+// 为什么返回数值是整数，但输出的答案是数组呢?
+//
+// 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
+//
+// 你可以想象内部操作如下:
+//
+// // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
+//int len = removeDuplicates(nums);
+//
+//// 在函数里修改输入数组对于调用者是可见的。
+//// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
+//for (int i = 0; i < len; i++) {
+//    print(nums[i]);
+//}
+//
+// Related Topics 数组 双指针
+
+
+func main() {
+	nums := []int{1,3,34,34,45,45,45}
+	removeDuplicates(nums)
+	removeDuplicates2(nums)
+}
+
+/**
+	left right指针作比较，将相等的移到右侧 d
+ */
+func removeDuplicates(nums []int) int {
+	left, right := 0, 1
+	for ; right < len(nums); right++ {
+		if nums[left] == nums[right] {
+			continue
+		}
+		left ++
+		nums[left] = nums[right]
+	}
+	return left+1
+}
+
+/**
+	数组覆盖值
+ */
+func removeDuplicates2(nums []int) int {
+	for i:=len(nums)-1; i>0; i-- {
+		if nums[i] == nums[i-1] {
+			nums = append(nums[:i], nums[i+1:]...)
+			fmt.Println(nums)
+		}
+	}
+	return len(nums)
+}
diff --git a/Week_01/G20200343040334/project/two/main.go b/Week_01/G20200343040334/project/two/main.go
@@ -0,0 +1,70 @@
+package main
+
+import "fmt"
+
+//给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
+//
+// 示例 1:
+//
+// 输入: [1,2,3,4,5,6,7] 和 k = 3
+//输出: [5,6,7,1,2,3,4]
+//解释:
+//向右旋转 1 步: [7,1,2,3,4,5,6]
+//向右旋转 2 步: [6,7,1,2,3,4,5]
+//向右旋转 3 步: [5,6,7,1,2,3,4]
+//
+//
+// 示例 2:
+//
+// 输入: [-1,-100,3,99] 和 k = 2
+//输出: [3,99,-1,-100]
+//解释:
+//向右旋转 1 步: [99,-1,-100,3]
+//向右旋转 2 步: [3,99,-1,-100]
+//
+// 说明:
+//
+//
+// 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
+// 要求使用空间复杂度为 O(1) 的 原地 算法。
+//
+// Related Topics 数组
+
+
+//leetcode submit region begin(Prohibit modification and deletion)
+/**
+	语法特性，
+ */
+func rotate(nums []int, k int)  {
+	k %= len(nums)
+	nums = append(nums[len(nums)-k:], nums[:len(nums)-k]...)
+	fmt.Println(nums)
+}
+
+/**
+	三层反转，前部分、后部分、全部
+ */
+func rotate2(nums []int, k int)  {
+	k %= len(nums)
+	reverse(nums[:len(nums)-k])
+	reverse(nums[len(nums)-k:])
+	reverse(nums)
+	fmt.Println(nums)
+}
+
+func reverse(nums []int) {
+	i,j := 0,len(nums)-1
+	for i < j{
+		nums[i], nums[j] = nums[j], nums[i]
+		i++
+		j--
+	}
+}
+//leetcode submit region end(Prohibit modification and deletion)
+
+func main() {
+	nums := []int{1,2,3,4,5,6,7}
+	rotate(nums, 5)
+	nums = []int{1,2,3,4,5,6,7}
+	rotate2(nums, 5)
+}
diff --git a/Week_02/G20200343040334/NOTE.md b/Week_02/G20200343040334/NOTE.md
@@ -1 +1,12 @@
-学习笔记
+### 学习笔记
+#### 栈
+`栈是一种特殊的线性表，具有和线性表的特点，同时也有特殊性：元素遵循“先进后出”的特点，也就是只能从栈顶插入或删除元素。同样可以用顺序存储和链式存储两种方式实现，分别称为顺序栈和链栈。栈结构可以用来实现表达式求值、括号匹配等。
+        栈的特点可以看成是一个桶，往桶里面装东西，取东西都是从上面进行的，最先放进去的要最后才能取出来`
+
+#### 队列
+`队列也是一种特殊的线性表，它的特殊性在于“先进先出”，如同现实生活中的排队问题：先来的人先服务完先走。不同于栈的地方在于队列一端用来插入新元素，一端用来删除元素，即有队首和队尾`
+
+
+
+#### hash
+`hash碰撞解决方式，拉链法 与开放定址法相比，拉链法有如下几个优点： ①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； ②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； ③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间； ④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。 （3）拉链法的缺点 　拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。`
diff --git a/Week_02/G20200343040334/project/test/1.两数之和/main.go b/Week_02/G20200343040334/project/test/1.两数之和/main.go
@@ -0,0 +1,38 @@
+package main
+
+import "fmt"
+
+/**
+//给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
+//
+// 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
+//
+// 示例:
+//
+// 给定 nums = [2, 7, 11, 15], target = 9
+//
+//因为 nums[0] + nums[1] = 2 + 7 = 9
+//所以返回 [0, 1]
+//
+// Related Topics 数组 哈希表
+
+
+*/
+func main() {
+	fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
+}
+
+func twoSum(nums []int, target int) []int {
+	var result []int
+	maps := map[int]int{}
+	for index, num := range nums {
+		if _, ok := maps[target - num]; ok{
+			result = append(result, index, maps[target - num])
+			return result
+		}
+		maps[num] = index
+	}
+	return result
+}
+
+
diff --git a/Week_02/G20200343040334/project/test/1.两数之和/note.md b/Week_02/G20200343040334/project/test/1.两数之和/note.md
@@ -0,0 +1,19 @@
+//给定一个整数数组 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)
+func twoSum(nums []int, target int) []int {
+
+}
+//leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week_02/G20200343040334/project/test/15.三数之和/15. 三数之和.md b/Week_02/G20200343040334/project/test/15.三数之和/15. 三数之和.md
@@ -0,0 +1,16 @@
+15. 三数之和
+给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
+
+注意：答案中不可以包含重复的三元组。
+
+
+
+示例：
+
+给定数组 nums = [-1, 0, 1, 2, -1, -4]，
+
+满足要求的三元组集合为：
+[
+  [-1, 0, 1],
+  [-1, -1, 2]
+]
diff --git a/Week_02/G20200343040334/project/test/15.三数之和/main.go b/Week_02/G20200343040334/project/test/15.三数之和/main.go
@@ -0,0 +1,62 @@
+package main
+
+import "fmt"
+
+func main() {
+	fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))
+}
+
+func threeSum(nums []int) [][]int {
+	if len(nums) < 3 { return [][]int{} }
+
+	QuickSort(nums) // 快排 O(n log n), 本地修改
+
+	ret := make([][]int, 0, 0)
+	for i := 0; i < len(nums) - 1; i++ {
+		l, r := i + 1, len(nums) - 1
+
+		if nums[i] > 0 || nums[i] + nums[l] > 0 { break }	// 优化掉不可能的情况
+
+		if i > 0 && nums[i] == nums[i-1] { continue }	// i 去重
+
+		for l < r {
+			if l > i + 1 && nums[l] == nums[l-1] {	// l 去重
+				l++; continue
+			}
+			if r < len(nums) - 2 && nums[r] == nums[r+1] {	// r 去重
+				r--; continue
+			}
+
+			if nums[i] + nums[l] + nums[r] > 0 {	//
+				r--
+			} else if nums[i] + nums[l] + nums[r] < 0 {
+				l++
+			} else {
+				ret = append(ret, []int{nums[i], nums[l], nums[r]})
+				l++; r--
+			}
+		}
+	}
+
+	return ret
+}
+
+func QuickSort(array []int) {
+	if len(array) < 2 { return }
+
+	pivot := array[0]
+	l, r := 0, len(array) - 1
+
+	for i := 1; i <= r; {
+		if array[i] < pivot { //
+			array[l], array[i] = array[i], array[l]
+			l++; i++
+		} else {
+			array[r], array[i] = array[i], array[r]
+			r--
+		}
+	}
+
+	QuickSort(array[:l])
+	QuickSort(array[l + 1:])
+}
diff --git a/Week_02/G20200343040334/project/test/20. 有效的括号/20. 有效的括号.md b/Week_02/G20200343040334/project/test/20. 有效的括号/20. 有效的括号.md
@@ -0,0 +1,30 @@
+20. 有效的括号
+
+给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
+
+有效字符串需满足：
+
+左括号必须用相同类型的右括号闭合。
+左括号必须以正确的顺序闭合。
+注意空字符串可被认为是有效字符串。
+
+示例 1:
+
+输入: "()"
+输出: true
+示例 2:
+
+输入: "()[]{}"
+输出: true
+示例 3:
+
+输入: "(]"
+输出: false
+示例 4:
+
+输入: "([)]"
+输出: false
+示例 5:
+
+输入: "{[]}"
+输出: true
diff --git a/Week_02/G20200343040334/project/test/20. 有效的括号/main.go b/Week_02/G20200343040334/project/test/20. 有效的括号/main.go
@@ -0,0 +1,30 @@
+package main
+
+import "fmt"
+
+func main() {
+	//s:= "({((())))"
+	s:= "(((())))"
+	isValid := isValid(s)
+	fmt.Println(isValid)
+}
+// 解题思路：
+// 定义map dict := map[byte]byte{'(':')','{':'}','[':']'}
+// 定义stack数组
+// 循环遍历
+// if stack为空则判断最后的元素和当前字符在map中是否存在  如果存在则出栈，不存在则继续入栈
+func isValid(s string) bool {
+	dict := map[byte]byte{'(':')','{':'}','[':']'}
+	var stack []byte
+	for _,v := range s{
+		if len(stack) > 0{
+			if byte(v) == dict[stack[len(stack)-1]]{
+				stack = stack[:len(stack)-1]
+				continue
+			}
+		}
+		stack = append(stack, byte(v))
+		fmt.Println(stack)
+	}
+	return len(stack)<1
+}