算法训练营打卡day5 哈希表part1_算法

看到题目的第一思路：

可以用暴力解法两个for loop分别遍历两个字符串对比是否包含字母一致

代码随想录之后的想法和总结：

首先感受到用数组来做哈希表带来的便利，明白了数组就是一个简单的哈希表，其次学会了新的方法和思维方式：当要比较两个字符串的字母是否一致时，比起一个一个遍历逐一比较，新建一个数组用来记录字符串里字符出现的次数是一个更好的方法，对于第一个字符串里的字符出现了可以元素+1，然后第二个字符串里字符出现了可以元素-1，最后看这个数组里的元素是否为0，则表示两个字符串包含字符都一致

遇到的困难：

1 第一次见到ascii？其实就是用数值表示字符的方法，比如character a 就是数字97，可以用这个方法把从a到z的字母都表示成数字，以此来给他们添加上数组当中的索引下标方便我们使用

2 遇到

record[ord(i)-ord("a")]+= 1

有疑惑，但是发现这个步骤其实就是对于每一个字符串里的字符，首先用ord(i)-ord(a) 来求出这个字符的索引下标值，然后用+1来给这个索引位置的元素+1（用来表示这个字符出现的次数+1）

可以记录备用的固定代码方法模版：

class solution:
    def isanagram(self, s: str, t: str) -> bool:
        record = [0] *26
        for i in s :
            record[ord(i)-ord("a")]+= 1
            #用求出字符相对数值的方法来求出字符所在的索引下标数值，然后给这个索引的元素+1

        for i in t:
            record[ord(i)- ord("a")]-= 1
            #同理，另一个字符串遇到的字符的元素-1
        for i in range(26):
            if record[i] != 0: 
            #record数组如果有的元素不为0，说明两个字符串的字符不一致，则return false
                return false


        return true #否则说明两个字符串是字母异味词

时间复杂度以及空间复杂度：

时间：o(n)-遍历两个字符串为o(n), n是字符串长度，遍历其他比如26为o(1)所以总体为o(n)

空间：this array has a fixed size of 26, regardless of the input size. so, it uses 𝑂(1)o(1) space.

看到题目的第一思路：

使用数组

代码随想录之后的想法和总结：

遇到要使用哈希表的情况，了解了什么时候用数组/set/map（如果数组的数值数字很大或者分布很分散，都不适合用数组来解决，因为占用内存太大，所以这道题目用了set集合的方法

哈希表在这里的作用是为了加快查找的速度。在第一个循环中，我们将nums1中的元素作为键存储在table中，并将它们的出现次数作为值。这样，我们就可以在第二个循环中，通过检查nums2中的元素是否在table中，来确定它们是否是nums1和nums2的交集之一。（哈希表table在题目中的用处）

集合仍然具有类似于哈希表的性质，例如快速的查找、插入和删除操作，并且在这个算法中，集合的去重功能正是我们所需要的。因此，虽然集合res并非通过哈希表建立，但它仍然在这个算法中发挥了类似哈希表的作用。（集合res在题目中的使用与区别）

遇到的困难：

1 当创建字典并且用空的字典储存字符串出现元素的次数时，使用了table[num] = table.get(num, 0) + 1有点困惑，但是举例之后明白了

2 在遍历第二个字符串，del table[num]时候有点困惑，明白之后发现是很好的给最后输出结果去重的方法，以后可以使用起来

del table[num] ensures that each element from nums2 that is found in table is processed only once and then removed, preventing duplicate entries in the result set res.

3 difference between dictionary and set: a set is like a dict with keys but no values, ( no duplicate items as well) and they're both implemented using a hash table. 这道题目是遍历第一个元素把次数存储在字典当中使用了哈希表的方法

键值对结构：字典是由键值对组成的，每个键都是唯一的，并且与一个值相关联。这使得字典更适合于需要键值关联的情况，而不仅仅是存储元素的集合。
可变性：字典是可变的，可以通过添加、删除和修改键值对来改变其内容。相比之下，一些集合类型（如python中的集合）是不可变的，一旦创建就无法更改。
哈希表实现：字典通常是使用哈希表来实现的，这使得字典具有快速的查找、插入和删除操作，平均情况下为o(1)时间复杂度。集合也可以使用哈希表实现，因此在某种程度上字典和集合都可以被看作是基于哈希表的数据结构。

因此，虽然字典可以被看作是一种特殊的集合，但由于其键值对的结构和可变性，它们在使用和设计上有一些不同之处。

可以记录备用的固定代码方法模版：

class solution:
    def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
        #create a empty dictionary to store elements of nums1 and their counts
        table = {}
        for num in nums1:
        #add each element of nums1 to the dictionary with its count
            table[num] = table.get(num, 0) + 1
        
        # 使用集合存储结果
        res = set()
        for num in nums2:
        # if the current element of nums2 is in the dictionary, 
        #it means it is also in nums1
            if num in table:
        # add the element to the result set
                res.add(num)
        # remove the element from the dictionary to ensure uniqueness in the result
                del table[num]
        
        # convert the set to a list and return it as the result
        return list(res)

时间复杂度以及空间复杂度：

step 1: o(n)-

for each element in nums1, we insert it into the dictionary table.
inserting an element into a hash table (dictionary) is an average o(1) operation.
if n is the length of nums1, this step takes o(n) time in total.

