基础算法求助（已解决）

发布于 2022-09-06 11:45:22 字数 1988 浏览 17 评论 0

一个看起来较为基础的计算机算法问题，求大神解惑！

（已解决，末尾给出参考答案）

参数

给定一组长度为 length 的随机正整数列表 list，list 中元素均小于或等于 max；（注：length > 2）
给定正整数参数 mid、 short、long，且满足 0 < short < long < length、0 < mid < max；

条件

从 list 中选取包括首尾元素在内的若干个元素组成一个新的列表 list_cut，list_cut 需要满足以下几个条件：

list_cut 中各个元素均需小于 mid；
list_cut 中相邻元素在 list 中的索引值差为 gap, 且满足 0 < short <= gap <= long；

返回值

若给定的参数无法选出 list_cut，返回 False；
若给定的参数可以选出多个 list_cut，则返回所有 list_cut 中元素平均值最低的一个。

示例一

# 输入
list = [4, 7, 3, 5, 8, 6, 2, 3, 1, 2]
mid = 5
short, long = 2, 4

# 输出
list_cut = [4, 3, 2, 2]

示例二

# 输入
list = [4, 7, 6, 5, 8, 6, 2, 3, 1, 2]
mid = 5
short, long = 2, 4

# 输出
list_cut = False

参考答案

多谢 @SegmentWarrior 大佬提供的思路与 C++ 代码;
下面给出我“翻译”并稍加改进后的 python 版的答案。

def find_list(nums: list, s: int, l: int, mid: int):
    """
    nums: 目标数组
    s: short 最短长度
    l: long 最长长度
    mid: 限制大小
    """
    # dp 到当前位置的上一个最优解的 index
    n = len(nums)
    dp = [-1] * n
    dp[0] = 0
    for i in range(n-s):
        for j in range(i+s, min(i+l+1, n)):
            if nums[j] >= mid:
                continue
            elif dp[i] != -1:
                dp[j] = i

    if dp[-1] == -1:
        return False

    res = []
    inx = n - 1
    while inx > 0:
        res.append(nums[inx])
        inx = dp[inx]
    res.append(nums[0])
    return res[::-1]

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

命比纸薄 2022-09-13 11:45:22

可以用dfs,backtracking或者dp来做
如果这题是OJ的话，dfs和backtracking的复杂度太高，O(2^n)可能不能pass
如果用DP的话，复杂度是O(n^2)

C++ 实现的DP算法：
Time: O(n^2)
Space: O(n)

sums记录了到当前位置最优解的总和
div 记录了到当前位置的最优解的个数
dp 记录了到当前位置的上一个最优解的index(最后一个index是本身)，可以当做linked list来看，用最后的while loop找到list_cut

谢谢@CRIMX指出来的错误，先前的代码没有考虑到平均值相等的情况。

代码如下：

vector<int> find(vector<int>& nums, int s, int l, int mid) {
    int n = nums.size();
    vector<int> sums(n, INT_MAX), dp(n, -1);
    vector<double> div(n, 1.0);
    sums[0] = nums[0];
    for (int i = 0; i < n; i++) {
        if (sums[i] == INT_MAX) continue;
        for (int j = i + s; j <= i + l && j < n; j++) {
            if (nums[j] >= mid) continue;
            double avg1 = (nums[j] + sums[i]) / (div[i] + 1.0);
            double avg2 = sums[j] / div[j];
            if (avg1 < avg2 || (avg1 == avg2 && div[i] >= div[j])) {
                sums[j] = sums[i] + nums[j];
                div[j] = div[i] + 1.0;
                dp[j] = i;
            }
        }
    }

    if (dp.back() == -1) return{};

    vector<int> res;
    int idx = n - 1;
    while (idx >= 0) {
        res.push_back(nums[idx]);
        idx = dp[idx];
    }
    reverse(res.begin(), res.end());
    return res;
}

Backtracking 代码如下：
res为最终的list-cut

