【五月集训】Day07——哈希表

• 前言
• 一、练习题目
• 二、思路与代码
• • 1. 好数对的数目
  • 2.差的绝对值为 K 的数对数目
  • 3. 制造字母异位词的最小步骤数
  • 4. 变位词组
• 三、七日复盘
• • 1.关于刷题
  • 2.知识管理

        第7天：哈希表
        哈希表则提供了更快的查找方式，线性枚举时间复杂度为O( n n n)，遇到有序顺序表时采用二分查找的方式时间复杂度为O( log ⁡ 2 n log_2 n log2​n)。把需要查找的数据，通过一个函数映射，找到存储数据位置的过程为哈希。哈希表，又称散列表，使用 O(n) 空间复杂度存储数据，通过哈希函数映射位置，从而实现近似 O(1) 时间复杂度的插入、查找、删除等操作。
        Python中常见的数据结构有列表、字典、集合以及元组。

        题目描述:
        给你一个整数数组 nums 。如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。返回好数对的数目。

解题思路:
        1)根据题目提示，nums取值范围在100以内，创建一个长度为101的哈希数组Hash；
        2)哈希数组的下标为nums的取值，每新出现一个相同下标，新的好数对加Hash[nums[i]]个，Hash[nums[i]] += 1 。

class Solution(object):
    def numIdenticalPairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        Hash = [0]*101
        ans = 0
        for i in range(len(nums)):
            ans += Hash[nums[i]] #每次新出现一个相同带下的数字，出现Hash[nums[i]]次新的组合
            Hash[nums[i]] += 1
            
        return ans

        题目描述:
        给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。
        |x| 的值定义为：
        如果 x >= 0 ，那么值为 x 。
        如果 x < 0 ，那么值为 -x 。

解题思路:
        思路与第一题相差不大，区别在于需要判别一下num[i]+k是否在哈希表长度范围内。

class Solution(object):
    def countKDifference(self, nums, k):
        Hash = [0]*101 #依据nums给定的取值范围设定哈希表
        ans = 0
        for i, num in enumerate(nums): 
            x = nums[i] + k
            if x < 101 and x >= 0:
                ans += Hash[x]
            x = nums[i] - k
            if x < 101 and x >= 0:
                ans += Hash[x]
            Hash[nums[i]] += 1
        return ans

        题目描述:
        给你两个长度相等的字符串 s 和 t。每一个步骤中，你可以选择将 t 中的任一字符 替换为 另一个字符。返回使 t 成为 s 的字母异位词的最小步骤数。字母异位词 指字母相同，但排列不同（也可能相同）的字符串。

解题思路1:
        1)创建两个字典，分别以字符串中字符作为key，字符数量作为value；
        2)调取统计后的两个字典中键值，并进行比较即可。

class Solution(object):
    def minSteps(self, s, t):
        ds, dt = {}, {}
        tmp, ans = 0, 0
        for i in s:
            if i in ds:
                ds[i] += 1
            else:
                ds[i] = 1
        for i in t:
            if i in dt:
                dt[i] += 1
            else:
                dt[i] = 1
        for i in ds:
            if i not in dt: #如果字典dt中没有字典ds中的字符，添加该字符到dt中，并将其大小设置为0
                dt[i] = 0
                tmp = ds[i] - dt[i]
            else:    
                tmp = ds[i] - dt[i] 
            if tmp > 0:
                ans += tmp
        return ans

解题思路2：
        结合python内置set集合数据结构，利用count()函数，就是那集合中每个字符出现的次数，加和复合条件的差值即可。

class Solution(object):
    def minSteps(self, s, t):
    	pd=0
    	for i in set(s):
        	a=s.count(i)
        	b=t.count(i)
        	if a>b:
            	pd=pd+a-b
    	return pd

        题目描述:
        编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

解题思路:
        1)对给出的字符串列表中的每个字符串排序，若隶属同一变位词，则排序后的字符串相同；
        2)巧妙利用defaultdict()创建字典，以排序后的字符作为字典的key值，隶属同一变位词的字符串列表作为字典的value；
        2)返回字典的值即可。

class Solution(object):
    def groupAnagrams(self, strs):
        d = defaultdict(list)
        for s in strs:
            d[''.join(sorted(s))].append(s)
        return  list(d.values())

        从五一到今天，一共刷了大概28道题目，题目集中在数组与字符串的查找操作，无论是排序、贪心算法、双指针、滑动窗口还是今天的哈希表，都是为了更好更快的查找到符合条件的目标，“增删改查”涵盖了数据结构所有内容。

        这周另外一件投入精力比较多的事是学习知识管理软件Obsidian的使用，源于一个博客（参考资料第一个链接），博客中“学习的核心是找到并建立起新节点与旧知识的联系”给我留下了很深刻的印象，因为在此之前的学习状态十分随机，机器学习，计算机视觉，数据结构，java等等，这些我都曾学过，但如果被问起学得怎么样，我并没有信心去回答这个问题，因为我并没有建立起他们之间的联系，也就谈不上深入理解。
        知识管理类软件似乎就是在解决这个问题，途径有如关键词、标签、双向链接等等，我还在探索，有机会写一篇详细的体验报告。
        知识管理的最终目的是产出，这也是我在尝试去做的事情，理想状态是做好每日复盘，并尽可能的让别人知道自己在做什么，也不至于太无聊。

参考资料
[1]Roam Research 最佳实践——知识管理与任务管理：https://me.ursb.me/archives/roam-research.html