Merge pull request algorithm001#712 from zhaowende/master

GeekUniversity · web-flow · commit bdfbe9ff5850 · 2019-05-13T17:19:56.000+08:00
123号学员 第四周作业
diff --git a/Week_04/id_123/LeetCode_455_123.go b/Week_04/id_123/LeetCode_455_123.go
@@ -0,0 +1,24 @@
+package id_123
+
+import (
+	"sort"
+)
+
+func findContentChildren(g []int, s []int) int {
+	count := 0
+
+	sort.Ints(g)
+	sort.Ints(s)
+
+	for _, needSize := range g {
+		for index, actualSize := range s {
+			if needSize <= actualSize {
+				count += 1
+				s = s[index+1:]
+				break
+			}
+		}
+	}
+
+	return count
+}
diff --git a/Week_04/id_123/LeetCode_455_123_test.go b/Week_04/id_123/LeetCode_455_123_test.go
diff --git a/Week_04/id_123/LeetCode_720_123.go b/Week_04/id_123/LeetCode_720_123.go
@@ -0,0 +1,46 @@
+package id_123
+
+type TrieNode struct {
+	data         byte
+	children     [26]*TrieNode
+	isEndingChar bool
+}
+
+// 往 Trie 树中插入一个字符串
+func insert(root *TrieNode, text string) {
+	p := root
+	for i := 0; i < len(text); i++ {
+		index := text[i] - 'a'
+		if p.children[index] == nil {
+			newNode := &TrieNode{data: text[i]}
+			p.children[index] = newNode
+		}
+		p = p.children[index]
+	}
+	p.isEndingChar = true
+}
+
+func longestWord(words []string) string {
+	root := &TrieNode{}
+	for _, word := range words {
+		insert(root, word)
+	}
+
+	finalResult := ""
+	tempStr := ""
+	findLongestWord(root, &tempStr, &finalResult)
+	return finalResult
+}
+
+func findLongestWord(root *TrieNode, resWord *string, finalResult *string) {
+	for i := 0; i < 26; i++ {
+		if root.children[i] != nil && root.children[i].isEndingChar {
+			newStr := *resWord + string(root.children[i].data)
+			if len(newStr) > len(*finalResult) {
+				*finalResult = newStr
+			}
+
+			findLongestWord(root.children[i], &newStr, finalResult)
+		}
+	}
+}
diff --git a/Week_04/id_123/LeetCode_720_123_test.go b/Week_04/id_123/LeetCode_720_123_test.go
@@ -0,0 +1,36 @@
+package id_123
+
+import "testing"
+
+func Test_longestWord(t *testing.T) {
+	type args struct {
+		words []string
+	}
+	tests := []struct {
+		name string
+		args args
+		want string
+	}{
+		{
+			name: "test1",
+			args: args{
+				words: []string{"w", "wo", "wor", "worl", "world"},
+			},
+			want: "world",
+		},
+		{
+			name: "test2",
+			args: args{
+				words: []string{"b", "bo", "boy", "w", "wo", "wor", "worl", "world"},
+			},
+			want: "world",
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			if got := longestWord(tt.args.words); got != tt.want {
+				t.Errorf("longestWord() = %v, want %v", got, tt.want)
+			}
+		})
+	}
+}
