本文介绍: 哈希表,主要是对那些函数应用

哈希

哈希表主要是使用 mapunordered_mapset、unorerdered_setmulti_完成映射操作,主要是相应的函数mapset有序的,使用的是树的形式,unordered_mapunordered_set使用的是散列比表的,无序

相应函数

set multiset

相应的地址

map multimap

相应地址

unordered_map unordered_multimap

相应位置

unordered_set unordered_multiset

相应地址

刷题

多数元素

在这里插入图片描述
朴素方法map统计,绷不住了,嘎嘎嘎

class Solution {
public:
    int majorityElement(vector<int&gt;&amp; nums) {
        map<int,int&gt; d;
        for(int i=0;i<nums.size();i++){
            d[nums[i]]++;
            if(d[nums[i]]&gt;nums.size()/2){
                return nums[i];
            }
        }
        return 0;
    }

};

罗马数字整数

在这里插入图片描述
只根据规定的格式进行匹配

class Solution {
public:
    int romanToInt(string s) {
        map<char,int&gt; 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'&amp;&amp;(s[i]=='V'| s[i]=='X')){
                sum-=2;
                last = ' ';
             
            } else if(last == 'X'&amp;&amp; (s[i]=='L'| s[i]=='C')){
                    sum-=20;
                    last = ' ';
            
            }else if(last=='C'&amp;&amp;(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>&amp; 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>&amp; 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进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注