看英语做游戏的网站,seo百度贴吧,青云 wordpress加速,wordpress ping列表目录
70.爬楼梯
198.打家劫舍
139.单词拆分
322.零钱兑换 300.最长递增子序列 70.爬楼梯 题意#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f; 提示#xff1a; 1 n …目录
70.爬楼梯
198.打家劫舍
139.单词拆分
322.零钱兑换 300.最长递增子序列 70.爬楼梯 题意 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 提示 1 n 45 【输入样例】n2 【输出样例】2 解题思路 1. 明确当爬到第一阶台阶的时候只有一种做法就是这一步爬1个台阶爬到第二阶台阶的时候有两种做法就是走2个1台阶或1次2台阶。 2.当你要爬到第n阶台阶的时候你有两种选择一种选择是最后一步走1个台阶意味着你的爬法走到n-1个台阶的爬法第二种选择是最后一步走2个台阶意味着你的爬法走到n-2个台阶的爬法所有走到n阶的爬法应该是走到n-1走到n-2 3. 因为n的范围很小用数组实现如果要方便直接将num[1]和num[2]的值先赋值好的话初始化不要写new int[n]不然需要先判断n是否大于1是否大于2. class Solution {public int climbStairs(int n) {int[] numnew int[50];num[1]1;num[2]2;for(int i3;in;i){num[i] num[i-1]num[i-2];}return num[n];}
} 时间 击败了100.00% 内存 击败了39.14% 198.打家劫舍 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 提示 1 nums.length 1000 nums[i] 400 【输入样例】[1,2,3,1] 【输出样例】4 解题思路 1.定义一个数组count存储打劫到第i家的时候可以获得的最高金额 2.寻找关系为了不触动警报的前提下获取最多金额我们采取隔房打劫的思路在第i家的时候如果选择打劫第i家那么其金额应该是nums[i]count[i-2]如果不选择打劫第i家到这里的的金额是count[i-1]要获得最高的金额就需要比较哪一种做法金额较高 3. 确定初始值打劫第一家的时候没有选择count[1]nums[1],打劫第二家也一样不能触发警报只能打劫本身count[2]nums[2],但是其也可以选择不打劫第二家打劫第一家即count[2]max(nums[2],count[1]) class Solution {public int rob(int[] nums) {int len nums.length;int[] count new int[len];count[0] nums[0];if(len 2 )count[1] Math.max(nums[1],count[0]);for(int i 2;ilen;i){count[i] Math.max(count[i-1],count[i-2]nums[i]);}return count[len-1];}
} 时间 击败了100.00% 内存 击败了67.42% 139.单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 提示 1 s.length 3001 wordDict.length 10001 wordDict[i].length 20s 和 wordDict[i] 仅由小写英文字母组成wordDict 中的所有字符串 互不相同 【输入样例】s leetcode, wordDict [leet, code] 【输出样例】true 解题思路 1. 定义数组dp[i]表示字符串长度为i时是否可以拆解为一个或多个在字典中出现的单词可以为true不让为false 2. dp[0]表示空字符串此时默认为true 3. 字符串长度为i时dp[i]的取值依靠什么假设ji,dp[j]true且字符串字串j,i]存在字典中则dp[i]为true 4. 遍历结束时将dp[s.length]return 5. 为了更好的判断字串(j,i]是否在字典中先将字典转换成set class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSetString(wordDict);boolean[] dp new boolean[s.length()1];dp[0] true;for(int i1;is.length();i){for(int j0;j i;j){if(dp[j] set.contains(s.substring(j,i))){dp[i] true;break;//j这里不用再遍历了从下一位i开始}}}return dp[s.length()];}
} 时间 击败了66.63% 内存 击败了70.02% 322.零钱兑换 给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。 你可以认为每种硬币的数量是无限的。 【输入样例】coins [1, 2, 5], amount 11 【输出样例】3 11551 解题思路 1. 定义数组dp[i]表示凑足总额为i所需的最高硬币个数 2. 寻找规律凑足金额为i-coins[j]的最少个数为dp[i-coins[j]],那么只需要加上一个硬币coins[j]即可获得dp[i]dp[i]取小min(dp[i],dp[i-coins[j]]1); 3. 数组初始化凑如总金额为0所需的钱币个数为0dp[0]0其余的dp[i]下标为最大值因为要进行min操作 class Solution {public int coinChange(int[] coins, int amount) {int max Integer.MAX_VALUE;int[] dp new int[amount1];//初始化数组for(int i 1; i amount1;i){dp[i] max;}dp[0] 0;for(int j 0;j coins.length;j){//从这个钱币开始for(int i coins[j]; i amount; i){if(dp[i-coins[j]] ! max){dp[i] Math.min(dp[i],dp[i-coins[j]]1);}}}return dp[amount] max ? -1 : dp[amount];}
} 时间 击败了45.96% 内存 击败了19.52% 300.最长递增子序列 给你一个整数数组 nums 找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 【输入样例】nums [10,9,2,5,3,7,101,18] 【输出样例】4 [2,3,7,101] 解题思路 1. 定义数组dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度 2. 位置i的最长递增子序列等于j从0到i-1各个位置的最长递增子序列1的最大值 3. dp[i]的默认大小为1就是只选择本身的情况 class Solution {public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length];int res 1;for(int i0;inums.length;i){dp[i] 1;}for(int i 1; i nums.length; i){for(int j 0;j i; j){if(nums[i] nums[j]){//递增子序列所以要大才可以计算dp[i] Math.max(dp[i],dp[j]1);}res Math.max(dp[i],res);}}return res;}
} 时间 击败了25.90% 内存 击败了15.18%
