当前位置:网站首页>动态规划、背包问题 6/28 121-124
动态规划、背包问题 6/28 121-124
2022-08-10 05:36:00 【吉良吉影__.】
1.最长回文子序列( LeetCode 516 )
动态规划
dp[i][j] i,j之间的最长回文子序列
class Solution {
/* dp[i][j] = 下标i 到 下标j 之间的最长回文子序列长度 初始值 i > j 时dp[i][j] = 0 dp[i][i] = 1 状态转移: 当s[i] = s[j]时,dp[i][j] = dp[i + 1][j - 1] + 2 当s[i] != s[j]时,dp[i][j] = Math.max(dp[i][j - 1],dp[i + 1][j]) */
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
//状态转移时需要用到下一行的数据,所以会逆着遍历
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
}
2.最长回文子串( LeetCode 5 )
方法一:动态规划
参照上一题
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int[][] dp = new int[n][n];
int ans = 1;
int[] ansStr = new int[2];
//状态转移时需要用到下一行的数据,所以会逆着遍历
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);
//如果 j - i + 1 == dp[i][j] 成立,则代表i,j范围为回文串,包括i,j
if (j - i + 1 > ans && (j - i + 1 == dp[i][j])){
ans = j - i + 1;
ansStr[0] = i;
ansStr[1] = j;
}
}
}
return s.substring(ansStr[0],ansStr[1] + 1);
}
}
方法二:动态规划
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
boolean[][] dp = new boolean[len][len];
// 初始化:所有长度为 1 的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
// 枚举左边界,左边界的上限设置可以宽松一些
for (int i = 0; i < len; i++) {
// 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界,就可以退出当前循环
if (j >= len) {
break;
}
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
3.目标和( LeetCode 494 )
方法一:回溯
class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int target) {
backtrack(nums, target, 0, 0);
return count;
}
public void backtrack(int[] nums, int target, int index, int sum) {
if (index == nums.length) {
if (sum == target) {
count++;
}
} else {
backtrack(nums, target, index + 1, sum + nums[index]);
backtrack(nums, target, index + 1, sum - nums[index]);
}
}
}
方法二:动态规划
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int n = nums.length, neg = diff / 2;
//dp[i][j]nums前i个数中凑成和为j的组合数
int[][] dp = new int[n + 1][neg + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= neg; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= num) {
dp[i][j] += dp[i - 1][j - num];
}
}
}
return dp[n][neg];
}
}
4.最后一块石头的重量 II( LeetCode 1049 )
方法一:动态规划
01背包
朴素数组
class Solution {
public int lastStoneWeightII(int[] ss) {
int n = ss.length;
int sum = 0;
for (int i : ss) sum += i;
int t = sum / 2;
int[][] f = new int[n + 1][t + 1];
for (int i = 1; i <= n; i++) {
int x = ss[i - 1];
for (int j = 0; j <= t; j++) {
f[i][j] = f[i - 1][j];
if (j >= x) f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + x);
}
}
return Math.abs(sum - f[n][t] - f[n][t]);
}
}
方法二:
01背包 滚动数组优化
class Solution {
public int lastStoneWeightII(int[] ss) {
int n = ss.length;
int sum = 0;
for (int i : ss) sum += i;
int t = sum / 2;
int[][] f = new int[2][t + 1];
for (int i = 1; i <= n; i++) {
int x = ss[i - 1];
int a = i & 1, b = (i - 1) & 1;
for (int j = 0; j <= t; j++) {
f[a][j] = f[b][j];
if (j >= x) f[a][j] = Math.max(f[a][j], f[b][j - x] + x);
}
}
return Math.abs(sum - f[n&1][t] - f[n&1][t]);
}
}
方法三:
01背包 一维数组优化
class Solution {
public int lastStoneWeightII(int[] ss) {
int n = ss.length;
int sum = 0;
for (int i : ss) sum += i;
int t = sum / 2;
int[] f = new int[t + 1];
for (int i = 1; i <= n; i++) {
int x = ss[i - 1];
for (int j = t; j >= x; j--) {
f[j] = Math.max(f[j], f[j - x] + x);
}
}
return Math.abs(sum - f[t] - f[t]);
}
}
边栏推荐
猜你喜欢
随机推荐
51单片机室内环境甲醛PM2.5光照温度湿度检测及窗帘加湿消毒控制系统
Exploratory Data Analysis EDA
51单片机BH1750智能补光灯台灯光强光照恒流源LED控制系统
LeetCode 1894. Find the student number that needs to be supplemented with chalk
LeetCode 1720. Decoding XORed Arrays (Simple)
mysql分组排序并取各分组前几个数据
51单片机AD590温度测量ADC0832运放2.73V减法电压变换
51单片机RS485远程双机多机温度采集主从机多节点蜂鸣器报警
Unity对象池实现
二叉树 6/20 86-90
在Unity中判断游戏物体是否在游戏屏幕范围之内
【接口自动化】
LeetCode 1351. Counting Negative Numbers in Ordered Matrices (Simple)
详解样条曲线(上)(包含贝塞尔曲线)
内核性能分析总结
二叉树 6/16 81-85
废水中氟离子去除方法
LruCache与DiskLruCache结合简单实现ImageLoader
VTK 初步 (1) ----- 可视化管线
每日刷题(day03)——leetcode 899. 有序队列