舒适的湿度

LCP 65. 舒适的湿度

力扣嘉年华为了确保更舒适的游览环境条件，在会场的各处设置了湿度调节装置，这些调节装置受控于总控室中的一台控制器。控制器中已经预设了一些调节指令，整数数组operate[i] 表示第 i 条指令增加空气湿度的大小。现在你可以将任意数量的指令修改为降低湿度（变化的数值不变），以确保湿度尽可能的适宜：

控制器会选择 一段连续的指令 ，从而进行湿度调节的操作；
这段指令最终对湿度影响的绝对值，即为当前操作的「不适宜度」
在控制器所有可能的操作中，最大的「不适宜度」即为「整体不适宜度」

请返回在所有修改指令的方案中，可以得到的最小「整体不适宜度」。

示例 1：

输入：operate = [5,3,7]

输出：8

解释：对于方案 2 的 [5,3,-7] 操作指令 [5],[3],[-7] 的「不适宜度」分别为 5,3,7 操作指令 [5,3],[3,-7] 的「不适宜度」分别为 8,4 操作指令 [5,3,-7] 的「不适宜度」为 1，因此对于方案 [5,3,-7]的「整体不适宜度」为 8，其余方案的「整体不适宜度」均不小于 8，如下表所示： {:width=650px}

示例 2：

输入：operate = [20,10]

输出：20

提示：

1 <= operate.length <= 1000
1 <= operate[i] <= 1000

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int unSuitability(vector<int>& operate) { } };

golang 解法, 执行用时: 28 ms, 内存消耗: 3.8 MB, 提交时间: 2023-09-05 07:44:14

func unSuitability(operate []int) int {
	const inf = math.MaxInt32
	mx := 0
	for _, x := range operate {
		mx = max(mx, x)
	}
	mx *= 2
	pre := make([]int, mx+1)
	for i := range pre {
		pre[i] = inf
	}
	pre[0] = 0
	f := make([]int, mx+1)
	for _, x := range operate {
		for i := range f {
			f[i] = inf
		}
		for j, dis := range pre {
			if pre[j] == inf { // 无效的长度（无法组成）
				continue
			}
			if j+x <= mx {
				f[j+x] = min(f[j+x], max(dis, j+x))
			}
			if j >= x {
				f[j-x] = min(f[j-x], dis)
			} else {
				f[0] = min(f[0], dis-j+x)
			}
		}
		pre, f = f, pre
	}
	ans := inf
	for _, x := range pre {
		ans = min(ans, x)
	}
	return ans
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

cpp 解法, 执行用时: 56 ms, 内存消耗: 9.4 MB, 提交时间: 2023-09-05 07:44:00

class Solution {
public:
    int unSuitability(vector<int> &operate) {
        int mx = *max_element(operate.begin(), operate.end()) * 2 + 1;
        int pre[mx], f[mx];
        memset(pre, 0x3f, sizeof(pre));
        pre[0] = 0;
        for (int x : operate) {
            memset(f, 0x3f, sizeof(f));
            for (int j = 0; j < mx; ++j) {
                int dis = pre[j];
                if (dis == 0x3f3f3f3f) continue; // 无效的长度（无法组成）
                if (j + x < mx) f[j + x] = min(f[j + x], max(dis, j + x));
                if (j >= x) f[j - x] = min(f[j - x], dis);
                else f[0] = min(f[0], dis - j + x);
            }
            memcpy(pre, f, sizeof(f));
        }
        return *min_element(pre, pre + mx);
    }
};

java 解法, 执行用时: 36 ms, 内存消耗: 41.9 MB, 提交时间: 2023-09-05 07:43:48

class Solution {
    public int unSuitability(int[] operate) {
        var mx = Arrays.stream(operate).max().orElseThrow() * 2 + 1;
        int[] pre = new int[mx], f = new int[mx];
        Arrays.fill(pre, Integer.MAX_VALUE);
        pre[0] = 0;
        for (var x : operate) {
            Arrays.fill(f, Integer.MAX_VALUE);
            for (var j = 0; j < mx; ++j) {
                var dis = pre[j];
                if (dis == Integer.MAX_VALUE) continue; // 无效的长度（无法组成）
                if (j + x < mx) f[j + x] = Math.min(f[j + x], Math.max(dis, j + x));
                if (j >= x) f[j - x] = Math.min(f[j - x], dis);
                else f[0] = Math.min(f[0], dis - j + x);
            }
            var tmp = pre;
            pre = f;
            f = tmp;
        }
        return Arrays.stream(pre).min().orElseThrow();
    }
}

python3 解法, 执行用时: 4580 ms, 内存消耗: 16.4 MB, 提交时间: 2023-09-05 07:43:21

class Solution:
    def unSuitability(self, operate: List[int]) -> int:
        mx = max(operate) * 2
        pre = [0] + [inf] * mx
        for x in operate:
            f = [inf] * (mx + 1)
            for j, dis in enumerate(pre):
                if dis == inf: continue  # 无效的长度（无法组成）
                if j + x <= mx: f[j + x] = min(f[j + x], max(dis, j + x))
                if j >= x: f[j - x] = min(f[j - x], dis)
                else: f[0] = min(f[0], dis - j + x)
            pre = f
        return min(pre)

上一题

下一题

详情