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

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) { } };

rust 解法, 执行用时: 35 ms, 内存消耗: 2.3 MB, 提交时间: 2025-02-21 09:16:13

use std::cmp::{max, min};
use std::mem::swap;

impl Solution {
    pub fn minimum_white_tiles1(floor: String, num_carpets: i32, carpet_len: i32) -> i32 {
        let num_carpets = num_carpets as usize;
        let carpet_len = carpet_len as usize;
        let floor: Vec<_> = floor.chars().collect();
        let n = floor.len();
        let mut d = vec![vec![i32::MAX/2; num_carpets + 1]; n + 1];

        for j in 0..=num_carpets {
            d[0][j] = 0;
        }
        for i in 1..=n {
            d[i][0] = d[i - 1][0] + if floor[i - 1] == '1' { 1 } else { 0 };
        }

        for i in 1..=n {
            for j in 1..=num_carpets {
                d[i][j] = d[i - 1][j] + if floor[i - 1] == '1' { 1 } else { 0 };
                let p = if i >= carpet_len { i - carpet_len } else { 0 };
                d[i][j] = min(d[i][j], d[p][j - 1]);
            }
        }
        d[n][num_carpets]
    }

    // 滚动数组优化
    pub fn minimum_white_tiles(floor: String, num_carpets: i32, carpet_len: i32) -> i32 {
        let num_carpets = num_carpets as usize;
        let carpet_len = carpet_len as usize;
        let floor: Vec<_> = floor.chars().collect();
        let n = floor.len();
        let inf = i32::MAX / 2;
        let mut d = vec![inf; n + 1];
        let mut f = vec![inf; n + 1];

        d[0] = 0;
        for i in 1..=n {
            d[i] = d[i - 1] + if floor[i - 1] == '1' { 1 } else { 0 };
        }

        for j in 1..=num_carpets {
            f[0] = 0;
            for i in 1..=n {
                f[i] = f[i - 1] + if floor[i - 1] == '1' { 1 } else { 0 };
                let p = if i >= carpet_len { i - carpet_len } else { 0 };
                f[i] = min(f[i], d[p]);
            }
            swap(&mut f, &mut d);
        }
        d[n]
    }
}

javascript 解法, 执行用时: 101 ms, 内存消耗: 65.3 MB, 提交时间: 2025-02-21 09:15:15

const INF = 0x3f3f3f3f;

/**
 * @param {string} floor
 * @param {number} numCarpets
 * @param {number} carpetLen
 * @return {number}
 */
var minimumWhiteTiles1 = function(floor, numCarpets, carpetLen) {
    const n = floor.length;
    const d = Array.from({ length: n + 1 }, () => Array(numCarpets + 1).fill(INF));
    for (let j = 0; j <= numCarpets; j++) {
        d[0][j] = 0;
    }
    for (let i = 1; i <= n; i++) {
        d[i][0] = d[i - 1][0] + (floor[i - 1] === '1' ? 1 : 0);
    }
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= numCarpets; j++) {
            d[i][j] = d[i - 1][j] + (floor[i - 1] === '1' ? 1 : 0);
            d[i][j] = Math.min(d[i][j], d[Math.max(0, i - carpetLen)][j - 1]);
        }
    }
    return d[n][numCarpets];
};


// 滚动数组优化
var minimumWhiteTiles = function(floor, numCarpets, carpetLen) {
    let n = floor.length;
    let d = new Array(n + 1).fill(INF);
    let f = new Array(n + 1).fill(INF);
    d[0] = 0;

    for (let i = 1; i <= n; i++) {
        d[i] = d[i - 1] + (floor[i - 1] === '1' ? 1 : 0);
    }

    for (let j = 1; j <= numCarpets; j++) {
        f[0] = 0;
        for (let i = 1; i <= n; i++) {
            f[i] = f[i - 1] + (floor[i - 1] === '1' ? 1 : 0);
            f[i] = Math.min(f[i], d[Math.max(0, i - carpetLen)]);
        }
        [d, f] = [f, d];
    }

    return d[n];
}

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]

上一题

下一题

详情