算法---一和零(Kotlin)

题目

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：

输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ones-and-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决思路

解决方法

    fun findMaxForm(strs: Array<String>, m: Int, n: Int): Int {

        val size = strs.size
        val dp = Array(size + 1) { Array(m + 1) { Array(n + 1) { 0 } } }

        //统计0 和 1 的个数
        val array = Array(size) { Array(2) { 0 } }
        strs.forEachIndexed { index, s ->
            val toCharArray = s.toCharArray()
            toCharArray.forEach {
                if (it == '0') {
                    array[index][0]++
                } else {
                    array[index][1]++
                }
            }
        }


        //填充dp数组
        for (i in 0..size) {
            for (j in 0..m) {
                for (k in 0..n) {
                    if (i > 0) {
                        dp[i][j][k] = dp[i - 1][j][k]
                        if (j - array[i - 1][0] >= 0 && k - array[i - 1][1] >= 0) {
                            dp[i][j][k] = dp[i][j][k].coerceAtLeast(dp[i - 1][j - array[i - 1][0]][k - array[i - 1][1]] + 1)
                        }
                    }
                }
            }
        }
        return dp[size][m][n]
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

总结

1.思路要清晰
我们要把问题分解开来，只思考要不要把当前加到集合里面
要么不加入，那么就等于前一个最大的值，要么加入，则最大值就等前面的a个0，b个1的最大值 + 1

七夕快乐