老马的程序人生 / 待分类 / 技术图文:字典技术在求解算法题中的应用

分享

   

技术图文:字典技术在求解算法题中的应用

2020-08-17  老马的程...

背景

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

在总结这篇图文的时候,顺便总结了 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<stringstring> dic = new Dictionary<stringstring>();
    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<stringstring> 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 = [271115], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9,所以返回 [01]

示例2:

给定 nums = [2308639165859814043167858812704353847788877557403378692325422815650920125277336221847168236776140013687436339419986399779458712432121295776417331442292778393028230650644926691568687309337375311804147512854660371493370527387435411345732822765236543080359858538427583368375173809896370789], target = 542

因为 nums[28] + nums[45] = 221 + 321 = 542,所以返回 [2845]

思路:利用字典的方式

把字典当作一个存储容器,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<intint> dic = new Dictionary<intint>();
        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 - val
            if find in dic is not None:
                result = [dic[find], index]
                break
            else:
                dic[val] = index

        return 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<intint> dict = new Dictionary<intint>();
        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] += 1
            else:
                dic[num] = 1

        for k, v in dic.items():
            if v == 1:
                return k
        return -1

题目3:罗马数字转整数

  • 题号:13

  • 难度:简单

  • https://leetcode-cn.com/problems/roman-to-integer/

罗马数字包含以下七种字符: I, V, X, L,C,DM

字符          数值
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<stringint> dic = new Dictionary<stringint>();
        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 = 0
        count = len(s)
        i = 0
        while i < count:
            c = s[i]
            if i + 1 < count and s[i:i + 2in dic:
                result += dic[s[i:i + 2]]
                i += 2
            else:
                result += dic[c]
                i += 1
        return 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(11);
cache.put(22);
cache.get(1);       // 返回  1
cache.put(33);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(44);    // 该操作会使得密钥 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<intint> _dict;


    public LRUCache(int capacity)
    
{
        _keys = new List<int>(capacity);
        _dict = new Dictionary<intint>(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 = capacity
        self._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 -1

    def 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!


    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>