用地毯覆盖后的最少白色砖块

2209. 用地毯覆盖后的最少白色砖块

给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。

floor[i] = '0' 表示地板上第 i 块砖块的颜色是黑色。
floor[i] = '1' 表示地板上第 i 块砖块的颜色是白色。

同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条黑色的地毯，每一条黑色的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余白色砖块的数目最小。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的最少数目。

示例 1：

输入：floor = "10110101", numCarpets = 2, carpetLen = 2
输出：2
解释：
上图展示了剩余 2 块白色砖块的方案。
没有其他方案可以使未被覆盖的白色砖块少于 2 块。

示例 2：

输入：floor = "11111", numCarpets = 2, carpetLen = 3
输出：0
解释：
上图展示了所有白色砖块都被覆盖的一种方案。
注意，地毯相互之间可以覆盖。

提示：

1 <= carpetLen <= floor.length <= 1000
floor[i] 要么是 '0' ，要么是 '1' 。
1 <= numCarpets <= 1000

原站题解

去查看

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

class Solution { public: int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) { } };

golang 解法, 执行用时: 36 ms, 内存消耗: 11.3 MB, 提交时间: 2023-09-14 00:41:59

func minimumWhiteTiles(floor string, n, carpetLen int) int {
	m := len(floor)
	if n*carpetLen >= m { // 剪枝
		return 0
	}
	f := make([][]int, n+1)
	f[0] = make([]int, m)
	f[0][0] = int(floor[0] & 1)
	for i := 1; i < m; i++ {
		f[0][i] = f[0][i-1] + int(floor[i]&1)
	}
	for i := 1; i <= n; i++ {
		f[i] = make([]int, m)
		// j < carpetLen * i 的 f[i][j] 均为 0
		for j := carpetLen * i; j < m; j++ {
			f[i][j] = min(f[i][j-1]+int(floor[j]&1), f[i-1][j-carpetLen])
		}
	}
	return f[n][m-1]
}

func minimumWhiteTiles2(floor string, n, carpetLen int) int {
	m := len(floor)
	if n*carpetLen >= m { // 剪枝
		return 0
	}
	pre := make([]int, m)
	f := make([]int, m)
	pre[0] = int(floor[0] & 1)
	for i := 1; i < m; i++ {
		pre[i] = pre[i-1] + int(floor[i]&1)
	}
	for i := 1; i <= n; i++ {
		// j < carpetLen * i 的 f[i][j] 均为 0
		f[carpetLen*i-1] = 0
		for j := carpetLen * i; j < m; j++ {
			f[j] = min(f[j-1]+int(floor[j]&1), pre[j-carpetLen])
		}
		pre, f = f, pre
	}
	return pre[m-1]
}

func min(a, b int) int { if a > b { return b }; return a }

cpp 解法, 执行用时: 152 ms, 内存消耗: 85.9 MB, 提交时间: 2023-09-14 00:41:16

class Solution {
public:
    int minimumWhiteTiles(string &floor, int n, int carpetLen) { // 默认代码没加引用，这里补上
        int m = floor.length();
        if (n * carpetLen >= m) return 0; // 剪枝
        vector<vector<int>> f(n + 1, vector<int>(m));
        f[0][0] = (floor[0] == '1');
        for (int i = 1; i < m; ++i)
            f[0][i] = f[0][i - 1] + (floor[i] == '1');
        for (int i = 1; i <= n; ++i)
            // j < carpetLen * i 的 f[i][j] 均为 0
            for (int j = carpetLen * i; j < m; ++j)
                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen]);
        return f[n][m - 1];
    }
    
    // 滚动数组压缩掉第一维
    int minimumWhiteTiles2(string &floor, int n, int carpetLen) { // 默认代码没加引用，这里补上
        int m = floor.length();
        if (n * carpetLen >= m) return 0; // 剪枝
        vector<int> pre(m), f(m);
        pre[0] = (floor[0] == '1');
        for (int i = 1; i < m; ++i)
            pre[i] = pre[i - 1] + (floor[i] == '1');
        for (int i = 1; i <= n; ++i) {
            // j < carpetLen * i 的 f[i][j] 均为 0
            f[carpetLen * i - 1] = 0;
            for (int j = carpetLen * i; j < m; ++j)
                f[j] = min(f[j - 1] + (floor[j] == '1'), pre[j - carpetLen]);
            swap(pre, f);
        }
        return pre[m - 1];
    }


};

java 解法, 执行用时: 31 ms, 内存消耗: 44.7 MB, 提交时间: 2023-09-14 00:40:31

class Solution {
    public int minimumWhiteTiles(String floor, int n, int carpetLen) {
        var m = floor.length();
        if (n * carpetLen >= m) return 0; // 剪枝
        var f = new int[n + 1][m];
        f[0][0] = floor.charAt(0) % 2;
        for (var i = 1; i < m; ++i)
            f[0][i] = f[0][i - 1] + floor.charAt(i) % 2;
        for (var i = 1; i <= n; ++i)
            // j < carpetLen * i 的 f[i][j] 均为 0
            for (var j = carpetLen * i; j < m; ++j)
                f[i][j] = Math.min(f[i][j - 1] + floor.charAt(j) % 2, f[i - 1][j - carpetLen]);
        return f[n][m - 1];
    }

    // 滚动数组压缩第一维
    public int minimumWhiteTiles2(String floor, int n, int carpetLen) {
        var m = floor.length();
        if (n * carpetLen >= m) return 0; // 剪枝
        var pre = new int[m];
        var f = new int[m];
        pre[0] = floor.charAt(0) % 2;
        for (var i = 1; i < m; ++i)
            pre[i] = pre[i - 1] + floor.charAt(i) % 2;
        for (var i = 1; i <= n; ++i) {
            // j < carpetLen * i 的 f[i][j] 均为 0
            f[carpetLen * i - 1] = 0;
            for (var j = carpetLen * i; j < m; ++j)
                f[j] = Math.min(f[j - 1] + floor.charAt(j) % 2, pre[j - carpetLen]);
            var tmp = f;
            f = pre;
            pre = tmp;
        }
        return pre[m - 1];
    }
}

python3 解法, 执行用时: 1252 ms, 内存消耗: 27.5 MB, 提交时间: 2023-09-14 00:39:38

'''
f[i][j] 表示用 i 条地毯覆盖前 j 块板砖时，没被覆盖的白色砖块的最少数目。

'''
class Solution:
    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:
        m = len(floor)
        if n * carpetLen >= m: return 0  # 剪枝
        f = [[0] * m for _ in range(n + 1)]
        f[0][0] = (floor[0] == '1')
        for i in range(1, m):
            f[0][i] = f[0][i - 1] + (floor[i] == '1')
        for i in range(1, n + 1):
            # j < carpetLen * i 的 f[i][j] 均为 0
            for j in range(carpetLen * i, m):
                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])
        return f[n][-1]
        
    # 用滚动数组压缩掉第一维
    def minimumWhiteTiles2(self, floor: str, n: int, carpetLen: int) -> int:
        m = len(floor)
        if n * carpetLen >= m: return 0  # 剪枝
        pre, f = [0] * m, [0] * m
        pre[0] = (floor[0] == '1')
        for i in range(1, m):
            pre[i] = pre[i - 1] + (floor[i] == '1')
        for i in range(1, n + 1):
            # j < carpetLen * i 的 f[i][j] 均为 0
            f[carpetLen * i - 1] = 0
            for j in range(carpetLen * i, m):
                f[j] = min(f[j - 1] + (floor[j] == '1'), pre[j - carpetLen])
            pre, f = f, pre
        return pre[-1]

上一题

下一题

详情