hijackedbycsdn的博客

如果有三个人，那么 1 号不能独吞，他至少要争取一个人的支持，而要争取的那个人可以是 2 或者 3，那么应该选择 3，因为 2 可能会反对，因为如果能把 1 号投掉，会回到只有两个人的情况，那么 2 号一定稳拿 100，所以 1 号必须要争取 3 号，而要争取 3 号，只用给 3 号一个金币就行了，因为如果 3 号不支持 1 号，1 号就可能被投掉，那么回到只有两个人的情况，3 号一个金币也拿不到，所以只要分到 1 个金币，3 号一定会支持 1 号；若只剩唯一可提出的方案，则此方案直接通过。

又因为在环中的指针走整数倍的圈数不影响它的位置，所以新指针走 a 步走到了入环点，而 slow 指针走的 c + (n - 1)(b + c) 步，原来在 b 步的位置，现在其实就是 b + c + (n - 1)(b + c) = n(b + c)，%(b + c) 得 0，也就是 slow 指针也走到了入环点。首先其实要知道的是，在环中，假设以入环点为序号 0，某个指针现在的序号为 i，环的长度为 len，那么如果你在环中某一个走了 n 步，你接下来的序号为 (n + i) % len。

问题还是出在左右侧和相等的时候……这题如果要用两个数组，一个数组记录从位置 0 到 i 中出现的 0 的个数，一个数组记录从位置 0 到 i 中出现的 1 的个数。那么之后的 1 1 1 0 0 其实还可以与前面的 1 1 0 0 一起考虑，得到 一个 0 0 1 1 1 0 的连续子数组。更进一步，这个 pre 数组的更新可以和 j 的查找放在同一个 i 循环中，因为查找 j 的时候用不到以后的没遍历到的 i。之后看了题解，说是把数组中的 0 转化成 - 1，然后转化成和为 0 的最长连续子数组的问题。

这个很好理解，因为异或是不进位加法，所以如果自己加自己，只存在 1 和 1 相加，0 和 0 相加这两种情况，其中 0 和 0 相加自然得 0，1 和 1 相加本来是有进位的，但是由于异或是不进位加法，所以 1 和 1 相加也得 0，并且没有进位，对其他位没有产生影响，所以全都得 0，结果就是 0。所以综上所述，我们就可以对于任意一个 x，知道它的最高位的 1 的位置，然后使用这个信息把 x 拆成 y + z，然后就得到状态转移方程 dp[x] = d[z] + 1，其中 dp[z] 已知。

就比如我这里，数组中的元素刚好为 n 时他会少一些元素，而之所以会少，是因为没有考虑到这 n 个元素中所有元素所产生的新的丑数，也就是说只考虑到了前面的一些丑数，序号为 n-2 n-1 n 的丑数可能产生的新丑数没有考虑。显然，如果这个数小于 100，那么一次也不出现，如果这个数在 100 ~ 199 之间，那么出现 1 的次数就是 num - 100 + 1，如果大于 199，那么就是出现了 100 次。但是很显然，我明明是从小的丑数生成大的丑数，我明明是已经有了一个大小关系的，只是我不能一下子找到。

一开始我还在想类似基数排序的方法比如我会想3033459这个顺序，会不会是先排每个数的最高的位数，然后再排第二高的位数如果某个数没有第二个位数，那么就复制前面的位数比如303(3)345(5)9(9)之后想到百位数啊千位数啊，我就晕了之后看题解才知道还可以直接通过两两之间的拼接结果的比较，来得到整个序列的最小拼接结果感觉这应该是要用离散数学证明……？不懂一开始比较 和 我是这么写的虽然对于简单的例子能行，但是对于大数来说会溢出最后还是复制了别人的题解规则是，如果 代表 这样就遵循了传统的从小到

目录剑指 Offer第 1 天 栈与队列（简单）剑指 Offer 09. 用两个栈实现队列剑指 Offer 30. 包含min函数的栈算法运行的每一步保存一次状态第 2 天 链表（简单）剑指 Offer 06. 从尾到头打印链表剑指 Offer 24. 反转链表剑指 Offer 35. 复杂链表的复制第 3 天 字符串（简单）剑指 Offer 05. 替换空格剑指 Offer 58 - II. 左旋转字符串第 4 天 查找算法（简单）剑指 Offer 03. 数组中重复的数字原地交换 把 x 交换到 arr