【力扣系列题目】最后一块石头的重量 分割回文串 验证回文串 等差数列划分{最大堆 背包 动态规划}
文章目录
- 七、最后一块石头的重量
- 最后一块石头的重量【堆】
- [最后一块石头的重量 II](https://leetcode.cn/problems/last-stone-weight-ii/)【背包】
- 八、分割回文串
- 分割回文串【分割子串方案数量】
- [分割回文串 II](https://leetcode.cn/problems/omKAoA/)【最少分割次数】
- [分割回文串 III](https://leetcode.cn/problems/palindrome-partitioning-iii/)【分割成k个+可修改】
- [分割回文串 IV](https://leetcode.cn/problems/palindrome-partitioning-iv/)【是否能发成三个】
- 九、验证回文串
- 验证回文串
- [验证回文串 II](https://leetcode.cn/problems/RQku0D/)【最多删除一个】
- [验证回文串 III](https://leetcode.cn/problems/valid-palindrome-iii/)【可删除k个】
- [验证回文串 IV](https://leetcode.cn/problems/valid-palindrome-iv/)【可删除一或两个】
- 十、等差数列划分
- 前言
- 等差数列划分【等差数组的子数组个数】
- [等差数列划分 II - 子序列](https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/)
- 十一、demo
七、最后一块石头的重量
最后一块石头的重量【堆】
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q;
for (int s : stones) {
q.push(s);
}
while (q.size() > 1) {
int a = q.top();
q.pop();
int b = q.top();
q.pop();
if (a > b) {
q.push(a - b);
}
}
return q.empty() ? 0 : q.top();
}
};
最后一块石头的重量 II【背包】
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for (auto x : stones)
sum += x;
int n = stones.size(), m = sum / 2;
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= stones[i - 1])
dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] +
stones[i - 1]);
}
}
return sum - 2 * dp[n][m];
}
};
八、分割回文串
分割回文串【分割子串方案数量】
class Solution {
private:
vector<vector<int>> f;
vector<vector<string>> ans;
vector<string> path;
int n;
void dfs(const string& s, int i) {
if (i == n) {
ans.push_back(path);
return;
}
for (int j = i; j < n; ++j) {
if (isPalindrome(s, i, j) == 1) {
path.push_back(s.substr(i, j - i + 1));
dfs(s, j + 1);
path.pop_back();
}
}
}
// 0未搜索 1回文串 -1不是回文串
int isPalindrome(const string& s, int i, int j) {
if (f[i][j] != 0)
return f[i][j];
if (i > j || i == j || (i + 1 == j && s[i] == s[j]))
return f[i][j] = 1;
f[i][j] = (s[i] == s[j] ? isPalindrome(s, i + 1, j - 1) : -1);
return f[i][j];
}
public:
vector<vector<string>> partition(string s) {
n = s.size();
f.assign(n, vector<int>(n));
dfs(s, 0);
return ans;
}
};
分割回文串 II【最少分割次数】
class Solution
{
void init(const string &s, vector<vector<bool>> &isPal)
{
int n = s.size();
for (int i = n - 1; i >= 0; i--)
{
for (int j = i; j < n; j++)
{
if (i == j || (i + 1 == j && s[i] == s[j]))
isPal[i][j] = true;
else if (s[i] == s[j])
isPal[i][j] = isPal[i + 1][j - 1];
}
}
}
public:
int minCut(string s)
{
int n = s.size();
vector<vector<bool>> isPal(n, vector<bool>(n,false));
init(s, isPal);
vector<int> dp(n, INT_MAX);
for (int i = 0; i < n; i++)
{
if (isPal[0][i])
dp[i] = 0;
else
{
for (int j = 1; j <= i; j++)
if (isPal[j][i])
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
return dp[n - 1];
}
};
分割回文串 III【分割成k个+可修改】
class Solution {
int cost2(string& s, int l, int r) {
int ret = 0;
for (int i = l, j = r; i < j; ++i, --j) {
if (s[i] != s[j])
++ret;
}
return ret;
}
void init(string& s, vector<vector<int>>& cost) {
int n = s.size();
// span：区间长度; i：区间起点; j：区间终点
for (int span = 2; span <= n; ++span) {
for (int i = 0; i <= n - span; ++i) {
int j = i + span - 1;
cost[i][j] = cost[i + 1][j - 1] + (s[i] == s[j] ? 0 : 1);
}
}
}
public:
int palindromePartition(string& s, int k) {
int n = s.size();
vector<vector<int>> cost(n, vector<int>(n));
init(s, cost);
vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= min(k, i); ++j) {
if (j == 1)
// f[i][j] = cost(s, 0, i - 1);
f[i][j] = cost[0][i - 1];
else {
for (int i0 = j - 1; i0 < i; ++i0) {
f[i][j] =
// min(f[i][j], f[i0][j - 1] + cost(s, i0, i - 1));
min(f[i][j], f[i0][j - 1] + cost[i0][i - 1]);
}
}
}
}
return f[n][k];
}
};
分割回文串 IV【是否能发成三个】
class Solution {
void init(const string& s, vector<vector<bool>>& isPal) {
int n = s.size();
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (i == j || (i + 1 == j && s[i] == s[j]))
isPal[i][j] = true;
else if (s[i] == s[j])
isPal[i][j] = isPal[i + 1][j - 1];
}
}
}
public:
bool checkPartitioning(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
init(s, dp);
for (int i = 1; i < n - 1; i++)
for (int j = i; j < n - 1; j++)
if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
return true;
return false;
}
};
九、验证回文串
验证回文串
class Solution {
public:
bool isPalindrome(string s) {
int n = s.size();
int left = 0, right = n - 1;
while (left < right) {
while (left < right && !isalnum(s[left]))
++left;
while (left < right && !isalnum(s[right]))
--right;
if (left < right) {
if (tolower(s[left]) != tolower(s[right]))
return false;
++left;
--right;
}
}
return true;
}
};
验证回文串 II【最多删除一个】
class Solution {
public:
bool checkPalindrome(const string& s, int low, int high) {
int i = low, j = high;
while (i < j) {
if (s[i] != s[j])
return false;
++i;
--j;
}
return true;
}
bool validPalindrome(string s) {
int low = 0, high = s.size() - 1;
while (low < high) {
char c1 = s[low], c2 = s[high];
if (c1 == c2) {
++low;
--high;
} else {
return checkPalindrome(s, low, high - 1) ||
checkPalindrome(s, low + 1, high);
}
}
return true;
}
};
验证回文串 III【可删除k个】
class Solution {
bool fun(string& s, int k) {
int n = s.size();
vector<vector<int>> f(n, vector<int>(n));
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (i == j || (i + 1 == j && s[i] == s[j]))
f[i][j] = 0;
if (i + 1 == j && s[i] != s[j])
f[i][j] = 1;
if (s[i] == s[j])
f[i][j] = f[i + 1][j - 1];
else
f[i][j] = min(f[i][j - 1], f[i + 1][j]) + 1;
}
}
return f[0][n - 1] <= k;
}
public:
vector<vector<int>> memo;
int dfs(string& s, int i, int j) {
if (i == j)
return 0;
if (i + 1 == j)
return s[i] == s[j] ? 0 : 1;
if (memo[i][j] != -1)
return memo[i][j];
if (s[i] == s[j])
return memo[i][j] = dfs(s, i + 1, j - 1);
return memo[i][j] = 1 + min(dfs(s, i + 1, j), dfs(s, i, j - 1));
}
bool isValidPalindrome(string s, int k) {
return fun(s, k);
memo.resize(s.length(), vector<int>(s.length(), -1));
return dfs(s, 0, s.length() - 1) <= k;
}
};
验证回文串 IV【可删除一或两个】
class Solution {
public:
bool makePalindrome(string s) {
int need = 0;
int l = 0, r = s.size() - 1;
while (l < r) {
if (s[l] != s[r])
need++;
l++;
r--;
}
return need <= 2;
}
};
十、等差数列划分
前言
先看这道题
最长等差数列
按照固定i j后两位 然后找k的存在的思想在本题中无法解决。因为该题的测试用例中，a可能存在多个，题目需要“最长”， 当i前有多个a时，我们需要的是最近的a，所以初始化index数组时，不能将所有元素提前处理好，map中的键是唯一的，故，后来的a会覆盖之前的a，也就无法在枚举i时，特定的去i前找。
错误解法示例
class Solution
{
public:
int longestArithSeqLength(vector<int> &arr)
{
unordered_map<int, int> indices;
int n = arr.size();
for (int i = 0; i < n; i++)
indices[arr[i]] = i;
vector<vector<int>> dp(n, vector<int>(n,2));
int ans = 2;
for (int i = 2; i < n; i++)
{
for (int j = i - 1; j >= 0; j--)
{
// a b c a=b-(c-b)=2b-c
// k j i
int k = -1;
int x = 2 * arr[j] - arr[i];
if (indices.count(x))
k = indices[x];
if (0 <= k && k < j)
dp[j][i] = dp[k][j] + 1;
ans = max(ans, dp[j][i]);
}
}
return ans;
}
};
非得按照之前的思路
class Solution {
public:
int longestArithSeqLength(vector<int>& arr) {
int n = arr.size();
unordered_map<int, vector<int>> hash;
for (int i = 0; i < n; i++)
hash[arr[i]].push_back(i);
vector<vector<int>> dp(n, vector<int>(n, 2));
int ans = 2;
// a b c a=b-(c-b)=2b-c
// k j i
for (int i = 2; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
int k = -1;
int x = 2 * arr[j] - arr[i];
if (hash.count(x)) {
for (int k : hash[x]) {
if (0 <= k && k < j)
dp[j][i] = dp[k][j] + 1;
}
}
ans = max(ans, dp[j][i]);
}
}
return ans;
}
};
class Solution
{
public:
int longestArithSeqLength(vector<int> &nums)
{
unordered_map<int, int> hash;
hash[nums[0]] = 0;
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, 2));
int ret = 2;
// a b c a=b-(c-b)=2b-c
// k j i
for (int j = 1; j < n; j++)
{
for (int i = j + 1; i < n; i++)
{
int a = 2 * nums[j] - nums[i];
if (hash.count(a))
dp[j][i] = dp[hash[a]][j] + 1;
ret = max(ret, dp[j][i]);
}
hash[nums[j]] = j;
}
return ret;
}
};
等差数列划分【等差数组的子数组个数】
class Solution {
// a b c
// a b c d && b c d
public:
int numberOfArithmeticSlices(vector<int>& nums) {
// dp[i] 表⽰必须「以 i 位置的元素为结尾」的等差数列有多少种。
int n = nums.size();
vector<int> dp(n);
int sum = 0;
for (int i = 2; i < n; i++) {
dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]
? dp[i - 1] + 1
: 0;
sum += dp[i];
}
return sum;
}
};
等差数列划分 II - 子序列
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
unordered_map<long long, vector<int>> hash;
for (int i = 0; i < n; i++)
hash[nums[i]].push_back(i);
vector<vector<int>> dp(n, vector<int>(n));
int sum = 0;
for (int j = 2; j < n; j++)
{
for (int i = 1; i < j; i++) {
long long a = (long long)nums[i] * 2 - nums[j];
if (hash.count(a))
for (auto k : hash[a])
if (k < i)
dp[i][j] += dp[k][i] + 1;
else
break;
sum += dp[i][j];
}
}
return sum;
}
};
十一、demo
最短回文串