Ones and Zeroes

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

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云服務(wù)器云服務(wù)器 Ones Zeroes And between and

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66594.html

相關(guān)文章

[Leetcode] Set Matrix Zeroes 矩陣置零

摘要：這個(gè)方法的缺點(diǎn)在于，如果我們直接將存入首行或首列來(lái)表示相應(yīng)行和列要置的話(huà)，我們很難判斷首行或者首列自己是不是該置。 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 評(píng)論0 收藏0
leetcode73. Set Matrix Zeroes

摘要：題目要求當(dāng)遇到數(shù)組中的值時(shí)，即將該值所在的行和列全部改為。新建兩個(gè)數(shù)組分別代表該行和該列是否需要清零。然后根據(jù)這兩個(gè)數(shù)組的情況對(duì)原數(shù)組進(jìn)行賦值。雖然這意味著犧牲了一點(diǎn)時(shí)間性能，但是如果數(shù)據(jù)量非常龐大的話(huà)是非常好的一種實(shí)現(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 評(píng)論0 收藏0
[LintCode/LeetCode/CC] Set Matrix Zeroes

摘要：把矩陣所有零點(diǎn)的行和列都置零，要求不要額外的空間。對(duì)于首行和首列的零點(diǎn)，進(jìn)行額外的標(biāo)記即可。這道題我自己做了四遍，下面幾個(gè)問(wèn)題需要格外注意標(biāo)記首行和首列時(shí)，從到遍歷時(shí)，若有零點(diǎn)，則首列標(biāo)記為從到遍歷，若有零點(diǎn)，則首行標(biāo)記為。 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 評(píng)論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 評(píng)論0 收藏0
前端 | 每天一個(gè) LeetCode

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

張漢慶 2019-08-23 13:42 評(píng)論0 收藏0