背景

前段时间，在知识星球立了一个Flag，这是总结Leetcode刷题的第二篇图文。

在总结这篇图文的时候，顺便总结了 C# 中Dictionary类的实现，大家可以参考一下：

• 浅析 C# Dictionary实现原理

理论部分

C# 中字典的常用方法

对于 C# 中的 Dictionary类 相信大家都不陌生，这是一个 Collection(集合) 类型，可以通过 Key/Value (键值对) 的形式来存放数据；该类最大的优点就是它查找元素的时间复杂度接近 O(1)，实际项目中常被用来做一些数据的本地缓存，提升整体效率。

常用方法如下：

• public Dictionary(); -> 构造函数
• public Dictionary(int capacity); -> 构造函数
• public void Add(TKey key, TValue value); -> 将指定的键和值添加到字典中。
• public bool Remove(TKey key); -> 将带有指定键的值移除。
• public void Clear(); -> 将所有键和值从字典中移除。
• public bool ContainsKey(TKey key); -> 确定是否包含指定键。
• public bool ContainsValue(TValue value); -> 确定否包含特定值。
• public TValue this[TKey key] { get; set; } -> 获取或设置与指定的键关联的值。
• public KeyCollection Keys { get; } -> 获得键的集合。
• public ValueCollection Values { get; } -> 获得值的集合。

public static void DicSample()
{Dictionary<string, string> dic = new Dictionary<string, string>();try{if (dic.ContainsKey("Item1") == false){dic.Add("Item1", "ZheJiang");}if (dic.ContainsKey("Item2") == false){dic.Add("Item2", "ShangHai");}else{dic["Item2"] = "ShangHai";}if (dic.ContainsKey("Item3") == false){dic.Add("Item3", "BeiJing");}}catch (Exception e){Console.WriteLine("Error: {0}", e.Message);}if (dic.ContainsKey("Item1")){Console.WriteLine("Output: " + dic["Item1"]);}foreach (string key in dic.Keys){Console.WriteLine("Output Key: {0}", key);}foreach (string value in dic.Values){Console.WriteLine("Output Value: {0}", value);}foreach (KeyValuePair<string, string> item in dic){Console.WriteLine("Output Key : {0}, Value : {1} ", item.Key, item.Value);}
}// Output: ZheJiang
// Output Key: Item1
// Output Key: Item2
// Output Key: Item3
// Output Value: ZheJiang
// Output Value: ShangHai
// Output Value: BeiJing
// Output Key: Item1, Value: ZheJiang
// Output Key: Item2, Value: ShangHai
// Output Key: Item3, Value: BeiJing

注意：增加键值对之前需要判断是否存在该键，如果已经存在该键而不判断，将抛出异常。

Python 中字典的常用方法

Python中的 字典 是无序的 键:值（key:value）对集合，在同一个字典之内键必须是互不相同的。

• dict 内部存放的顺序和 key 放入的顺序是没有关系的。
• dict 查找和插入的速度极快，不会随着 key 的增加而增加，但是需要占用大量的内存。

字典 定义语法为 {元素1, 元素2, ..., 元素n}

• 其中每一个元素是一个「键值对」-- 键:值 (key:value)
• 关键点是「大括号 {}」,「逗号 ,」和「冒号 :」
• 大括号 – 把所有元素绑在一起
• 逗号 – 将每个键值对分开
• 冒号 – 将键和值分开

常用方法如下：

• dict() -> 构造函数。
• dict(mapping) -> 构造函数。
• dict(**kwargs) -> 构造函数。
• dict.keys() -> 返回一个可迭代对象，可以使用 list() 来转换为列表，列表为字典中的所有键。
• dict.values() -> 返回一个迭代器，可以使用 list() 来转换为列表，列表为字典中的所有值。
• dict.items() -> 以列表返回可遍历的 (键, 值) 元组数组。
• dict.get(key, default=None) -> 返回指定键的值，如果值不在字典中返回默认值。
• dict.setdefault(key, default=None) -> 和get()方法 类似, 如果键不存在于字典中，将会添加键并将值设为默认值。
• key in dict -> in 操作符用于判断键是否存在于字典中，如果键在字典 dict 里返回true，否则返回false。
• key not in dict -> not in操作符刚好相反，如果键在字典 dict 里返回false，否则返回true。
• dict.pop(key[,default]) -> 删除字典给定键 key 所对应的值，返回值为被删除的值。key 值必须给出。若key不存在，则返回 default 值。
• del dict[key] -> 删除字典给定键 key 所对应的值。

