基礎算法求助（已解決）

一個看起來較為基礎的計算機算法問題，求大神解惑！

（已解決，末尾給出參考答案）

參數(shù)

給定一組長度為 length 的隨機正整數(shù)列表 list，list 中元素均小于或等于 max；（注： length > 2 ）
給定正整數(shù)參數(shù) mid short、long，且滿足 0 < short < long < length、0 < mid < max；

條件

從 list 中選取包括首尾元素在內(nèi)的若干個元素組成一個新的列表 list_cut，list_cut 需要滿足以下幾個條件：
1. list_cut 中各個元素均需小于 mid；
2. list_cut 中各個元素間在 list 中的索引值差為 gap, 且滿足 0 < short <= gap <= long；
3. 若給定的參數(shù)無法選出 list_cut，返回 False；
4. 若給定的參數(shù)可以選出多個 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: 目標數(shù)組
    s: short 最短長度
    l: long 最長長度
    mid: 限制大小
    """
    # dp 到當前位置的上一個最優(yōu)解的 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]

回答

編輯回答

朕略萌

你好像忘記了提問題

2017年1月26日 06:04

編輯回答

陪她鬧

可以用dfs,backtracking或者dp來做
如果這題是OJ的話，dfs和backtracking的復雜度太高，O(2^n)可能不能pass
如果用DP的話，復雜度是O(n^2)

C++ 實現(xiàn)的DP算法：
Time: O(n^2)
Space: O(n)

sums記錄了到當前位置最優(yōu)解的總和
div 記錄了到當前位置的最優(yōu)解的個數(shù)
dp 記錄了到當前位置的上一個最優(yōu)解的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);

2017年2月13日 01:24

編輯回答

網(wǎng)妓

我的思路是從左到右遞歸地看，對于每個符合的數(shù)字，要么取，要么不取，最后判斷最小平均值。

沒有說明語言就用 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)

2018年8月2日 13:08

編輯回答

伐木累

這是我寫了老半天的一點兒想法，就算不能完全滿足你的要求，也希望你能從中看出些端倪，最后能進行完善！
這是我用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 = [];
    //循環(huán)數(shù)據(jù)
    for (let i = 0; i < list.length; i++) {
        //先判斷是否小于mid
        if (list[i] < mid) {
            if (preData(i) && nextData(i)) {
                list_cut.push(list[i]);
            }
        }
    }
    //向前判斷函數(shù)
    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;
    }
    //向后判斷函數(shù)
    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];