【今日作业】《七月集训》（第07天）——哈希表（自闭，先做两题）

206 阅读 0 评论 136 点赞

我是靠谱客的博主稳重小馒头，这篇文章主要介绍【今日作业】《七月集训》（第07天）——哈希表（自闭，先做两题），现在分享给大家，希望可以做个参考。

七月第七天解题报告

本文实现了超链接跳转，查询题目可直接点击题号跳转LeetCode

题目

970. 强整数

代码演示

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        vector<int>xs, ys;
        int i, j;
        int prex = 1, prey = 1;
        for(i = 1; prex <= bound; ++i){
            xs.push_back(prex);
            prex *= x;
            if(x == 1){
                break;
            }
        }
        for(i = 1; prey <= bound; ++i){
            ys.push_back(prey);
            prey *= y;
            if(y == 1){
                break;
            }
        }
        int hash[1000010];
        memset(hash, 0, sizeof(hash));
        for(i = 0; i < xs.size(); ++i){
            for(j = 0; j < ys.size(); ++j){
                int val = xs[i] + ys[j];
                if(val <= bound){
                    hash[val] = 1;
                }
            }
        }
        vector<int>ans;
        for(i = 1; i <= 1000000; ++i){
            if(hash[i])
                ans.push_back(i);
        }
        return ans;
    }
};

914. 卡牌分组

代码演示

class Solution {
    int gcd(int a,int b){
        return !b ? a : gcd(b, a%b);
    }
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        int hash[10010];
        memset(hash, 0, sizeof(hash));
        for(int i = 0; i < deck.size(); ++i){
            ++hash[ deck[i] ];
        }
        int totgcd = -1;
        for(int i = 0; i < 10000; ++i){
            if(hash[i]){
                if(totgcd == -1){
                totgcd = hash[i];
                }else{
                totgcd = gcd(totgcd, hash[i]);
                }
            }
        }
        return totgcd > 1;
    }
};