做网站文章要一篇一篇的写吗,公司建设网站怎么做账,万维建设网站,百度热门一.动态规划
474.一和零 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度#xff0c;该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素#xff0c;集合 x 是集合 y 的 子集 。 思路:这道题更像是另一种的0-…一.动态规划
474.一和零 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素集合 x 是集合 y 的 子集 。 思路:这道题更像是另一种的0-1背包问题 其中m和n相当于背包容量字符串本身的个数相当于物品的价值value[i]。首先初始化dp数组然后要统计每个字符串的0和1的数量才能进行下面的操作 class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (n 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum 0, zeroNum 0;for (char c : str) {if (c 0) zeroNum;else oneNum;}for(int im;izeroNum;i--){//m n相当于背包容量 要从大到小去遍历for(int jn;joneNum;j--){// dp[i][j]max(dp[i][j],dp[i-zeroNum][j-oneNum]1);}}}return dp[m][n];}
}; 完全背包问题:
完全背包问题和0-1背包问题最主要的区别在于一个物品是能取一次还是取多次。 在代码上的区别的话就是滚动数组第二个for循环是正序遍历因为正序遍历和倒序遍历的区别就是在于能否重复选取。
518.零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 思路: 是一种完全背包问题amount是要凑的零钱数 相当于背包容量coins相当于物品 用来凑成amount的(凑背包容量)注意 求装满背包有几种方法类似的题目递推公式基本都是这样的 dp[j] dp[j - nums[i]] 如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
为什么呢? 因为求组合数时 外层先遍历物品就是先拿出一件物品遍历一遍之后在拿出一件物品遍历一遍不会出现{2,1}的情况而外层for遍历背包内层for循环遍历物品。物品是会被反复取到的。详细说一说的话就是: 先遍历物品后遍历背包是这样比如外层循环固定coins【1】在内层循环遍历背包时随着背包不断增加coins【1】可以重复被添加进来而由于外层循环固定了因此coins【2】只能在下一次外层循环添加进不同大小的背包中这么看的话coins【i1】只能在coins【i】之后了如果先遍历背包后遍历物品那么外层循环先固定背包大小j然后在大小为j的背包中循环遍历添加物品然后在下次外层循环背包大小变为j1此时仍要执行内层循环遍历添加物品也就会出现在上一轮外层循环中添加coins【2】的基础上还能再添加coins【1】的情况那么就有了coins【1】在coins【2】之后的情况了。 class Solution {
public:int change(int amount, vectorint coins) {//完全背包问题vectorint dp(amount1,0);dp[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];}
}; 377.组合问题④ 给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 class Solution {
public:int combinationSum4(vectorint nums, int target) {//组合不强调元素之间的顺序 排列强调元素之间的顺序。//1.先遍历物品在遍历背包是组合 //2.先遍历背包在遍历物品是排序数// 由于在题目下面的定义中 顺序不同的序列被视作不同的组合//所以选择第二个vectorint dp(target1,0);dp[0]1;for(int i0;itarget;i){for(int j0;jnums.size();j){if(inums[j]dp[i]INT_MAX-dp[i-nums[j]])//当前的背包容量要大于物品容量 否则无意义//防止整数溢出 如果不进行这个判断当dp[i]和dp[i-nums[j]]都很大时直接相加可能会导致整数溢出。dp[i]dp[i-nums[j]];}}return dp[target];}
};
二.GitHub链接本地仓库
频繁出现gitgithub.com: Permission denied (publickey).的问题跟着csdn上的博主重走一遍流程就好了 流程如下:
进入git bash界面然后 第1步git config --global --list 验证邮箱与GitHub注册时输入的是否一致 可以通过git config --global user.name “yourname”git config --global user.email “emailemail.com ”这里得名字和邮箱都是注册github时用的设置全局用户名和邮箱。 第2步ssh-keygen -t rsa -C “这里换上你的邮箱”一路回车(注意不需要输入其他内容直到生成密钥。 注意;根据上面地址和文件名可知 会在/Users/***/路径下生成一个.ssh\id_rsa.pub文件密钥就存储在其中:
第3步使用浏览器到git仓库添加秘钥右上角-- settings -- SSH and GPG keys 根据生成的秘钥在github上加入ssh秘钥
最后 ssh -T gitgithub.com 测试一下通不通通了显示如下 三.将本地仓库的文件推送到远程仓库:
本地仓库和远程仓库的示意图如下:(取自GeekHour) 链接成功后,可以在本地仓库创建文件并通过push命令将文件推送给远程仓库
首先通过
创建远程仓库别名和地址
然后通过
查看一下 可知 当前的远程仓库名为test001
我在创建一个test002(测试)
切换main分支
并将当前文件推送到远程仓库的main分支 github上显示 代表推送成功。
