算法工程師第五天（● 哈希表理論基礎 ● 242.有效的字母異位詞 ● 349. 兩個數組的交集 ● 202. 快樂數● 1. 兩數之和）

參考文獻代碼隨想錄

一、有效的字母異位詞

給定兩個字符串?s?和?t?，編寫一個函數來判斷?t?是否是?s?的字母異位詞。

注意：若?s?和?t?中每個字符出現的次數都相同，則稱?s?和?t?互為字母異位詞。

示例?1:

輸入: s = "anagram", t = "nagaram"
輸出: true

示例 2:

輸入: s = "rat", t = "car"
輸出: false

提示:

1 <= s.length, t.length <= 5 * 104
s?和?t?僅包含小寫字母

解法1：在python中使用統計某個字符，然后在判斷與另外一個列表中的字符是否相等，需要注意的是，它們的長度必須相等，如果不想等的話，那么久返回False，一下這個方法僅供參考，因為本人也沒有通過（超時）超時的原因：就是你每次都要尋找一次，有寫字母已經判斷過了，但是這個思路仍然需要進行統計字符出現的次數，而且統計字母次數的時間復雜度為O（n），所以就超時了

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""# 可以把它們轉化為列表的形式，然后在統計每個字母的次數是否已與另外一個字符列表相等(兩個字符列表相等的情況下，還有不相等的情況，那肯定就返回False)sList = list(s)tList = list(t)if len(sList) != len(tList):return Falsefor char in sList:if sList.count(char) != tList.count(char):return Falsereturn True

解法二：通過字典來計數，先統計提一個字符串中每個字符出現的次數，然后，在根據另外一個字符串中每個字母出現，來--，如果，對應的值都為0，說明，兩個字符串中每個字母出現的次數剛好相等，否則，要么一個字符的字母多了，或者少了。

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""# 定義一個列表，存放的是每個字母出現的個數，然后初始值都為0，先遍歷一個列表，左++，另外一個列表做--，如果定義的這個列表中出現了不是為0的說明，要么一個列表多了，要么少了indexList = [0] * 26for i in s:  # 先統計s這個字符串每個字母出現的次數indexList[ord(i) - ord("a")] += 1for i in t:  # 遍歷t上一個字符串中每個字母出現的次數做--，操作，如果為零，說明s,和，t的每個字符出現的次數同一樣indexList[ord(i) - ord("a")] -= 1for i in indexList:if i != 0:return Falsereturn True

二、兩個數組的交集

給定兩個數組?nums1?和?nums2?，返回?它們的?交集?。輸出結果中的每個元素一定是?唯一?的。我們可以?不考慮輸出結果的順序?。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]

示例 2：

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]
解釋：[4,9] 也是可通過的

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

解法1：判斷第一個數組里面的元素是否在另外一數組里面，如果存在，那么就添加到另外一臨時數組里，否則什么也不做操作。

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""aid = []for i in nums1:if i in nums2:aid.append(i)return list(set(aid))

解法二：使用集合，求交集即可

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""a = set(nums1)b = set(nums2)return list(a & b)

解法三：使用2個數組，分別存儲每個列表中的元素，如果兩個列表對應的值大于1，說明了，是交集

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""aid1 = [0] *  1001aid2 = [0] * 1001for i in nums1:aid1[i] += 1for j in nums2:aid2[j] += 1r = []for i in range(1001):if aid1[i] * aid2[i] > 0:r.append(i)return r

三、快樂數

編寫一個算法來判斷一個數?n?是不是快樂數。

「快樂數」?定義為：

對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
然后重復這個過程直到這個數變為 1，也可能是?無限循環?但始終變不到 1。
如果這個過程?結果為?1，那么這個數就是快樂數。

如果?n?是?快樂數?就返回?true?；不是，則返回?false?。

示例 1：

輸入：n = 19
輸出：true
解釋：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

輸入：n = 2
輸出：false

提示：

1 <= n <= 231 - 1

問題分析：首先要考慮的是，如何防止死循環，可以使用一個列表來存儲，如果它出現了2次說明已經死循環，就可以調出了，否則就添加到列表中，然后統計每個各位上平方之和，在判斷是否為1，如果不是那么就要跟新到n的值

class Solution(object):def isHappy(self, n):""":type n: int:rtype: bool"""record = []  # 為了下面的判斷，不要陷入死循環while n not in record:record.append(n)  # 把這個數添加到列表中，防止死循環num_sum = 0  # 記錄每次數的各個位上平方之和n_str = str(n)for i in n_str:num_sum += int(i) ** 2if num_sum == 1:  # 如果各個位上平方之和 == 1說明已經找到了return Trueelse:  # 否則跟新nn = num_sumreturn False

四、兩數之和

????????給定一個整數數組?nums?和一個整數目標值?target，請你在該數組中找出?和為目標值?target? 的那?兩個?整數，并返回它們的數組下標。你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。

你可以按任意順序返回答案。

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]

示例 3：

輸入：nums = [3,3], target = 6
輸出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只會存在一個有效答案

問題分析：我們可以把當前遍歷的數添加到一個數組或者是字典里，然后在循環里，先判斷目標數-當前循環的元素是否在之前的數組或者是字典里，如果在那么返回對應的下標，如果不在，則返回空數組

數組版本：

????????在Python中，對于頻繁的數據訪問操作，數組（通常指列表，即list類型）和字典（dict類型）的效率差別不大。數組的訪問時間復雜度是O(1)，而字典的平均時間復雜度是O(1)，看起來似乎都是常數級別的時間復雜度。

但在特定情況下，數組和字典的表現可能會有明顯差異：

數組（列表）：適合當你需要通過索引來快速訪問元素，或者在列表末尾頻繁添加或刪除元素。
字典：適合當你需要通過鍵來快速訪問元素，并且不關心元素的順序或者它們的添加/刪除頻率。

如果你需要頻繁地通過鍵來訪問元素，并且不需要關心元素的順序，使用字典會更高效。

如果你需要保持元素的插入順序，并且需要通過索引來頻繁訪問元素，或者你需要在列表的任意位置頻繁插入和刪除元素，使用數組（列表）會更高效。

在實際應用中，除非有極端的性能需求，否則通常不需要過度關注哪個更高效，而是根據需求選擇合適的數據結構

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""# 使用的是數組li = [100000000000000] * 100000for index, value in enumerate(nums):if target - value in li:  # 就是用目標值減去當前遍歷的值，然后在判斷剩下的部分是否在之前的字典中return [li.index(target - value), index]li[index] = valuereturn []

字典版本：

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""# 使用的是字典aid = {}for index, value in enumerate(nums):if target - value in aid:  # 就是用目標值減去當前遍歷的值，然后在判斷剩下的部分是否在之前的字典中return [aid[target - value], index]aid[value] = indexreturn []
為什么不寫aid[index] = value呢？因為當你查找剩下的數的下標的時候不知道，這時你就知道當前元素的下標而已，但你不知道剩下元素的下標是多少，也可以使用其它方法來尋找，但是這些方法不常用