哈希表
哈希表主要是使用 map、unordered_map、set、unorerdered_set、multi_，完成映射操作，主要是相应的函数。map和set是有序的，使用的是树的形式，unordered_map和unordered_set使用的是散列比表的，无序。
相应函数
set multiset
map multimap
unordered_map unordered_multimap
unordered_set unordered_multiset
刷题
多数元素
最朴素的方法，map统计，绷不住了，嘎嘎嘎
class Solution {
public:
int majorityElement(vector<int>& nums) {
map<int,int> d;
for(int i=0;i<nums.size();i++){
d[nums[i]]++;
if(d[nums[i]]>nums.size()/2){
return nums[i];
}
}
return 0;
}
};
罗马数字转整数
只根据规定的格式进行匹配
class Solution {
public:
int romanToInt(string s) {
map<char,int> d;
d['I'] = 1;
d['V'] = 5;
d['X'] = 10;
d['L'] = 50;
d['C'] = 100;
d['D'] = 500;
d['M'] = 1000;
char last;
int sum = 0;
for(int i =0;i<s.length();i++){
sum += d[s[i]];
if(last == 'I'&&(s[i]=='V'| s[i]=='X')){
sum-=2;
last = ' ';
} else if(last == 'X'&& (s[i]=='L'| s[i]=='C')){
sum-=20;
last = ' ';
}else if(last=='C'&&(s[i]=='D'| s[i]=='M')){
sum-=200;
last = ' ';
}else{
last = s[i];
}
}
return sum;
}
};
整数转罗马数字
直接暴力if eiseif，绷不住了
class Solution {
public:
string intToRoman(int num) {
map<int,char> d;
d[1] = 'I';
d[5] = 'V';
d[10] = 'X';
d[50] = 'L' ;
d[100] ='C';
d[500] = 'D';
d[1000] = 'M' ;
string s;
int n=num;
while(n>0){
if(n/1000){
s.push_back(d[1000]);
n-=1000;
}else if(n/500){
if(n>=900){
s.push_back(d[100]);
s.push_back(d[1000]);
n-=900;
}else{
s.push_back(d[500]);
n-=500;
}
}else if(n/100){
if(n>=400){
s.push_back(d[100]);
s.push_back(d[500]);
n-=400;
}else{
s.push_back(d[100]);
n-=100;
}
}else if(n/50){
if(n>=90){
s.push_back(d[10]);
s.push_back(d[100]);
n-=90;
}else{
s.push_back(d[50]);
n-=50;
}
}else if(n/10){
if(n>=40){
s.push_back(d[10]);
s.push_back(d[50]);
n-=40;
}else{
n-=10;
s.push_back(d[10]);
}
}else if(n/5){
if(n>=9){
s.push_back(d[1]);
s.push_back(d[10]);
n-=9;
}else{
n-=5;
s.push_back(d[5]);
}
}else{
if(n>=4){
s.push_back(d[1]);
s.push_back(d[5]);
n-=4;
}else{
n-=1;
s.push_back(d[1]);
}
}
}
return s;
}
};
电话号码的字母组合
就是暴力，emm，题解挺简单的,用一个map存储映射，然后开始暴力操作。
class Solution {
public:
vector<string> letterCombinations(string digits) {
map<int,string> m;
m['2']="abc";
m['3']="def";
m['4']="ghi";
m['5']="jkl";
m['6']="mno";
m['7']="pqrs";
m['8']="tuv";
m['9']="wxyz";
vector<string> data;
for(int i=0;i<digits.length();i++){
vector<string> d;
d=data;
data.clear();
string digi = m[digits[i]];
for(int j=0;j<digi.length();j++){
if(d.empty()){
string aaa;
aaa+=digi[j];
data.push_back(aaa);
}else{
for(int h=0;h<d.size();h++){
data.push_back(d[h]+digi[j]);
}
}
}
}
return data;
}
};
存在重复元素
就一个集合解决
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
set<int> data;
for(int i=0;i<nums.size();i++){
if(data.find(nums[i])==data.end()){
data.insert(nums[i]);
}else{
return true;
}
}
return false;
}
};
重复元素2
用一个映射存储数据，直接遍历，可能某个元素会出现多此，所以需要进行一个map位置的实时更新。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
map<int,int> m;
for(int i=0;i<nums.size();i++){
if(m.find(nums[i])!=m.end()){
if((i-m[nums[i]])<=k){
return true;
}else{
m[nums[i]]=i;
}
}else{
m[nums[i]]=i;
}
}
return false;
}
};
