统计放置房子的方式数

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

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 10⁴

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int countHousePlacements(int n) { } };

python3 解法, 执行用时: 108 ms, 内存消耗: 15.8 MB, 提交时间: 2023-10-10 15:56:35

class Solution:
    def countHousePlacements(self, n: int) -> int:
        # 当前放不放房子?
        yes, no = 1, 1
        for i in range(2, n + 1):
            yes, no = no, yes + no
        return (yes + no) ** 2 % int(1e9 + 7)

java 解法, 执行用时: 4 ms, 内存消耗: 38.1 MB, 提交时间: 2023-10-10 15:56:05

class Solution {
    public int countHousePlacements(int n) {
        if (n == 1) return 4;
        if (n == 2) return 9;
        int mod = 1000000007, a = 2, b = 3, c = 0;
        for (int i = 2; i < n; i++) {
            c = (a + b) % mod;
            a = b;
            b = c;
        }
        return (int)(1L * c * c % mod);
    }
}

java 解法, 执行用时: 7 ms, 内存消耗: 41.3 MB, 提交时间: 2023-10-10 15:55:52

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

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-10 15:55:16

func countHousePlacements(n int) int {
    // 动态规划
    divd := 1000000007
    
    pre := 1
    cur := 2
    next := 2
    for i:=2; i<=n; i++ {
        next = (pre+cur) % divd
        pre = cur
        cur = next
    }
    return 1*next*next % divd
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-10 15:54:23

const mod int = 1e9 + 7
var f = [1e4 + 1]int{1, 2}
func init() {
	for i := 2; i <= 1e4; i++ {
		f[i] = (f[i-1] + f[i-2]) % mod
	}
}

func countHousePlacements(n int) int {
	return f[n] * f[n] % mod
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 6.4 MB, 提交时间: 2023-10-10 15:53:58

const int MOD = 1e9 + 7, MX = 1e4 + 1;
int f[MX] = {1, 2};
int init = []() {
    for (int i = 2; i < MX; ++i)
        f[i] = (f[i - 1] + f[i - 2]) % MOD;
    return 0;
}();

class Solution {
public:
    int countHousePlacements(int n) {
        return (long) f[n] * f[n] % MOD;
    }
};

java 解法, 执行用时: 4 ms, 内存消耗: 38.2 MB, 提交时间: 2023-10-10 15:53:44

class Solution {
    static final int MOD = (int) 1e9 + 7, MX = (int) 1e4 + 1;
    static final int[] f = new int[MX];

    static {
        f[0] = 1;
        f[1] = 2;
        for (var i = 2; i < MX; ++i)
            f[i] = (f[i - 1] + f[i - 2]) % MOD;
    }

    public int countHousePlacements(int n) {
        return (int) ((long) f[n] * f[n] % MOD);
    }
}

python3 解法, 执行用时: 64 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-10 15:53:29

MOD = 10 ** 9 + 7
f = [1, 2]
for _ in range(10 ** 4 - 1):
    f.append((f[-1] + f[-2]) % MOD)

class Solution:
    def countHousePlacements(self, n: int) -> int:
        return f[n] ** 2 % MOD

上一题

下一题

详情