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

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

Jun 19 '20 12:06 lgwebdream

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]
    }

Jun 23 '20 03:06 Genzhen

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

Jul 08 '20 08:07 pws019

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)

Jul 12 '20 10:07 QiuYiLiang

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

答题已更新哈

Jul 13 '20 02:07 Genzhen

@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

Jul 13 '20 08:07 licong-site

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

Jul 13 '20 14:07 BruceYuj

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

Jul 17 '20 08:07 duoduoing

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

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

Jul 20 '20 02:07 Genzhen

@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

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

Jul 20 '20 02:07 Genzhen

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
}

Jul 20 '20 06:07 pioneer22

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

Aug 16 '20 09:08 FlyingRabbit7

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

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

Sep 01 '20 04:09 Genzhen

没这么麻烦吧其实直接就是瀑布流布局的思想啊 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)

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

Oct 27 '20 12:10 Aeolos1994

leetcode 有类似的题吗？

Nov 03 '20 08:11 AielloChan

leetcode 有类似的题吗？

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

Nov 05 '20 02:11 Genzhen

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

Dec 11 '20 06:12 jimwjl666

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)

Dec 21 '20 15:12 TurnerXi

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

Mar 03 '21 03:03 zxmajunhong

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

Apr 14 '21 06:04 qzruncode

思想：排序+双端遍历 即可实现
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]

Apr 14 '21 06:04 qzruncode

没这么麻烦吧其实直接就是瀑布流布局的思想啊 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

May 06 '21 14:05 zouqianghtml

// 思路：把大的数插入数组，再用小的数找齐三组数和的差距，就可以尽量均匀的分成三组了。
// 代码逻辑：数组从大到小排序，把数依次往和最小的数组中插入。
function sliceArray(arr) {
    const newErr = [...arr].sort((a, b) => b - a); // 一定要倒序排列，大的排在前面。
    const arr1 = [], arr2 = [], arr3 = []; // 用于储存结果的三个数组
    let arr1Sum = 0, arr2Sum = 0, arr3Sum = 0; // 三个数组对应数的和

    for (const item of newErr) {
        const min = Math.min(arr1Sum, arr2Sum, arr3Sum);
        switch (min) {
            case arr1Sum:
                arr1.push(item);
                arr1Sum += item;
                break;
            case arr2Sum:
                arr2.push(item);
                arr2Sum += item;
                break;
            case arr3Sum:
                arr3.push(item);
                arr3Sum += item;
                break;

            default:
                break;
        }
    }
    return [arr1, arr2, arr3];
}

Oct 07 '21 10:10 nhyu

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)

你这有个bug，就是current > avg的时候,arr再splice回去后，arr forEach的index会受影响。 let arr = [11, 42, 23, 4, 5, 6, 4, 5, 6] 我试这个的时候发现的。不过好棒，我也想到这么做了，但是没写出来！学习了～

Nov 03 '21 08:11 SnailOwO

// 借助上面大佬们的思想写出来的改版
 let arr = [11, 42, 23, 4, 5, 6, 4, 5, 6, 11, 23, 42, 56, 78, 90]

    function f1(arr, count) {
        // 从大到小排序
        arr.sort((a, b) => b - a)
            // 求和 & 平均数
        const avg = Math.ceil(arr.reduce((acc, cur) => acc + cur) / count)
            // for循环相加
        const resAry = []
        for (let i = 0; i < count - 1; i++) {
            let total = 0
            resAry[i] = []
            arr.forEach((item, index) => {
                if (avg >= total + item) {
                    total += item
                    resAry[i].push(item)
                    arr.splice(index, 1)
                }
            })
        }
        resAry[count - 1] = arr
        return resAry
    }
`

Nov 03 '21 09:11 SnailOwO

@SnailOwO ，输入[1,2,3,4]不是最优解

Sep 01 '22 02:09 AAA611

var a = [11, 42, 23, 4, 5, 6, 4, 5, 6, 11, 23, 42, 56, 78, 90]
var res = [{sum: 0, arr: []}, {sum: 0, arr: []}, {sum: 0, arr: []}]
// 从大到小排序，最后放细沙
a.sort((a,b) => b-a).map(el => {
   var min = res.sort((a,b) => a.sum - b.sum)[0]
    min.sum += el
    min.arr.push(el)
})

res.map(el => el.arr)

Oct 09 '22 13:10 dolphin0618

var a = [11, 42, 23, 4, 5, 6, 4, 5, 6, 11, 23, 42, 56, 78, 90]
var res = [{sum: 0, arr: []}, {sum: 0, arr: []}, {sum: 0, arr: []}]
// 从大到小排序，最后放细沙
a.sort((a,b) => b-a).map(el => {
   var min = res.sort((a,b) => a.sum - b.sum)[0]
    min.sum += el
    min.arr.push(el)
})

res.map(el => el.arr)

思路跟你一样，但你的代码超简洁

Nov 14 '22 14:11 facethesunsea

FE-Interview FE-Interview copied to clipboard

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

FE-Interview
FE-Interview copied to clipboard