给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。
示例 1：
输入：nums = [21,4,7] 输出：32 解释： 21 有 4 个因数：1, 3, 7, 21 4 有 3 个因数：1, 2, 4 7 有 2 个因数：1, 7 答案仅为 21 的所有因数的和。
示例 2:
输入: nums = [21,21] 输出: 64
示例 3:
输入: nums = [1,2,3,4,5] 输出: 0
提示：
登录
1 <= nums.length <= 1041 <= nums[i] <= 105对于一个数，它有哪些因子？这不能一眼看出来。
但反过来，对于一个数 $i$，$i$ 的倍数都有因子 $i$。
枚举 $i=1,2,3,\ldots,10^5$，以及 $i$ 的倍数 $j$，把 $j$ 的因子个数加一，因子和加上 $i$。
对于 $\textit{nums}$ 中的因子个数为 $4$ 的元素，累加这些元素的因子和，即为答案。
###py
MX = 100_001
divisor_num = [0] * MX
divisor_sum = [0] * MX
for i in range(1, MX):
for j in range(i, MX, i): # 枚举 i 的倍数 j
divisor_num[j] += 1 # i 是 j 的因子
divisor_sum[j] += i
class Solution:
def sumFourDivisors(self, nums: List[int]) -> int:
ans = 0
for x in nums:
if divisor_num[x] == 4:
ans += divisor_sum[x]
return ans
###java
class Solution {
private static final int MX = 100_001;
private static final int[] divisorNum = new int[MX];
private static final int[] divisorSum = new int[MX];
private static boolean initialized = false;
// 这样写比 static block 快
public Solution() {
if (initialized) {
return;
}
initialized = true;
for (int i = 1; i < MX; i++) {
for (int j = i; j < MX; j += i) { // 枚举 i 的倍数 j
divisorNum[j]++; // i 是 j 的因子
divisorSum[j] += i;
}
}
}
public int sumFourDivisors(int[] nums) {
int ans = 0;
for (int x : nums) {
if (divisorNum[x] == 4) {
ans += divisorSum[x];
}
}
return ans;
}
}
###cpp
constexpr int MX = 100'001;
int divisor_num[MX];
int divisor_sum[MX];
int init = [] {
for (int i = 1; i < MX; i++) {
for (int j = i; j < MX; j += i) { // 枚举 i 的倍数 j
divisor_num[j]++; // i 是 j 的因子
divisor_sum[j] += i;
}
}
return 0;
}();
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int ans = 0;
for (int x : nums) {
if (divisor_num[x] == 4) {
ans += divisor_sum[x];
}
}
return ans;
}
};
###go
const mx = 100_001
var divisorNum, divisorSum [mx]int
func init() {
for i := 1; i < mx; i++ {
for j := i; j < mx; j += i { // 枚举 i 的倍数 j
divisorNum[j]++ // i 是 j 的因子
divisorSum[j] += i
}
}
}
func sumFourDivisors(nums []int) (ans int) {
for _, x := range nums {
if divisorNum[x] == 4 {
ans += divisorSum[x]
}
}
return
}
设 $U=\max(\textit{nums})$。预处理的时间为 $\mathcal{O}(U\log U)$（调和级数和），空间为 $\mathcal{O}(U)$，不计入。
见下面数学题单的「§1.5 因子」。
欢迎关注 B站@灵茶山艾府
我们可以遍历数组 nums 中的每个元素，依次判断这些元素是否恰好有四个因数。对于任一元素 x，我们可以用类似质数判定的方法得到它的因数个数，其本质为：如果整数 x 有因数 y，那么也必有因数 x/y，并且 y 和 x/y 中至少有一个不大于 sqrt(x)。这样我们只需要在 [1, sqrt(x)] 的区间内枚举可能为整数 x 的因数 y，并通过 x/y 得到整数 x 的其它因数，时间复杂度为 $O(\sqrt{x})$。
如果 x 恰好有四个因数，我们就将其因数之和累加到答案中。
###C++
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int ans = 0;
for (int num: nums) {
// factor_cnt: 因数的个数
// factor_sum: 因数的和
int factor_cnt = 0, factor_sum = 0;
for (int i = 1; i * i <= num; ++i) {
if (num % i == 0) {
++factor_cnt;
factor_sum += i;
if (i * i != num) { // 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
++factor_cnt;
factor_sum += num / i;
}
}
}
if (factor_cnt == 4) {
ans += factor_sum;
}
}
return ans;
}
};
###Java
class Solution {
public int sumFourDivisors(int[] nums) {
int ans = 0;
for (int num : nums) {
// factor_cnt: 因数的个数
// factor_sum: 因数的和
int factor_cnt = 0, factor_sum = 0;
for (int i = 1; i * i <= num; ++i) {
if (num % i == 0) {
++factor_cnt;
factor_sum += i;
if (i * i != num) { // 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
++factor_cnt;
factor_sum += num / i;
}
}
}
if (factor_cnt == 4) {
ans += factor_sum;
}
}
return ans;
}
}
###Python
class Solution:
def sumFourDivisors(self, nums: List[int]) -> int:
ans = 0
for num in nums:
# factor_cnt: 因数的个数
# factor_sum: 因数的和
factor_cnt = factor_sum = 0
i = 1
while i * i <= num:
if num % i == 0:
factor_cnt += 1
factor_sum += i
if i * i != num: # 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
factor_cnt += 1
factor_sum += num // i
i += 1
if factor_cnt == 4:
ans += factor_sum
return ans
###C#
public class Solution {
public int SumFourDivisors(int[] nums) {
int ans = 0;
foreach (int num in nums) {
// factor_cnt: 因数的个数
// factor_sum: 因数的和
int factor_cnt = 0, factor_sum = 0;
for (int i = 1; i * i <= num; ++i) {
if (num % i == 0) {
++factor_cnt;
factor_sum += i;
if (i * i != num) { // 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
++factor_cnt;
factor_sum += num / i;
}
}
}
if (factor_cnt == 4) {
ans += factor_sum;
}
}
return ans;
}
}
###Go
func sumFourDivisors(nums []int) int {
ans := 0
for _, num := range nums {
// factor_cnt: 因数的个数
// factor_sum: 因数的和
factor_cnt, factor_sum := 0, 0
for i := 1; i*i <= num; i++ {
if num%i == 0 {
factor_cnt++
factor_sum += i
if i*i != num { // 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
factor_cnt++
factor_sum += num / i
}
}
}
if factor_cnt == 4 {
ans += factor_sum
}
}
return ans
}
###C
int sumFourDivisors(int* nums, int numsSize) {
int ans = 0;
for (int idx = 0; idx < numsSize; idx++) {
int num = nums[idx];
// factor_cnt: 因数的个数
// factor_sum: 因数的和
int factor_cnt = 0, factor_sum = 0;
for (int i = 1; i * i <= num; ++i) {
if (num % i == 0) {
++factor_cnt;
factor_sum += i;
if (i * i != num) { // 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
++factor_cnt;
factor_sum += num / i;
}
}
}
if (factor_cnt == 4) {
ans += factor_sum;
}
}
return ans;
}
###JavaScript
var sumFourDivisors = function(nums) {
let ans = 0;
for (const num of nums) {
// factor_cnt: 因数的个数
// factor_sum: 因数的和
let factor_cnt = 0, factor_sum = 0;
for (let i = 1; i * i <= num; ++i) {
if (num % i === 0) {
++factor_cnt;
factor_sum += i;
if (i * i !== num) { // 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
++factor_cnt;
factor_sum += num / i;
}
}
}
if (factor_cnt === 4) {
ans += factor_sum;
}
}
return ans;
};
###TypeScript
function sumFourDivisors(nums: number[]): number {
let ans = 0;
for (const num of nums) {
// factor_cnt: 因数的个数
// factor_sum: 因数的和
let factor_cnt = 0, factor_sum = 0;
for (let i = 1; i * i <= num; ++i) {
if (num % i === 0) {
++factor_cnt;
factor_sum += i;
if (i * i !== num) { // 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
++factor_cnt;
factor_sum += num / i;
}
}
}
if (factor_cnt === 4) {
ans += factor_sum;
}
}
return ans;
}
###Rust
impl Solution {
pub fn sum_four_divisors(nums: Vec<i32>) -> i32 {
let mut ans = 0;
for &num in &nums {
// factor_cnt: 因数的个数
// factor_sum: 因数的和
let mut factor_cnt = 0;
let mut factor_sum = 0;
let mut i = 1;
while i * i <= num {
if num % i == 0 {
factor_cnt += 1;
factor_sum += i;
if i * i != num { // 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
factor_cnt += 1;
factor_sum += num / i;
}
}
i += 1;
}
if factor_cnt == 4 {
ans += factor_sum;
}
}
ans
}
}
复杂度分析
时间复杂度：$O(N\sqrt{C})$，其中 $N$ 是数组 nums 的长度，$C$ 是数组 nums 中元素值的范围，在本题中 $C$ 不超过 $10^5$。
空间复杂度：$O(1)$。
预备知识
分析与算法
直觉告诉我们，恰好有四个因数的整数不会有很多，我们是否可以预先找出它们呢？
根据「算数基本定理」（又叫「唯一分解定理」），如果整数 $x$ 可以分解为：
$$
x = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
$$
其中 $p_i$ 为互不相同的质数（即 $x$ 的质因数）。那么 $x$ 的因数个数为：
$$
\textit{factor_count}(x) = \prod_{i=1}^k (\alpha_i + 1)
$$
如果 $\textit{factor_count}(x)$ 的值为 $4$，那么只有两种可能：
整数 $x$ 只有一个质因数，对应的指数为 $3$，此时 $\textit{factor_count}(x) = (3+1) = 4$；
整数 $x$ 有两个质因数，对应的指数均为 $1$，此时 $\textit{factor_count}(x) = (1+1)(1+1) = 4$。
对于第一种情况，我们需要找到所有不大于 $C^{1/3}$ 的质数；对于第二种情况，我们需要找到所有不大于 $C$ 的质数，再将它们两两相乘并筛去超过 $C$ 的那些结果。这里 $C$ 的定义与方法一中的复杂度分析部分一致。综上所述，我们需要找到所有不大于 $C$ 的质数。
我们如何找出所有不大于 $C$ 的质数呢？这时就需要「埃拉托斯特尼筛法」或「欧拉筛法」的帮助了。它们可以帮助我们快速找到这些质数。这两种筛法的算法细节不是这篇题解的重点，这里不再赘述。在找到了这些质数后，我们就可以构造出所有满足上述两种可能的 $x$ 了。我们将 $x$ 以及它的因数之和存入哈希映射（HashMap）中，这样就可以在 $O(1)$ 的时间判断数组 nums 中的每个元素是否满足要求，并统计满足要求的元素的因数之和了。
下面的代码给出了 Python 和 C++ 语言的「埃拉托斯特尼筛法」以及「欧拉筛法」的实现。
###C++
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
// C 是数组 nums 元素的上限，C3 是 C 的立方根
int C = 100000, C3 = 46;
vector<int> isprime(C + 1, 1);
vector<int> primes;
// 埃拉托斯特尼筛法
for (int i = 2; i <= C; ++i) {
if (isprime[i]) {
primes.push_back(i);
}
for (int j = i + i; j <= C; j += i) {
isprime[j] = 0;
}
}
// 欧拉筛法
/*
for (int i = 2; i <= C; ++i) {
if (isprime[i]) {
primes.push_back(i);
}
for (int prime: primes) {
if (i * prime > C) {
break;
}
isprime[i * prime] = 0;
if (i % prime == 0) {
break;
}
}
}
*/
// 通过质数表构造出所有的四因数
unordered_map<int, int> factor4;
for (int prime: primes) {
if (prime <= C3) {
factor4[prime * prime * prime] = 1 + prime + prime * prime + prime * prime * prime;
}
}
for (int i = 0; i < primes.size(); ++i) {
for (int j = i + 1; j < primes.size(); ++j) {
if (primes[i] <= C / primes[j]) {
factor4[primes[i] * primes[j]] = 1 + primes[i] + primes[j] + primes[i] * primes[j];
}
else {
break;
}
}
}
int ans = 0;
for (int num: nums) {
if (factor4.count(num)) {
ans += factor4[num];
}
}
return ans;
}
};
###Java
class Solution {
public int sumFourDivisors(int[] nums) {
// C 是数组 nums 元素的上限，C3 是 C 的立方根
int C = 100000, C3 = 46;
boolean[] isPrime = new boolean[C + 1];
Arrays.fill(isPrime, true);
List<Integer> primes = new ArrayList<Integer>();
// 埃拉托斯特尼筛法
for (int i = 2; i <= C; ++i) {
if (isPrime[i]) {
primes.add(i);
}
for (int j = i + i; j <= C; j += i) {
isPrime[j] = false;
}
}
// 欧拉筛法
/*
for (int i = 2; i <= C; ++i) {
if (isPrime[i]) {
primes.add(i);
}
for (int prime : primes) {
if (i * prime > C) {
break;
}
isPrime[i * prime] = false;
if (i % prime == 0) {
break;
}
}
}
*/
// 通过质数表构造出所有的四因数
Map<Integer, Integer> factor4 = new HashMap<Integer, Integer>();
for (int prime : primes) {
if (prime <= C3) {
factor4.put(prime * prime * prime, 1 + prime + prime * prime + prime * prime * prime);
}
}
for (int i = 0; i < primes.size(); ++i) {
for (int j = i + 1; j < primes.size(); ++j) {
if (primes.get(i) <= C / primes.get(j)) {
factor4.put(primes.get(i) * primes.get(j), 1 + primes.get(i) + primes.get(j) + primes.get(i) * primes.get(j));
} else {
break;
}
}
}
int ans = 0;
for (int num : nums) {
if (factor4.containsKey(num)) {
ans += factor4.get(num);
}
}
return ans;
}
}
###Python
class Solution:
def sumFourDivisors(self, nums: List[int]) -> int:
# C 是数组 nums 元素的上限，C3 是 C 的立方根
C, C3 = 100000, 46
isprime = [True] * (C + 1)
primes = list()
# 埃拉托斯特尼筛法
for i in range(2, C + 1):
if isprime[i]:
primes.append(i)
for j in range(i + i, C + 1, i):
isprime[j] = False
# 欧拉筛法
"""
for i in range(2, C + 1):
if isprime[i]:
primes.append(i)
for prime in primes:
if i * prime > C:
break
isprime[i * prime] = False
if i % prime == 0:
break
"""
# 通过质数表构造出所有的四因数
factor4 = dict()
for prime in primes:
if prime <= C3:
factor4[prime**3] = 1 + prime + prime**2 + prime**3
for i in range(len(primes)):
for j in range(i + 1, len(primes)):
if primes[i] * primes[j] <= C:
factor4[primes[i] * primes[j]] = 1 + primes[i] + primes[j] + primes[i] * primes[j]
else:
break
ans = 0
for num in nums:
if num in factor4:
ans += factor4[num]
return ans
###C#
public class Solution {
public int SumFourDivisors(int[] nums) {
// C 是数组 nums 元素的上限，C3 是 C 的立方根
int C = 100000, C3 = 46;
int[] isprime = new int[C + 1];
for (int i = 2; i <= C; i++) isprime[i] = 1;
List<int> primes = new List<int>();
// 埃拉托斯特尼筛法
for (int i = 2; i <= C; ++i) {
if (isprime[i] == 1) {
primes.Add(i);
}
for (int j = i + i; j <= C; j += i) {
isprime[j] = 0;
}
}
// 欧拉筛法
/*
for (int i = 2; i <= C; ++i) {
if (isprime[i] == 1) {
primes.Add(i);
}
foreach (int prime in primes) {
if (i * prime > C) {
break;
}
isprime[i * prime] = 0;
if (i % prime == 0) {
break;
}
}
}
*/
// 通过质数表构造出所有的四因数
Dictionary<int, int> factor4 = new Dictionary<int, int>();
foreach (int prime in primes) {
if (prime <= C3) {
factor4[prime * prime * prime] = 1 + prime + prime * prime + prime * prime * prime;
}
}
for (int i = 0; i < primes.Count; ++i) {
for (int j = i + 1; j < primes.Count; ++j) {
if (primes[i] <= C / primes[j]) {
factor4[primes[i] * primes[j]] = 1 + primes[i] + primes[j] + primes[i] * primes[j];
}
else {
break;
}
}
}
int ans = 0;
foreach (int num in nums) {
if (factor4.ContainsKey(num)) {
ans += factor4[num];
}
}
return ans;
}
}
###Go
func sumFourDivisors(nums []int) int {
// C 是数组 nums 元素的上限，C3 是 C 的立方根
C, C3 := 100000, 46
isprime := make([]int, C+1)
for i := 2; i <= C; i++ {
isprime[i] = 1
}
primes := []int{}
// 埃拉托斯特尼筛法
for i := 2; i <= C; i++ {
if isprime[i] == 1 {
primes = append(primes, i)
}
for j := i + i; j <= C; j += i {
isprime[j] = 0
}
}
// 欧拉筛法
/*
for i := 2; i <= C; i++ {
if isprime[i] == 1 {
primes = append(primes, i)
}
for _, prime := range primes {
if i * prime > C {
break
}
isprime[i * prime] = 0
if i % prime == 0 {
break
}
}
}
*/
// 通过质数表构造出所有的四因数
factor4 := make(map[int]int)
for _, prime := range primes {
if prime <= C3 {
factor4[prime * prime * prime] = 1 + prime + prime * prime + prime * prime * prime
}
}
for i := 0; i < len(primes); i++ {
for j := i + 1; j < len(primes); j++ {
if primes[i] <= C / primes[j] {
factor4[primes[i] * primes[j]] = 1 + primes[i] + primes[j] + primes[i] * primes[j]
} else {
break
}
}
}
ans := 0
for _, num := range nums {
if val, exists := factor4[num]; exists {
ans += val
}
}
return ans
}
###C
int sumFourDivisors(int* nums, int numsSize) {
// C 是数组 nums 元素的上限，C3 是 C 的立方根
const int C = 100000, C3 = 46;
int* isprime = (int*)malloc((C + 1) * sizeof(int));
memset(isprime, 0, (C + 1) * sizeof(int));
int* primes = (int*)malloc((C + 1) * sizeof(int));
int primeCount = 0;
// 埃拉托斯特尼筛法
for (int i = 2; i <= C; ++i) {
isprime[i] = 1;
}
for (int i = 2; i <= C; ++i) {
if (isprime[i]) {
primes[primeCount++] = i;
}
for (int j = i + i; j <= C; j += i) {
isprime[j] = 0;
}
}
// 欧拉筛法
/*
for (int i = 2; i <= C; ++i) {
if (isprime[i]) {
primes[primeCount++] = i;
}
for (int j = 0; j < primeCount; ++j) {
if (i * primes[j] > C) {
break;
}
isprime[i * primes[j]] = 0;
if (i % primes[j] == 0) {
break;
}
}
}
*/
// 通过质数表构造出所有的四因数
int* factor4_keys = (int*)malloc(primeCount * primeCount * sizeof(int));
int* factor4_values = (int*)malloc(primeCount * primeCount * sizeof(int));
int factor4_count = 0;
for (int i = 0; i < primeCount; ++i) {
int prime = primes[i];
if (prime <= C3) {
factor4_keys[factor4_count] = prime * prime * prime;
factor4_values[factor4_count] = 1 + prime + prime * prime + prime * prime * prime;
factor4_count++;
}
}
for (int i = 0; i < primeCount; ++i) {
for (int j = i + 1; j < primeCount; ++j) {
if (primes[i] <= C / primes[j]) {
factor4_keys[factor4_count] = primes[i] * primes[j];
factor4_values[factor4_count] = 1 + primes[i] + primes[j] + primes[i] * primes[j];
factor4_count++;
} else {
break;
}
}
}
int ans = 0;
for (int idx = 0; idx < numsSize; ++idx) {
int num = nums[idx];
for (int i = 0; i < factor4_count; ++i) {
if (factor4_keys[i] == num) {
ans += factor4_values[i];
break;
}
}
}
free(isprime);
free(primes);
free(factor4_keys);
free(factor4_values);
return ans;
}
###JavaScript
var sumFourDivisors = function(nums) {
// C 是数组 nums 元素的上限，C3 是 C 的立方根
const C = 100000, C3 = 46;
let isprime = new Array(C + 1).fill(0);
let primes = [];
// 埃拉托斯特尼筛法
for (let i = 2; i <= C; i++) {
isprime[i] = 1;
}
for (let i = 2; i <= C; i++) {
if (isprime[i]) {
primes.push(i);
}
for (let j = i + i; j <= C; j += i) {
isprime[j] = 0;
}
}
// 欧拉筛法
/*
for (let i = 2; i <= C; i++) {
if (isprime[i]) {
primes.push(i);
}
for (let prime of primes) {
if (i * prime > C) {
break;
}
isprime[i * prime] = 0;
if (i % prime === 0) {
break;
}
}
}
*/
// 通过质数表构造出所有的四因数
let factor4 = new Map();
for (let prime of primes) {
if (prime <= C3) {
factor4.set(prime * prime * prime, 1 + prime + prime * prime + prime * prime * prime);
}
}
for (let i = 0; i < primes.length; i++) {
for (let j = i + 1; j < primes.length; j++) {
if (primes[i] <= C / primes[j]) {
factor4.set(primes[i] * primes[j], 1 + primes[i] + primes[j] + primes[i] * primes[j]);
} else {
break;
}
}
}
let ans = 0;
for (let num of nums) {
if (factor4.has(num)) {
ans += factor4.get(num);
}
}
return ans;
};
###TypeScript
function sumFourDivisors(nums: number[]): number {
// C 是数组 nums 元素的上限，C3 是 C 的立方根
const C: number = 100000, C3: number = 46;
let isprime: number[] = new Array(C + 1).fill(0);
let primes: number[] = [];
// 埃拉托斯特尼筛法
for (let i = 2; i <= C; i++) {
isprime[i] = 1;
}
for (let i = 2; i <= C; i++) {
if (isprime[i]) {
primes.push(i);
}
for (let j = i + i; j <= C; j += i) {
isprime[j] = 0;
}
}
// 欧拉筛法
/*
for (let i = 2; i <= C; i++) {
if (isprime[i]) {
primes.push(i);
}
for (let prime of primes) {
if (i * prime > C) {
break;
}
isprime[i * prime] = 0;
if (i % prime === 0) {
break;
}
}
}
*/
// 通过质数表构造出所有的四因数
let factor4: Map<number, number> = new Map();
for (let prime of primes) {
if (prime <= C3) {
factor4.set(prime * prime * prime, 1 + prime + prime * prime + prime * prime * prime);
}
}
for (let i = 0; i < primes.length; i++) {
for (let j = i + 1; j < primes.length; j++) {
if (primes[i] <= C / primes[j]) {
factor4.set(primes[i] * primes[j], 1 + primes[i] + primes[j] + primes[i] * primes[j]);
} else {
break;
}
}
}
let ans: number = 0;
for (let num of nums) {
if (factor4.has(num)) {
ans += factor4.get(num)!;
}
}
return ans;
}
###Rust
use std::collections::HashMap;
impl Solution {
pub fn sum_four_divisors(nums: Vec<i32>) -> i32 {
// C 是数组 nums 元素的上限，C3 是 C 的立方根
const C: i32 = 100000;
const C3: i32 = 46;
let mut isprime = vec![0; (C + 1) as usize];
let mut primes = Vec::new();
// 埃拉托斯特尼筛法
for i in 2..=C {
isprime[i as usize] = 1;
}
for i in 2..=C {
if isprime[i as usize] == 1 {
primes.push(i);
}
let mut j = i + i;
while j <= C {
isprime[j as usize] = 0;
j += i;
}
}
// 欧拉筛法
/*
for i in 2..=C {
if isprime[i as usize] == 1 {
primes.push(i);
}
for &prime in &primes {
if i * prime > C {
break;
}
isprime[(i * prime) as usize] = 0;
if i % prime == 0 {
break;
}
}
}
*/
// 通过质数表构造出所有的四因数
let mut factor4 = HashMap::new();
for &prime in &primes {
if prime <= C3 {
let key = prime * prime * prime;
let value = 1 + prime + prime * prime + prime * prime * prime;
factor4.insert(key, value);
}
}
for i in 0..primes.len() {
for j in i + 1..primes.len() {
if primes[i] <= C / primes[j] {
let key = primes[i] * primes[j];
let value = 1 + primes[i] + primes[j] + primes[i] * primes[j];
factor4.insert(key, value);
} else {
break;
}
}
}
let mut ans = 0;
for num in nums {
if let Some(&value) = factor4.get(&num) {
ans += value;
}
}
ans
}
}
复杂度分析
时间复杂度：$O(\pi^2(C) + C\log\log C + N)$ 或 $O(\pi^2(C) + C + N)$，其中 $\pi(X)$ 为「质数计数函数」，表示不超过 $X$ 的质数个数。「埃拉托斯特尼筛法」的时间复杂度为 $O(C\log\log C)$，「欧拉筛法」的时间复杂度为 $O(C)$；通过质数表构造出所有四因数的时间复杂度为 $O(\pi(C^{1/3})) + O(\pi^2(C)) = O(\pi^2(C))$，遍历数组 nums 中的所有元素并检查是否为四因数的时间复杂度为 $O(N)$。
空间复杂度：$O(C + \pi(C))$，无论哪一种筛法，都需要长度为 $C$ 的数组记录每个数是否为质数，以及长度为 $\pi(C)$ 的数组存储所有的质数。
过不了的问题主要出在测试用的83521和2401这两个数上，分别是17和7的四次方。
写法没啥特别的，遍历到根号，计数，但是比赛全程都卡在最后这个巨长的用例上，始终找不到为啥。
这是比赛途中采用的代码：
#include <math.h>
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int res = 0;
for(int i = 0; i < nums.size(); ++i){
int cnt = 0;
int sum = 0;
for(int j = 2; j < sqrt(nums[i]); ++j){
if(nums[i] % j == 0){
cnt++;
sum += j;
sum += nums[i] / j;
}
if(cnt > 1) break;
}
if(cnt == 1){
res = res + sum + nums[i] + 1;
}
}
return res;
}
};
这里我以为j < sqrt(nums[i])而不用等于就可以避免平方根的问题，但是显然忽略了更高阶的四次方情况。
排错方式比较智障，人工二分法测试，找到了83521和2401这两个数，发现其四次方特性。
参考评论区各位前辈代码，把平方判断单独拿出来写：
#include <math.h>
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int res = 0;
for(int i = 0; i < nums.size(); ++i){
int cnt = 0;
int sum = 0;
int sq = sqrt(nums[i]);
for(int j = 2; j <= sq; ++j){
if(nums[i] % j == 0){
cnt++;
sum += j;
sum += nums[i] / j;
}
if(cnt > 1) break;
}
if(cnt == 1 && sq * sq != nums[i]){
res = res + sum + nums[i] + 1;
}
}
return res;
}
};
通过~
你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。
给你网格图的行数 n 。
请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。
示例 1：
输入：n = 1 输出：12 解释：总共有 12 种可行的方法：
示例 2：
输入：n = 2 输出：54
示例 3：
输入：n = 3 输出：246
示例 4：
输入：n = 7 输出：106494
示例 5：
输入：n = 5000 输出：30228214
提示：
n == grid.lengthgrid[i].length == 31 <= n <= 5000考虑暴力搜索，枚举每个格子涂哪种颜色。
从下往上涂色（这样可以在多组测试数据间复用记忆化的结果），我们需要知道：
三种颜色分别用 $0,1,2$ 表示，存储一个格子的颜色信息需要 $2$ 个比特位，一行的颜色就需要 $2\cdot 3 = 6$ 个比特位。
注意取模。为什么可以在中途取模？原理见 模运算的世界：当加减乘除遇上取模。
###py
MOD = 1_000_000_007
# (i, j)：当前位置
# pre_row：上一行（i+1 行）的颜色
# cur_row：当前这一行已填入的颜色
@cache # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int, j: int, pre_row: int, cur_row: int) -> int:
if i == 0: # 所有格子都已涂色
return 1 # 找到一个合法方案
if j == 3: # i 行已涂色
# 开始对 i-1 行涂色，cur_row 变成 pre_row
return dfs(i - 1, 0, cur_row, 0)
res = 0
for color in range(3): # 枚举 (i, j) 的颜色 color
# 不能和下面相邻格子 (i+1, j) 颜色相同
# 不能和左侧相邻格子 (i, j-1) 颜色相同
if pre_row and color == pre_row >> (j * 2) & 3 or \
j and color == cur_row >> ((j - 1) * 2) & 3:
continue
res += dfs(i, j + 1, pre_row, cur_row | (color << (j * 2)))
return res % MOD
class Solution:
def numOfWays(self, n: int) -> int:
return dfs(n, 0, 0, 0) # 从最后一行开始涂色
###java
class Solution {
private static final int MOD = 1_000_000_007;
// 全局 memo，记忆化的内容可以在不同测试数据间共享
private static Map<Integer, Integer> memo = new HashMap<>();
public int numOfWays(int n) {
return dfs(n, 0, 0, 0);
}
// (i, j)：当前位置
// preRow：上一行（i+1 行）的颜色
// curRow：当前这一行已填入的颜色
private int dfs(int i, int j, int preRow, int curRow) {
if (i == 0) { // 所有格子都已涂色
return 1; // 找到一个合法方案
}
if (j == 3) { // i 行已涂色
// 开始对 i-1 行涂色，curRow 变成 preRow
return dfs(i - 1, 0, curRow, 0);
}
// 参数压缩到一个 int 中
int key = (i << 14) | (j << 12) | (preRow << 6) | curRow;
if (memo.containsKey(key)) { // 之前计算过
return memo.get(key);
}
int res = 0;
for (int color = 0; color < 3; color++) { // 枚举 (i, j) 的颜色 color
if (preRow > 0 && color == (preRow >> (j * 2) & 3) || // 不能和下面相邻格子 (i+1, j) 颜色相同
j > 0 && color == (curRow >> ((j - 1) * 2) & 3)) { // 不能和左侧相邻格子 (i, j-1) 颜色相同
continue;
}
res = (res + dfs(i, j + 1, preRow, curRow | (color << (j * 2)))) % MOD;
}
memo.put(key, res); // 记忆化
return res;
}
}
###cpp
constexpr int MOD = 1'000'000'007;
// 全局 memo，记忆化的内容可以在不同测试数据间共享
unordered_map<int, int> memo;
// (i, j)：当前位置
// pre_row：上一行（i+1 行）的颜色
// cur_row：当前这一行已填入的颜色
int dfs(int i, int j, int pre_row, int cur_row) {
if (i == 0) { // 所有格子都已涂色
return 1; // 找到一个合法方案
}
if (j == 3) { // i 行已涂色
// 开始对 i-1 行涂色，cur_row 变成 pre_row
return dfs(i - 1, 0, cur_row, 0);
}
// 参数压缩到一个 int 中
int key = (i << 14) | (j << 12) | (pre_row << 6) | cur_row;
if (memo.contains(key)) { // 之前计算过
return memo[key];
}
int res = 0;
for (int color = 0; color < 3; color++) { // 枚举 (i, j) 的颜色 color
if (pre_row > 0 && color == (pre_row >> (j * 2) & 3) || // 不能和下面相邻格子 (i+1, j) 颜色相同
j > 0 && color == (cur_row >> ((j - 1) * 2) & 3)) { // 不能和左侧相邻格子 (i, j-1) 颜色相同
continue;
}
res = (res + dfs(i, j + 1, pre_row, cur_row | (color << (j * 2)))) % MOD;
}
memo[key] = res; // 记忆化
return res;
}
class Solution {
public:
int numOfWays(int n) {
return dfs(n, 0, 0, 0);
}
};
###go
const mod = 1_000_000_007
type tuple struct{ i, j, preRow, curRow int }
// 全局 memo，记忆化的内容可以在不同测试数据间共享
var memo = map[tuple]int{}
// (i, j)：当前位置
// preRow：上一行（i+1 行）的颜色
// curRow：当前这一行已填入的颜色
func dfs(i, j, preRow, curRow int) int {
if i == 0 { // 所有格子都已涂色
return 1 // 找到一个合法方案
}
if j == 3 { // i 行已涂色
// 开始对 i-1 行涂色，curRow 变成 preRow
return dfs(i-1, 0, curRow, 0)
}
t := tuple{i, j, preRow, curRow}
if res, ok := memo[t]; ok { // 之前计算过
return res
}
res := 0
for color := range 3 { // 枚举 (i, j) 的颜色 color
if preRow > 0 && color == preRow>>(j*2)&3 || // 不能和下面相邻格子 (i+1, j) 颜色相同
j > 0 && color == curRow>>((j-1)*2)&3 { // 不能和左侧相邻格子 (i, j-1) 颜色相同
continue
}
res = (res + dfs(i, j+1, preRow, curRow|color<<(j*2))) % mod
}
memo[t] = res // 记忆化
return res
}
func numOfWays(n int) int {
return dfs(n, 0, 0, 0)
}
回顾方法一，总体上看，DP 过程是一个线性递推（从 $(n-1)\times 3$ 网格图最后一行的所有涂色方案线性转移到 $n\times 3$ 网格图的最后一行），所以必然有线性递推式。
定义 $f[n]$ 表示给 $n\times 3$ 网格图涂色的方案数。
根据 Berlekamp-Massey 算法，用方法一求出 $f$ 的连续若干项（具体多少在文章中有解释，本题只需 $4$ 项），就可以用 Berlekamp-Massey 算法直接得到线性递推式
$$
f[i] = 5\cdot f[i-1]-2\cdot f[i-2] \ \ (i \ge 3)
$$
初始值 $f[1] = 12,\ f[2] = 54$。
也可以倒推出 $f[0]=3$，把 $f[0]$ 和 $f[1]$ 作为初始值。
###py
class Solution:
def numOfWays(self, n: int) -> int:
MOD = 1_000_000_007
f = [0] * (n + 1)
f[0] = 3
f[1] = 12
for i in range(2, n + 1):
f[i] = (f[i - 1] * 5 - f[i - 2] * 2) % MOD
return f[n]
###java
class Solution {
public int numOfWays(int n) {
final int MOD = 1_000_000_007;
int[] f = new int[n + 1];
f[0] = 3;
f[1] = 12;
for (int i = 2; i <= n; i++) {
f[i] = (int) ((f[i - 1] * 5L - f[i - 2] * 2L) % MOD); // 注意这里有减法，结果可能是负数
}
return (f[n] + MOD) % MOD; // 保证结果非负
}
}
###cpp
class Solution {
public:
int numOfWays(int n) {
constexpr int MOD = 1'000'000'007;
vector<int> f(n + 1);
f[0] = 3;
f[1] = 12;
for (int i = 2; i <= n; i++) {
f[i] = (f[i - 1] * 5LL - f[i - 2] * 2LL) % MOD; // 注意这里有减法，结果可能是负数
}
return (f[n] + MOD) % MOD; // 保证结果非负
}
};
###go
func numOfWays(n int) int {
const mod = 1_000_000_007
f := make([]int, n+1)
f[0] = 3
f[1] = 12
for i := 2; i <= n; i++ {
f[i] = (f[i-1]*5 - f[i-2]*2) % mod // 注意这里有减法，结果可能是负数
}
return (f[n] + mod) % mod // 保证结果非负
}
把方法二的递推式用矩阵乘法表示，即
$$
\begin{bmatrix}
f[i] \
f[i-1] \
\end{bmatrix}
= \begin{bmatrix}
5 & -2 \
1 & 0 \
\end{bmatrix}
\begin{bmatrix}
f[i-1] \
f[i-2] \
\end{bmatrix}
$$
把上式中的三个矩阵分别记作 $F[i],M,F[i-1]$，即
$$
F[i] = M\times F[i-1]
$$
那么有
$$
\begin{aligned}
F[n] &= M\times F[n-1] \
&= M\times M\times F[n-2] \
&= M\times M\times M\times F[n-3] \
&\ \ \vdots \
&= M^{n-1}\times F[1] \
\end{aligned}
$$
其中 $M^{n-1}$ 可以用快速幂计算，原理请看【图解】一张图秒懂快速幂。
初始值
$$
F[1] = \begin{bmatrix}
f[1] \
f[0] \
\end{bmatrix}
= \begin{bmatrix}
12 \
3 \
\end{bmatrix}
$$
答案为 $f[n]$，即 $F[n]$ 的第一项。
###py
MOD = 1_000_000_007
# a @ b，其中 @ 是矩阵乘法
def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
return [[sum(x * y for x, y in zip(row, col)) % MOD for col in zip(*b)]
for row in a]
# a^n @ f0
def pow_mul(a: List[List[int]], n: int, f0: List[List[int]]) -> List[List[int]]:
res = f0
while n:
if n & 1:
res = mul(a, res)
a = mul(a, a)
n >>= 1
return res
class Solution:
def numOfWays(self, n: int) -> int:
m = [[5, -2], [1, 0]]
f1 = [[12], [3]]
fn = pow_mul(m, n - 1, f1)
return fn[0][0]
###py
import numpy as np
class Solution:
def numOfWays(self, n: int) -> int:
MOD = 1_000_000_007
m = np.array([[5, -2], [1, 0]], dtype=object)
f1 = np.array([12, 3], dtype=object)
fn = np.linalg.matrix_power(m, n - 1) @ f1
return fn[0] % MOD
###java
class Solution {
private static final int MOD = 1_000_000_007;
public int numOfWays(int n) {
int[][] m = {
{5, -2},
{1, 0},
};
int[][] f1 = {{12}, {3}};
int[][] fn = powMul(m, n - 1, f1);
return (fn[0][0] + MOD) % MOD; // 保证结果非负
}
// a^n * f0
private int[][] powMul(int[][] a, int n, int[][] f0) {
int[][] res = f0;
while (n > 0) {
if ((n & 1) > 0) {
res = mul(a, res);
}
a = mul(a, a);
n >>= 1;
}
return res;
}
// 返回矩阵 a 和矩阵 b 相乘的结果
private int[][] mul(int[][] a, int[][] b) {
int[][] c = new int[a.length][b[0].length];
for (int i = 0; i < a.length; i++) {
for (int k = 0; k < a[i].length; k++) {
if (a[i][k] == 0) {
continue;
}
for (int j = 0; j < b[k].length; j++) {
c[i][j] = (int) ((c[i][j] + (long) a[i][k] * b[k][j]) % MOD);
}
}
}
return c;
}
}
###cpp
constexpr int MOD = 1'000'000'007;
using matrix = vector<vector<int>>;
// 返回矩阵 a 和矩阵 b 相乘的结果
matrix mul(matrix& a, matrix& b) {
int n = a.size(), m = b[0].size();
matrix c = matrix(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int k = 0; k < a[i].size(); k++) {
if (a[i][k] == 0) {
continue;
}
for (int j = 0; j < m; j++) {
c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
}
}
}
return c;
}
// a^n * f0
matrix pow_mul(matrix a, int n, matrix& f0) {
matrix res = f0;
while (n) {
if (n & 1) {
res = mul(a, res);
}
a = mul(a, a);
n >>= 1;
}
return res;
}
class Solution {
public:
int numOfWays(int n) {
matrix m = {
{5, -2},
{1, 0},
};
matrix f1 = {{12}, {3}};
matrix fn = pow_mul(m, n - 1, f1);
return (fn[0][0] + MOD) % MOD; // 保证结果非负
}
};
###go
const mod = 1_000_000_007
type matrix [][]int
func newMatrix(n, m int) matrix {
a := make(matrix, n)
for i := range a {
a[i] = make([]int, m)
}
return a
}
// 返回矩阵 a 和矩阵 b 相乘的结果
func (a matrix) mul(b matrix) matrix {
c := newMatrix(len(a), len(b[0]))
for i, row := range a {
for k, x := range row {
if x == 0 {
continue
}
for j, y := range b[k] {
c[i][j] = (c[i][j] + x*y) % mod
}
}
}
return c
}
// a^n * f0
func (a matrix) powMul(n int, f0 matrix) matrix {
res := f0
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = a.mul(res)
}
a = a.mul(a)
}
return res
}
func numOfWays(n int) int {
m := matrix{
{5, -2},
{1, 0},
}
f1 := matrix{{12}, {3}}
fn := m.powMul(n-1, f1)
return (fn[0][0] + mod) % mod // 保证结果非负
}
注：也可以用 Kitamasa 算法 计算，在矩阵更大（递推式更长）时有优势。
见下面动态规划题单的「§9.5 轮廓线 DP」和「§11.6 矩阵快速幂优化 DP」。
欢迎关注 B站@灵茶山艾府
我们可以用 $f[i][\textit{type}]$ 表示当网格的大小为 $i \times 3$ 且最后一行的填色方法为 $\textit{type}$ 时的方案数。由于我们在填充第 $i$ 行时，会影响我们填充方案的只有它上面的那一行（即 $i - 1$ 行），因此用 $f[i][\textit{type}]$ 表示状态是合理的。
那么我们如何计算 $f[i][\textit{type}]$ 呢？可以发现：
首先，$\textit{type}$ 本身是要满足要求的。每一行有 $3$ 个网格，如果我们用 $0, 1, 2$ 分别代表红黄绿，那么 $\textit{type}$ 可以看成一个三进制数，例如 $\textit{type} = (102)_3$ 时，表示 $3$ 个网格从左到右的颜色分别为黄、红、绿；
其次，$f[i][\textit{type}]$ 应该等于所有 $f[i - 1][\textit{type}']$ 的和，其中 $\textit{type'}$ 和 $\textit{type}$ 可以作为相邻的行。也就是说，$\textit{type'}$ 和 $\textit{type}$ 的对应位置不能相同。
递推解法的本身不难想出，难度在于上述的预处理以及编码实现。下面给出包含详细注释的 C++、Java 和 Python 代码。
###C++
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int numOfWays(int n) {
// 预处理出所有满足条件的 type
vector<int> types;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
if (i != j && j != k) {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types.push_back(i * 9 + j * 3 + k);
}
}
}
}
int type_cnt = types.size();
// 预处理出所有可以作为相邻行的 type 对
vector<vector<int>> related(type_cnt, vector<int>(type_cnt));
for (int i = 0; i < type_cnt; ++i) {
// 得到 types[i] 三个位置的颜色
int x1 = types[i] / 9, x2 = types[i] / 3 % 3, x3 = types[i] % 3;
for (int j = 0; j < type_cnt; ++j) {
// 得到 types[j] 三个位置的颜色
int y1 = types[j] / 9, y2 = types[j] / 3 % 3, y3 = types[j] % 3;
// 对应位置不同色，才能作为相邻的行
if (x1 != y1 && x2 != y2 && x3 != y3) {
related[i][j] = 1;
}
}
}
// 递推数组
vector<vector<int>> f(n + 1, vector<int>(type_cnt));
// 边界情况，第一行可以使用任何 type
for (int i = 0; i < type_cnt; ++i) {
f[1][i] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < type_cnt; ++j) {
for (int k = 0; k < type_cnt; ++k) {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if (related[k][j]) {
f[i][j] += f[i - 1][k];
f[i][j] %= mod;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
int ans = 0;
for (int i = 0; i < type_cnt; ++i) {
ans += f[n][i];
ans %= mod;
}
return ans;
}
};
###Java
class Solution {
static final int MOD = 1000000007;
public int numOfWays(int n) {
// 预处理出所有满足条件的 type
List<Integer> types = new ArrayList<Integer>();
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
if (i != j && j != k) {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types.add(i * 9 + j * 3 + k);
}
}
}
}
int typeCnt = types.size();
// 预处理出所有可以作为相邻行的 type 对
int[][] related = new int[typeCnt][typeCnt];
for (int i = 0; i < typeCnt; ++i) {
// 得到 types[i] 三个位置的颜色
int x1 = types.get(i) / 9, x2 = types.get(i) / 3 % 3, x3 = types.get(i) % 3;
for (int j = 0; j < typeCnt; ++j) {
// 得到 types[j] 三个位置的颜色
int y1 = types.get(j) / 9, y2 = types.get(j) / 3 % 3, y3 = types.get(j) % 3;
// 对应位置不同色，才能作为相邻的行
if (x1 != y1 && x2 != y2 && x3 != y3) {
related[i][j] = 1;
}
}
}
// 递推数组
int[][] f = new int[n + 1][typeCnt];
// 边界情况，第一行可以使用任何 type
for (int i = 0; i < typeCnt; ++i) {
f[1][i] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < typeCnt; ++j) {
for (int k = 0; k < typeCnt; ++k) {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if (related[k][j] != 0) {
f[i][j] += f[i - 1][k];
f[i][j] %= MOD;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
int ans = 0;
for (int i = 0; i < typeCnt; ++i) {
ans += f[n][i];
ans %= MOD;
}
return ans;
}
}
###Python
class Solution:
def numOfWays(self, n: int) -> int:
mod = 10**9 + 7
# 预处理出所有满足条件的 type
types = list()
for i in range(3):
for j in range(3):
for k in range(3):
if i != j and j != k:
# 只要相邻的颜色不相同就行
# 将其以十进制的形式存储
types.append(i * 9 + j * 3 + k)
type_cnt = len(types)
# 预处理出所有可以作为相邻行的 type 对
related = [[0] * type_cnt for _ in range(type_cnt)]
for i, ti in enumerate(types):
# 得到 types[i] 三个位置的颜色
x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3
for j, tj in enumerate(types):
# 得到 types[j] 三个位置的颜色
y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3
# 对应位置不同色，才能作为相邻的行
if x1 != y1 and x2 != y2 and x3 != y3:
related[i][j] = 1
# 递推数组
f = [[0] * type_cnt for _ in range(n + 1)]
# 边界情况，第一行可以使用任何 type
f[1] = [1] * type_cnt
for i in range(2, n + 1):
for j in range(type_cnt):
for k in range(type_cnt):
# f[i][j] 等于所有 f[i - 1][k] 的和
# 其中 k 和 j 可以作为相邻的行
if related[k][j]:
f[i][j] += f[i - 1][k]
f[i][j] %= mod
# 最终所有的 f[n][...] 之和即为答案
ans = sum(f[n]) % mod
return ans
###C#
public class Solution {
private const int mod = 1000000007;
public int NumOfWays(int n) {
// 预处理出所有满足条件的 type
List<int> types = new List<int>();
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
if (i != j && j != k) {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types.Add(i * 9 + j * 3 + k);
}
}
}
}
int type_cnt = types.Count;
// 预处理出所有可以作为相邻行的 type 对
int[][] related = new int[type_cnt][];
for (int i = 0; i < type_cnt; ++i) {
related[i] = new int[type_cnt];
// 得到 types[i] 三个位置的颜色
int x1 = types[i] / 9, x2 = types[i] / 3 % 3, x3 = types[i] % 3;
for (int j = 0; j < type_cnt; ++j) {
// 得到 types[j] 三个位置的颜色
int y1 = types[j] / 9, y2 = types[j] / 3 % 3, y3 = types[j] % 3;
// 对应位置不同色，才能作为相邻的行
if (x1 != y1 && x2 != y2 && x3 != y3) {
related[i][j] = 1;
}
}
}
// 递推数组
int[][] f = new int[n + 1][];
for (int i = 0; i <= n; ++i) {
f[i] = new int[type_cnt];
}
// 边界情况，第一行可以使用任何 type
for (int i = 0; i < type_cnt; ++i) {
f[1][i] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < type_cnt; ++j) {
for (int k = 0; k < type_cnt; ++k) {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if (related[k][j] == 1) {
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
int ans = 0;
for (int i = 0; i < type_cnt; ++i) {
ans = (ans + f[n][i]) % mod;
}
return ans;
}
}
###Go
func numOfWays(n int) int {
// 预处理出所有满足条件的 type
mod := 1000000007
types := []int{}
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
for k := 0; k < 3; k++ {
if i != j && j != k {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types = append(types, i*9 + j*3 + k)
}
}
}
}
type_cnt := len(types)
// 预处理出所有可以作为相邻行的 type 对
related := make([][]int, type_cnt)
for i := range related {
related[i] = make([]int, type_cnt)
}
for i := 0; i < type_cnt; i++ {
// 得到 types[i] 三个位置的颜色
x1 := types[i] / 9
x2 := types[i] / 3 % 3
x3 := types[i] % 3
for j := 0; j < type_cnt; j++ {
// 得到 types[j] 三个位置的颜色
y1 := types[j] / 9
y2 := types[j] / 3 % 3
y3 := types[j] % 3
// 对应位置不同色，才能作为相邻的行
if x1 != y1 && x2 != y2 && x3 != y3 {
related[i][j] = 1
}
}
}
// 递推数组
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, type_cnt)
}
// 边界情况，第一行可以使用任何 type
for i := 0; i < type_cnt; i++ {
f[1][i] = 1
}
for i := 2; i <= n; i++ {
for j := 0; j < type_cnt; j++ {
for k := 0; k < type_cnt; k++ {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if related[k][j] == 1 {
f[i][j] = (f[i][j] + f[i-1][k]) % mod
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
ans := 0
for i := 0; i < type_cnt; i++ {
ans = (ans + f[n][i]) % mod
}
return ans
}
###C
int numOfWays(int n) {
// 预处理出所有满足条件的 type
const int mod = 1000000007;
int types[12];
int type_cnt = 0;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
if (i != j && j != k) {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types[type_cnt++] = i * 9 + j * 3 + k;
}
}
}
}
// 预处理出所有可以作为相邻行的 type 对
int related[12][12] = {0};
for (int i = 0; i < type_cnt; ++i) {
// 得到 types[i] 三个位置的颜色
int x1 = types[i] / 9, x2 = types[i] / 3 % 3, x3 = types[i] % 3;
for (int j = 0; j < type_cnt; ++j) {
// 得到 types[j] 三个位置的颜色
int y1 = types[j] / 9, y2 = types[j] / 3 % 3, y3 = types[j] % 3;
// 对应位置不同色，才能作为相邻的行
if (x1 != y1 && x2 != y2 && x3 != y3) {
related[i][j] = 1;
}
}
}
// 递推数组
int f[n + 1][type_cnt];
// 初始化
for (int i = 0; i <= n; ++i) {
for (int j = 0; j < type_cnt; ++j) {
f[i][j] = 0;
}
}
// 边界情况，第一行可以使用任何 type
for (int i = 0; i < type_cnt; ++i) {
f[1][i] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < type_cnt; ++j) {
for (int k = 0; k < type_cnt; ++k) {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if (related[k][j]) {
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
int ans = 0;
for (int i = 0; i < type_cnt; ++i) {
ans = (ans + f[n][i]) % mod;
}
return ans;
}
###JavaScript
var numOfWays = function(n) {
// 预处理出所有满足条件的 type
const mod = 1000000007;
const types = [];
for (let i = 0; i < 3; ++i) {
for (let j = 0; j < 3; ++j) {
for (let k = 0; k < 3; ++k) {
if (i !== j && j !== k) {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types.push(i * 9 + j * 3 + k);
}
}
}
}
const type_cnt = types.length;
// 预处理出所有可以作为相邻行的 type 对
const related = Array.from({length: type_cnt}, () => new Array(type_cnt).fill(0));
for (let i = 0; i < type_cnt; ++i) {
// 得到 types[i] 三个位置的颜色
const x1 = Math.floor(types[i] / 9);
const x2 = Math.floor(types[i] / 3) % 3;
const x3 = types[i] % 3;
for (let j = 0; j < type_cnt; ++j) {
// 得到 types[j] 三个位置的颜色
const y1 = Math.floor(types[j] / 9);
const y2 = Math.floor(types[j] / 3) % 3;
const y3 = types[j] % 3;
// 对应位置不同色，才能作为相邻的行
if (x1 !== y1 && x2 !== y2 && x3 !== y3) {
related[i][j] = 1;
}
}
}
// 递推数组
const f = Array.from({length: n + 1}, () => new Array(type_cnt).fill(0));
// 边界情况，第一行可以使用任何 type
for (let i = 0; i < type_cnt; ++i) {
f[1][i] = 1;
}
for (let i = 2; i <= n; ++i) {
for (let j = 0; j < type_cnt; ++j) {
for (let k = 0; k < type_cnt; ++k) {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if (related[k][j]) {
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
let ans = 0;
for (let i = 0; i < type_cnt; ++i) {
ans = (ans + f[n][i]) % mod;
}
return ans;
};
###TypeScript
function numOfWays(n: number): number {
// 预处理出所有满足条件的 type
const mod: number = 1000000007;
const types: number[] = [];
for (let i = 0; i < 3; ++i) {
for (let j = 0; j < 3; ++j) {
for (let k = 0; k < 3; ++k) {
if (i !== j && j !== k) {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types.push(i * 9 + j * 3 + k);
}
}
}
}
const type_cnt: number = types.length;
// 预处理出所有可以作为相邻行的 type 对
const related: number[][] = Array.from({length: type_cnt}, () => new Array(type_cnt).fill(0));
for (let i = 0; i < type_cnt; ++i) {
// 得到 types[i] 三个位置的颜色
const x1: number = Math.floor(types[i] / 9);
const x2: number = Math.floor(types[i] / 3) % 3;
const x3: number = types[i] % 3;
for (let j = 0; j < type_cnt; ++j) {
// 得到 types[j] 三个位置的颜色
const y1: number = Math.floor(types[j] / 9);
const y2: number = Math.floor(types[j] / 3) % 3;
const y3: number = types[j] % 3;
// 对应位置不同色，才能作为相邻的行
if (x1 !== y1 && x2 !== y2 && x3 !== y3) {
related[i][j] = 1;
}
}
}
// 递推数组
const f: number[][] = Array.from({length: n + 1}, () => new Array(type_cnt).fill(0));
// 边界情况，第一行可以使用任何 type
for (let i = 0; i < type_cnt; ++i) {
f[1][i] = 1;
}
for (let i = 2; i <= n; ++i) {
for (let j = 0; j < type_cnt; ++j) {
for (let k = 0; k < type_cnt; ++k) {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if (related[k][j]) {
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
let ans: number = 0;
for (let i = 0; i < type_cnt; ++i) {
ans = (ans + f[n][i]) % mod;
}
return ans;
}
###Rust
impl Solution {
pub fn num_of_ways(n: i32) -> i32 {
// 预处理出所有满足条件的 type
let mod_val = 1000000007;
let n = n as usize;
let mut types = Vec::new();
for i in 0..3 {
for j in 0..3 {
for k in 0..3 {
if i != j && j != k {
// 只要相邻的颜色不相同就行
// 将其以十进制的形式存储
types.push(i * 9 + j * 3 + k);
}
}
}
}
let type_cnt = types.len();
// 预处理出所有可以作为相邻行的 type 对
let mut related = vec![vec![0; type_cnt]; type_cnt];
for i in 0..type_cnt {
// 得到 types[i] 三个位置的颜色
let x1 = types[i] / 9;
let x2 = types[i] / 3 % 3;
let x3 = types[i] % 3;
for j in 0..type_cnt {
// 得到 types[j] 三个位置的颜色
let y1 = types[j] / 9;
let y2 = types[j] / 3 % 3;
let y3 = types[j] % 3;
// 对应位置不同色，才能作为相邻的行
if x1 != y1 && x2 != y2 && x3 != y3 {
related[i][j] = 1;
}
}
}
// 递推数组
let mut f = vec![vec![0; type_cnt]; n + 1];
// 边界情况，第一行可以使用任何 type
for i in 0..type_cnt {
f[1][i] = 1;
}
for i in 2..=n {
for j in 0..type_cnt {
for k in 0..type_cnt {
// f[i][j] 等于所有 f[i - 1][k] 的和
// 其中 k 和 j 可以作为相邻的行
if related[k][j] == 1 {
f[i][j] = (f[i][j] + f[i - 1][k]) % mod_val;
}
}
}
}
// 最终所有的 f[n][...] 之和即为答案
let mut ans = 0;
for i in 0..type_cnt {
ans = (ans + f[n][i]) % mod_val;
}
ans
}
}
复杂度分析
时间复杂度：$O(T^2N)$，其中 $T$ 是满足要求的 $\textit{type}$ 的数量，在示例一中已经给出了 $T = 12$。在递推的过程中，我们需要计算所有的 $f[i][\textit{type}]$，并且需要枚举上一行的 $\textit{type}'$。
空间复杂度：$O(T^2 + TN)$。我们需要 $T * T$ 的二维数组存储 $\textit{type}$ 之间的关系，$T * N$ 的数组存储递推的结果。注意到由于 $f[i][\textit{type}]$ 只和上一行的状态有关，我们可以使用两个一维数组存储当前行和上一行的 $f$ 值，空间复杂度降低至 $O(T^2 + 2T) = O(T^2)$。
如果读者有一些高中数学竞赛基础，就可以发现上面的这个递推式是线性的，也就是说：
我们可以进行一些化简；
它存在通项公式。
直观上，我们怎么化简方法一中的递推呢？
我们把满足要求的 $\textit{type}$ 都写出来，一共有 $12$ 种：
010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210, 212
我们可以把它们分成两类：
ABC 类：三个颜色互不相同，一共有 $6$ 种：012, 021, 102, 120, 201, 210；
ABA 类：左右两侧的颜色相同，也有 $6$ 种：010, 020, 101, 121, 202, 212。
这样我们就可以把 $12$ 种 $\textit{type}$ 浓缩成了 $2$ 种，尝试写出这两类之间的递推式。我们用 $f[i][0]$ 表示 ABC 类，$f[i][1]$ 表示 ABA 类。在计算时，我们可以将任意一种满足要求的涂色方法带入第 i - 1 行，并检查第 i 行的方案数，这是因为同一类的涂色方法都是等价的：
第 i - 1 行是 ABC 类，第 i 行是 ABC 类：以 012 为例，那么第 i 行只能是120 或 201，方案数为 $2$；
第 i - 1 行是 ABC 类，第 i 行是 ABA 类：以 012 为例，那么第 i 行只能是 101 或 121，方案数为 $2$；
第 i - 1 行是 ABA 类，第 i 行是 ABC 类：以 010 为例，那么第 i 行只能是 102 或 201，方案数为 2；
第 i - 1 行是 ABA 类，第 i 行是 ABA 类：以 010 为例，那么第 i 行只能是 101，121 或 202，方案数为 3。
因此我们就可以写出递推式：
$$
\begin{cases}
f[i][0] = 2 * f[i - 1][0] + 2 * f[i - 1][1] \
f[i][1] = 2 * f[i - 1][0] + 3 * f[i - 1][1]
\end{cases}
$$
###C++
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int numOfWays(int n) {
int fi0 = 6, fi1 = 6;
for (int i = 2; i <= n; ++i) {
int new_fi0 = (2LL * fi0 + 2LL * fi1) % mod;
int new_fi1 = (2LL * fi0 + 3LL * fi1) % mod;
fi0 = new_fi0;
fi1 = new_fi1;
}
return (fi0 + fi1) % mod;
}
};
###Java
class Solution {
static final int MOD = 1000000007;
public int numOfWays(int n) {
long fi0 = 6, fi1 = 6;
for (int i = 2; i <= n; ++i) {
long newFi0 = (2 * fi0 + 2 * fi1) % MOD;
long newFi1 = (2 * fi0 + 3 * fi1) % MOD;
fi0 = newFi0;
fi1 = newFi1;
}
return (int) ((fi0 + fi1) % MOD);
}
}
###Python
class Solution:
def numOfWays(self, n: int) -> int:
mod = 10**9 + 7
fi0, fi1 = 6, 6
for i in range(2, n + 1):
fi0, fi1 = (2 * fi0 + 2 * fi1) % mod, (2 * fi0 + 3 * fi1) % mod
return (fi0 + fi1) % mod
###C#
public class Solution {
private const int mod = 1000000007;
public int NumOfWays(int n) {
long fi0 = 6, fi1 = 6;
for (int i = 2; i <= n; ++i) {
long new_fi0 = (2 * fi0 + 2 * fi1) % mod;
long new_fi1 = (2 * fi0 + 3 * fi1) % mod;
fi0 = new_fi0;
fi1 = new_fi1;
}
return (int)((fi0 + fi1) % mod);
}
}
###Go
func numOfWays(n int) int {
mod := 1000000007
fi0, fi1 := 6, 6
for i := 2; i <= n; i++ {
new_fi0 := (2*fi0 + 2*fi1) % mod
new_fi1 := (2*fi0 + 3*fi1) % mod
fi0, fi1 = new_fi0, new_fi1
}
return (fi0 + fi1) % mod
}
###C
int numOfWays(int n) {
const int mod = 1000000007;
long long fi0 = 6, fi1 = 6;
for (int i = 2; i <= n; ++i) {
long long new_fi0 = (2 * fi0 + 2 * fi1) % mod;
long long new_fi1 = (2 * fi0 + 3 * fi1) % mod;
fi0 = new_fi0;
fi1 = new_fi1;
}
return (fi0 + fi1) % mod;
}
###JavaScript
var numOfWays = function(n) {
const mod = 1000000007;
let fi0 = 6, fi1 = 6;
for (let i = 2; i <= n; i++) {
const new_fi0 = (2 * fi0 + 2 * fi1) % mod;
const new_fi1 = (2 * fi0 + 3 * fi1) % mod;
fi0 = new_fi0;
fi1 = new_fi1;
}
return (fi0 + fi1) % mod;
};
###TypeScript
function numOfWays(n: number): number {
const mod: number = 1000000007;
let fi0: number = 6, fi1: number = 6;
for (let i = 2; i <= n; i++) {
const new_fi0: number = (2 * fi0 + 2 * fi1) % mod;
const new_fi1: number = (2 * fi0 + 3 * fi1) % mod;
fi0 = new_fi0;
fi1 = new_fi1;
}
return (fi0 + fi1) % mod;
}
###Rust
impl Solution {
pub fn num_of_ways(n: i32) -> i32 {
let mod_val: i64 = 1000000007;
let mut fi0: i64 = 6;
let mut fi1: i64 = 6;
for _ in 2..= n {
let new_fi0 = (2 * fi0 + 2 * fi1) % mod_val;
let new_fi1 = (2 * fi0 + 3 * fi1) % mod_val;
fi0 = new_fi0;
fi1 = new_fi1;
}
((fi0 + fi1) % mod_val) as i32
}
}
复杂度分析
时间复杂度：$O(N)$。
空间复杂度：$O(1)$。
1.观察LEETCODE给的官方N=1示例，可以抽象区分为2种类型，ABA和ABC
2.分情况讨论，可知，在下方增加1行时，有9种情况，又可以分为ABA和ABC两个大类
本层的结果 = ABA类的个数m + ABC类的个数n
本层的每个ABA类 => 下层演化 3个ABA + 2个ABC
本层的每个ABC类 => 下层演化 2个ABA + 2个ABC
下层的结果 = ABA类的个数 + ABC类的个数 = (3m+2n) + (2m+2n)
3.数学计算
4.最后给出代码
###csharp
public class Solution {
public int NumOfWays(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 12;
var temp = 1000000007;
long repeat = 6;
long unrepeat = 6;
for(int i = 2; i <=n; i++)
{
long newrep = (repeat * 3) % temp + unrepeat * 2 % temp;
long newunrep = repeat * 2 % temp + unrepeat * 2 % temp;
repeat = newrep;
unrepeat = newunrep;
}
return (int)((repeat + unrepeat)%temp);
}
}
遍历 $\textit{nums}$，同时用一个哈希集合记录遍历过的数。
如果遍历到相同数字（哈希集合中有），由于题目保证只有一个数字是重复的，返回这个数。
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
seen = set()
for x in nums:
if x in seen:
return x
seen.add(x)
class Solution {
public int repeatedNTimes(int[] nums) {
HashSet<Integer> seen = new HashSet<>();
for (int x : nums) {
if (!seen.add(x)) { // x 在 seen 中
return x;
}
}
return -1; // 代码不会执行到这里
}
}
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
unordered_set<int> seen;
for (int x : nums) {
if (!seen.insert(x).second) { // x 在 seen 中
return x;
}
}
return -1; // 代码不会执行到这里
}
};
func repeatedNTimes(nums []int) int {
seen := map[int]struct{}{}
for _, x := range nums {
if _, ok := seen[x]; ok {
return x
}
seen[x] = struct{}{}
}
panic(-1)
}
如何做到 $\mathcal{O}(1)$ 空间？下面再介绍三种方法。
为了让出现 $n$ 次的那个数变成绝对众数，我们可以分类讨论：
这两件事情可以在同一个循环中完成。
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
ans = hp = 0
for x in nums[1:]: # 也可以写 for i in range(1, len(nums)) 避免切片
if x == nums[0]:
return x
if hp == 0: # x 是初始擂主，生命值为 1
ans, hp = x, 1
else: # 比武，同门加血，否则扣血
hp += 1 if x == ans else -1
return ans
class Solution {
public int repeatedNTimes(int[] nums) {
int ans = 0;
int hp = 0;
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x == nums[0]) {
return x;
}
if (hp == 0) { // x 是初始擂主，生命值为 1
ans = x;
hp = 1;
} else { // 比武，同门加血，否则扣血
hp += x == ans ? 1 : -1;
}
}
return ans;
}
}
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
int ans = 0, hp = 0;
for (int i = 1; i < nums.size(); i++) {
int x = nums[i];
if (x == nums[0]) {
return x;
}
if (hp == 0) { // x 是初始擂主，生命值为 1
ans = x;
hp = 1;
} else { // 比武，同门加血，否则扣血
hp += x == ans ? 1 : -1;
}
}
return ans;
}
};
func repeatedNTimes(nums []int) (ans int) {
hp := 0
for _, x := range nums[1:] {
if x == nums[0] {
return x
}
if hp == 0 { // x 是初始擂主，生命值为 1
ans, hp = x, 1
} else if x == ans { // 比武，同门加血，否则扣血
hp++
} else {
hp--
}
}
return
}
设出现次数为 $n$ 的那个数为 $x$。
如果相邻两个 $x$ 之间都至少有一个数，那么 $\textit{nums}$ 至少要有 $2n-1$ 个数，这是合法的。
如果相邻两个 $x$ 之间都至少有两个数，那么 $\textit{nums}$ 至少要有 $3n-2$ 个数。
为了兼容 $n=2$ 的情况，我们可以判断 $\textit{nums}[i]$ 是否与下标 $[i-3, i-1]$ 中的元素相等。
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
x = nums[i]
if x == nums[i - 1] or \
i > 1 and x == nums[i - 2] or \
i > 2 and x == nums[i - 3]:
return x
class Solution {
public int repeatedNTimes(int[] nums) {
for (int i = 1; ; i++) {
int x = nums[i];
if (x == nums[i - 1] ||
i > 1 && x == nums[i - 2] ||
i > 2 && x == nums[i - 3]) {
return x;
}
}
}
}
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
for (int i = 1; ; i++) {
int x = nums[i];
if (x == nums[i - 1] ||
i > 1 && x == nums[i - 2] ||
i > 2 && x == nums[i - 3]) {
return x;
}
}
}
};
func repeatedNTimes(nums []int) int {
for i := 1; ; i++ {
x := nums[i]
if x == nums[i-1] ||
i > 1 && x == nums[i-2] ||
i > 2 && x == nums[i-3] {
return x
}
}
}
在 $\textit{nums}$ 中随机选择两个下标不同的元素，如果两数相等，即找到了重复元素。
首先，在 $[0,n-1]$ 中随机一个数，作为下标 $i$。
然后，我们要在 $[0,i-1]\cup [i+1,n-1]$ 中随机另一个下标 $j$。
但是，标准库只支持在一个连续范围中随机元素，如何在一个间断的区间中随机元素呢？
考虑映射，把 $[0,n-2]$ 映射到 $[0,i-1]\cup [i+1,n-1]$ 中：
$$
f(x) =
\begin{cases}
x, & 0\le x \le i-1 \
x+1, & i\le x \le n-2 \
\end{cases}
$$
具体地，在 $[0,n-2]$ 中随机一个数 $x$：
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
n = len(nums)
while True:
# 在 [0, n-1] 中随机生成两个不同下标
i = randrange(n)
j = randrange(n - 1)
if j >= i:
j += 1
if nums[i] == nums[j]:
return nums[i]
class Solution {
private static final Random rand = new Random();
public int repeatedNTimes(int[] nums) {
int n = nums.length;
while (true) {
// 在 [0, n-1] 中随机生成两个不同下标
int i = rand.nextInt(n);
int j = rand.nextInt(n - 1);
if (j >= i) {
j++;
}
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
}
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
int n = nums.size();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
while (true) {
// 在 [0, n-1] 中随机生成两个不同下标
int i = uniform_int_distribution<>(0, n - 1)(rng);
int j = uniform_int_distribution<>(0, n - 2)(rng);
if (j >= i) {
j++;
}
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
};
func repeatedNTimes(nums []int) int {
n := len(nums)
for {
// 在 [0, n-1] 中随机生成两个不同下标
i := rand.Intn(n)
j := rand.Intn(n - 1)
if j >= i {
j++
}
if nums[i] == nums[j] {
return nums[i]
}
}
}
见下面数学题单的「§6.2 随机化技巧」。
欢迎关注 B站@灵茶山艾府
给你一个整数数组 nums ，该数组具有以下属性：
nums.length == 2 * n.nums 包含 n + 1 个 不同的 元素nums 中恰有一个元素重复 n 次找出并返回重复了 n 次的那个元素。
示例 1：
输入：nums = [1,2,3,3] 输出：3
示例 2：
输入：nums = [2,1,2,5,3,2] 输出：2
示例 3：
输入：nums = [5,1,5,2,5,3,5,4] 输出：5
提示：
2 <= n <= 5000nums.length == 2 * n0 <= nums[i] <= 104nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次根据题目给定的三个条件可推断出：数组中仅有一个元素出现多次，其余元素均出现一次。
又利用数据范围为 $10^4$，我们可以使用数组充当哈希表进行计数，当出现一个 $nums[i]$ 重复出现即是答案。
代码：
###Java
class Solution {
int[] cnts = new int[10010];
public int repeatedNTimes(int[] nums) {
for (int x : nums) {
if (++cnts[x] > 1) return x;
}
return -1;
}
}
假设重复出现的数字是 $x$，数字 $x$ 重复了 $n$ 次，要将这 $n$ 个相同的 $x$ 间隔开，需要 $n - 1$ 个额外数字，而实际上我们除 $x$ 以外还有 $n$ 个额外数字（数字总数为 $n + 1$ 个），因此在我们所能构造出的所有排列方式中，最多 使相邻 $x$ 之间间隔了 $2$ 个额外数字。
对于每个 $nums[i]$ 而言，我们检查往前的三个位置（若有），如果有重复相等情况，说明当前的 $nums[i]$ 即是答案。
代码：
###Java
class Solution {
public int repeatedNTimes(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
int t = nums[i];
if (i - 1 >= 0 && nums[i - 1] == t) return t;
if (i - 2 >= 0 && nums[i - 2] == t) return t;
if (i - 3 >= 0 && nums[i - 3] == t) return t;
}
return -1;
}
}
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！
今天的题目是说，有一个长度为 $2*n$ 的数组，其中有 $n + 1$ 种不同数字，其中有一种数字重复了 $n$ 次。
让我们找出这个重复 $n$ 次的数字。
官方题解中的「哈希表」、「随机选择」方法，都很好理解。
我来解释一下「数学方法」。
结论就是：重复的数字之间的间隔最大为 $2$。
题目给了 $n >= 2$，也就是说数组的长度最少为 $4$。
我们看一下，当数组长度为 $4$ 时，如果让重复的数字间隔尽可能大，我们该怎么做？
把重复的数字放在数组的两头，这样它们之间的间隔是最大的，也就是 $2$。
当数组长度为 $6$ 时，相当于在长度为 $4$ 的数组后面又追加了两个数字，其中还必须有一个重复数字。
你会发现，无论是将长度为 $4$ 的数组重新排列，还是换追加的两个数字的位置，重复数字的 「最小间隔」 都是 $1$。
因此，当数组长度 $>= 6$ 时，重复数字之间的 「最小间隔」 都是 $1$。
综上，重复数字的「最小间隔」为 $1$ 或者 $2$。即，下标之差的最大值为$2$或者 $3$。
我们从左到右遍历数组，分别比较
一定能找到重复数字。
最坏情况是什么呢？
重复数字都集中在数组的右半部分，遍历到右边这一半的数组才能找到重复数字。
使用两层 $for$ 循环，外层 $for$ 是为了遍历，内层 $for$ 是为了遍历可能的间隔。
###Java
class Solution {
public int repeatedNTimes(int[] nums) {
int N = nums.length;
for (int i = 0; i < nums.length - 1; ++i) {
for (int j = 1; j <= 3 && i + j < N; ++j) {
if (nums[i] == nums[i + j])
return nums[i];
}
}
return -1;
}
}
###Python
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
N = len(nums)
for i in range(N - 1):
for j in range(1, 4):
if nums[i] == nums[min(i + j, N - 1)]:
return nums[i]
###C++
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
const int N = nums.size();
for (int i = 0; i < nums.size() - 1; ++i) {
for (int j = 1; j <= 3 && i + j < N; ++j) {
if (nums[i] == nums[i + j])
return nums[i];
}
}
return -1;
}
};
我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。
思路与算法
记重复 $n$ 次的元素为 $x$。由于数组 $\textit{nums}$ 中有 $n+1$ 个不同的元素，而其长度为 $2n$，那么数组中剩余的元素均只出现了一次。也就是说，我们只需要找到重复出现的元素即为答案。
因此我们可以对数组进行一次遍历，并使用哈希集合存储已经出现过的元素。如果遍历到了哈希集合中的元素，那么返回该元素作为答案。
代码
###C++
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
unordered_set<int> found;
for (int num: nums) {
if (found.count(num)) {
return num;
}
found.insert(num);
}
// 不可能的情况
return -1;
}
};
###Java
class Solution {
public int repeatedNTimes(int[] nums) {
Set<Integer> found = new HashSet<Integer>();
for (int num : nums) {
if (!found.add(num)) {
return num;
}
}
// 不可能的情况
return -1;
}
}
###C#
public class Solution {
public int RepeatedNTimes(int[] nums) {
ISet<int> found = new HashSet<int>();
foreach (int num in nums) {
if (!found.Add(num)) {
return num;
}
}
// 不可能的情况
return -1;
}
}
###Python
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
found = set()
for num in nums:
if num in found:
return num
found.add(num)
# 不可能的情况
return -1
###C
struct HashItem {
int key;
UT_hash_handle hh;
};
void freeHash(struct HashItem **obj) {
struct HashItem *curr, *tmp;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr);
}
}
int repeatedNTimes(int* nums, int numsSize){
struct HashItem *found = NULL;
for (int i = 0; i < numsSize; i++) {
struct HashItem *pEntry = NULL;
HASH_FIND_INT(found, &nums[i], pEntry);
if (pEntry != NULL) {
freeHash(&found);
return nums[i];
} else {
pEntry = (struct HashItem *)malloc(sizeof(struct HashItem));
pEntry->key = nums[i];
HASH_ADD_INT(found, key, pEntry);
}
}
// 不可能的情况
freeHash(&found);
return -1;
}
###go
func repeatedNTimes(nums []int) int {
found := map[int]bool{}
for _, num := range nums {
if found[num] {
return num
}
found[num] = true
}
return -1 // 不可能的情况
}
###JavaScript
var repeatedNTimes = function(nums) {
const found = new Set();
for (const num of nums) {
if (found.has(num)) {
return num;
}
found.add(num);
}
// 不可能的情况
return -1;
};
复杂度分析
时间复杂度：$O(n)$。我们只需要对数组 $\textit{nums}$ 进行一次遍历。
空间复杂度：$O(n)$，即为哈希集合需要使用的空间。
思路与算法
我们可以考虑重复的元素 $x$ 在数组 $\textit{nums}$ 中出现的位置。
如果相邻的 $x$ 之间至少都隔了 $2$ 个位置，那么数组的总长度至少为：
$$
n + 2(n - 1) = 3n - 2
$$
当 $n > 2$ 时，$3n-2 > 2n$，不存在满足要求的数组。因此一定存在两个相邻的 $x$，它们的位置是连续的，或者只隔了 $1$ 个位置。
当 $n = 2$ 时，数组的长度最多为 $2n = 4$，因此最多只能隔 $2$ 个位置。
这样一来，我们只需要遍历所有间隔 $2$ 个位置及以内的下标对，判断对应的元素是否相等即可。
代码
###C++
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
int n = nums.size();
for (int gap = 1; gap <= 3; ++gap) {
for (int i = 0; i + gap < n; ++i) {
if (nums[i] == nums[i + gap]) {
return nums[i];
}
}
}
// 不可能的情况
return -1;
}
};
###Java
class Solution {
public int repeatedNTimes(int[] nums) {
int n = nums.length;
for (int gap = 1; gap <= 3; ++gap) {
for (int i = 0; i + gap < n; ++i) {
if (nums[i] == nums[i + gap]) {
return nums[i];
}
}
}
// 不可能的情况
return -1;
}
}
###C#
public class Solution {
public int RepeatedNTimes(int[] nums) {
int n = nums.Length;
for (int gap = 1; gap <= 3; ++gap) {
for (int i = 0; i + gap < n; ++i) {
if (nums[i] == nums[i + gap]) {
return nums[i];
}
}
}
// 不可能的情况
return -1;
}
}
###Python
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
n = len(nums)
for gap in range(1, 4):
for i in range(n - gap):
if nums[i] == nums[i + gap]:
return nums[i]
# 不可能的情况
return -1
###C
int repeatedNTimes(int* nums, int numsSize) {
for (int gap = 1; gap <= 3; ++gap) {
for (int i = 0; i + gap < numsSize; ++i) {
if (nums[i] == nums[i + gap]) {
return nums[i];
}
}
}
// 不可能的情况
return -1;
}
###go
func repeatedNTimes(nums []int) int {
for gap := 1; gap <= 3; gap++ {
for i, num := range nums[:len(nums)-gap] {
if num == nums[i+gap] {
return num
}
}
}
return -1 // 不可能的情况
}
###JavaScript
var repeatedNTimes = function(nums) {
const n = nums.length;
for (let gap = 1; gap <= 3; ++gap) {
for (let i = 0; i + gap < n; ++i) {
if (nums[i] === nums[i + gap]) {
return nums[i];
}
}
}
// 不可能的情况
return -1;
};
复杂度分析
时间复杂度：$O(n)$。我们最多对数组进行三次遍历（除了 $n=2$ 之外，最多两次遍历）。
空间复杂度：$O(1)$。
思路与算法
我们可以每次随机选择两个不同的下标，判断它们对应的元素是否相等即可。如果相等，那么返回任意一个作为答案。
代码
###C++
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
int n = nums.size();
mt19937 gen{random_device{}()};
uniform_int_distribution<int> dis(0, n - 1);
while (true) {
int x = dis(gen), y = dis(gen);
if (x != y && nums[x] == nums[y]) {
return nums[x];
}
}
}
};
###Java
class Solution {
public int repeatedNTimes(int[] nums) {
int n = nums.length;
Random random = new Random();
while (true) {
int x = random.nextInt(n), y = random.nextInt(n);
if (x != y && nums[x] == nums[y]) {
return nums[x];
}
}
}
}
###C#
public class Solution {
public int RepeatedNTimes(int[] nums) {
int n = nums.Length;
Random random = new Random();
while (true) {
int x = random.Next(n), y = random.Next(n);
if (x != y && nums[x] == nums[y]) {
return nums[x];
}
}
}
}
###Python
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
n = len(nums)
while True:
x, y = random.randrange(n), random.randrange(n)
if x != y and nums[x] == nums[y]:
return nums[x]
###C
int repeatedNTimes(int* nums, int numsSize) {
srand(time(NULL));
while (true) {
int x = random() % numsSize, y = random() % numsSize;
if (x != y && nums[x] == nums[y]) {
return nums[x];
}
}
}
###go
func repeatedNTimes(nums []int) int {
n := len(nums)
for {
x, y := rand.Intn(n), rand.Intn(n)
if x != y && nums[x] == nums[y] {
return nums[x]
}
}
}
###JavaScript
var repeatedNTimes = function(nums) {
const n = nums.length;
while (true) {
const x = Math.floor(Math.random() * n), y = Math.floor(Math.random() * n);
if (x !== y && nums[x] === nums[y]) {
return nums[x];
}
}
};
复杂度分析
时间复杂度：期望 $O(1)$。选择两个相同元素的概率为 $\dfrac{n}{2n} \times \dfrac{n-1}{2n} \approx \dfrac{1}{4}$，因此期望 $4$ 次结束循环。
空间复杂度：$O(1)$。
给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。
将大整数加 1，并返回结果的数字数组。
示例 1：
输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。 加 1 后得到 123 + 1 = 124。 因此，结果应该是 [1,2,4]。
示例 2：
输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：输入数组表示数字 4321。 加 1 后得到 4321 + 1 = 4322。 因此，结果应该是 [4,3,2,2]。
示例 3：
输入：digits = [9] 输出：[1,0] 解释：输入数组表示数字 9。 加 1 得到了 9 + 1 = 10。 因此，结果应该是 [1,0]。
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9digits 不包含任何前导 0。题目让我们模拟加一运算。
比如 $23999+1 = 24000$，$999+1=1000$。
算法：
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1 # 进位
return digits
digits[i] = 0 # 进位数字的右边数字都变成 0
# digits 全是 9，加一后变成 100...00
return [1] + digits
class Solution {
public int[] plusOne(int[] digits) {
int n = digits.length;
for (int i = n - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++; // 进位
return digits;
}
digits[i] = 0; // 进位数字的右边数字都变成 0
}
// digits 全是 9，加一后变成 100...00
int[] ans = new int[n + 1];
ans[0] = 1;
return ans;
}
}
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
for (int i = digits.size() - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++; // 进位
return digits;
}
digits[i] = 0; // 进位数字的右边数字都变成 0
}
// digits 全是 9，加一后变成 100...00
digits.push_back(0);
digits[0] = 1;
return digits;
}
};
int* plusOne(int* digits, int digitsSize, int* returnSize) {
for (int i = digitsSize - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++; // 进位
*returnSize = digitsSize;
return digits;
}
digits[i] = 0; // 进位数字的右边数字都变成 0
}
// digits 全是 9，加一后变成 100...00
*returnSize = digitsSize + 1;
int* ans = calloc(digitsSize + 1, sizeof(int));
ans[0] = 1;
return ans;
}
func plusOne(digits []int) []int {
for i, d := range slices.Backward(digits) {
if d < 9 {
digits[i]++ // 进位
return digits
}
digits[i] = 0 // 进位数字的右边数字都变成 0
}
// digits 全是 9，加一后变成 100...00
digits = append(digits, 0)
digits[0] = 1
return digits
}
var plusOne = function(digits) {
for (let i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++; // 进位
return digits;
}
digits[i] = 0; // 进位数字的右边数字都变成 0
}
// digits 全是 9，加一后变成 100...00
digits.push(0);
digits[0] = 1;
return digits;
};
impl Solution {
pub fn plus_one(mut digits: Vec<i32>) -> Vec<i32> {
for d in digits.iter_mut().rev() {
if *d < 9 {
*d += 1; // 进位
return digits;
}
*d = 0; // 进位数字的右边数字都变成 0
}
// digits 全是 9，加一后变成 100...00
digits.push(0);
digits[0] = 1;
digits
}
}
欢迎关注 B站@灵茶山艾府
45 => 46
499 => 500
999 => 1000
###Java
class Solution {
public int[] plusOne(int[] digits) {
int len = digits.length;
for(int i = len - 1; i >= 0; i--) {
digits[i]++;
digits[i] %= 10;
if(digits[i]!=0)
return digits;
}
digits = new int[len + 1];
digits[0] = 1;
return digits;
}
}
###JavaScript
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
const len = digits.length;
for(let i = len - 1; i >= 0; i--) {
digits[i]++;
digits[i] %= 10;
if(digits[i]!=0)
return digits;
}
digits = [...Array(len + 1)].map(_=>0);;
digits[0] = 1;
return digits;
};
<,,,>
想看大鹏画解更多高频面试题，欢迎阅读大鹏的 LeetBook：《画解剑指 Offer 》，O(∩_∩)O
根据题意加一，没错就是加一这很重要，因为它是只加一的所以有可能的情况就只有两种：
加一得十进一位个位数为 $0$ 加法运算如不出现进位就运算结束了且进位只会是一。
所以只需要判断有没有进位并模拟出它的进位方式，如十位数加 $1$ 个位数置为 $0$，如此循环直到判断没有再进位就退出循环返回结果。
然后还有一些特殊情况就是当出现 $99$、$999$ 之类的数字时，循环到最后也需要进位，出现这种情况时需要手动将它进一位。
###Java
class Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10;
if (digits[i] != 0) return digits;
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
}
}
PS：本人并非大佬，这是第一次写思路解释，如有写的不好的地方请多多包涵，哈哈哈
3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？
注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以包含最多15的数字。
示例 1：
输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2] 输出: 1 解释: 下面的子矩阵是一个 3 x 3 的幻方：
示例 2:
输入: grid = [[8]] 输出: 0
提示:
row == grid.lengthcol == grid[i].length1 <= row, col <= 100 <= grid[i][j] <= 15$3\times 3$ 的幻方必须包含 $1$ 到 $9$ 所有数字，这意味着幻方元素和为 $1+2+\cdots + 9 = 45$。
由于每行的和都要相等，所以每行的和为 $\dfrac{45}{3} = 15$。这也是每列的和，对角线的和。
有 $4$ 条经过幻方正中心的线：第二行，第二列，两条对角线。
这 $4$ 条线：
设正中心的数为 $x$ ，则有
$$
1+2+\cdots + 9 + 3x = 60
$$
解得
$$
x = 5
$$
换言之（逆否命题），如果 $3\times 3$ 矩阵正中心的数不是 $5$，那么该矩阵必然不是幻方。
如果 $3\times 3$ 矩阵包含 $1$ 到 $9$ 所有整数，且前两行的和都是 $15$，那么第三行的和为
$$
1+2+\cdots+9-15-15 = 15
$$
同理，如果前两列的和都是 $15$，那么第三列的和必然是 $15$。
如果 $3\times 3$ 矩阵：
下面证明：矩阵对角线的和一定都是 $15$。
设矩阵为
$$
\begin{bmatrix}
a & b & c \
d & 5 & f \
g & h & i \
\end{bmatrix}
$$
由于正中心的数是 $5$，只需证明对角两数之和等于 $10$，即 $a+i=c+g=10$。
在 $1$ 到 $9$ 中选两个不同整数相加等于 $10$，只有如下 $4$ 种情况：
由于已知 $b+h=d+f=10$，消耗了两种情况，剩余的四个数必然在 $a,c,g,i$ 中。比如 $b+h=1+9$，$d+f=3+7$，那么剩余的 $2,4,6,8$ 必然在 $a,c,g,i$ 中。
比如左上角的 $a=4$，那么 $6$ 在哪？
用同样的方法可以证明，$a$ 等于其他数的时候，对角的数 $i$ 一定等于 $10-a$。剩余的另一对和为 $10$ 的数在另一对角。
综上，由已知条件可得，两条对角线的和都是 $15$。
如何快速判断矩阵包含 $1$ 到 $9$ 所有数？可以把数字压缩到一个二进制数 $\textit{mask}$ 中，$\textit{mask}$ 从低到高的 $i$ 位是 $1$ 表示 $i$ 在矩阵中。矩阵包含 $1$ 到 $9$ 所有数相当于 $\textit{mask} = 1111111110_{(2)} = 2^{10}-2=1022$。
###py
class Solution:
def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
ans = 0
for i in range(m - 2):
for j in range(n - 2):
if grid[i + 1][j + 1] != 5:
continue
mask = 0
r_sum = [0] * 3
c_sum = [0] * 3
for r in range(3):
for c in range(3):
x = grid[i + r][j + c]
mask |= 1 << x
r_sum[r] += x
c_sum[c] += x
if mask == 1022 and r_sum[0] == r_sum[1] == c_sum[0] == c_sum[1] == 15:
ans += 1
return ans
###java
class Solution {
public int numMagicSquaresInside(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int ans = 0;
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n - 2; j++) {
if (grid[i + 1][j + 1] != 5) {
continue;
}
int mask = 0;
int[] rSum = new int[3];
int[] cSum = new int[3];
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
int x = grid[i + r][j + c];
mask |= 1 << x;
rSum[r] += x;
cSum[c] += x;
}
}
if (mask == (1 << 10) - 2 &&
rSum[0] == 15 && rSum[1] == 15 &&
cSum[0] == 15 && cSum[1] == 15) {
ans++;
}
}
}
return ans;
}
}
###cpp
class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n - 2; j++) {
if (grid[i + 1][j + 1] != 5) {
continue;
}
int mask = 0;
int r_sum[3]{};
int c_sum[3]{};
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
int x = grid[i + r][j + c];
mask |= 1 << x;
r_sum[r] += x;
c_sum[c] += x;
}
}
if (mask == (1 << 10) - 2 &&
r_sum[0] == 15 && r_sum[1] == 15 &&
c_sum[0] == 15 && c_sum[1] == 15) {
ans++;
}
}
}
return ans;
}
};
###c
int numMagicSquaresInside(int** grid, int gridSize, int* gridColSize) {
int m = gridSize, n = gridColSize[0];
int ans = 0;
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n - 2; j++) {
if (grid[i + 1][j + 1] != 5) {
continue;
}
int mask = 0;
int r_sum[3] = {};
int c_sum[3] = {};
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
int x = grid[i + r][j + c];
mask |= 1 << x;
r_sum[r] += x;
c_sum[c] += x;
}
}
if (mask == (1 << 10) - 2 &&
r_sum[0] == 15 && r_sum[1] == 15 &&
c_sum[0] == 15 && c_sum[1] == 15) {
ans++;
}
}
}
return ans;
}
###go
func numMagicSquaresInside(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
for i := range m - 2 {
for j := range n - 2 {
if grid[i+1][j+1] != 5 {
continue
}
mask := 0
var rSum, cSum [3]int
for r, row := range grid[i : i+3] {
for c, x := range row[j : j+3] {
mask |= 1 << x
rSum[r] += x
cSum[c] += x
}
}
if mask == 1<<10-2 &&
rSum[0] == 15 && rSum[1] == 15 &&
cSum[0] == 15 && cSum[1] == 15 {
ans++
}
}
}
return
}
###js
var numMagicSquaresInside = function (grid) {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
for (let i = 0; i < m - 2; i++) {
for (let j = 0; j < n - 2; j++) {
if (grid[i + 1][j + 1] !== 5) {
continue;
}
let mask = 0;
const rSum = [0, 0, 0];
const cSum = [0, 0, 0];
for (let r = 0; r < 3; r++) {
for (let c = 0; c < 3; c++) {
const x = grid[i + r][j + c];
mask |= 1 << x;
rSum[r] += x;
cSum[c] += x;
}
}
if (mask === (1 << 10) - 2 &&
rSum[0] === 15 && rSum[1] === 15 &&
cSum[0] === 15 && cSum[1] === 15) {
ans++;
}
}
}
return ans;
};
###rust
impl Solution {
pub fn num_magic_squares_inside(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut ans = 0;
for i in 0..m.saturating_sub(2) {
for j in 0..n.saturating_sub(2) {
if grid[i + 1][j + 1] != 5 {
continue;
}
let mut mask = 0;
let mut r_sum = [0; 3];
let mut c_sum = [0; 3];
for (r, row) in grid[i..i + 3].iter().enumerate() {
for (c, &x) in row[j..j + 3].iter().enumerate() {
mask |= 1 << x;
r_sum[r] += x;
c_sum[c] += x;
}
}
if mask == (1 << 10) - 2 &&
r_sum[0] == 15 && r_sum[1] == 15 &&
c_sum[0] == 15 && c_sum[1] == 15 {
ans += 1;
}
}
}
ans
}
}
欢迎关注 B站@灵茶山艾府
