一個看起來較為基礎(chǔ)的計算機算法問題,求大神解惑!
(已解決,末尾給出參考答案)
length
的隨機正整數(shù)列表 list
,list
中元素均小于或等于 max
;(注: length > 2
)
mid
short
、long
,且滿足 0 < short < long < length
、0 < mid < max
;從 list
中選取包括首尾元素在內(nèi)的若干個元素組成一個新的列表 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: 目標(biāo)數(shù)組
s: short 最短長度
l: long 最長長度
mid: 限制大小
"""
# dp 到當(dāng)前位置的上一個最優(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]
可以用dfs,backtracking或者dp來做
如果這題是OJ的話,dfs和backtracking的復(fù)雜度太高,O(2^n)
可能不能pass
如果用DP的話,復(fù)雜度是O(n^2)
C++ 實現(xiàn)的DP算法:
Time: O(n^2)
Space: O(n)
sums
記錄了到當(dāng)前位置最優(yōu)解的總和div
記錄了到當(dāng)前位置的最優(yōu)解的個數(shù)dp
記錄了到當(dāng)前位置的上一個最優(yōu)解的index(最后一個index是本身),可以當(dāng)做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);
我的思路是從左到右遞歸地看,對于每個符合的數(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 // 結(jié)果
_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() // 復(fù)制一份結(jié)果
}
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)
這是我寫了老半天的一點兒想法,就算不能完全滿足你的要求,也希望你能從中看出些端倪,最后能進行完善!
這是我用JavaScript
寫的,直接復(fù)制粘貼運行便可看到效果:
<!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];
輸出: 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]
只能說水平有限,盡力了!
北大青鳥APTECH成立于1999年。依托北京大學(xué)優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國家
北大青鳥中博軟件學(xué)院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網(wǎng)學(xué)院和江蘇省首批服務(wù)外包人才培訓(xùn)基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團創(chuàng)建于1999年,經(jīng)過二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術(shù)與教育服務(wù)機構(gòu),發(fā)展為教育服務(wù)業(yè)的綜合性企業(yè)集團,成為集合面授教學(xué)培訓(xùn)、網(wǎng)
達內(nèi)教育集團成立于2002年,是一家由留學(xué)海歸創(chuàng)辦的高端職業(yè)教育培訓(xùn)機構(gòu),是中國一站式人才培養(yǎng)平臺、一站式人才輸送平臺。2014年4月3日在美國成功上市,融資1
曾工作于聯(lián)想擔(dān)任系統(tǒng)開發(fā)工程師,曾在博彥科技股份有限公司擔(dān)任項目經(jīng)理從事移動互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍懿科技有限責(zé)任公司從事總經(jīng)理職務(wù)負責(zé)iOS教學(xué)及管理工作。
浪潮集團項目經(jīng)理。精通Java與.NET 技術(shù), 熟練的跨平臺面向?qū)ο箝_發(fā)經(jīng)驗,技術(shù)功底深厚。 授課風(fēng)格 授課風(fēng)格清新自然、條理清晰、主次分明、重點難點突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫,具有快速界面開發(fā)的能力,對瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁制作和網(wǎng)頁游戲開發(fā)。
具有10 年的Java 企業(yè)應(yīng)用開發(fā)經(jīng)驗。曾經(jīng)歷任德國Software AG 技術(shù)顧問,美國Dachieve 系統(tǒng)架構(gòu)師,美國AngelEngineers Inc. 系統(tǒng)架構(gòu)師。