【力扣系列题目】最后一块石头的重量分割回文串验证回文串等差数列划分{最大堆背包动态规划}

文章目录

七、最后一块石头的重量
- 最后一块石头的重量【堆】
- [最后一块石头的重量 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;
    }
};