Fe-interview: 第 13 题：有一堆整数，请把他们分成三份，确保每一份和尽量相等（11，42，23，4，5，6 4 5 6 11 23 42 56 78 90）

Created on 19 Jun 2020 · 21Comments · Source: lgwebdream/FE-Interview

欢迎在下方发表您的优质见解

滴滴算法

Source

lgwebdream

👍3 👀2 🚀2 ❤2 😕2 🎉2 😄2 👎2

Most helpful comment

@Genzhen
// 在某些情况下获取的不是最优解
// 输入 [1,2,3,4,5,6,7,8]
// 结果是： [[8, 3, 2], [6, 5, 1], [7, 4]] 三个数组项的和分别为 13，12，11
// 最优解应该为 [[8, 4], [6, 5, 1], [7, 3, 2]] 三个数组项的和分别为 12，12，12

licong-site on 13 Jul 2020

👍3

All 21 comments

function foo(arr) {
        let AMOUNT = arr.length
        if (!AMOUNT) return false;
        if (AMOUNT === 3) return arr;
        arr.sort((a, b) => a - b);
        let total = 0;
        let maxNumberTotal = 0;
        for (let i = 0; i < AMOUNT; i++) {
            total += arr[i];
        }
        maxNumberTotal = total / 3;
        let tempTotal = arr[AMOUNT - 1];

        let firstArr = [arr[AMOUNT - 1]];
        let delIndex = [AMOUNT - 1];
        let firstIndex = -1;

        // 获取第一份数组
        for (let i = AMOUNT - 2; i > 0; i--) {
            const el = arr[i];
            tempTotal += el; // 每次拿最大的;
            firstArr.push(el);
            delIndex.push(i);
            if (tempTotal === maxNumberTotal) { // 刚好等于最大值跳出循环
                break;
            } else if (tempTotal > maxNumberTotal) { // 发现超过最大值, 减回去
                tempTotal -= el;
                delIndex.pop();
                firstArr.pop();
            } else if (tempTotal < maxNumberTotal) { // 发现超过最小值, 处理边界问题
                let nextTotal = tempTotal + arr[i + 1]
                if (maxNumberTotal - tempTotal < Math.abs(maxNumberTotal - nextTotal)) { // 当前总值比上一个总值大; 这里是临界值, 说明上一个总值肯定是一个比最大值大, 所以这里需要和绝对值比较
                    if (maxNumberTotal - tempTotal > arr[0]) { // 如果下一个平局值和总值相减, 比数组第一个数还大, 说明还可以继续走下去;
                        continue;
                    } else {
                        break;
                    }
                }
            }
        }
        for (let i = 0; i < delIndex.length; i++) {
            arr.splice(delIndex[i], 1)            
        }

        AMOUNT = arr.length; // 注意每次的arr都是不一样的
        let secondArr = [arr[AMOUNT - 1]];
        delIndex = [AMOUNT - 1];
        let secondIndex = -1;
        tempTotal = arr[AMOUNT - 1];
        // 获取第二份数组
        for (let i = AMOUNT - 2; i > 0; i--) {
            const el = arr[i];
            tempTotal += el; // 每次拿最大的;
            secondArr.push(el);
            delIndex.push(i);
            if (tempTotal === maxNumberTotal) { // 刚好等于最大值跳出循环
                break;
            } else if (tempTotal > maxNumberTotal) { // 发现超过最大值, 减回去
                tempTotal -= el;
                delIndex.pop();
                secondArr.pop();
            } else if (tempTotal < maxNumberTotal) { // 发现超过最小值, 处理边界问题
                let nextTotal = tempTotal + arr[i + 1]
                if (maxNumberTotal - tempTotal < Math.abs(maxNumberTotal - nextTotal)) { // 当前总值恒小于下一个总值; 这里是临界值
                    if (maxNumberTotal - tempTotal > arr[0]) {
                        continue;
                    } else {
                        break;
                    }
                }
            }
        }
        for (let i = 0; i < delIndex.length; i++) {
            arr.splice(delIndex[i], 1)            
        }
        // 公平处理, 当出现极差情况就需要做公平处理了, 这里暂时不考虑极差情况
        return [firstArr, secondArr, arr]
    }

Genzhen on 23 Jun 2020

🎉1 👍1

// 若总和不能被 3 整除，说明不能分成相等的 3 个部分，然后return了，题目不是说尽量相等嘛？？？

pws019 on 8 Jul 2020

function f1 (arr,count){
    //数组从大到小排序
    arr.sort((a,b) => b - a);
    //计算平均值
    let avg = arr.reduce((a,b) => a + b) / count;
    //从大到小求和，取最接近平均值的一组，放入二维数组
    let resArr = [];
    let current = 0;
    for (let i = 0; i < count-1; i++) {
        if(current + arr[arr.length-1]/2 < avg && i){
            arr.pop();
            resArr[i-1].push(arr[arr.length-1]);
        }
        current = 0;
        resArr[i] = [];
        arr.forEach((item,index) => {
            current += item;
            arr.splice(index,1);
            resArr[i].push(item);
            if(current > avg){
                current -= item;
                arr.splice(index,0,item);
                resArr[i].pop();
            }
        })
    }
    resArr[count-1] = arr;
    return resArr
}
//测试，第一个参数为数组，第二个为份数
f1([11,42,23,4,5,6,4,5,6,11,23,42,56,78,90],3)

