LeetCode 676. Implement Magic Dictionary 实现一个魔法字典 (C++/Java)

25-02-20 13

对于想了解LeetCode676.ImplementMagicDictionary实现一个魔法字典(C++/Java)的读者，本文将提供新的信息，并且为您提供关于(OK)Research,implem

对于想了解LeetCode 676. Implement Magic Dictionary 实现一个魔法字典 (C++/Java)的读者，本文将提供新的信息，并且为您提供关于(OK) Research, implementation, and improvement of MPTCP on mobile smart devices、676. 实现一个魔法字典 : 结合 DFS 的 Trie 运用题、C#中字典集合HashTable、Dictionary、ConcurrentDictionary三者区别、Database Systems--- A practical Approach to Design, Implementation, and Management Fifth Edtion的有价值信息。

本文目录一览：

LeetCode 676. Implement Magic Dictionary 实现一个魔法字典 (C++/Java)
(OK) Research, implementation, and improvement of MPTCP on mobile smart devices
676. 实现一个魔法字典 : 结合 DFS 的 Trie 运用题
C#中字典集合HashTable、Dictionary、ConcurrentDictionary三者区别
Database Systems--- A practical Approach to Design, Implementation, and Management Fifth Edtion

LeetCode 676. Implement Magic Dictionary 实现一个魔法字典 (C++/Java)

题目：

Implement a magic directory with buildDict, and search methods.

For the method buildDict, you''ll be given a list of non-repetitive words to build a dictionary.

For the method search, you''ll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Example 1:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

Note:

You may assume that all the inputs are consist of lowercase letters a-z.
For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.

分析：

实现一个带有 buildDict, 以及 search 方法的魔法字典。

对于 buildDict 方法，你将被给定一串不重复的单词来构建一个字典。

对于 search 方法，你将被给定一个单词，并且判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

最先想到的是将每一个单词的每一个字母用另外的 25 个字母来替换，并放进 set 中，最后再在 set 中查询单词便可。

我们来看另一个有趣的解法。

对于一个单词，我们可以将每个字母用 * 号来代替存进 map 中，其对应的值则是替换的字母的集合，例如 hello 在 map 中存有：

*ello -> {h}

h*llo -> {e}

he*lo -> {l}

hel*o -> {l}

hell* -> {o}

当我们查询一个单词是否在魔法字典中，也将单词的每个字母用 * 号来替换，如果 map 中存在，且替换的字母不在对应 set 中，意味着能够查询到。

例：查询 pello 是否在字典中，先替换为 (*ello，p)，字典中有 * ello，且 p 不在 {h} 中，我们应该返回 true。

查询 hello 是否在字典中，先替换为 (*ello，h)，字典中有 * ello，且 h 在 {h} 中，应该返回 false。

如果我们将 hello，pello 存进字典中，再查询 pello 会是什么情况呢？

此时的字典中 * ello->{h，p}，若此时查询 pello，因为 p 在 {h，p} 中，会返回 false，可实际上应该要返回 true 的，所以我们还要加一个条件，就是或者当 set 中的元素大于一个的时候，意味着，*ello 中的 * 可以替换为 26 个字母中的任意一个了，因为原来的 hello 无法通过修改一个字母来对应到 hello，但有了 pello 的加入，hello 可以通过替换第一个字母来对应到 pello 上。

此题还可以通过字典树来实现 (后续补充)。

程序：

C++

class MagicDictionary {
public:
    /** Initialize your data structure here. */
    MagicDictionary() {
       mydict.clear(); 
    }
    
    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for(string word:dict){
            for(int i = 0; i < word.length(); ++i){
                char c = word[i];
                word[i] = ''*'';
                mydict[word].insert(c);
                word[i] = c;
            }
        }
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {
        for(int i = 0; i < word.length(); ++i){
            char c = word[i];
            word[i] = ''*'';
            if(mydict.count(word)){
                if (!mydict[word].count(c) || mydict[word].size() > 1)
                    return true;
            }
            word[i] = c;
        }
        return false;
    }
private:
    unordered_map<string, unordered_set<char>> mydict;
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dict);
 * bool param_2 = obj->search(word);
 */

Java

(OK) Research, implementation, and improvement of MPTCP on mobile smart devices

download the paper: https://www.tandfonline.com/eprint/Ka6GNdE6zu9iwCvSSTu9/full

https://www.tandfonline.com/doi/full/10.1080/1206212X.2018.1455020

https://pan.baidu.com/s/1Ny3z-0_fD2eAuUjhd3Yikw

Abstract

