README.md

2320. 统计放置房子的方式数

English Version

题目描述

一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。

注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。

 

示例 1：

输入：n = 1
输出：4
解释：
可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。

示例 2：

输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。

 

提示：

• 1 <= n <= 104

解法

Python3

class Solution:
    def countHousePlacements(self, n: int) -> int:
        mod = 10**9 + 7
        f = [[0] * 2 for _ in range(n)]
        f[0] = [1, 1]
        for i in range(1, n):
            f[i][0] = f[i - 1][0] + f[i - 1][1]
            f[i][1] = f[i - 1][0]
        s = sum(f[-1])
        return (s * s) % mod

Java

class Solution {
    public int countHousePlacements(int n) {
        int mod = (int) 1e9 + 7;
        long[][] f = new long[n][2];
        f[0] = new long[] {1, 1};
        for (int i = 1; i < n; ++i) {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
            f[i][1] = f[i - 1][0];
        }
        long s = f[n - 1][0] + f[n - 1][1];
        return (int) ((s * s) % mod);
    }
}

C++

class Solution {
public:
    int countHousePlacements(int n) {
        int mod = 1e9 + 7;
        vector<vector<long>> f(n, vector<long>(2));
        f[0] = {1, 1};
        for (int i = 1; i < n; ++i) {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
            f[i][1] = f[i - 1][0];
        }
        long s = f[n - 1][0] + f[n - 1][1];
        return (int)((s * s) % mod);
    }
};

Go

func countHousePlacements(n int) int {
	mod := int(1e9) + 7
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, 2)
	}
	f[0] = []int{1, 1}
	for i := 1; i < n; i++ {
		f[i][0] = (f[i-1][0] + f[i-1][1]) % mod
		f[i][1] = f[i-1][0]
	}
	s := f[n-1][0] + f[n-1][1]
	return (s * s) % mod
}

TypeScript

function countHousePlacements(n: number): number {
    const mod = BigInt(10 ** 9 + 7);
    let pre = 1n,
        count = 2n;
    for (let i = 2; i <= n; i++) {
        [count, pre] = [(count + pre) % mod, count];
    }
    return Number(count ** 2n % mod);
}

...