首页 > 其他分享 >LeetCode 474.一和零

LeetCode 474.一和零

时间:2023-08-12 17:31:37浏览次数:45  
标签:int strs ones 子集 474 zeros LeetCode dp

1.题目:

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

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

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

 https://leetcode.cn/problems/ones-and-zeroes/description/

示例 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 。



2.代码:

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp= new int[m+1][n+1];
        for(String s:strs){//得到每一个字符串
            int zeros=0,ones=0;//分别记录每一个字符串中的0和1的数量
            for(char c:s.toCharArray()){
                if(c=='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];
    }
}













标签:int,strs,ones,子集,474,zeros,LeetCode,dp
From: https://blog.51cto.com/u_15806469/7060387

相关文章

  • #yyds干货盘点# LeetCode程序员面试金典:最短回文串
    题目:给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 示例1:输入:s="aacecaaa"输出:"aaacecaaa"示例2:输入:s="abcd"输出:"dcbabcd"代码实现:classSolution{publicStringshortestPalindrome(Strings){......
  • #yyds干货盘点# LeetCode程序员面试金典:超级次方
    1.简述:你的任务是计算  对  取模, 是一个正整数, 是一个非常大的正整数且会以数组形式给出。ab1337ab 示例1:输入:a=2,b=[3]输出:8示例2:输入:a=2,b=[1,0]输出:1024示例3:输入:a=1,b=[4,3,3,8,5,2]输出:1示例4:输入:a=2147483647,b=[2,0,0]输出:11982.代码实......
  • #yyds干货盘点# LeetCode程序员面试金典:打家劫舍 II
    题目:你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。给定一个代表每个房屋存放金......
  • #yyds干货盘点# LeetCode程序员面试金典:两整数之和
    1.简述:给你两个整数 和 ,不使用 运算符  和  ,计算并返回两整数之和。ab+- 示例1:输入:a=1,b=2输出:3示例2:输入:a=2,b=3输出:52.代码实现:classSolution{publicintgetSum(inta,intb){while(b!=0){intcarry=(a&b)<<1;......
  • LeetCode 494.目标和
    1.题目:https://leetcode.cn/problems/target-sum/description/给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :例如,nums=[2,1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后......
  • LeetCode 刷题难?动画图解才是正确姿势!
    BAT等国内的一线名企,在招聘工程师的过程中,对算法和数据结构都会重点考察。但算法易学难精,我的很多粉丝技术能力不错,但面试时总败在算法这一关,拿不到好Offer。但说实话,数据结构和算法花点时间,用对方法,很容易解决。面试官为什么爱问数据结构与算法,答案很简单:算法能力能够准确辨别一......
  • LeetCode 1049.最后一块石头的重量II
    1.题目:1049. 最后一块石头的重量II有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x<=y。那么粉碎的可能结果如下:如果 x==y,那么两块石头都会被完全粉......
  • Leetcode 977. 有序数组的平方(Squares of a sorted array)
    题目链接给你一个按非递减顺序排序的整数数组nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序.示例1:输入:nums=[-4,-1,0,3,10]输出:[0,1,9,16,100]解释:平方后,数组变为[16,1,0,9,100]排序后,数组变为[0,1,9,16,100]示例2:输入:nums=[-7,-3,2,3,11]输......
  • Leetcode 27. 移除元素(Remove Element)
    题目链接给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后数组的新长度.不要使用额外的数组空间,你必须仅使用O(1)额外空间并原地修改输入数组.元素的顺序可以改变.你不需要考虑数组中超出新长度后面的元素.说明:为什么返回数值是整数,但输......
  • Leetcode167. 两数之和 II - 输入有序数组(双指针)
    题目:两数之和II-输入有序数组(双指针)给你一个下标从1开始的整数数组numbers,该数组已按非递减顺序排列,请你从数组中找出满足相加之和等于目标数target的两个数。如果设这两个数分别是numbers[index1]和numbers[index2],则1<=index1<index2<=numbers.length......