def DicSample(self):dic = dict()try:if "Item1" not in dic:dic["Item1"] = "ZheJiang"if "Item2" not in dic:dic.setdefault("Item2", "ShangHai")else:dic["Item2"] = "ShangHai"dic["Item3"] = "BeiJing"except KeyError as error:print("Error:{0}".format(str(error)))if "Item1" in dic:print("Output: {0}".format(dic["Item1"]))for key in dic.keys():print("Output Key: {0}".format(key))for value in dic.values():print("Output Value: {0}".format(value))for key, value in dic.items():print("Output Key: {0}, Value: {1}".format(key, value))# Output: ZheJiang
# Output Key: Item1
# Output Key: Item2
# Output Key: Item3
# Output Value: ZheJiang
# Output Value: ShangHai
# Output Value: BeiJing
# Output Key: Item1, Value: ZheJiang
# Output Key: Item2, Value: ShangHai
# Output Key: Item3, Value: BeiJing

应用部分

题目1：两数之和

• 题号：1
• 难度：简单
• https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例1:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

示例2：

给定 nums = [230, 863, 916, 585, 981, 404, 316, 785, 88, 12, 70, 435, 384, 778, 887, 755, 740, 337, 86, 92, 325, 422, 815, 650, 920, 125, 277, 336, 221, 847, 168, 23, 677, 61, 400, 136, 874, 363, 394, 199, 863, 997, 794, 587, 124, 321, 212, 957, 764, 173, 314, 422, 927, 783, 930, 282, 306, 506, 44, 926, 691, 568, 68, 730, 933, 737, 531, 180, 414, 751, 28, 546, 60, 371, 493, 370, 527, 387, 43, 541, 13, 457, 328, 227, 652, 365, 430, 803, 59, 858, 538, 427, 583, 368, 375, 173, 809, 896, 370, 789], target = 542因为 nums[28] + nums[45] = 221 + 321 = 542，所以返回 [28, 45]

思路：利用字典的方式

把字典当作一个存储容器，key 存储已经出现的数字，value 存储数组的下标。

C# 语言

• 执行结果：通过
• 执行用时：280 ms, 在所有 C# 提交中击败了 96.53% 的用户
• 内存消耗：31.1 MB, 在所有 C# 提交中击败了 6.89% 的用户

public class Solution 
{public int[] TwoSum(int[] nums, int target) {int[] result = new int[2];Dictionary<int, int> dic = new Dictionary<int, int>();for (int i = 0; i < nums.Length; i++){int find = target - nums[i];if (dic.ContainsKey(find)){result[0] = dic[find];result[1] = i;break;}if (dic.ContainsKey(nums[i]) == false)dic.Add(nums[i], i);}return result;    }
}  

Python 语言

• 执行结果：通过
• 执行用时：52 ms, 在所有 Python3 提交中击败了 86.77% 的用户
• 内存消耗：15.1 MB, 在所有 Python3 提交中击败了 7.35% 的用户

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:result = list()dic = dict()for index, val in enumerate(nums):find = target - valif find in dic is not None:result = [dic[find], index]breakelse:dic[val] = indexreturn result

题目2：只出现一次的数字 II

• 题号：137
• 难度：中等
• https://leetcode-cn.com/problems/single-number-ii/

给定一个 非空 整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

思路：利用字典的方式

把字典当作一个存储容器，key 存储数组中的数字，value 存储该数字出现的频数。

C# 语言

• 执行结果：通过
• 执行用时：112 ms, 在所有 C# 提交中击败了 91.53% 的用户
• 内存消耗：25.4 MB, 在所有 C# 提交中击败了 100.00% 的用户

public class Solution
{public int SingleNumber(int[] nums){Dictionary<int, int> dict = new Dictionary<int, int>();for (int i = 0; i < nums.Length; i++){if (dict.ContainsKey(nums[i])){dict[nums[i]]++;}else{dict.Add(nums[i], 1);}}return dict.Single(a => a.Value == 1).Key;}
}

Python 语言

• 执行结果：通过
• 执行用时：40 ms, 在所有 Python3 提交中击败了 89.20% 的用户
• 内存消耗：15.1 MB, 在所有 Python3 提交中击败了 25.00% 的用户

class Solution:def singleNumber(self, nums: List[int]) -> int:dic = dict()for num in nums:if num in dic:dic[num] += 1else:dic[num] = 1for k, v in dic.items():if v == 1:return kreturn -1

题目3：罗马数字转整数

• 题号：13
• 难度：简单
• https://leetcode-cn.com/problems/roman-to-integer/

罗马数字包含以下七种字符: I， V， X， L，C，D和M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做II，即为两个并列的 1。12 写做XII，即为X + II。 27 写做XXVII, 即为XX + V + II。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做IIII，而是IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入:"III"
输出: 3

示例 2:

输入: "IV"
输出: 4

示例 3:

输入: "IX"
输出: 9

示例 4:

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

思路：利用字典的方式

把字典当作一个存储容器，key 存储罗马字符的所有组合，value 存储该组合代表的值。

