牛客刷题系列之进阶版（幸运的袋子，06-散列查找1 电话聊天狂人，前K个高频单词）

#include<iostream>
#include<algorithm>
using namespace std;
int get(int* arr,int n,int pos,int add,int multi) //pos：访问到的位置   add：加到了多少  multi; 乘到了多少
{
    int count =0;
    for(int i=pos;i<n;i++)
    {
       add+=arr[i];
        multi*=arr[i];
        
        if(add > multi) //假如add > multi ， 该条件满足，并且往下面找满足的条件
        {
            count+=1+ get(arr,n, i+1,add,multi);
        }
        else if(arr[i]==1) //假如arr[i]==1 ，则该条件无效， 向后面找寻有效条件
            count+= get(arr,n, i+1,add,multi);
        
        else
            break;
        
        add-=arr[i];
        multi/=arr[i];
        while (i < n - 1 &amp;&amp; arr[i] == arr[i + 1]) //将相同项移出，不再假如循环
        {
            i++;
        }
    }
    return count;
  
}
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n); //先将数组排序
    cout<< get(arr,n,0,0,1);
    
      
 return 0;
}

#include<iostream>
#include<vector>
#include<map>
using namespace std;

int main()
{
    map<long long, long long, greater<long long>> a; //利用map来记录，注意仿函数要用 greater<long long> 的，要将最小的在后面再访问
    int n;
    cin >> n;
    while (n--)
    {
        long long tem;
        cin >> tem;

        a[tem]++;
        cin >> tem;
        a[tem]++;
    }
    unsigned long long max = 0, ret = -1;
    int count = 0;
    for (auto&amp; e : a)
    {
        if (max < e.second)
        {
            max = e.second;
            ret = e.first;
            count = 1; //注意
       }
        else if (max == e.second)
        {
           ret = e.first; //因为仿函数是greater<long long>，如果出现次数相同，则后面出现的必然会更小
           count++;
        }
    }
   
    cout << ret << " " << max;
    if (count > 1)
        cout << " " << count;
}

class Solution {
public:
    vector<string> topKFrequent(vector<string>&amp; words, int k) {
          //sort不稳定,堆排序也一样
          //用两个map来排序
          map<string,int> countMap;
          for(auto&amp; e: words)
          {
              countMap[e]++;
          }

          multimap<int,string,greater<int>> Map; //必须要用multimap，不然出现次数相同的string会被抵消掉
          for(auto&amp; e:countMap )
          {
              Map.insert(make_pair(e.second,e.first));
          }
          auto it = Map.begin();
          vector<string> v;
          while(k--)
          {
               v.push_back(it->second);
               it++;
          }
          return v;
    }
};