301. 删除无效的括号【困难】
301.删除无效的括号
困难
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1： 输入：s = "()())()" 输出：["(())()","()()()"] 示例 2： 输入：s = "(a)())()" 输出：["(a())()","(a)()()"] 示例 3： 输入：s = ")(" 输出：[""]
提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号
class Solution { private List<String> res = new ArrayList<String>(); public List<String> removeInvalidParentheses(String s) { int lremove = 0; int rremove = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { lremove++; } else if (s.charAt(i) == ')') { if (lremove == 0) { rremove++; } else { lremove--; } } } helper(s, 0, 0, 0, lremove, rremove); return res; } private void helper(String str, int start, int lcount, int rcount, int lremove, int rremove) { if (lremove == 0 && rremove == 0) { if (isValid(str)) { res.add(str); } return; } for (int i = start; i < str.length(); i++) { if (i != start && str.charAt(i) == str.charAt(i - 1)) { continue; } // 如果剩余的字符无法满足去掉的数量要求，直接返回 if (lremove + rremove > str.length() - i) { return; } // 尝试去掉一个左括号 if (lremove > 0 && str.charAt(i) == '(') { helper(str.substring(0, i) + str.substring(i + 1), i, lcount, rcount, lremove - 1, rremove); } // 尝试去掉一个右括号 if (rremove > 0 && str.charAt(i) == ')') { helper(str.substring(0, i) + str.substring(i + 1), i, lcount, rcount, lremove, rremove - 1); } if (str.charAt(i) == ')') { lcount++; } else if (str.charAt(i) == ')') { rcount++; } // 当前右括号的数量大于左括号的数量则为非法,直接返回. if (rcount > lcount) { break; } } } private boolean isValid(String str) { int cnt = 0; for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '(') { cnt++; } else if (str.charAt(i) == ')') { cnt--; if (cnt < 0) { return false; } } } return cnt == 0; } }
309. 最佳买卖股票时机含冷冻期【中等】
309.最佳买卖股票时机含冷冻期
中等
1.5K
相关企业
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1: 输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 示例 2: 输入: prices = [1] 输出: 0
提示：
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
参考
动态规划
class Solution { //动态规划-参考 public int maxProfit(int[] prices) { int n=prices.length; int f[][]=new int[n][3]; for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ if(i==0){ f[i][0]=-prices[0]; f[i][1]=0; f[i][2]=0; }else{ f[i][0]=Math.max(f[i-1][0],f[i-1][2]-prices[i]); f[i][1]=f[i-1][0]+prices[i]; f[i][2]=Math.max(f[i-1][1],f[i-1][2]); } } } return Math.max(f[n-1][1],f[n-1][2]); } }
312. 戳气球【困难】
312.戳气球
困难
1.3K
相关企业
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1： 输入：nums = [3,1,5,8] 输出：167 解释： nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167 示例 2： 输入：nums = [1,5] 输出：10
提示：
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
参考
递归
class Solution { public int[][] rec;//记忆化搜索，结果保存 相当于缓存 public int[] val; public int maxCoins(int[] nums) { //初始化 int n=nums.length; val=new int[n+2]; for(int i=1;i<=n;i++){ val[i]=nums[i-1]; } val[0]=val[n+1]=1; rec=new int[n+2][n+2]; for(int i=0;i<=n+1;i++){//赋值-1 没有计算出结果 Arrays.fill(rec[i],-1); } return solve(0,n+1); } //二分法递归 public int solve(int left,int right){ if(left>=right-1){ return 0; } //没有记忆 if(rec[left][right]!=-1){ return rec[left][right]; } //进行计算 for(int i=left+1;i<right;i++){ int sum=val[left]*val[i]*val[right]; sum+=solve(left,i)+solve(i,right); rec[left][right]=Math.max(rec[left][right],sum); } return rec[left][right]; } }
参考
动态规划
class Solution { public int[][] rec;//记忆化搜索，结果保存 相当于缓存 public int[] val; public int maxCoins(int[] nums) { //初始化 int n=nums.length; val=new int[n+2]; for(int i=1;i<=n;i++){ val[i]=nums[i-1]; } val[0]=val[n+1]=1; rec=new int[n+2][n+2]; //动态规划 for(int i=n-1;i>=0;i--){//从前往后 for(int j=i+2;j<=n+1;j++){//从后往前 for(int k=i+1;k<j;k++){//遍历中间 int sum=val[i]*val[k]*val[j]; sum+=rec[i][k]+rec[k][j]; rec[i][j]=Math.max(rec[i][j],sum); } } } return rec[0][n+1]; } }
322. 零钱兑换【中等】
322.零钱兑换
中等
2.5K
相关企业
给你一个整数数组 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
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
参考
动态规划
class Solution { public int coinChange(int[] coins, int amount) { int max=amount+1; int[] dp=new int[amount+1]; Arrays.fill(dp,max); //初始化 dp[0]=0; for(int i=1;i<=amount;i++){ for(int j=0;j<coins.length;j++){ if(coins[j]<=i){ dp[i]=Math.min(dp[i],dp[i-coins[j]]+1); } } } return dp[amount]>amount?-1:dp[amount]; } }
最后
2023-7-2 10:43:44
