第一题是个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);
}