具有最大工资问题的贪心算法？

Question

我正在尝试解决以下问题。我认为我的解决方案运行良好。但是，我尝试上传解决方案的系统不接受我的解决方案。可能有些测试失败了。我可以知道我错过了什么吗？

问题是：

作为成功面试的最后一个问题，你的老板给你几张纸，上面写着数字，让你从这些数字中组成一个最大的数字。得到的数字将成为你的薪水，所以你非常想最大化这个数字。你怎么能这样做？

Sample 1

Input:

2

21 2

Output: 221

Sample 2

Input:

3

23 39 92

Output: 923923

我的解决办法是：

function MaxSallary(nums) {
  let maxSize = Math.max(...nums).toString().length;
  let newArr = [];

  nums.map((num) => {
    while (num.toString().length < maxSize) {
      num = num.toString().concat(num.toString().split("").slice(-1)[0]);
    }

    newArr.push(Number(num));
  });

  finalArr = [];
  while (newArr.length > 0) {
    let minIndex = newArr.indexOf(Math.max(...newArr));
    newArr.splice(minIndex, 1);
    finalArr.push(...nums.splice(minIndex, 1));
  }
  return finalArr.join("");
}

console.log(MaxSallary([2, 12, 34, 11, 43, 21, 5]));

Answer 1

您想知道应该以什么顺序连接数字，以便在解析回数字后，结果是可能的最高值。这样改写，看起来我们应该先对数组进行排序。

当比较两个数字a和b时，要知道哪个先来，我们需要知道${a}${b}和${b}${a}之间的which one is higher :

.sort((a, b) => parseInt(`${b}${a}`, 10) - parseInt(`${a}${b}`, 10)))

.sort mutates the array (and returns it), so I'm cloning it先.

function MaxSallary(nums) {
  const salary = [...nums]
    .sort((a, b) => parseInt(`${b}${a}`, 10) - parseInt(`${a}${b}`, 10))
    .join("");
  return salary;
}

console.log(MaxSallary([21, 2]));
console.log(MaxSallary([23, 39, 92]));
console.log(MaxSallary([2, 12, 34, 11, 43, 21, 5]));

具有最大工资问题的贪心算法？

Greedy Algorithm with Maximum Salary Problem?

javascript

algorithm

greedy