京东笔试 京东笔试第三题 漂亮串
关于第三题 求大神指导 自己想的对不对
漂亮串我想到了思路 但是一直不知道怎么在O(1)的时间计算出排列组合
首先漂亮串必须大于等于6
那么如果n >=6 那么这里面可以包含[2, n / 3]个red
我们分别计算[2, n / 3]有多少种排列组合
假设当前red = 2 那么考虑这两个red怎么放 然后乘以(n - red * 2)^26
假设当前red = 3 那么考虑这三个red怎么放 然后乘以(n - red * 3)^26
假设当前red = 4 那么考虑这四个red怎么放 然后乘以(n - red * 4)^26
...
直到 red = n / 3
问题就是怎么去计算red的个数确定后 red有多少种方法,也就是如何在O(1)的复杂度中从n个数中选出k个不重叠的区间且区间的长度= 3
然后指数运算时用快速幂算法
首先漂亮串必须大于等于6
那么如果n >=6 那么这里面可以包含[2, n / 3]个red
我们分别计算[2, n / 3]有多少种排列组合
假设当前red = 2 那么考虑这两个red怎么放 然后乘以(n - red * 2)^26
假设当前red = 3 那么考虑这三个red怎么放 然后乘以(n - red * 3)^26
假设当前red = 4 那么考虑这四个red怎么放 然后乘以(n - red * 4)^26
...
直到 red = n / 3
问题就是怎么去计算red的个数确定后 red有多少种方法,也就是如何在O(1)的复杂度中从n个数中选出k个不重叠的区间且区间的长度= 3
然后指数运算时用快速幂算法
有没有大佬指点下 这个对吗?