每次取一个字符，判断这个字符之后是否还有字符。如果有，则判断这两个字符是否在字典中，如果存在则取值。否则，按照一个字符去取值即可。

C# 语言

• 执行结果：通过
• 执行用时：120 ms, 在所有 C# 提交中击败了 42.16% 的用户
• 内存消耗：25.8 MB, 在所有 C# 提交中击败了 5.27% 的用户

public class Solution
{public int RomanToInt(string s){Dictionary<string, int> dic = new Dictionary<string, int>();dic.Add("I", 1);dic.Add("II", 2);dic.Add("IV", 4);dic.Add("IX", 9);dic.Add("X", 10);dic.Add("XL", 40);dic.Add("XC", 90);dic.Add("C", 100);dic.Add("CD", 400);dic.Add("CM", 900);dic.Add("V", 5);dic.Add("L", 50);dic.Add("D", 500);dic.Add("M", 1000);int result = 0;int count = s.Length;int i = 0;while (i < count){char c = s[i];if (i + 1 < count && dic.ContainsKey(s.Substring(i, 2))){result += dic[s.Substring(i, 2)];i += 2;}else{result += dic[c.ToString()];i += 1;}}return result;}
}

Python 语言

• 执行结果：通过
• 执行用时：72 ms, 在所有 Python3 提交中击败了 24.93% 的用户
• 内存消耗：13.5 MB, 在所有 Python3 提交中击败了 5.05% 的用户

class Solution:def romanToInt(self, s: str) -> int:dic = {"I": 1, "II": 2, "IV": 4, "IX": 9, "X": 10, "XL": 40, "XC": 90,"C": 100, "CD": 400, "CM": 900, "V": 5,"L": 50, "D": 500, "M": 1000}result = 0count = len(s)i = 0while i < count:c = s[i]if i + 1 < count and s[i:i + 2] in dic:result += dic[s[i:i + 2]]i += 2else:result += dic[c]i += 1return result

题目4：LRU缓存机制

• 题号：146
• 难度：中等
• https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

思路：利用 字典 + 单链表 的方式

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

把字典当作一个存储容器，由于字典是无序的，即 dict 内部存放的顺序和 key 放入的顺序是没有关系的，所以需要一个 list 来辅助排序。

C# 语言

• 状态：通过
• 18 / 18 个通过测试用例
• 执行用时: 392 ms, 在所有 C# 提交中击败了 76.56% 的用户
• 内存消耗: 47.9 MB, 在所有 C# 提交中击败了 20.00% 的用户

public class LRUCache
{private readonly List<int> _keys;private readonly Dictionary<int, int> _dict;public LRUCache(int capacity){_keys = new List<int>(capacity);_dict = new Dictionary<int, int>(capacity);}public int Get(int key){if (_dict.ContainsKey(key)){_keys.Remove(key);_keys.Add(key);return _dict[key];}return -1;}public void Put(int key, int value){if (_dict.ContainsKey(key)){_dict.Remove(key);_keys.Remove(key);}else if (_keys.Count == _keys.Capacity){_dict.Remove(_keys[0]);_keys.RemoveAt(0);}_keys.Add(key);_dict.Add(key, value);}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.Get(key);* obj.Put(key,value);*/

Python 语言

• 执行结果：通过
• 执行用时：628 ms, 在所有 Python3 提交中击败了 12.15% 的用户
• 内存消耗：22 MB, 在所有 Python3 提交中击败了 65.38% 的用户

class LRUCache:def __init__(self, capacity: int):self._capacity = capacityself._dict = dict()self._keys = list()def get(self, key: int) -> int:if key in self._dict:self._keys.remove(key)self._keys.append(key)return self._dict[key]return -1def put(self, key: int, value: int) -> None:if key in self._dict:self._dict.pop(key)self._keys.remove(key)elif len(self._keys) == self._capacity:self._dict.pop(self._keys[0])self._keys.remove(self._keys[0])self._keys.append(key)self._dict[key] = value# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

注意，这两行代码不能颠倒顺序，否则dict中就不会存在_keys[0]了。

self._dict.pop(self._keys[0])
self._keys.remove(self._keys[0])

总结

本篇图文总结了字典的概念，以及 C# 和 Python语言对这种常用数据结构类型的封装。并以四道Leetcode习题举例说明字典作为一种容器的具体应用。好了，今天就到这里吧！Flag进度为40%，See You！

往期活动

LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！

• Python基础刻意练习活动即将开启，你参加吗？
• Task01：变量、运算符与数据类型
• Task02：条件与循环
• Task03：列表与元组
• Task04：字符串与序列
• Task05：函数与Lambda表达式
• Task06：字典与集合
• Task07：文件与文件系统
• Task08：异常处理
• Task09：else 与 with 语句
• Task10：类与对象
• Task11：魔法方法
• Task12：模块

我是 终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：