赣州网站建设公司,深圳网站建设 外包合作,网站怎么设计,搜索引擎优化的具体措施文章目录前言一、完全平方数#xff08;力扣279#xff09;二、单词拆分#xff08;力扣139#xff09;三、打家劫舍#xff08;力扣198#xff09;四、打家劫舍 II前言
1、完全平方数 2、单词拆分 3、打家劫舍 4、打家劫舍 II 一、完全平方数#xff08;力扣279#…
文章目录前言一、完全平方数力扣279二、单词拆分力扣139三、打家劫舍力扣198四、打家劫舍 II前言
1、完全平方数 2、单词拆分 3、打家劫舍 4、打家劫舍 II 一、完全平方数力扣279
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 分析 每一个元素可以重复使用----完全背包问题 每一个物品并没有直接放进数组 每一个物品都是完全平方数 1 、4、9、16、25、36…… 组合数不是排列数 ----外层循环物品 内层循环背包 本题外层for遍历背包内层for遍历物品还是外层for遍历物品内层for遍历背包都是可以的
class Solution {public int numSquares(int n) {int[] nums new int[101];for(int i1;inums.length;i){nums[i] i*i;}int max Integer.MAX_VALUE;int[] dp new int[n1];//初始化for (int j 0; j n; j) {dp[j] max;}dp[0] 0;for(int i1;inums.length;i){for(int j1;jn;j){if(jnums[i])dp[j] Math.min(dp[j],dp[j-nums[i]]1);}}return dp[n];}
}二、单词拆分力扣139
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 分析 可以重复使用字典中的单词----完全背包问题 排列数----外层循环背包、内层循环物品单词
1、dp[j]数组以及含义 dp[j] j是字符串s的长度 dp[j] true表示可以由wordDict拼接而成 2、递推公式 如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true if([j,i] dp[j]true) dp[i] true; 3、初始化 dp[0] true; 其他非零下标全部初始为false 4、遍历顺序 外层循环背包、内层循环物品单词
class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet(wordDict);boolean[] valid new boolean[s.length()1];valid[0] true;for(int j1;js.length();j){for(int i0;ij !valid[j];i){//截取字符串长度if(set.contains(s.substring(i,j)) valid[i])valid[j] true;}}return valid[s.length()];}
}三、打家劫舍力扣198
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 分析 当前的状态我是偷还是不偷呢 当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。
1、确定dp数组以及下标的含义 dp[i]考虑下标i包括i以内的房屋最多可以偷窃的金额为dp[i]。
2、确定递推公式 决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间dp[i] dp[i - 2] nums[i] 第i-1房是不考虑的找出 下标i-2包括i-2以内的房屋最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。如果不偷第i房间dp[i] dp[i-1]; 即考虑i-1房
dp[i] 取最大值dp[i] Math.max[dp[i-1], dp[i-2]nums[i] ];
3、dp数组初始化
从递推公式dp[i] max(dp[i - 2] nums[i], dp[i - 1]);可以看出递推公式的基础就是dp[0] 和 dp[1] dp[0] nums[0]; dp[1] max(nums[0], nums[1]);
4、遍历顺序 从前往后
class Solution {public int rob(int[] nums) {int[] dp new int[nums.length];if (nums.length 1) return nums[0];//初始化dp[0] nums[0];dp[1] Math.max(nums[0],nums[1]);//遍历for(int i2;inums.length;i){dp[i] Math.max(dp[i-1],dp[i-2]nums[i]);}return dp[nums.length-1];}
}四、打家劫舍 II
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 能够偷窃到的最高金额。 分析 与上一题相比 区别在于成环了
成环的话主要有如下三种情况 情况一考虑不包含首尾元素 情况二考虑包含首元素不包含尾元素 情况三考虑包含尾元素不包含首元素 情况二 和 情况三 都包含了情况一了所以只考虑情况二和情况三就可以了。 计算出情况二和情况三的值最后取较大值即可。
class Solution {public int rob(int[] nums) {int len nums.length;if(numsnull||len0) return 0;if(len1) return nums[0];return Math.max(robI(nums,0,len-1),robI(nums,1,len));}int robI(int[] nums,int start,int end) {int x0,y0,z0;for(int istart;iend;i){yz; //y: i-1zMath.max(y,xnums[i]);//z: ixy; //x: i-2;}return z;}
}
