广州正规网站建设企业,c2c十大平台,知名企业,权威网站leetcode 150道题 计划花两个月时候刷完之未完成后转#xff0c;今天完成了5道(114-118)150
gap 了一周#xff0c;以后就不记录时间了。。
114.(70. 爬楼梯) 题目描述#xff1a;
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不…leetcode 150道题 计划花两个月时候刷完之未完成后转今天完成了5道(114-118)150
gap 了一周以后就不记录时间了。。
114.(70. 爬楼梯) 题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢第一版经典动态规划或者递归题目只需要看他最后是跳一次还是跳二次而且他最后跳一次前面的方案和他最后跳一次前面的方案是不冲突的所以是 fxfx-1fx-2
class Solution {public int climbStairs(int n) {if(n1){return 1;}int[] dpnew int[n1];dp[0]1;dp[1]1;for(int i2;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n];}
}115.(198. 打家劫舍) 题目描述
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。第一版还是动态规划但是这个里面是求最大的金额fx 代表的就是 一共 x 个房间可以获得的最大金额也是有两种情况x 这家偷和 不偷 所以 fx max( x金额fx-2 , fx-1)
class Solution {public int rob(int[] nums) {int lennums.length;if(len1){return nums[0];}int[] dpnew int[len1];dp[0]0;dp[1]nums[0];for(int i2;ilen;i){dp[i]Math.max(nums[i-1]dp[i-2],dp[i-1]);}return dp[len];}
}116.(139. 单词拆分) 题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。第一版这个没写出来刚开始想着用递归就可以了超时了
class Solution {public boolean wordBreak(String s, ListString wordDict) {return wordBreakCore(0,s.length(),s,wordDict);} public boolean wordBreakCore(int start,int end,String s, ListString wordDict) {if(startend){return true;}if(startend){return false;}for(int i0;iwordDict.size();i){if(s.substring(start,end).indexOf(wordDict.get(i))!-1){int lefts.substring(start,end).indexOf(wordDict.get(i))start;int rightleftwordDict.get(i).length();boolean tempwordBreakCore(start,left,s,wordDict)wordBreakCore(right,end,s,wordDict);if(temp){return temp;}}}return false;}
}第二版动态规划思路是对的但是没写出来
class Solution {public boolean wordBreak(String s, ListString wordDict) {SetString dictnew HashSet();for(String str:wordDict){dict.add(str);}int lens.length();boolean[] dpnew boolean[len1];dp[0]true;for(int i1;ilen;i){for(int ji-1;j0;j--){if(dp[j]dict.contains(s.substring(j,i))){dp[i]true;break;}}}return dp[len];}
}117.322. 零钱兑换题目描述
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。第一版动态规划fx 代表 x 可以用多少硬币凑出来这个里面有个坑一看最少硬币我就想到排序但是有坑 就是如果 x8 硬币为 【146】 应该最少的是 2 所以不能排序要把所有的走一遍求最小值, fxf(x-coin)1
class Solution {public int coinChange(int[] coins, int amount) {int[] dpnew int[amount1];dp[0]0;for(int i1;iamount;i){boolean flagtrue;dp[i]i;for(int j0;jcoins.length;j){if(i-coins[j]0dp[i-coins[j]]0){dp[i]Math.min(dp[i],dp[i-coins[j]]1);flagfalse;}}if(flag){dp[i]-1;}}return dp[amount];}
}118.(300. 最长递增子序列) 题目描述
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列
。第一版 动态规划
class Solution {public int lengthOfLIS(int[] nums) {int lennums.length;if(len1){return len;}int[] dpnew int[len];int res1;dp[0]1;for(int i1;ilen;i){dp[i]1;for(int ji-1;j0;j--){if(nums[i]nums[j]){dp[i]Math.max(dp[i],dp[j]1);}}resMath.max(res,dp[i]);}return res;}
}总结一下就是刷题还是有点用的看成果真第一次做出来三个题
