8000 Merge pull request #659 from AHaoPang/master · algorithm001/algorithm@cff94bb · GitHub
[go: up one dir, main page]
Skip to content

Commit cff94bb

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request #659 from AHaoPang/master
009-庞雁豪-第四周作业
2 parents dc3d90b + 073cea4 commit cff94bb

File tree

3 files changed

+233
-1
lines changed

3 files changed

+233
-1
lines changed

‎Week_04/id_9/LeetCode_211_9.cs‎

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace ProblemSolutions
8+
{
9+
public class Problem211 : IProblem
10+
{
11+
public void RunProblem()
12+
{
13+
WordDictionary obj = new WordDictionary();
14+
obj.AddWord("bad");
15+
obj.AddWord("dad");
16+
obj.AddWord("mad");
17+
bool param_2 = obj.Search("pad");
18+
param_2 = obj.Search("bad");
19+
param_2 = obj.Search(".ad");
20+
param_2 = obj.Search("b..");
21+
param_2 = obj.Search("b.d");
22+
}
23+
24+
public class WordDictionary
25+
{
26+
public class TrieNode
27+
{
28+
public TrieNode(char c)
29+
{
30+
m_char = c;
31+
}
32+
public char m_char;
33+
public bool m_isWord;
34+
public TrieNode[] m_nextNode = new TrieNode[26];
35+
}
36+
37+
private TrieNode rootNode = new TrieNode('\\');
38+
39+
/** Initialize your data structure here. */
40+
public WordDictionary()
41+
{
42+
43+
}
44+
45+
/** Adds a word into the data structure. */
46+
public void AddWord(string word)
47+
{
48+
var nodeTemp = rootNode;
49+
foreach (var wordItem in word)
50+
{
51+
var charIndex = wordItem - 'a';
52+
if (nodeTemp.m_nextNode[charIndex] == null)
53+
nodeTemp.m_nextNode[charIndex] = new TrieNode(wordItem);
54+
55+
nodeTemp = nodeTemp.m_nextNode[charIndex];
56+
}
57+
nodeTemp.m_isWord = true;
58+
}
59+
60+
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
61+
public bool Search(string word)
62+
{
63+
return RecurSive(rootNode, word, -1);
64+
}
65+
66+
private bool RecurSive(TrieNode node, string word, int charIndex)
67+
{
68+
//查看当前节点满足的条件
69+
if (charIndex > word.Length - 1) return false;
70+
if (charIndex == word.Length - 1) return node.m_isWord && (node.m_char == word[charIndex] || word[charIndex] == '.');
71+
72+
//查看下一个节点满足的条件
73+
var curChar = word[charIndex + 1];
74+
if (curChar == '.')
75+
{
76+
foreach (var nodeItem in node.m_nextNode)
77+
{
78+
var isOk = false;
79+
if (nodeItem != null)
80+
isOk = RecurSive(nodeItem, word, charIndex + 1);
81+
82+
if (isOk) return true;
83+
}
84+
}
85+
else
86+
{
87+
var cIndex = curChar - 'a';
88+
if (node.m_nextNode[cIndex] != null)
89+
return RecurSive(node.m_nextNode[cIndex], word, charIndex + 1);
90+
}
91+
92+
return false;
93+
}
94+
}
95+
96+
/**
97+
* Your WordDictionary object will be instantiated and called as such:
98+
* WordDictionary obj = new WordDictionary();
99+
* obj.AddWord(word);
100+
* bool param_2 = obj.Search(word);
101+
*/
102+
}
103+
}