As more and more mobile smart devices (MSDs) are equipped with multiple wireless network interfaces (e.g. WiFi, cellular, etc.), MultiPath TCP (MPTCP) can enable MSDs to send data over several interfaces or paths and can achieve better throughput and robust data transfers. MPTCP thus attracts an increasing interest from both academia and industry. This paper systematically studies MPTCP and clearly describes the relationship between each portions of MPTCP. Up to now, MPTCP has not been widely used in the mobile Internet, one of the reasons is that it is a challenge to research, implement and test MPTCP on the actual MSDs. To overcome the shortcoming of the existing researches on MPTCP being mainly limited to network simulators, a novel approach to port MPTCP to MSDs is proposed, which includes three main steps: first, run real mobile operating system (MOS) on VirtualBox; second, port MPTCP to MOS on VirtualBox and test; third, directly copy modified files in the second step to real MOS on MSD and test. By using this method, MPTCP V0.90 is successfully ported to a real smartphone running Android-7.1.1 for the first time. The validity of the method is proved by experiments. In addition, this paper improves the subpath establishment algorithm of MPTCP and applies the improved MPTCP to Mobile Ad Hoc Network (MANET) constructed by MSDs, the test result shows that our algorithm has better performance than the original MPTCP in achieving higher data throughput.

KeyWords: MPTCP, mobile smart device, VirtualBox, NS-3, Android, MANET

676. 实现一个魔法字典 : 结合 DFS 的 Trie 运用题

题目描述

这是 LeetCode 上的 676. 实现一个魔法字典 ，难度为中等。

Tag : 「字典树」、「DFS」

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词互不相同。如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

MagicDictionary() 初始化对象
void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord，判定能否只将字符串中一个字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true；否则，返回 false。

示例：

输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]

输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 ''h'' 替换为 ''e'' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

提示：

$1 <= dictionary.length <= 100$
$1 <= dictionary[i].length <= 100$
dictionary[i] 仅由小写英文字母组成
dictionary 中的所有字符串互不相同
$1 <= searchWord.length <= 100$
searchWord 仅由小写英文字母组成
buildDict 仅在 search 之前调用一次
最多调用 $100$ 次 search

Trie + DFS

为了方便，我们令 dictionary 为 ss，令 searchWord 为 s。

整体题意：给定字符串 s，问能否存在替换掉 s 中的某个字符，使得新字符串出现在 ss 数组中。

考虑如何使用「字典树/Trie」求解该问题：

buildDict 操作：我们可以将所有的 $ss[i]$ 存入字典树中，方便后续检索；
search 操作：设计递归函数 boolean query(String s, int idx, int p, int limit)，其中 s 为待检索的字符串，idx 为当前处理到字符串 s 的哪一位，p 为当前搜索到字典树的索引编号（起始有 $p = 0$），limit 为当前剩余的替换字符次数，根据题意，limit 固定为 $1$，含义为必须替换掉 s 的一个字符。
对于 $s[idx]$ 而言，我们可以枚举新字符串在当前位置是何种字符（$C = 26$ 个选择），若当前枚举到的字符与 $s[idx]$ 一致，则不消耗替换次数。
爆搜过程中替换次数为负数直接剪枝，当爆搜到结尾位置，再检查当前的字典树索引 $p$ 是否为单词结尾节点（对应查询数组 ss 中是否存在该字符串），以及剩余的替换次数 limit 是否为 $0$。

不了解「Trie / 字典树」的同学可以看前置：字典树入门。里面通过图例展示了字典树基本形态，以及提供了「数组实现」和「TrieNode 实现」两种方式，还有「数组大小估算方式」和「Trie 应用面」介绍

代码：

class MagicDictionary {
    int N = 100 * 100, M = 26, idx = 0;
    int[][] tr = new int[N][M];
    boolean[] isEnd = new boolean[N * M];
    void add(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - ''a'';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        isEnd[p] = true;
    }
    boolean query(String s, int idx, int p, int limit) {
        if (limit < 0) return false;
        if (idx == s.length()) return isEnd[p] && limit == 0;
        int u = s.charAt(idx) - ''a'';
        for (int i = 0; i < 26; i++) {
            if (tr[p][i] == 0) continue;
            if (query(s, idx + 1, tr[p][i], i == u ? limit : limit - 1)) return true;
        }
        return false;
    }
    public void buildDict(String[] ss) {
        for (String s : ss) add(s);
    }
    public boolean search(String s) {
        return query(s, 0, 0, 1);
    }
}

