第一题是个rand5生成rand7的经典题,关键在于若m>n,则randm()可以直接生成randn(),只要randm()生成1到n之间返回即可,生成的数大于n就重新调用。然后可以用(randm() - 1) * m + randm()来生成1到m^2的随机数。
楼主用三进制的做法,此时命中率是(2*89)/(3^5)178/243
其实也可以生成3^6=729以内的数,然后在8*89=712以内返回,结果对89求余后加1即可,命中率是712/729,只不过每次要多调用1次rand3()。如果要深抠命中率的话就太麻烦了。
第二题好像在哪里看过原题,记录子串起始位置,整个迭代过程中子串保持不含重复字符的性质,每次不能保持该性质时比较下最大长度。写了下还是磕磕绊绊的,主要是之前命名太随意导致各种写错……

int longest_unique_substr_len(const std::string& s) {
    constexpr size_t kInitPos = -1;
    std::vector<size_t> hashmap(26, kInitPos);
    size_t low = 0;
    size_t maxlen = 0;
    for (size_t i = 0; i != s.size(); ++i) {
        size_t key = s[i] - 'a';
        if (hashmap[key] != kInitPos && hashmap[key] >= low) {
            maxlen = std::max(maxlen, i - low);
            low = hashmap[key] + 1;
        }
        hashmap[key] = i;
    }
    return std::max(maxlen, s.size() - low);
}