‎Week_04/id_9/LeetCode_720_9.cs‎

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace ProblemSolutions
8+
{
9+
public class Problem720 : IProblem
10+
{
11+
public void RunProblem()
12+
{
13+
string[] words = new string[] { "a", "apple", "b", "be", "bee", "beer" };
14+
var temp = LongestWord(words);
15+
}
16+
17+
public string LongestWord(string[] words)
18+
{
19+
/*
20+
* 实现思路：
21+
* 1.使用数据源来“喂养”TrieTree
22+
* 2.再让TrieTree告知我们，满足题目需求的结果
23+
*
24+
* 时间复杂度：输入的单词，是要遍历一次的，构建trieTree，然后要拿到结果，还是要做回溯的，那么是对树所有节点又遍历一次
25+
* 空间复杂度：主要是TrieTree占用的存储空间
26+
*
27+
* 使用此种方式，其实就是数据源越大越是有利
28+
*/
29+
30+
var trieTree = new TrieTree();
31+
32+
foreach (var wordItem in words)
33+
trieTree.AddWord(wordItem);
34+
35+
return trieTree.GetLongestWord();
36+
}
37+
38+
public class TrieTree
39+
{
40+
public class TrieNode
41+
{
42+
public string m_words;
43+
public TrieNode[] m_nextIndex = new TrieNode[26];
44+
public bool m_isWord;
45+
}
46+
47+
private TrieNode m_rootNode = new TrieNode();
48+
49+
public void AddWord(string word)
50+
{
51+
var trieNodeTemp = m_rootNode;
52+
foreach (var wordItem in word)
53+
{
54+
var intTemp = wordItem - 'a';
55+
56+
if (trieNodeTemp.m_nextIndex[intTemp] == null)
57+
trieNodeTemp.m_nextIndex[intTemp] = new TrieNode();
58+
59+
trieNodeTemp = trieNodeTemp.m_nextIndex[intTemp];
60+
}
61+
trieNodeTemp.m_isWord = true;
62+
trieNodeTemp.m_words = word;
63+
}
64+
65+
public string GetLongestWord()
66+
{
67+
Recursive(m_rootNode, -1);
68+
return longestWord;
69+
}
70+
71+
private int longest = 0;
72+
private string longestWord = "";
73+
private void Recursive(TrieNode node, int length)
74+
{
75+
length++;
76+
77+
if (node.m_isWord && length > longest)
78+
{
79+
longest = length;
80+
longestWord = node.m_words;
81+
}
82+
83+
for (int i = 0; i < node.m_nextIndex.Length; i++)
84+
{
85+
if (node.m_nextIndex[i] != null && node.m_nextIndex[i].m_isWord)
86+
{
87+
Recursive(node.m_nextIndex[i], length);
88+
}
89+
}
90+
}
91+
}
92+
93+
public string LongestWord1(string[] words)
94+
{
95+
/*
96+
* 思路：
97+
* 1.结果要求按照字典序来处理相同长度的单词，那么就先对数组做字典序排序，复杂度：O(nlogn);
98+
* 2.遍历新的数组，寻找满足条件的最长单词
99+
*
100+
* 时间复杂度：O(nlogn + n)，但是还要考虑到字符串比较的复杂度才行，字符串比较，应该是使用简单的比较方法才对
101+
* 空间复杂度：O(n)，因为会把所有的单词存入到set中去
102+
*/
103+
104+
var forReturn = "";
105+
HashSet<string> sets = new HashSet<string>();
106+
107+
var sortedArray = words.OrderBy(i => i);
108+
109+
foreach (var arrayItem in sortedArray)
110+
{
111+
if (arrayItem.Length == 1 || sets.Contains(arrayItem.Substring(0, arrayItem.Length - 1)))
112+
{
113+
if (forReturn.Length < arrayItem.Length)
114+
forReturn = arrayItem;
115+
116+
sets.Add(arrayItem);
117+
}
118+
}
119+
120+
return forReturn;
121+
}
122+
}
123+
}

‎Week_04/id_9/NOTE.md‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,7 @@
1-
# 学习笔记
1+
# 学习笔记
2+
1. 本次主要是练习TrieTree相关的题目，一个简单的一个中等的；
3+
2. 两个题，其实都用到的是：TrieTree的构建+回溯法
4+
3. 当需要尝试各种可能性时，使用回溯法是很不错的；
5+
4. 第1题，要找出满足条件的最长字符串，不遍历一遍TrieTree，是不会知道最长的字符串的
6+
5. 第2题，相当于做的是模糊匹配，有多种可能的匹配方式，只要一种匹配尝试成功了就是成功
7+
6. TrieTree是很实用的，构建也是相当简单的，单个的Trie节点，可以携带业务信息来加速查找，比如“是否是单词”，“当前字符是什么”，“若是一个单词，那么这个单词是什么”

0 commit comments

Comments
 (0)
0