栈有效的括号20. 有效的括号 - 力扣LeetCode给定一个只包括(){}[]的字符串s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例 1输入s ()输出true示例 2输入s ()[]{}输出true示例 3输入s (]输出false示例 4输入s ([])输出true示例 5输入s ([)]输出false解法及思路栈遇到左括号入栈遇到右括号检查栈顶是否匹配。1. 遍历字符串 2. 遇到左括号入栈 3. 遇到右括号 - 栈为空 → false - 栈顶不匹配 → false - 匹配 → 弹出栈顶 4. 遍历结束栈为空 → true输入{[]}遍历 { → 入栈 → stack[{] [ → 入栈 → stack[{, [] ] → 栈顶是[匹配 → 弹出 → stack[{] } → 栈顶是{匹配 → 弹出 → stack[] } → 字符串遍历完 栈为空 → true ✅输入([)]遍历 ( → 入栈 → stack[(] [ → 入栈 → stack[(, [] ) → 栈顶是[不匹配 → false ❌ 结果falseclass Solution { public boolean isValid(String s) { DequeCharacter stacknew ArrayDeque(); for(char c:s.toCharArray()){ if(c(){ stack.push()); }else if(c[){ stack.push(]); }else if(c{){ stack.push(}); }else{ if(stack.isEmpty()||stack.pop()!c){ return false; } } } return stack.isEmpty(); } }最小栈155. 最小栈 - 力扣LeetCode设计一个支持pushpoptop操作并能在常数时间内检索到最小元素的栈。实现MinStack类:MinStack()初始化堆栈对象。void push(int value)将元素value推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。示例 1:输入[MinStack,push,push,push,getMin,pop,top,getMin] [[],[-2],[0],[-3],[],[],[],[]]输出[null,null,null,null,-3,null,0,-2]解释MinStack minStack new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); -- 返回 -3. minStack.pop(); minStack.top(); -- 返回 0. minStack.getMin(); -- 返回 -2.解法及思路辅助栈用一个辅助栈记录每个位置的最小值。主栈存储所有元素 辅助栈存储对应位置的最小值 push时 主栈入栈 辅助栈入 min(当前元素, 辅助栈栈顶) pop时 两个栈都弹出 getMin时 返回辅助栈栈顶操作序列push(-2), push(0), push(-3)push(-2): 主栈[-2] 辅助栈[-2] ← 最小值-2 push(0): 主栈[-2, 0] 辅助栈[-2, -2] ← min(0, -2) -2 push(-3): 主栈[-2, 0, -3] 辅助栈[-2, -2, -3] ← min(-3, -2) -3 getMin() → 辅助栈栈顶 -3 ✅ pop(): 主栈[-2, 0] 辅助栈[-2, -2] top() → 主栈栈顶 0 ✅ getMin() → 辅助栈栈顶 -2 ✅class MinStack { private DequeInteger stack; private DequeInteger minstack; public MinStack() { stacknew ArrayDeque(); minstacknew ArrayDeque(); } public void push(int value) { stack.push(value); //辅助入栈min if(minstack.isEmpty()){ minstack.push(value); }else{ int minvalMath.min(minstack.peek(),value); minstack.push(minval); } } public void pop() { stack.pop(); minstack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minstack.peek(); } }贪心算法买股票的最佳时机121. 买卖股票的最佳时机 - 力扣LeetCode给定一个数组prices它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择某一天买入这只股票并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回0。示例 1输入[7,1,5,3,6,4]输出5解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。 注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。示例 2输入prices [7,6,4,3,1]输出0解释在这种情况下, 没有交易完成, 所以最大利润为 0。解法及思路一次遍历遍历价格记录历史最低价计算当前卖出的利润更新最大利润。1. 记录历史最低价 minPrice 2. 对于每天的价格 - 计算利润 当前价格 - minPrice - 更新最大利润 - 更新 minPrice min(minPrice, 当前价格)prices [7, 1, 5, 3, 6, 4]第1天price7 minPrice 7 maxProfit 0 第2天price1 profit 1 - 7 -6不买 minPrice min(7, 1) 1 maxProfit 0 第3天price5 profit 5 - 1 4 maxProfit max(0, 4) 4 minPrice min(1, 5) 1 第4天price3 profit 3 - 1 2 maxProfit max(4, 2) 4 第5天price6 profit 6 - 1 5 maxProfit max(4, 5) 5 minPrice min(1, 6) 1 第6天price4 profit 4 - 1 3 maxProfit max(5, 3) 5 结果5 ✅class Solution { public int maxProfit(int[] prices) { int minpriceInteger.MAX_VALUE; int maxprofit0; for(int i0;iprices.length;i){ if(prices[i]minprice){ minpriceprices[i];//更新最小价格 }else if(prices[i]-minpricemaxprofit){ maxprofitprices[i]-minprice;//更新最大利润 } } return maxprofit; } }跳跃游戏55. 跳跃游戏 - 力扣LeetCode给你一个非负整数数组nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回true否则返回false。示例 1输入nums [2,3,1,1,4]输出true解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2输入nums [3,2,1,0,4]输出false解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。解法及思路贪心维护能到达的最远位置遍历数组更新最远位置。1. 初始化 maxReach 0能到达的最远位置 2. 遍历数组 - 如果 i maxReach说明当前位置不可达返回false - 更新 maxReach max(maxReach, i nums[i]) - 如果 maxReach n-1返回true 3. 遍历结束返回truenums [2,3,1,1,4]初始maxReach 0 i0: nums[0]2 i0 maxReach0 ✅ maxReach max(0, 02) 2 2 4继续 i1: nums[1]3 i1 maxReach2 ✅ maxReach max(2, 13) 4 4 4 → 返回true ✅nums [3,2,1,0,4]初始maxReach 0 i0: nums[0]3 maxReach max(0, 03) 3 i1: nums[1]2 maxReach max(3, 12) 3 i2: nums[2]1 maxReach max(3, 21) 3 i3: nums[3]0 maxReach max(3, 30) 3 i4: nums[4]4 i4 maxReach3 ❌ 不可达 → 返回falseclass Solution { public boolean canJump(int[] nums) { int maxreach0; for(int i0;inums.length;i){ if(imaxreach) return false; maxreachMath.max(maxreach,inums[i]); if(inums[i]nums.length-1){ return true; } } return false; } }动态规划爬楼梯70. 爬楼梯 - 力扣LeetCode假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢示例 1输入n 2输出2解释有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶示例 2输入n 3输出3解释有三种方法可以爬到楼顶。 1. 1 阶 1 阶 1 阶 2. 1 阶 2 阶 3. 2 阶 1 阶解法及思路动态规划到达第 n 阶可以从第 n-1 阶爬1步或从第 n-2 阶爬2步。dp[n] dp[n-1] dp[n-2] dp[1] 1 dp[2] 2n 5dp[1] 11种1 dp[2] 22种11, 2 dp[3] dp[2] dp[1] 2 1 3 dp[4] dp[3] dp[2] 3 2 5 dp[5] dp[4] dp[3] 5 3 8示意图n1: 1 n2: 2 n3: 3 n4: 5 n5: 8就是斐波那契数列class Solution { public int climbStairs(int n) { if(n2) return n; int[] dpnew int[n1]; dp[1]1; dp[2]2; for(int i3;in;i){ dp[i]dp[i-1]dp[i-2]; } return dp[n]; } }打家劫舍198. 打家劫舍 - 力扣LeetCode你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。示例 1输入[1,2,3,1]输出4解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。 偷窃到的最高金额 1 3 4 。示例 2输入[2,7,9,3,1]输出12解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。 偷窃到的最高金额 2 9 1 12 。解法及思路动态规划对于第 i 间房有两种选择1. 偷第 i 间金额 dp[i-2] nums[i] 2. 不偷第 i 间金额 dp[i-1] 取最大值状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])nums [2, 7, 9, 3, 1]dp[0] 2只有1间房偷 dp[1] max(2, 7) 7偷7 dp[2] max(7, 29) max(7, 11) 11偷2和9 dp[3] max(11, 73) max(11, 10) 11不偷3 dp[4] max(11, 111) max(11, 12) 12偷2,9,1 结果12 ✅class Solution { public int rob(int[] nums) { if(nums.length0) return 0; if(nums.length1) return nums[0]; int[] dpnew int[nums.length]; dp[0]nums[0]; dp[1]Math.max(nums[0],nums[1]); for(int i2;inums.length;i){ //选和不选 dp[i]Math.max(dp[i-2]nums[i],dp[i-1]); } return dp[nums.length-1]; } }零钱兑换322. 零钱兑换 - 力扣LeetCode给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1 。你可以认为每种硬币的数量是无限的。示例 1输入coins [1, 2, 5], amount 11输出3解释11 5 5 1示例 2输入coins [2], amount 3输出-1示例 3输入coins [1], amount 0输出0解法及思路动态规划dp[i] 表示凑成金额 i 所需的最少硬币数。dp[i] min(dp[i - coin]) 1 对所有 coin dp[0] 0解释凑成金额 i可以选一枚硬币 coin 然后凑成 i - coin 所以 dp[i] dp[i - coin] 1 取所有 coin 中最小的coins [1, 2, 5], amount 11dp[0] 0 dp[1] min(dp[0]1) 1 dp[2] min(dp[1]1, dp[0]1) min(2, 1) 1 dp[3] min(dp[2]1, dp[1]1) min(2, 2) 2 dp[4] min(dp[3]1, dp[2]1) min(3, 2) 2 dp[5] min(dp[4]1, dp[3]1, dp[0]1) min(3, 3, 1) 1 ... dp[11] min(dp[10]1, dp[9]1, dp[6]1) min(3, 3, 3) 3结果3 ✅class Solution { public int coinChange(int[] coins, int amount) { int[] dpnew int[amount1]; Arrays.fill(dp,amount1); dp[0]0; for(int i1;iamount;i){ for(int coin:coins){ if(coini){ dp[i]Math.min(dp[i-coin]1,dp[i]); } } } return dp[amount]amount?-1:dp[amount]; } }单词拆分139. 单词拆分 - 力扣LeetCode给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。示例 1输入:s leetcode, wordDict [leet, code]输出:true解释:返回 true 因为 leetcode 可以由 leet 和 code 拼接成。示例 2输入:s applepenapple, wordDict [apple, pen]输出:true解释:返回 true 因为 applepenapple 可以由 apple pen apple 拼接成。 注意你可以重复使用字典中的单词。示例 3输入:s catsandog, wordDict [cats, dog, sand, and, cat]输出:false解法及思路动态规划dp[i] 表示 s 的前 i 个字符能否被拆分。dp[i] true 表示 s[0..i-1] 可以被拆分 dp[0] true空字符串可以被拆分 对于每个 i遍历 j i 如果 dp[j] true 且 s[j..i-1] 在字典中 则 dp[i] trues leetcode, wordDict [leet, code]dp[0] true空串 i1: s[0..0]l不在字典 → dp[1]false i2: s[0..1]le不在字典 → dp[2]false i3: s[0..2]lee不在字典 → dp[3]false i4: s[0..3]leet在字典 → dp[4]true i5: 检查j0..4 j0: dp[0]true, s[0..4]leetc不在字典 j1: dp[1]false j2: dp[2]false j3: dp[3]false j4: dp[4]true, s[4..4]c不在字典 → dp[5]false i6: 检查j0..5 j4: dp[4]true, s[4..5]co不在字典 → dp[6]false i7: 检查j0..6 j4: dp[4]true, s[4..6]cod不在字典 → dp[7]false i8: 检查j0..7 j4: dp[4]true, s[4..7]code在字典 → dp[8]true 结果dp[8]true ✅class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString setnew HashSet(wordDict); boolean[] dpnew boolean[s.length()1]; dp[0]true; for(int i1;is.length();i){ for(int j0;ji;j){ if(dp[j]set.contains(s.substring(j,i))){ dp[i]true; break; } } } return dp[s.length()]; } }最长递增子序列300. 最长递增子序列 - 力扣LeetCode给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例 1输入nums [10,9,2,5,3,7,101,18]输出4解释最长递增子序列是 [2,3,7,101]因此长度为 4 。示例 2输入nums [0,1,0,3,2,3]输出4示例 3输入nums [7,7,7,7,7,7,7]输出1解法及思路动态规划dp[i] 以 nums[i] 结尾的最长递增子序列长度。对于每个 i遍历 j i 如果 nums[j] nums[i] 则 dp[i] max(dp[i], dp[j] 1)nums [10, 9, 2, 5, 3, 7, 101, 18]dp[0] 110 dp[1] 19前面没有比9小的 dp[2] 12 dp[3] 22,5 dp[4] 22,3 dp[5] 32,3,7 dp[6] 42,3,7,101 dp[7] 42,3,7,18 结果4 ✅class Solution { public int lengthOfLIS(int[] nums) { int[] dpnew int[nums.length]; Arrays.fill(dp, 1); int maxlen1; for(int i1;inums.length;i){ for(int j0;ji;j){ if(nums[j]nums[i]){ dp[i]Math.max(dp[i],dp[j]1); } } maxlenMath.max(maxlen,dp[i]); } return maxlen; } }