706. 設(shè)計(jì)哈希映射
沒(méi)有想到resize可以這樣用，要不然就做不出來(lái)了~
鏈地址法還沒(méi)有熟練掌握。
方法一 自己瞎寫(xiě)的用vector
這里因?yàn)轭}目說(shuō)0 <= key, value <= 10^6，才能用key當(dāng)index這樣做，但凡有小于0的key這個(gè)方法就不適用了。
class MyHashMap {
public:
/** Initialize your data structure here. */
vector<int> fakeH;
MyHashMap() {
}
/** value will always be non-negative. */
void put(int key, int value) {
if(fakeH.size() <= key){
fakeH.resize(key+1,-1);
}
fakeH[key] = value;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
if(key < fakeH.size() && fakeH[key]!=-1) return fakeH[key];
else return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
if(key < fakeH.size())
fakeH[key] = -1;
}
};
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/
方法二 鏈地址法
? C++ list的用法
本題考查我們對(duì)于實(shí)現(xiàn)哈希表，有哪些方法，分別有什么利弊？
實(shí)現(xiàn)哈希表的原理，其實(shí)我們會(huì)遇到一個(gè)抉擇，那就是時(shí)間和空間的取舍。
實(shí)現(xiàn)方式有兩種：
超大數(shù)組：不考慮空間復(fù)雜度，創(chuàng)建超大數(shù)組，每個(gè)數(shù)都能單獨(dú)存入，且不會(huì)位置沖突。
鏈地址法：空間/時(shí)間的最佳實(shí)踐，基于數(shù)組實(shí)現(xiàn)，并且通過(guò)一個(gè) hashhash 函數(shù)生成一個(gè)對(duì)應(yīng)的索引，當(dāng)多個(gè)數(shù)索引一致的時(shí)候，再處理沖突問(wèn)題，一般我們使用鏈地址法解決沖突。
class MyHashMap {
private:
vector<list<pair<int, int>>> data;
static const int base = 769;
static int hash(int key) {
return key % base;
}
public:
MyHashMap(): data(base) {}
void put(int key, int value) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it).first == key) {
(*it).second = value;
return;
}
}
data[h].push_back(make_pair(key, value));
}
int get(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it).first == key) {
return (*it).second;
}
}
return -1;
}
void remove(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it).first == key) {
data[h].erase(it);
return;
}
}
}
};
740. 刪除并獲得點(diǎn)數(shù)
這道題可以算打家劫舍的plus版本，也是選定一個(gè)數(shù)字，與它相鄰的兩個(gè)數(shù)字帶來(lái)的增益點(diǎn)數(shù)就不能算了。
但是把它轉(zhuǎn)變成打家劫舍問(wèn)題，首先得創(chuàng)建一個(gè)數(shù)組，數(shù)組的index表示，待刪除的數(shù)，vals[index]表示刪除這個(gè)數(shù)所獲得的增益值是多少。
方法一 轉(zhuǎn)變?yōu)榇蚣医偕釂?wèn)題
class Solution {
public:
int robe(vector<int>&nums){
int n = nums.size();
int a = nums[0], b = max(nums[0],nums[1]);
for(int i = 2; i < n; i++){
int t = max(a+(nums[i]),b);
a = b;
b = t;
}
return b;
}
int deleteAndEarn(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];
int maxVal = 0;
for(auto it:nums){
maxVal = max(maxVal,it);
}
vector<int> vals(maxVal+1,0);
for(auto it:nums){
vals[it]+=it;
}
return robe(vals);
}
};
時(shí)間復(fù)雜度：O(N+M)，其中 N 是數(shù)組nums 的長(zhǎng)度，M 是 nums 中元素的最大值。
空間復(fù)雜度：O(M)。
方法二 排序+動(dòng)態(tài)規(guī)劃
class Solution {
public:
int robe(vector<int>&nums){
int n = nums.size();
// if(n == 0) return 0;
if(n == 1) return nums[0];
int a = nums[0], b = max(nums[0],nums[1]);
for(int i = 2; i < n; i++){
int t = max(a+(nums[i]),b);
a = b;
b = t;
}
return b;
}
int deleteAndEarn(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];
int maxVal = 0;
sort(nums.begin(),nums.end());
vector<int> sums = {nums[0]};
int ans = 0;
for(int i =1; i< n; i++){
int val = nums[i];
if(val == nums[i-1]){
sums.back() += val;
}else if(val == nums[i-1]+1){
sums.push_back(val);
}else{
ans += robe(sums);
sums = {val};
}
}
return ans+robe(sums);
}
};