step 2: o(m)

for each element in nums2, we check if it exists in the dictionary table and add it to the set res if it does.
checking membership in a hash table is an average o(1) operation, and adding an element to a set is also o(1).
if m is the length of nums2, this step takes o(m) time in total.

step 3: o(min(n, m))

converting a set of size k to a list takes o(k) time, where k is the number of unique elements in the intersection.
in the worst case, k could be the minimum of n and m (let's denote it as min(n, m)).
therefore, this step takes o(min(n, m)) time in the worst case.

the overall time complexity is: 𝑂(𝑛+𝑚)o(n+m)

inserting an element into a hash table (or dictionary) is considered an average o(1) operation because of the way hash tables are designed and operate

看到题目的第一思路：

数学题目

代码随想录之后的想法和总结：

重点在于题目中的无限循环-如果循环了那肯定就不是快乐数。

那这道题就可以转化成：【在“将正整数替换为它每个位置上的数字的平方和”过程中，新出现的正整数是否曾经出现过。】我们记录出现过的正整数，然后将新元素与之前出现过的正整数比较。在一堆数中查找一个数，当然是使用哈希。

题目可以重点拆解成两个步骤：

将当前数进行数位分离，求各位上平方的和。
每次生成的数，查是否在哈希集合中，在的话就不是快乐数，不在的话就添到集合里。（这里的集合主要是起记录数据的作用，比如19-82-68-100-1 这过程中每一次演变的数字记录下来，直到变成1为止可以判断出是快乐数，停止计算）

遇到的困难：

1 n,r = divmod(n,10）的运算不太熟悉

以n = 82为例，这个方法可以计算出82的下一次平方和数字，并且用这个数字带入到下面的方法中来记录和判断是否是快乐数

initial value: 𝑛=82
first iteration:
- divmod(82, 10) gives 𝑛=8 (quotient) and 𝑟=2(remainder)
- 2平方为4
- new_num = 0 + 4 = 4
second iteration:
- divmod(8, 10) gives 𝑛=0= (quotient) and 𝑟=8r (remainder)
- 8平方为64
- new_num = 4 + 64 = 68
result:
- the loop ends because 𝑛=0n=0
- the method returns 68

可以记录备用的固定代码方法模版：

class solution:
    def get_sum(self,n:int) -> int: #求正整数num每个位置上数字的平方和
        new_num = 0
        while n:
            n,r = divmod(n,10)
            new_num += r **2
        return new_num

    def ishappy(self, n: int) -> bool:
        record = set() #用集合记录过程数据

        while true:
            n = self.get_sum(n) #将当前替换为它每个位置上的数字平方和
            if n ==1: #如果为1，则是快乐数
                return true
        # 如果替换后的数再之前出现过，则说明陷入无限循环，此数不是快乐数
            if n in record:  
                return false
            else:
                record.add(n)

时间复杂度以及空间复杂度：

一是求每个位置上数字的平方和为 o(logn)，二是看新元素是否在集合中，单个查询的时间复杂度为 o(1)，因为总会是在有限的个数内解决掉这个问题，所以总的时间复杂度为 o(logn)。

因为额外建了一个集合 mid，所以空间复杂度为 o(logn)。

看到题目的第一思路：

两个for 循环

代码随想录之后的想法和总结：

1 为什么用哈希法：因为这道题需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。

2 为什么用哈希法中的map数据结构：因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

3 map中的key,value分别代表什么：判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

4 map用来存什么：在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

（以上思路来自代码随想录）

遇到的困难：

1 python中enumerate(nums)结构来怎样更高效的track both the index and the value of each element

2 python 中dictionary怎样运作：records[value] = index怎样把当前访问元素加入map当中存储遍历过的元素和其下标

nums = [2, 7, 11, 15]
target = 9

initial state

records = {} (an empty dictionary)

iteration 1

index = 0, value = 2
calculate complement = target - value = 9 - 2 = 7
since records is empty, 7 is not found in records.
update records with records[value] = index, which is records[2] = 0.
after this step, records becomes {2: 0}.

可以记录备用的固定代码方法模版：

class solution:
    def twosum(self, nums: list[int], target: int) -> list[int]:
        records = dict()#新建一个dictionary/hashmap 去记录遍历过的integer

        for index,value in enumerate(nums):#遍历数组的每一个元素和它的下标
            if target-value in records:#对于当前元素，去map里面找是否有匹配元素
                return [records[target-value],index] #如果找到匹配元素就返回它和它下标
            records[value] = index #如果没有找到，就把当前访问过的元素和下标加入map
        return []

时间复杂度以及空间复杂度：

time:creating records dictionary: this takes o(1) time since it's created once at the beginning.
iterating through nums: the for loop iterates through each element in nums, which takes o(n) time, where n is the number of elements in nums.
checking for complement: for each element in nums, the code checks if target - value exists in records. the lookup operation in a dictionary (assuming an average case) is o(1).
overall: since the dominant operation is the loop iterating through nums, the overall time complexity is o(n).
space: records dictionary: the space required for the records dictionary is o(n), where n is the number of elements in nums. this is because, in the worst case, all elements of nums could be stored in the dictionary.therefore, the overall space complexity is o(n) due to the records dictionary.