Merge pull request 6boris#92 from kylesliu/develop

6boris · web-flow · commit bc249bfdaab6 · 2019-10-21T21:34:21.000+08:00
add 187 solution
diff --git a/go.mod b/go.mod
@@ -1,3 +1,5 @@
 module github.com/kylesliu/awesome-golang-leetcode
 
 require github.com/emirpasic/gods v1.12.0 // indirect
+
+go 1.13
diff --git a/src/0187.Repeated-DNA-Sequences/README.md b/src/0187.Repeated-DNA-Sequences/README.md
@@ -0,0 +1,41 @@
+# [187. Repeated DNA Sequences][title]
+
+## Description
+
+All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
+
+Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
+**Example 1:**
+
+```
+Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
+
+Output: ["AAAAACCCCC", "CCCCCAAAAA"]
+```
+
+**Tags:** Math, String
+
+## 题意
+> 所有DNA序列都可以用 A，C，G，T 四个字母表示，比如 "ACGAATTCCG"，研究DNA序列时，有时识别重复子串是很有意义的。
+  
+  请编写一个程序，找到所有长度为10的且出现次数多于1的子串。
+
+## 题解
+
+### 思路1
+> 用哈希表记录所有长度是10的子串的个数。
+  从前往后扫描，当子串出现第二次时，将其记录在答案中。
+  
+  时间复杂度分析：总共约 nn 个长度是10的子串，所以总共有 10n10n 个字符。计算量与字符数量成正比，所以时间复杂度是 O(n)O(n)。
+
+```go
+
+```
+
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
+
+[title]: https://leetcode.com/problems/repeated-dna-sequences/
+[me]: https://github.com/kylesliu/awesome-golang-leetcode
diff --git a/src/0187.Repeated-DNA-Sequences/Solution.go b/src/0187.Repeated-DNA-Sequences/Solution.go
@@ -0,0 +1,18 @@
+package Solution
+
+func findRepeatedDnaSequences(s string) []string {
+	ans := make([]string, 0)
+	if len(s) < 10 {
+		return ans
+	}
+
+	cache := make(map[string]int)
+	for i := 0; i <= len(s)-10; i++ {
+		curr := s[i : i+10]
+		if cache[curr] == 1 {
+			ans = append(ans, curr)
+		}
+		cache[curr] += 1
+	}
+	return ans
+}
diff --git a/src/0187.Repeated-DNA-Sequences/Solution_test.go b/src/0187.Repeated-DNA-Sequences/Solution_test.go
@@ -0,0 +1,39 @@
+package Solution
+
+import (
+	"reflect"
+	"strconv"
+	"testing"
+)
+
+func TestSolution(t *testing.T) {
+	//	测试用例
+	cases := []struct {
+		name   string
+		inputs string
+		expect []string
+	}{
+		{"TestCase", "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", []string{"AAAAACCCCC", "CCCCCAAAAA"}},
+	}
+
+	//	开始测试
+	for i, c := range cases {
+		t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
+			got := findRepeatedDnaSequences(c.inputs)
+			if !reflect.DeepEqual(got, c.expect) {
+				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
+					c.expect, got, c.inputs)
+			}
+		})
+	}
+}
+
+//	压力测试
+func BenchmarkSolution(b *testing.B) {
+
+}
+
+//	使用案列
+func ExampleSolution() {
+
+}

-Original file line number
+Diff line change
@@ @@ -1,3 +1,5 @@ @@
 module github.com/kylesliu/awesome-golang-leetcode
 require github.com/emirpasic/gods v1.12.0 // indirect
++
 +go 1.13