时间复杂度：buildDict 操作需要将所有字符存入 Trie，复杂度为 $\sum_{i = 0}^{n - 1} len(ss[i]])$；search 操作在不考虑 limit 以及字典树中最多只有 $100$ 具体方案所带来的剪枝效果的话，最坏情况下要搜索所有 $C^L$ 个方案，其中 $C = 26$ 为字符集大小，$L = 100$ 为搜索字符串的最大长度
空间复杂度：$O(N \times L \times C)$，其中 $N = 100$ 为存入 Trie 的最大方案数，$L = 100$ 为存入字符串的最大长度，$C = 26$ 为字符集大小

最后

这是我们「刷穿 LeetCode」系列文章的第 No.676 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSou... 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地

本文由mdnice多平台发布

C#中字典集合HashTable、Dictionary、ConcurrentDictionary三者区别

C#中HashTable、Dictionary、ConcurrentDictionar三者都表示键/值对的集合，但是到底有什么区别，下面详细介绍

一、HashTable

HashTable表示键/值对的集合。在.NET Framework中，Hashtable是System.Collections命名空间提供的一个容器，用于处理和表现类似key-value的键值对，其中key通常可用来快速查找，同时key是区分大小写；value用于存储对应于key的值。Hashtable中key-value键值对均为object类型，所以Hashtable可以支持任何类型的keyvalue键值对，任何非 null 对象都可以用作键或值。

HashTable是一种散列表，他内部维护很多对Key-Value键值对，其还有一个类似索引的值叫做散列值(HashCode)，它是根据GetHashCode方法对Key通过一定算法获取得到的，所有的查找操作定位操作都是基于散列值来实现找到对应的Key和Value值的。

散列函数(GetHashCode)让散列值对应HashTable的空间地址尽量不重复。

当一个HashTable被占用一大半的时候我们通过计算散列值取得的地址值可能会重复指向同一地址，这就造成哈希冲突。

C#中键值对在HashTable中的位置Position= (HashCode& 0x7FFFFFFF) % HashTable.Length，C#是通过探测法解决哈希冲突的，当通过散列值取得的位置Postion以及被占用的时候，就会增加一个位移x值判断下一个位置Postion+x是否被占用，如果仍然被占用就继续往下位移x判断Position+2*x位置是否被占用，如果没有被占用则将值放入其中。当HashTable中的可用空间越来越小时，则获取得到可用空间的难度越来越大，消耗的时间就越多。

使用方法如下：

using System;
using System.Collections;

