模拟:扑克洗牌
约 10 分钟
洗牌题给你一套固定的重排规则,让你重复洗若干次,输出结果。关键心法是:先把"洗一次"这个动作写对、写干净,再用循环重复调用它。一次都写错,循环再多也是错的。
"洗一次"通常是按某个规则把每张牌搬到新位置:
void shuffleOnce(vector<int>& a) {
int n = a.size();
vector<int> b(n);
for (int i = 0; i < n; i++)
b[newPos(i)] = a[i]; // 按规则算新位置
a = b; // 用新牌堆整体覆盖
}
// 主程序里
for (int t = 0; t < times; t++) shuffleOnce(a);
坑:一定要用临时数组 b 存结果,边搬边改原数组会互相覆盖;新旧位置的下标从 0 还是 1 开始要统一。
进阶技巧:如果要洗成千上万次,会发现牌的位置最终会循环,先求出循环周期 ,再对 times % T 取模,把复杂度从 降到 。
小纸条
为什么要先写对一次,再循环?
登录 后可看答案