哈希表
哈希表主要是使用 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
刷题
多数元素
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;
}
};
整数转罗马数字
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;
}
};
原文地址:https://blog.csdn.net/beidideshu/article/details/134786091
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_44312.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。