首页 > 其他分享 >哈希表

哈希表

时间:2024-01-24 11:56:20浏览次数:23  
标签:val int ret stk frequency 哈希 mymap

目录

895最大频率栈


复杂度爆了
简述一下思路:

  1. 用栈来存入栈元素,用哈希表来存出现次数,用一个frequency来记录最大出现次数
  2. 遍历栈,将栈顶元素放到另一个临时栈中,如果栈顶元素的出现次数=frequency,那么说明是最大元素,我就把他出栈然后用临时栈还原stk
  3. 如果遍历了一遍没有相等的,复原栈,frequency--,再遍历栈

优化思路:
感觉可以直接用vector来存元素,省去了出入栈的开销
frequency也可以在遍历的时候记录一个最大的,

class FreqStack {
public:
    FreqStack() {}

    void push(int val) {
        stk.push(val);
        mymap[val]++;
        if (mymap[val] > frequency) {
            frequency++;
        }
    }

    int pop() {
        int ret = -1;
        while (true) {
            while (!stk.empty()) {
                if (mymap[stk.top()] == frequency) {
                    ret = stk.top();
                    stk.pop();
                    break;
                }
                tempstk.push(stk.top());
                stk.pop();
            }
            while(!tempstk.empty())
            {
                stk.push(tempstk.top());
                tempstk.pop();
            }
            if(ret!=-1)
            {
                mymap[ret]--;
                return ret;
            }
            else
            {
                frequency--;
            }
        }

        while (!tempstk.empty()) {
            stk.push(tempstk.top());
            tempstk.pop();
        }
    }

private:
    stack<int> stk;
    stack<int> tempstk;
    unordered_map<int, int> mymap;
    int frequency = 0;
};

优化版本v1

还是有点爆

感觉主要是出在vector的erase上
继续优化:

class FreqStack {
public:
    FreqStack() {}

    void push(int val) {
        stk.push_back(val);
        mymap[val]++;
        if (mymap[val] > frequency)
            frequency++;
    }

    int pop() {
        int nextfrequency = 0;
        // int nextret=-1;
        int ret = -1;
        while (ret == -1) {
            for (int i = stk.size() - 1; i >= 0; i--) {
                if (mymap[stk[i]] == frequency) {
                    ret = stk[i];
                    mymap[ret]--;
                    stk.erase(stk.begin() + i);
                    break;
                } else {
                    if (mymap[stk[i]] > nextfrequency) {
                        nextfrequency = mymap[stk[i]];
                    }
                }
            }
            if(ret==-1)
                frequency=nextfrequency;
        }
        return ret;
    }

private:
    unordered_map<int, int> mymap;
    vector<int> stk;
    int frequency = 0;
};

优化版本v2

这个版本将erase变成=-1,在数据中不去检测为-1的数据,但是没有什么用
还是一样的复杂度

看题解了

我靠还有这种解法
自己写一下

class FreqStack {
public:
    FreqStack() {}

    void push(int val) {
        if (++mymap[val] > stkarr.size())
            stkarr.push_back(stack<int>());
        stkarr[mymap[val] - 1].push(val);
    }

    int pop() {
        int ret=stkarr.back().top();
        stkarr.back().pop();
        mymap[ret]--;
        if(stkarr.back().empty())
        {
            stkarr.pop_back();
        }
        return ret;
    }

private:
    vector<stack<int>> stkarr;
    unordered_map<int, int> mymap;
};

884

哈希表的简单使用,非常简单,但是处理字符串比较繁琐

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        unordered_map<string,int> map1;
        unordered_map<string,int> map2;
        vector<string> ans;

        int slowptr=0;
        for(int i=0;i<s1.length();i++)
        {
            if(s1[i]==' ')
            {
                map1[s1.substr(slowptr, i-slowptr)]++;
                slowptr=i+1;
            }
        }
        map1[s1.substr(slowptr, s1.length()-slowptr)]++;
        slowptr=0;
        for(int i=0;i<s2.length();i++)
        {
            if(s2[i]==' ')
            {
                map2[s2.substr(slowptr, i-slowptr)]++;
                slowptr=i+1;
            }
        }
        map2[s2.substr(slowptr, s2.length()-slowptr)]++;
        for(auto itr:map1)
        {
            if(itr.second==1&&map2.find(itr.first)==map2.end())
            {
                ans.push_back(itr.first);
            }
        }
        for(auto itr:map2)
        {
            if(itr.second==1&&map1.find(itr.first)==map1.end())
            {
                ans.push_back(itr.first);
            }
        }
        return ans;
    }
};

846一手顺子

