Ones and Zeroes

haitiancoder 發(fā)布于2019-08-14 17:22 / 730人閱讀

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.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

摘要：題目要求當遇到數(shù)組中的值時，即將該值所在的行和列全部改為。新建兩個數(shù)組分別代表該行和該列是否需要清零。然后根據(jù)這兩個數(shù)組的情況對原數(shù)組進行賦值。雖然這意味著犧牲了一點時間性能，但是如果數(shù)據(jù)量非常龐大的話是非常好的一種實現(xiàn)。題目要求 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

摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0