namespace WebApp { class Program { static void Main(string[] args) { Hashtable myHash=new Hashtable(); //插入 myHash.Add("1","joye.net"); myHash.Add("2", "joye.net2"); myHash.Add("3", "joye.net3"); //key 存在 try { myHash.Add("1", "1joye.net"); } catch { Console.WriteLine("Key = \"1\" already exists."); } //取值 Console.WriteLine("key = \"2\", value = {0}.", myHash["2"]); //修改 myHash["2"] = "http://www.cnblogs.com/yinrq/"; myHash["4"] = "joye.net4"; //修改的key不存在则新增 Console.WriteLine("key = \"2\", value = {0}.", myHash["2"]); Console.WriteLine("key = \"4\", value = {0}.", myHash["4"]); //判断key是否存在 if (!myHash.ContainsKey("5")) { myHash.Add("5", "joye.net5"); Console.WriteLine("key = \"5\": {0}", myHash["5"]); } //移除 myHash.Remove("1"); if (!myHash.ContainsKey("1")) { Console.WriteLine("Key \"1\" is not found."); } //foreach 取值 foreach (DictionaryEntry item in myHash) { Console.WriteLine("Key = {0}, Value = {1}", item.Key, item.Value); } //所有的值 foreach (var item in myHash.Values) { Console.WriteLine("Value = {0}",item); } //所有的key foreach (var item in myHash.Keys) { Console.WriteLine("Key = {0}", item); } Console.ReadKey(); } } }

结果如下：

更多参考微软官方文档：Hashtable 类

二、Dictionary

Dictionary<TKey, TValue> 泛型类提供了从一组键到一组值的映射。通过键来检索值的速度是非常快的，接近于 O(1)，这是因为 Dictionary<TKey, TValue> 类是作为一个哈希表来实现的。检索速度取决于为 TKey 指定的类型的哈希算法的质量。TValue可以是值类型，数组，类或其他。

Dictionary是一种变种的HashTable,它采用一种分离链接散列表的数据结构来解决哈希冲突的问题。

简单使用代码：

using System;
using System.Collections;
using System.Collections.Generic; namespace WebApp { class Program { static void Main(string[] args) { Dictionary<string, string> myDic = new Dictionary<string, string>(); //插入 myDic.Add("1", "joye.net"); myDic.Add("2", "joye.net2"); myDic.Add("3", "joye.net3"); //key 存在 try { myDic.Add("1", "1joye.net"); } catch { Console.WriteLine("Key = \"1\" already exists."); } //取值 Console.WriteLine("key = \"2\", value = {0}.", myDic["2"]); //修改 myDic["2"] = "http://www.cnblogs.com/yinrq/"; myDic["4"] = "joye.net4"; //修改的key不存在则新增 Console.WriteLine("key = \"2\", value = {0}.", myDic["2"]); Console.WriteLine("key = \"4\", value = {0}.", myDic["4"]); //判断key是否存在 if (!myDic.ContainsKey("5")) { myDic.Add("5", "joye.net5"); Console.WriteLine("key = \"5\": {0}", myDic["5"]); } //移除 myDic.Remove("1"); if (!myDic.ContainsKey("1")) { Console.WriteLine("Key \"1\" is not found."); } //foreach 取值 foreach (var item in myDic) { Console.WriteLine("Key = {0}, Value = {1}", item.Key, item.Value); } //所有的值 foreach (var item in myDic.Values) { Console.WriteLine("Value = {0}",item); } //所有的key foreach (var item in myDic.Keys) { Console.WriteLine("Key = {0}", item); } Console.ReadKey(); } } }

运行结果：

更多资料参考：Dictionary 类

三、ConcurrentDictionary

表示可由多个线程同时访问的键/值对的线程安全集合。

ConcurrentDictionary<TKey, TValue> framework4出现的，可由多个线程同时访问，且线程安全。用法同Dictionary很多相同，但是多了一些方法。ConcurrentDictionary 属于System.Collections.Concurrent 命名空间按照MSDN上所说：

System.Collections.Concurrent 命名空间提供多个线程安全集合类。当有多个线程并发访问集合时，应使用这些类代替 System.Collections 和 System.Collections.Generic 命名空间中的对应类型。

更多资料：ConcurrentDictionary<TKey,?TValue> 类

四、对比总结

分别插入500万条数据，然后遍历，看看耗时。

using System;
using System.Collections;
using System.Collections.Concurrent; using System.Collections.Generic; using System.Diagnostics; namespace WebApp { class Program { static Hashtable _hashtable; static Dictionary<string, string> _dictionary; static ConcurrentDictionary<string, string> _conDictionary; static void Main(string[] args) { Compare(5000000); Console.ReadLine(); Console.Read(); } public static void Compare(int dataCount) { _hashtable = new Hashtable(); _dictionary = new Dictionary<string, string>(); _conDictionary=new ConcurrentDictionary<string, string>(); Stopwatch stopWatch = new Stopwatch(); // Hashtable  stopWatch.Start(); for (int i = 0; i < dataCount; i++) { _hashtable.Add("key" + i.ToString(), "Value" + i.ToString()); } stopWatch.Stop(); Console.WriteLine("HashTable插" + dataCount + "条耗时(毫秒)：" + stopWatch.ElapsedMilliseconds); //Dictionary  stopWatch.Reset(); stopWatch.Start(); for (int i = 0; i < dataCount; i++) { _dictionary.Add("key" + i.ToString(), "Value" +i.ToString()); } stopWatch.Stop(); Console.WriteLine("Dictionary插" + dataCount + "条耗时(毫秒)：" + stopWatch.ElapsedMilliseconds); //ConcurrentDictionary  stopWatch.Reset(); stopWatch.Start(); for (int i = 0; i < dataCount; i++) { _conDictionary.TryAdd("key" + i.ToString(), "Value" + i.ToString()); } stopWatch.Stop(); Console.WriteLine("ConcurrentDictionary插" + dataCount + "条耗时(毫秒)：" + stopWatch.ElapsedMilliseconds); // Hashtable  stopWatch.Reset(); stopWatch.Start(); for (int i = 0; i < _hashtable.Count; i++) { var key = _hashtable[i]; } stopWatch.Stop(); Console.WriteLine("HashTable遍历时间(毫秒)：" + stopWatch.ElapsedMilliseconds); //Dictionary  stopWatch.Reset(); stopWatch.Start(); for (int i = 0; i < _hashtable.Count; i++) { var key = _dictionary["key" + i.ToString()]; } stopWatch.Stop(); Console.WriteLine("Dictionary遍历时间(毫秒)：" + stopWatch.ElapsedMilliseconds); //ConcurrentDictionary  stopWatch.Reset(); stopWatch.Start(); for (int i = 0; i < _hashtable.Count; i++) { var key = _conDictionary["key"+i.ToString()]; } stopWatch.Stop(); Console.WriteLine("ConcurrentDictionary遍历时间(毫秒)：" + stopWatch.ElapsedMilliseconds); } } }

运行结果：

可以看出：

大数据插入Dictionary花费时间最少

遍历HashTable最快是Dictionary的1/5,ConcurrentDictionary的1/10

单线程建议用Dictionary，多线程建议用ConcurrentDictionary或者HashTable（Hashtable tab = Hashtable.Synchronized(new Hashtable());获得线程安全的对象）

Database Systems--- A practical Approach to Design, Implementation, and Management Fifth Edtion

时间：2019年01月14日：

　在2010年冬天的时候，我们前单位（晋能信工）把我们送到了北大青鸟培训了两个月，最后，我还是没有考试过了。我觉得我不是学习计算机的一块料。一恍，十年过去了，我也不知道我也干什么的一块料。被命运牵着鼻子走。我是一个胆小懦弱而又不善言辞的人。一味地去听别人，看别人。从来也不知道自己是一个什么人，也不知道自己能干点啥。喜欢看一些不合时书，比如周易、韩非子之类的书。

在晋能信工，我也干了7年多，从2009年到2015年。这7年中，我看了不少的计算机方面书，可是自己却不会写一个"hello word!"。也许，这是从事过计算机人的最大耻辱。我想自学一下程序，顺便也提升一下自己的证书历程。上了十年班了，一个证书也没考下来。说起来，还嘲人了。蝎体斯人了。

　　英文不是中文，我连中国话也咬文嚼不清，有资格看英文类的书籍吗？

　　在我四婶住院期间，我四婶的姐姐说过，一个事情，说的是一个小学老师给小朋友们上学，台上的老师说一句：“open your book! open your eyes! 打开你的书，打开你的眼睛！”下边的一个小朋友说：“老师不对，应该是翻开你的书、睁开你的眼睛！”这句话，在我心里翻了好几次。语言的翻译必须符合国语的语序和语言习惯。

好吧！我也想翻译一些东西。自己还想自由译一些东西。可是，我的才华够吗？？？？

　英语单词，还没认识几个，就想翻译一些东西，就凭看过几年的数据库代码？是不是把自己看的太高了，还是我真得有这样的天赋了。

时间：2019年01月15日：

　　早上起来，还是看点书吧！只有书中的未知，才知充实自己。虽然是一页书，但是还是看了看。

Preface

Background

The history of database research over the past 30 year is one of exceptional productivity that led to the database system becoming arguably the most important development in the field of software engineering. The database is now the underlying framework of the information system and has fundamentally changed the way many organizations operate.In particular, the developments in this technology over the last few years have produced systems that are more powerful and more intuitive to use. This development has resulted in increasing availability of database systems for a wider variety of users. Unfortunately, the appearent simplicity of these systems has led to users creating databases and applications without the necessary knowledge to produce an effective and efficient system. And so the "software crisis" or, as it is sometimes referred to the "software depression" continues. 　　

　　The original stimulus for this book came from the author''s work in industry, providing consultancy on database design for new software systems or, as often as not, resolving inadequacies with existing systems. In addition, the authors'' move to academia brought similar problems from different users--students. The objectives of this book, therefore, are to provide a textbook that introduces the theory behind databases as clearly as possible and, in particular, to provide a methodology for database design that can be used by both technical and nontechnical readers.

Pre--face 脸的前面，是什么是？不知道，说实话，这个词以前见过，但是想不起是什么意思。也不知道是什么意思。也许就是一个前言的意思吧。

Back--ground . ground 是大地的意思，Background是什么意思。是背景的意思吗/

睡吧！看书是一件很痛苦的事情，也许，我是习惯学习吧！小学时，学习还行，初中就不行了。

今天关于LeetCode 676. Implement Magic Dictionary 实现一个魔法字典 (C++/Java)的介绍到此结束，谢谢您的阅读，有关(OK) Research, implementation, and improvement of MPTCP on mobile smart devices、676. 实现一个魔法字典 : 结合 DFS 的 Trie 运用题、C#中字典集合HashTable、Dictionary、ConcurrentDictionary三者区别、Database Systems--- A practical Approach to Design, Implementation, and Management Fifth Edtion等更多相关知识的信息可以在本站进行查询。

本文标签：