用map记录手中的牌,map中自带key值排序,再去遍历就可以了

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        int n=hand.size();
        if(n%groupSize!=0)
        {
            return false;
        }
        map<int,int> mymap;
        for(int i=0;i<n;i++)
        {
            mymap[hand[i]]++;
        }
        int x=n/groupSize;
        for(int i=0;i<x;i++)
        {
            int value=mymap.begin()->first;
            for(int j=0;j<groupSize;j++)
            {
                if(mymap.find(value)==mymap.end())
                {
                    return false;
                }
                mymap[value]--;
                if(mymap[value]==0)
                {
                    mymap.erase(value);
                }
                value++;
            }
        }
        return true;

    }
};

标签:val,int,ret,stk,frequency,哈希,mymap
From: https://www.cnblogs.com/liviayu/p/17984348

相关文章

  • 哈希学习笔记+杂题(进阶1 字符串哈希)
    哈希杂题前言:竟然下雪了,但是天是灰蒙蒙的。一、哈希学习笔记+杂题(进阶1字符串哈希)相关题单:戳我字符串哈希因为是一种玄学做法,所以具有极强的延展性。所以再碰到字符串的题时,抛开马拉车,kmp,字典树,AC自动机,SA&SAM,先想一下哈希的做法,如果时间复杂度允许,那就可以直接上哈希(虽然你......
  • 哈希学习笔记+杂题(进阶1 字符串哈希)
    哈希杂题前言:竟然下雪了,但是天是灰蒙蒙的。一、哈希学习笔记+杂题(进阶1字符串哈希)相关题单:戳我字符串哈希因为是一种玄学做法,所以具有极强的延展性。所以再碰到字符串的题时,抛开马拉车,kmp,字典树,AC自动机,SA&SAM,先想一下哈希的做法,如果时间复杂度允许,那就可以直接上哈希(虽然你......
  • 哈希学习笔记+杂题(基础2 字符串哈希)
    哈希杂题前言:骗分神器,我之前竟然没有学。一、哈希学习笔记+杂题(基础2字符串哈希)相关题单:戳我1.哈希(hash)简介哈希算法(HashAlgorithm),又称散列算法。有两种用法,第一种就是将一字符串转化成任意进制的数,目的是方便存储。第二种就是将大范围的数映射成小范围的数,目的也是方便存......
  • 线性表(散列)- 哈希表
    哈希表散列表(Hashtable,也叫哈希表),是根据关键码值(Keyvalue)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表HashSetandHashMap哈希表使用O(N)空间复杂度存储数据,并......
  • CF-1831-E-卡特兰数+异或哈希+差分
    1831-E题目大意给定一个整数\(n\),和\(k\)个区间,区间端点范围在\([1,n]\)内。如果有一个长为\(n\)合法的括号序列,且它的这\(k\)个区间\([l,r]\)中的子括号序列也是合法的,那么称这个括号序列是“好的”。请你求出有多少个长度为\(n\)的“好的”括号序列,答案对\(998244353\)取模......
  • 哈希表
    当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法1.JavaHashMapgetOrDefault()方法importjava.util.HashMap;classMain{  publicstaticvoidmain(String[]args){    //创建一个HashMap    HashMap<Integer,String>s......
  • 「笔记」哈希
    目录写在前面哈希是什么?写在最后写在前面大部分内容来自高中时期讲课PPT,在这里整理成了适合自学的形式。哈希是什么?一种用于统计复杂信息的的不完美算法。构造一个满射[1]的哈希函数,将复杂信息映射到便于统计的信息上。丢失了部分信息。写在最后进度有点太赶了!题单太难......
  • 哈希表的应用
    也是滑动窗口的应用,但用到了哈希表。哈希表一个索引,一个真值。索引可以是任何符号,因此可以表示一个事物的数量关系和对应关系.删除某个索引及真值时,要用迭代器,erase(it)。find是查找索引返回迭代器。点击查看代码classSolution{public:inttotalFruit(vector<int>&fr......
  • php rsa加密(非对称)实例 以及使用哈希256进行加密
    functiongetEncryptionUserID($client_secret):string{$str="-----BEGINPUBLICKEY-----MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCpw/k/rPHx4c1nEO8lQr8Fkz2MMTnqNbspRox1f2snoDNcssTQxg9TyBOMujQy14eRibKE+X+qPVeZJyyfruTrtvB4EomJL7v4URcacg7H00A2HL1nf7......
  • 字母异位词分组【哈希】
    Problem:49.字母异位词分组文章目录思路解题方法复杂度Code思路hash解题方法对于每一个字符串,都按字符从小打到进行排序,然后用hash去存,如果排序后的结果在hash表里面存在的话,那么就只需要把这个字符串加入进行;如果不存在,就新建一个键值对就可以了。关键就是字符串没有排序,所以......