当前位置:   article > 正文

算法练习Day5 (Leetcode/Python-哈希表)_python table.get(num,0)

python table.get(num,0)

哈希表在python中通常使用dictionary表示。以下是dict相关的一些常用指令

my_dict is a dictionary 

1. for key, value in my_dict.items(): 

2. my_dict.values(); my_dict.keys()

3. my_dict.get(num, 0)

Time complexity of the my_dict.get() method in Python dictionaries is typically O(1) on average.

Because dictionary lookups are implemented as hash table lookups, which are generally very efficient.

4. if num in my_dict. # check whether a key num is in dict table.  

set可以用于存储无序且唯一的元素。

在 Python 中,集合(Set)的实现主要有两种类型:基于哈希表的散列集合(set 类型)和基于有序列表的集合(collections.OrderedSet 或者使用 list 的方式)。

添加、删除、查找元素:

  • set 类型:平均时间复杂度 O(1)
  • collections.OrderedSet 类型:平均时间复杂度 O(n)(需要维护有序性)

并、交、差集:

  • set 类型:平均时间复杂度 O(len(s)),其中 s 是较小的集合
  • collections.OrderedSet 类型:平均时间复杂度 O(len(s) + len(t)),其中 s 和 t 是两个集合
  1. # 使用哈希集合
  2. hash_set = set()
  3. hash_set.add(element)
  4. # 使用有序集合
  5. ordered_set = collections.OrderedSet()
  6. ordered_set.add(element)
  7. # 使用哈希集合
  8. hash_set.remove(element)
  9. # 使用有序集合
  10. ordered_set.remove(element)
  11. # 使用哈希集合
  12. element in hash_set
  13. # 使用有序集合
  14. element in ordered_set
  15. # 使用哈希集合
  16. union_set = set1.union(set2)
  17. # 使用有序集合
  18. union_set = ordered_set1.union(ordered_set2)
  19. # 使用哈希集合
  20. intersection_set = set1.intersection(set2)
  21. # 使用有序集合
  22. intersection_set = ordered_set1.intersection(ordered_set2)
  23. # 使用哈希集合
  24. difference_set = set1.difference(set2)
  25. # 使用有序集合
  26. difference_set = ordered_set1.difference(ordered_set2)

242. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: trues

思路: 

用dict来记录出现过的letter,dict的查询比数组更快。

Solution:

  1. class Solution(object):
  2. def isAnagram(self, s, t):
  3. """
  4. :type s: str
  5. :type t: str
  6. :rtype: bool
  7. """
  8. if len(s) != len(t): # Early Stop
  9. return False
  10. freq = [0] * 26
  11. for i in range(len(s)): # two valid strings share same length, so one for-loop is enough!
  12. freq[ord(s[i])-ord('a')] += 1 #get the ASCII of letter s[i]
  13. freq[ord(t[i])-ord('a')] -= 1
  14. '''
  15. # 以上也可替换为下面的这段
  16. freq = {} #[0] * 26
  17. for i in range(len(s)):
  18. freq[s[i]] = freq.get(s[i], 0) + 1
  19. freq[t[i]] = freq.get(t[i], 0) + 1
  20. '''
  21. for i in range(len(freq)):
  22. if freq[i] != 0:
  23. return False
  24. return True # Don't remember return True

349. Intersection of Two Arrays

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

解法一:用dict存储已经出现的数字,搜索时if num in dict来判该数字是否在另一个数组中出现。

  1. class Solution:
  2. def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
  3. # 使用哈希表存储一个数组中的所有元素
  4. table = {}
  5. for num in nums1:
  6. table[num] = table.get(num, 0) + 1
  7. # 使用集合存储结果
  8. res = set()
  9. for num in nums2:
  10. if num in table:
  11. res.add(num)
  12. del table[num]
  13. return list(res)
'
运行

解法一:”&“可以取两个set的交集。

  1. class Solution:
  2. def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
  3. return list(set(nums1) & set(nums2))

202. Happy Number

happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解法一:数组

  1. class Solution(object):
  2. def isHappy(self, n):
  3. """
  4. :type n: int
  5. :rtype: bool
  6. """
  7. record = set()
  8. while n not in record:
  9. record.add(n) # add n at first, instead at the end.
  10. sum = 0
  11. for i in str(n):
  12. sum += int(i)**2 # remember to initialize sum
  13. if sum == 1:
  14. return True
  15. else:
  16. n = sum
  17. return False

解法二:快慢指针

  1. class Solution:
  2. def isHappy(self, n):
  3. slow = n
  4. fast = n
  5. while self.get_sum(fast) != 1 and self.get_sum(self.get_sum(fast)):
  6. slow = self.get_sum(slow)
  7. fast = self.get_sum(self.get_sum(fast))
  8. if slow == fast:
  9. return False
  10. return True
  11. def get_sum(self,n):
  12. new_num = 0
  13. while n:
  14. n, r = divmod(n, 10)
  15. new_num += r ** 2
  16. return new_num

Tips: sum of the squares of its digits:

  1. n_str = str(n)
  2. for i in n_str:
  3. new_num+=int(i)**2
  1. # Extract digits using % and //
  2. while number > 0:
  3. digit = number % 10 # Get the last digit
  4. result += digit**2 # Add the square of the digit to the result
  5. number //= 10 # Remove the last digit
'
运行
  1. while n:
  2. n, r = divmod(n, 10)
  3. new_num += r ** 2
'
运行

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution1:字典法

  1. class Solution(object):
  2. def twoSum(self, nums, target):
  3. """
  4. :type nums: List[int]
  5. :type target: int
  6. :rtype: List[int]
  7. """
  8. record={}
  9. for i in range(len(nums)):
  10. if target - nums[i] in record: # 互补的值已经被记录在了dict中吗?如果是的话,直接report记录中这个值所对应的位置
  11. return [record[target - nums[i]],i]
  12. record[nums[i]] = i # 值nums[i]所对应的位置i
  13. return [] #别忘了没找到配对的情况下return空

Solution2:排序后使用双指针法

注意!由于这里需要return的是原array里元素的序号,所以先用enumerate把原序号和元素的值记录下来[(0,2), (1,7), (2,11), (3,15)] 这样。然后再使用sorted(nums, key=lambda x: x[1]), 按照元素的值从小到大排序。最后return的时候由小到大输出排序后的原序号sorted([nums[l][0], nums[r][0]])。

  1. class Solution(object):
  2. def twoSum(self, nums, target):
  3. """
  4. :type nums: List[int]
  5. :type target: int
  6. :rtype: List[int]
  7. """
  8. nums = list(enumerate(nums))
  9. print(nums)
  10. # Sort based on the values
  11. nums = sorted(nums, key=lambda x: x[1])
  12. print(nums)
  13. # Initialize two pointers
  14. l, r = 0, len(nums) - 1
  15. while l < r:
  16. current_sum = nums[l][1] + nums[r][1]
  17. if current_sum == target:
  18. # Return the sorted indices
  19. return sorted([nums[l][0], nums[r][0]])
  20. elif current_sum < target:
  21. l += 1
  22. else:
  23. r -= 1
  24. # If no solution is found
  25. return []

都是O(n)的时间复杂度

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/812175
推荐阅读
相关标签
  

闽ICP备14008679号