QiuYiLiang on 12 Jul 2020

👍3

// 若总和不能被 3 整除，说明不能分成相等的 3 个部分，然后return了，题目不是说尽量相等嘛？？？

答题已更新哈

Genzhen on 13 Jul 2020

licong-site on 13 Jul 2020

👍3

题目来自于背包问题变种，思路比较简单，动态规划解决。

BruceYuj on 13 Jul 2020

const numSort = (arr) => {
  return arr.sort((a, b) => b - a)
};
const numArr = numSort([11, 42, 23, 4, 5, 6, 4, 5, 6, 11, 23, 42, 56, 78, 90]);
const sumTotal = eval(numArr.join('+'));
let a = 0, b = 0, c = 0;
const sumFN = (x) => {
  let newX = x;
  numArr.map((num, index) => {
    if ((newX + num) <= Math.ceil(sumTotal / 3)) {
      newX = newX + num;
      numArr.splice(index, 1);
    } else {
      return false;
    }
  })
  return newX
};
a = sumFN(a);
b = sumFN(b);
c = eval(numArr.join('+'));
console.log(a, b, c);
136 136 134

duoduoing on 17 Jul 2020

// 若总和不能被 3 整除，说明不能分成相等的 3 个部分，然后return了，题目不是说尽量相等嘛？？？

感谢指出问题，答案已更新哈

Genzhen on 20 Jul 2020

@Genzhen
// 在某些情况下获取的不是最优解
// 输入 [1,2,3,4,5,6,7,8]
// 结果是： [[8, 3, 2], [6, 5, 1], [7, 4]] 三个数组项的和分别为 13，12，11
// 最优解应该为 [[8, 4], [6, 5, 1], [7, 3, 2]] 三个数组项的和分别为 12，12，12

感谢指出问题，答案已更新哈

Genzhen on 20 Jul 2020

function sliceArray (arr, count) {
  // 平均值向上取整
  let average = Math.ceil(arr.reduce((acc, v) => acc + v, 0) / count)
  // 由大到小排列
  arr.sort((n1, n2) => n2 - n1)
  const getArr = () => {
    let sum = 0, newArr = [] // 存相应数据
    arr.map((v, i) => {
      if (sum + v <= average) {
        sum += v
        newArr.push(v)
        arr.splice(i, 1)
      }
    })
    return newArr;
  }

  let backArr = new Array(count).fill(0)
  backArr.forEach((x, i) => {
    backArr[i] = i === backArr.length - 1 ? arr : getArr()
  })
  return backArr
}

pioneer22 on 20 Jul 2020

输入 [1,1,12,12]
结果是： [[1], [1], [12,12]] 三个数组项的和分别为 1，1，24
最优解应该为 [[1, 1], [12], [12]] 三个数组项的和分别为 2，12，12

FlyingRabbit7 on 16 Aug 2020

输入 [1,1,12,12]
结果是： [[1], [1], [12,12]] 三个数组项的和分别为 1，1，24
最优解应该为 [[1, 1], [12], [12]] 三个数组项的和分别为 2，12，12

@FlyingRabbit7 感谢指出问题Thanks♪(･ω･)ﾉ答案已更新哈

Genzhen on 1 Sep 2020

没这么麻烦吧其实直接就是瀑布流布局的思想啊
function makeAlmostEqual (arr, part) {
let orderedArr = arr.sort((a,b) => b - a)
let res = Array(part).fill(void(0)).map(() => [])
orderedArr.forEach(value => {
let minArrIndex = getMinArrIndex(res)
res[minArrIndex].push(value)
})
return res
}

function getSum (arr) {
return arr.reduce((sum, v) => sum + v, 0)
}

function getMinArrIndex (arrs) {
let minArrIndex = 0
arrs.forEach((arr, index) => {
if (getSum(arrs[minArrIndex]) > getSum(arrs[index])) {
minArrIndex = index
}
})
// console.log(arrs)
return minArrIndex
}

makeAlmostEqual([1, 65, 4, 32, 95, 33, 9, 3], 3)

只要注意数组要倒序排列就好了

Aeolos1994 on 27 Oct 2020

leetcode 有类似的题吗？

AielloChan on 3 Nov 2020

👀1

leetcode 有类似的题吗？

@AielloChan 在leetcode 可以练习自己的解题思路，培养解题思维，练的多了，看到这样的题，就会知道怎么去解了，在leetcode 也不要盲目的从头开始刷，最好是分类练习

Genzhen on 5 Nov 2020

👍1

