今日任務(wù)
● 哈希表理論基礎(chǔ)
● 242.有效的字母異位詞
● 349. 兩個(gè)數(shù)組的交集
● 202. 快樂(lè)數(shù)
● 1. 兩數(shù)之和
詳細(xì)布置
哈希表理論基礎(chǔ)
文章講解：
了解哈希表的內(nèi)部實(shí)現(xiàn)原理，哈希函數(shù)，哈希碰撞，以及常見(jiàn)哈希表的區(qū)別，數(shù)組，set 和map。
什么時(shí)候想到用哈希法，當(dāng)我們遇到了要快速判斷一個(gè)元素是否出現(xiàn)集合里的時(shí)候，就要考慮哈希法。 這句話很重要，大家在做哈希表題目都要思考這句話。
242.有效的字母異位詞
給定兩個(gè)字符串 s 和 t ，編寫(xiě)一個(gè)函數(shù)來(lái)判斷 t 是否是 s 的字母異位詞。
示例 1: 輸入: s = "anagram", t = "nagaram" 輸出: true
示例 2: 輸入: s = "rat", t = "car" 輸出: false
說(shuō)明: 你可以假設(shè)字符串只包含小寫(xiě)字母。
python
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
s_dict = {}
for c in s :
if(s_dict.get(c)):
s_dict[c] += 1
else :
s_dict[c] = 1
for c in t:
if(s_dict.get(c) == None or s_dict[c] <= 0) :
return False
else :
s_dict[c] -= 1
for value in s_dict.values():
if (value != 0) :
return False
return True
c++
class Solution {
public:
bool isAnagram(string s, string t) {
std::unordered_map<char, int> s_dict;
for(int i = 0; i < s.size(); i++) {
s_dict.find(s[i]) == s_dict.end() ? s_dict[s[i]] = 1 : s_dict[s[i]] += 1;
}
for(int i = 0; i <t.size(); i++) {
if( s_dict.find(t[i]) == s_dict.end() ) return false;
s_dict[t[i]] -= 1;
}
for(auto iter: s_dict) {
if(iter.second != 0) {
return false;
}
}
return true;
}
};
349. 兩個(gè)數(shù)組的交集
python
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
s1 = set(nums1)
res = set()
for i in nums2:
if i in s1:
res.add(i)
return list(res)
c++
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> s_1(nums1.begin(), nums1.end());
unordered_set<int> res;
for(int i = 0; i < nums2.size(); i++) {
if(s_1.find(nums2[i]) != s_1.end()) {
res.insert(nums2[i]);
}
}
return vector<int>(res.begin(),res.end());
}
};
202. 快樂(lè)數(shù)
題目鏈接/文章講解：
力扣題目鏈接
編寫(xiě)一個(gè)算法來(lái)判斷一個(gè)數(shù) n 是不是快樂(lè)數(shù)。
「快樂(lè)數(shù)」定義為：對(duì)于一個(gè)正整數(shù)，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和，然后重復(fù)這個(gè)過(guò)程直到這個(gè)數(shù)變?yōu)?1，也可能是 無(wú)限循環(huán) 但始終變不到 1。如果 可以變?yōu)? 1，那么這個(gè)數(shù)就是快樂(lè)數(shù)。
如果 n 是快樂(lè)數(shù)就返回 True ；不是，則返回 False 。
示例：
輸入：19
輸出：true
解釋?zhuān)?br>
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
python
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
nums = set()
res = n
while (res not in nums) :
nums.add(res)
m = 0
while(res > 0) :
i = res % 10
m += i*i
res = res /10
res = m
if res == 1 :
return True
return False
c++
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> nums;
int res = n;
while(nums.find(res) == nums.end()) {
nums.insert(res);
int m = 0;
while(res > 0) {
int i = res % 10;
m += i * i;
res /= 10;
}
res = m;
if(res == 1) {
return true;
}
}
return false;
}
};
1. 兩數(shù)之和
力扣題目鏈接
題目鏈接/文章講解/視頻講解
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
python
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
target_nums = dict()
for i, n in enumerate(nums):
t = target - n
if t in target_nums:
return [i, target_nums[t]]
else :
target_nums[n] = i
c++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> target_nums;
vector<int> res;
for(int i = 0; i < nums.size(); i++) {
int n = target - nums[i];
if(target_nums.find(n) != target_nums.end()) {
res.push_back(target_nums[n]);
res.push_back(i);
} else {
target_nums[nums[i]] = i;
}
}
return res;
}
};
