Ones and Zeroes

haitiancoder 发布于2019-08-14 17:22 / 643人阅读

Ones and Zeroes

题目链接：https://leetcode.com/problems...

knapsack problem，这里是最基本的01背包，把cost变成了二维的。
参考背包九讲：http://love-oriented.com/pack...

public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        /* dp[k][i][j]: the maximum # of strings using i 0s and j 1s using strs[0,k]
         * reuse dp[k][i][j] for next level => dp[i][j]
         * value == 1, cost = # of 0s and # of 1s
         */
         int[][] dp = new int[m + 1][n + 1];
         for(String s : strs) {
             int zeros = 0, ones = 0;
             for(int i = 0; i < s.length(); i++) {
                 if(s.charAt(i) == "0") zeros++;
                 else ones++;
             }
             
             for(int i = m; i >= zeros; i--) {
                 for(int j = n; j >= ones; j--) {
                     dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                 }
             }
         }
         
         return dp[m][n];
    }
}

云服务器 GPU云服务器 Ones Zeroes And between and

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66594.html

[Leetcode] Set Matrix Zeroes 矩阵置零

摘要：这个方法的缺点在于，如果我们直接将存入首行或首列来表示相应行和列要置的话，我们很难判断首行或者首列自己是不是该置。 Set Matrix Zeroes Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up...

waltr 2019-08-14 12:31 评论0 收藏0
leetcode73. Set Matrix Zeroes

摘要：题目要求当遇到数组中的值时，即将该值所在的行和列全部改为。新建两个数组分别代表该行和该列是否需要清零。然后根据这两个数组的情况对原数组进行赋值。虽然这意味着牺牲了一点时间性能，但是如果数据量非常庞大的话是非常好的一种实现。题目要求 Given a m x n matrix, if an element is 0, set its entire row and column to 0....

lookSomeone 2019-08-15 10:48 评论0 收藏0
[LintCode/LeetCode/CC] Set Matrix Zeroes

摘要：把矩阵所有零点的行和列都置零，要求不要额外的空间。对于首行和首列的零点，进行额外的标记即可。这道题我自己做了四遍，下面几个问题需要格外注意标记首行和首列时，从到遍历时，若有零点，则首列标记为从到遍历，若有零点，则首行标记为。 Problem Given a m x n matrix, if an element is 0, set its entire row and column t...

zhangwang 2019-08-14 15:22 评论0 收藏0
[LeetCode] 165. Compare Version Numbers

Problem Compare two version numbers version1 and version2.If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0. You may assume that the version strings are non-empty an...

赵春朋 2019-08-16 14:25 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0