void find(vector<int>& nums, vector<int>& res, vector<int>& tmp, int start, int s, int l, int mid, double sum, double& min_avg) {
    tmp.emplace_back(nums[start]);
    sum += nums[start];
    if (start == nums.size() - 1 && sum / tmp.size() < min_avg) {
        min_avg = sum / tmp.size();
        res = tmp;
    }
    else {
        for (int i = start + s; i <= start + l && i < nums.size(); i++) {
            if (nums[i] >= mid) continue;
            find(nums, res, tmp, i, s, l, mid, sum, min_avg);
        }
    }
    tmp.pop_back();
}


vector<int> nums({ 5, 5, 5, 5, 9});
int mid = 10, s = 1, l = 4;
vector<int> res, tmp;
double min_avg = DBL_MAX;
find(nums, res, tmp, 0, s, l, mid, 0.0, min_avg);

回复收藏 0

笨死的猪 2022-09-13 11:45:22

这是我写了老半天的一点儿想法，就算不能完全满足你的要求，也希望你能从中看出些端倪，最后能进行完善！
这是我用JavaScript写的，直接复制粘贴运行便可看到效果：

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
</body>
<script>
    let list = [2, 9, 9, 9, 9, 9, 9, 9, 9, 2];
    let mid = 5;
    let [
        short,
        long
    ] = [
        2,
        4
    ];
    let list_cut = [];
    //循环数据
    for (let i = 0; i < list.length; i++) {
        //先判断是否小于mid
        if (list[i] < mid) {
            if (preData(i) && nextData(i)) {
                list_cut.push(list[i]);
            }
        }
    }
    //向前判断函数
    function preData(index) {
        let flag = false;
        if (index === 0) {
            return true;
        }
        for (let i = 0; i < index; i++) {
            let gap = index - i;
            if (list[i] < mid && gap >= short && gap <= long) {
                flag = true;
            }
        }
        return flag;
    }
    //向后判断函数
    function nextData(index) {
        let flag = false;
        if (index === list.length - 1) {
            return true;
        }
        for (let i = index; i < list.length; i++) {
            let gap = i - index;
            if (list[i] < mid && gap >= short && gap <= long) {
                flag = true;
            }
        }
        return flag;
    }
    console.log(list_cut.length ? list_cut : false);
</script>
</html>

1、输入：let list = [2, 9, 9, 9, 9, 9, 9, 9, 9, 2];

输出： false

2、输入：let list = [4, 7, 3, 5, 8, 6, 2, 3, 1, 2];

输出： [4, 3, 2, 2]

3、输入： let list = [4, 7, 6, 5, 8, 6, 2, 3, 1, 2];

输出： [2]

只能说水平有限，尽力了！

回复收藏 0

﹎☆浅夏丿初晴 2022-09-13 11:45:22

我的思路是从左到右递归地看，对于每个符合的数字，要么取，要么不取，最后判断最小平均值。

没有说明语言就用 JavaScript 写了一下

function test (list, mid, short, long) {
  if (list[0] >= mid || list[list.length - 1] >= mid) {
    return false
  }

  let minMean = Infinity // 最小平均值
  let result = false // 结果
  
  _test(0, [list[0]])
  
  return result

  function _test (iStart, path) {
    if (iStart >= list.length) { // 最后一个
      let mean = getMean(path)
      if (mean < minMean) {
        minMean = mean
        result = path.slice() // 复制一份结果
      }
      return
    }

    const iEnd = Math.min(iStart + long, list.length - 1)
    for (let i = iStart + short; i <= iEnd; i++) {
      if (list[i] < mid) {
        path.push(list[i]) // 取这个
        _test(i + 1, path)
        if (i !== list.length - 1) { // 不是最后一个
          path.pop() // 不取这个
          _test(i + 1, path)
        }
      }
    }
  }
}

function getMean (arr) {
  let sum = 0
  for (let i = 0; i < arr.length; i++) {
    sum += arr[0]
  }
  return sum / arr.length
}

test([4, 7, 3, 5, 8, 6, 2, 3, 1, 2], 5, 2, 4)

回复收藏 0