【C++ 算法进阶】算法提升二十三

左右数组相减绝对值最大值 （题意代换）

题目

现在给定你一个数组 数组中可能有正数 负数或零且数组长度大于2

现在让你将这个数组分为左右两个数组 请问这两个数组中的最大值相减的绝对值最大是多少

题目分析

这个题目我们可以直接暴力计算左右数组的最大值

也可以设置一个辅助数组 将左右数组的最大值填写到辅助数组中

不过最简单的方式是 我们可以从数组中寻找一个最大值 之后让这个最大值减去 左右两个边角中较小的那个值即可

原理如下

1. 假设max在左数组中 那么就要求右数组中的最大值尽可能的小 那么右数组中就应该只有最边角一个数
2. max在右数组中同理

因为本题解法代码很简单 所以说这里就不提供了

可整合数组 （题意代换）

题目

我们给定一个概念

一个数组 假设排序后是依次递增1的 我们就可以将这个数组称之为可整合数组

现在给定你一个数组 要求你给出这个数组中最大可整合子数组的长度

题目分析

我们这个时候要将可整合这个数组的概念转化为一个或者几个更加理解 code更容易写出来的条件

我们可以转化为如下的条件

1. 数组中无重复值
2. 数组中的最大值减去最小值等于数组的个数加一

代码

int process(vector<int>& nums) {
	if (nums.size() == 0) {
		return 0;
	}

	unordered_set<int> unset;
	int ans = 1;
	for (int i = 0; i < nums.size(); i++)
	{
		unset.clear();
		int lnmax = nums[i];
		int lnmin = nums[i];
		for (int j = i; j < nums.size(); j++) {
			if (unset.count(nums[j] == 1))
			{
				break;
			}
			else
			{
				unset.insert(nums[j]);
			}

			lnmax = max(lnmax, nums[j]);
			lnmin = min(lnmin, nums[j]);
			if (lnmax - lnmin == j - i) {
				ans = max(ans, j - i + 1);
			}
		}
	}

	return ans;
}

水王问题

题目

超级水王问题：给你一个数组，出现次数大于数组长度的一半的元素称之为水王数，怎么能快速找到水王数？

内存限制：时间复杂度O(n)，额外空间复杂度O(1)——也就是遍历数组的次数为有限次，申请的变量数为有限个

题目分析

我们注意到水王的一个明显特征 如果这个数是水王 哪怕其他所有数一对一和水王数同归于尽 那么最终剩下的也肯定是水王数

反之 如果这个数不是水王数 则说明这个数组中不存在水王

我们就可以使用这个特征来进行代码编写

代码

int process(vector<int> nums) {
	if (nums.size() == 0)
	{
		return -1;
	}

	int cand = 0;
	int hp = 0;
	for (auto x : nums) {
		if (hp == 0) {
			cand = x;
			hp = 1;
		}
		else
		{
			if (cand == x) {
				hp++;
			}
			else
			{
				hp--;
			}
		}
	}

	if (hp == 0) {
		return -1;
	}

	hp = 0;
	for (auto x : nums) {
		if (x == cand) {
			hp++;
		}
	}

	if (hp > nums.size() / 2) {
		return cand;
	}

	return -1;
}

水王问题变形

假设现在水王数定义为大于 7/N 我们应该如何做呢？

思路讲解

假设水王数大于 N/7 那么就表示数组中 最多有六个水王数

我们可以设置一张哈希表 每当哈希表不为空或者候选数目存在哈希表中的时候 我们可以将此数添加到哈希表中或者让此数的血量加一

如果候选表慢了 我们就可以直接让map中所有的候选血量减一 如果血量减为0 则删除该数

最后按照水王问题进行验证即可

合并石头的最低成本 （动态规划）

题目

本题为LC原题 题目如下

题目分析

本题是一个动态规划问题

我们首先要想出一个尝试函数

想出的尝试函数为

 process(vector<int>& stones, int k, int L, int R, int p) 

其中各个参数的含义为 k表示要连续石头个数 L和R表示尝试的范围 p表示需要分割成几块

我们最终调用的函数为

process(stones, k, 0, n - 1, 1)

从0~n-1上分割成一块

代码

const int N = 31;
int presum[N];
int dp[N][N][N]; // dp[L][R][p] 表示区间 [L, R] 合并成 p 堆的最小成本

class Solution {
public:
    int process(vector<int>& stones, int k, int L, int R, int p) {
        // 如果已经计算过该子问题，直接返回结果
        if (dp[L][R][p] != -1) {
            return dp[L][R][p];
        }

        if ((R - L + 1 - p) % (k - 1) != 0) {
            return dp[L][R][p] = -1; // 无法合并
        }
        if (L == R) {
            return dp[L][R][p] = (p == 1 ? 0 : -1); // 单点只能合并成1堆
        }

        if (p == 1) {
            int next = process(stones, k, L, R, k);
            if (next == -1) {
                return dp[L][R][p] = -1;
            } else {
                return dp[L][R][p] = next + presum[R + 1] - presum[L];
            }
        } else {
            int ans = INT_MAX;
            for (int mid = L; mid < R; mid += k - 1) {
                int next1 = process(stones, k, L, mid, 1);
                int next2 = process(stones, k, mid + 1, R, p - 1);
                if (next1 != -1 && next2 != -1) {
                    ans = min(ans, next1 + next2);
                }
            }
            return dp[L][R][p] = (ans == INT_MAX ? -1 : ans); // 记录结果
        }
    }

    int mergeStones(vector<int>& stones, int k) {
        int n = stones.size();
        if ((n - 1) % (k - 1) != 0) {
            return -1; // 无法合并为一堆
        }

        presum[0] = 0; // 初始化前缀和
        for (int i = 0; i < n; i++) {
            presum[i + 1] = presum[i] + stones[i];
        }

        // 初始化 dp 数组
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int p = 0; p < N; p++) {
                    dp[i][j][p] = -1; // -1 表示未计算
                }
            }
        }

        return process(stones, k, 0, n - 1, 1);
    }
};