let arr = [11,42,23,4,5,6,4,5,6,11,23,42,56,78,90]
    arr.sort((a,b)=>a-b)
    let arr0 = []
    let arr1 = []
    let arr2 = []
    let getsum = function(arr){
        return arr.reduce((a,b)=>{
        return a+b
    },0)
    }
    let sum = getsum(arr)
    let avg = sum/3
    console.log(avg)
    // 先分大数，大数影响分布均衡
    while(arr.length>0){
      // console.log(arr.length)
      let sum0 = getsum(arr0)
      let sum1 = getsum(arr1)
      let sum2 = getsum(arr2)

      if(Math.min(sum0,sum1,sum2)===sum0 && sum0<=avg){
        let popnum = arr.pop()
        arr0.push(popnum||0)
      }
      if(Math.min(sum0,sum1,sum2)===sum1 && sum1<=avg){
        let popnum = arr.pop()
        arr1.push(popnum||0)
      }
      if(Math.min(sum0,sum1,sum2)===sum2 && sum2<=avg){
        let popnum = arr.pop()
        arr2.push(popnum||0)
      }
    }
  console.log(arr0,arr1,arr2,getsum(arr0),getsum(arr1),getsum(arr2)) // 
 [90, 23, 11, 6, 5]  [78, 42, 11, 4]  [56, 42, 23, 6, 5, 4] 135 135 136

gitwujiaolong on 11 Dec 2020

function f1(arr, count) {
arr.sort((a, b) => a - b);
let max = 0;
const sums = Array(count).fill(0);
const arrs = Array(count).fill(0).map(() => []);

while (arr.length > 0) {
for (let i = 0; i < count && arr.length > 0; i++) {
if (sums[i] <= max) {
const item = arr.pop();
sums[i] += item;
arrs[i].push(item);
} else {
max = sums[i];
}
}
}
console.log(arrs, sums);
return arrs;
}

//测试，第一个参数为数组，第二个为份数
f1([1, 2, 3, 4, 5, 6, 7, 8], 3)

TurnerXi on 21 Dec 2020

能说说这个的实际应用场景吗

zxmajunhong on 3 Mar 2021

@zxmajunhong 算法题不是用来实际用的，是来练你的逻辑思维和语法熟练度的，理论和实际是两码事，理论好了实操才会更好，没有理论支持，实操能好到哪儿去？最多也是搬砖工

qzruncode on 14 Apr 2021

🎉1

思想：排序+双端遍历 即可实现
function findPart(arr) {
  arr = arr.sort((a, b) => a - b);
  const sum = arr.reduce((pre, cur) => pre + cur, 0);
  const part = Math.floor(sum / 3);
  function getPart() {
    const tmp = [];
    let i = 0, j = arr.length - 1;
    while(i <= j) {
      let flag = false;
      let tmpSum = tmp.reduce((pre, cur) => pre + cur, 0);
      if((tmpSum + arr[i]) <= part) {
        flag = true;
        tmp.push(arr[i]);
        i++;
      }
      if((tmpSum + arr[j]) <= part) {
        flag = true;
        tmp.push(arr[j]);
        j++;
      }
      if(!flag){
        break;
      }
    }
    arr = arr.slice(i, j - 1);
    return tmp;
  }
  return [getPart(), getPart(), getPart()];
}
findPart([11,42,23,4,5,6,4,5,6,11,23,42,56,78,90]);

结果
[4, 90, 4, 5, 5, 6, 6, 11]
[11, 78, 23, 23]
[42, 56]

qzruncode on 14 Apr 2021

❤1

没这么麻烦吧其实直接就是瀑布流布局的思想啊
function makeAlmostEqual (arr, part) {
let orderedArr = arr.sort((a,b) => b - a)
let res = Array(part).fill(void(0)).map(() => [])
orderedArr.forEach(value => {
let minArrIndex = getMinArrIndex(res)
res[minArrIndex].push(value)
})
return res
}

function getSum (arr) {
return arr.reduce((sum, v) => sum + v, 0)
}

function getMinArrIndex (arrs) {
let minArrIndex = 0
arrs.forEach((arr, index) => {
if (getSum(arrs[minArrIndex]) > getSum(arrs[index])) {
minArrIndex = index
}
})
// console.log(arrs)
return minArrIndex
}

makeAlmostEqual([1, 65, 4, 32, 95, 33, 9, 3], 3)

只要注意数组要倒序排列就好了

@Aeolos1994
// 在某些情况下获取的不是最优解
// 输入 [1,2,3,4,5,6,7,8]
// 结果是： [[8, 3, 2], [7, 4, 1], [6, 5]] 三个数组项的和分别为 13，12，11
// 最优解应该为 [[8, 4], [6, 5, 1], [7, 3, 2]] 三个数组项的和分别为 12，12，12

zouqianghtml on 6 May 2021

Was this page helpful?

0 / 5 - 0 ratings

Related issues

Day29：下面代码中 a 在什么情况下会打印 1

Genzhen · 4Comments

Day18：写出执行结果,并解释原因

Genzhen · 3Comments

第 22 题：node 中间层怎样做的请求合并转发

lgwebdream · 3Comments

Day28：写出执行结果,并解释原因(以最新谷歌浏览器为准)

Genzhen · 4Comments

Day3：写出执行结果，并解释原因

Genzhen · 4Comments