Merge pull request algorithm001#683 from v1xingyue/master

GeekUniversity · web-flow · commit 296e400ac29f · 2019-05-13T17:23:58.000+08:00
007-Week4 作业
diff --git a/Week_04/id_7/LeetCode_146_7.go b/Week_04/id_7/LeetCode_146_7.go
@@ -0,0 +1,68 @@
+package geekcode
+
+import (
+	"container/list"
+)
+
+type CacheItem struct {
+	key   int
+	value interface{}
+}
+
+type LRUCache struct {
+	dlist    *list.List
+	mapItems map[int]*list.Element
+	capacity int
+}
+
+func Constructor(max int) LRUCache {
+	l := LRUCache{}
+	l.capacity = max
+	l.Init()
+	return l
+}
+
+func (self *LRUCache) Init() {
+	self.dlist = new(list.List)
+	self.mapItems = make(map[int]*list.Element)
+}
+
+// 插入新数据的时候，对列表的操作需要注意:
+// 如果插入后，列表将满，那么先删除元素，再做插入
+func (self *LRUCache) Put(key int, value interface{}) {
+	if v, ok := self.mapItems[key]; ok && v != nil {
+		v.Value.(*CacheItem).value = value
+		self.dlist.MoveToFront(v)
+	} else {
+		i := &CacheItem{key: key, value: value}
+		self.mapItems[key] = self.dlist.PushFront(i)
+		self.Reduce()
+	}
+}
+
+func (self *LRUCache) Len() int {
+	return self.dlist.Len()
+}
+
+//获取数据以后，
+//数据移动顺序和插入，更新数据时候移动的方向是一致的
+func (self *LRUCache) Get(key int) interface{} {
+	n := self.mapItems[key]
+	if n != nil {
+		self.dlist.MoveToFront(n)
+		return n.Value.(*CacheItem).value
+	} else {
+		return -1
+	}
+}
+
+func (self *LRUCache) Reduce() {
+	if self.Len() > self.capacity {
+		n := self.dlist.Back()
+		if n != nil {
+			mapKey := n.Value.(*CacheItem).key
+			delete(self.mapItems, mapKey)
+			self.dlist.Remove(n)
+		}
+	}
+}
diff --git a/Week_04/id_7/LeetCode_720_7.go b/Week_04/id_7/LeetCode_720_7.go
@@ -0,0 +1,96 @@
+package geekcode
+
+// 存储节点数据
+// 省去一个isend , 用word == "" 来代替
+// 添加parent 指针，用来做返回判断
+type tries_node struct {
+	children map[byte]*tries_node
+	word     string      // 标记当前节点表示单词
+	parent   *tries_node // 标记父节点，省去遍历的麻烦
+}
+
+//往tries 树中添加一个单词
+func (self *tries_node) addString(word string) *tries_node {
+	last := self
+	for _, b := range word {
+		_b := byte(b)
+		if last.children == nil {
+			last.children = make(map[byte]*tries_node)
+		}
+
+		var n *tries_node
+		var ok bool
+
+		if n, ok = last.children[_b]; ok == false {
+			n = &tries_node{children: nil, word: "", parent: last}
+			last.children[_b] = n
+		}
+		last = n
+	}
+	last.word = word
+	return last
+}
+
+// 当前的单词，是否可以由其他的单词添加字符组成，
+// 从跟节点到当前节点走过的所有节点，必须world 不为空
+func (self *tries_node) isPathAllWord() (bool, int) {
+	len := 0
+	p := self
+	for p.parent != nil {
+		if p.word == "" {
+			return false, 0
+		}
+		len += 1
+		p = p.parent
+	}
+	return true, len
+}
+
+// 判断 a,b 的字典顺序，是否是 a > b
+// 前提 a,b 的长度相等
+func isab(a, b string) bool {
+	l := len(a)
+	for i := 0; i < l; i++ {
+		if byte(a[i]) > byte(b[i]) {
+			return true
+		}
+		if byte(a[i]) < byte(b[i]) {
+			return false
+		}
+	}
+	return false
+}
+
+//使用字典创建tries 树，获取深度最长的叶子节点
+func longestWord(words []string) string {
+	var word_nodes = make([]*tries_node, 0)
+	root_tree := new(tries_node)
+	root_tree.word = "-"
+	// 每个单词添加到tries 树中
+	for _, v := range words {
+		l := root_tree.addString(v)
+		word_nodes = append(word_nodes, l)
+	}
+
+	maxl := 0
+	var maxnode *tries_node
+	for _, w := range word_nodes {
+		//fmt.Println(w.word)
+		ok, l := w.isPathAllWord()
+		if ok {
+			if maxl < l {
+				maxl = l
+				maxnode = w
+				continue
+			}
+			if maxl == l {
+				//fmt.Println(maxnode.word, w.word)
+				if isab(maxnode.word, w.word) == true {
+					maxnode = w
+				}
+			}
+		}
+	}
+
+	return maxnode.word
+}
diff --git a/Week_04/id_7/LeetCode_784_7.go b/Week_04/id_7/LeetCode_784_7.go
@@ -0,0 +1,25 @@
+package geekcode
+
+// 784. 字母大小写全排列
+func letterCasePermutation(S string) []string {
+	l := len(S)
+	prefix := []string{""}
+	for i := 0; i < l; i++ {
+		n := make([]string, 0)
+		c := S[i]
+		for _, s := range prefix {
+			n = append(n, s+string(c))
+			// A ~ Z
+			if byte(c) >= 65 && byte(c) <= 90 {
+				n = append(n, s+string(c+32))
+			}
+			// a ~ z
+			if byte(c) >= 97 && byte(c) <= 122 {
+				n = append(n, s+string(c-32))
+			}
+		}
+
+		prefix = n
+	}
+	return prefix
+}
diff --git a/Week_04/id_7/NOTE.md b/Week_04/id_7/NOTE.md
@@ -1 +1,10 @@
-# 学习笔记
+# 学习笔记
+
+* [LRU缓存机制](https://leetcode-cn.com/problems/lru-cache/) 
+  [LeetCode_146_7.go](LeetCode_146_7.go)
+
+* [词典中最长的单词](https://leetcode-cn.com/problems/longest-word-in-dictionary/) 
+  [LeetCode_720_7.go](LeetCode_720_7.go)
+
+* [字母大小写全排列](https://leetcode-cn.com/problems/letter-case-permutation/submissions/) 
+  [LeetCode_784_7.go](LeetCode_784_7.go)
diff --git a/Week_04/id_7/geek_test.go b/Week_04/id_7/geek_test.go
@@ -0,0 +1,11 @@
+package geekcode
+
+import (
+	"testing"
+)
+
+func TestLongestWord(t *testing.T) {
+
+	words := []string{"t", "ti", "tig", "tige", "tiger", "e", "en", "eng", "engl", "engli", "englis", "english", "h", "hi", "his", "hist", "histo", "histor", "history"}
+	t.Log(longestWord(words))
+}
diff --git a/Week_04/id_7/lru_test.go b/Week_04/id_7/lru_test.go
@@ -0,0 +1,18 @@
+package geekcode
+
+import (
+	"testing"
+)
+
+func TestLRU(t *testing.T) {
+	cache := Constructor(2)
+	cache.Put(1, 1)
+	cache.Put(2, 2)
+	t.Log(cache.Get(1), " should be 1 ")
+	cache.Put(3, 3)
+	t.Log(cache.Get(2), " should be -1 ")
+	cache.Put(4, 4)
+	t.Log(cache.Get(1), " should be -1 ")
+	t.Log(cache.Get(3), " should be 3")
+	t.Log(cache.Get(4), " should be 4")
+}
diff --git a/Week_04/id_7/readme.md b/Week_04/id_7/readme.md
@@ -0,0 +1,10 @@
+# 学习笔记
+
+* [LRU缓存机制](https://leetcode-cn.com/problems/lru-cache/) 
+  [LeetCode_146_7.go](LeetCode_146_7.go)
+
+* [词典中最长的单词](https://leetcode-cn.com/problems/longest-word-in-dictionary/) 
+  [LeetCode_720_7.go](LeetCode_720_7.go)
+
+* [字母大小写全排列](https://leetcode-cn.com/problems/letter-case-permutation/submissions/) 
+  [LeetCode_784_7.go](LeetCode_784_7.go)
