javascript - 带有素数检查的三角形中的Javascript最大路径总和

Question

我被赋予了这个算法任务：

您将在下面有一个三角形输入，您需要根据下面给定的规则找到数字的最大总和；

您将从顶部开始并向下移动到相邻的数字，如下所示。

您只能沿对角线向下走。

你只能走过非质数。

你必须尽可能地到达金字塔的尽头。

           1
          8 4
        2  6  9
      8  5  9  3

正如你所看到的，这有几条符合 NOT PRIME NUMBERS 规则的路径；1>8>6>9, 1>4>6>9, 1>4>9>9 1 + 8 + 6 + 9 = 24. 如你所见 1, 8, 6, 9 都不是质数并且走超过这些产生最大的总和。

根据上述规则，以下输入的最大总和是多少？这意味着请将此金字塔作为您的实现的输入（作为文件或直接在代码中的常量）并使用它来解决。

                              215
                           193 124
                         117 237 442
                       218 935 347 235
                     320 804 522 417 345
                   229 601 723 835 133 124
                 248 202 277 433 207 263 257
               359 464 504 528 516 716 871 182
             461 441 426 656 863 560 380 171 923
           381 348 573 533 447 632 387 176 975 449
         223 711 445 645 245 543 931 532 937 541 444
       330 131 333 928 377 733 017 778 839 168 197 197
    131 171 522 137 217 224 291 413 528 520 227 229 928
  223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233

请注意，每个节点在这里只有两个孩子（除了最底部的孩子）。例如，您可以从 215 走到 124（因为 193 是素数），然后从 124 走到 237 或 442。从 124 不能走到 117，因为它不是 124 的直系子代。

    const isNotPrime = (num) => {
      for (let i = 2; i <= Math.sqrt(num); i++) {
      if (num % i === 0) return true;
      }
      return false;
      }

    function maximumTrianglePathSum(triangle) {

        function distilLastLine() {
          let lastLine = triangle.pop(),
              aboveLine = triangle.pop()
          for (let i = 0; i < aboveLine.length; i++)
          if(isNotPrime(lastLine[i]) && isNotPrime(lastLine[i + 1])){
            aboveLine[i] = Math.max(
              aboveLine[i] + lastLine[i],
              aboveLine[i] + lastLine[i + 1]
            )
          }else if(isNotPrime(lastLine[i]) && !isNotPrime(lastLine[i + 1]) ) {
            aboveLine[i] = aboveLine[i] + lastLine[i]
          }else if(!isNotPrime(lastLine[i]) && isNotPrime(lastLine[i + 1]) ){
            aboveLine[i] = aboveLine[i] + lastLine[i + 1]
          }
          triangle.push(aboveLine)
        }

        do {
          distilLastLine()
        } while (triangle.length > 1)
        return triangle[0][0]
      }

      // testing
      const myArray = [[1],
      [8, 4],
      [2, 6, 9], 
      [8, 5, 9, 3]]
      let theTriangle = [[215],
      [193, 124],
      [117, 237, 442],
      [218, 935, 347, 235],
      [320, 804, 522, 417, 345],
      [229, 601, 723, 835, 133, 124],
      [248, 202, 277, 433, 207, 263, 257],
      [359, 464, 504, 528, 516, 716, 871, 182],
      [461, 441, 426, 656, 863, 560, 380, 171, 923],
      [381, 348, 573, 533, 447, 632, 387, 176, 975, 449],
      [223, 711, 445, 645, 245, 543, 931, 532, 937, 541, 444],
      [330, 131, 333, 928, 377, 733, 17, 778, 839, 168, 197, 197],
      [131, 171, 522, 137, 217, 224, 291, 413, 528, 520, 227, 229, 928],
      [223, 626, 34, 683, 839, 53, 627, 310, 713, 999, 629, 817, 410, 121],
      [924, 622, 911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233]]

      console.log(maximumTrianglePathSum(myArray))
      console.log(maximumTrianglePathSum(theTriangle))

所以实际上在第一个例子中它打印的是 23 而不是 24 并且最大路径是 24。

有人可以帮我检查一下代码，看看有什么问题。

标签： javascriptarraysalgorithm

Answer 1

const isPrime = (num) => {
    for (let i = 2; i*i <= num; i++) {
        if (num % i === 0) return false;
    }    
    return num !== 1;
}

function maximumTrianglePathSum(triangle){
    if(triangle === undefined || triangle.length === 0 || triangle[0].length === 0 || isPrime(triangle[0][0])){
        return 0;
    }
    let sum_values = createEmptyTriangleStructure(triangle);
    for(let k = triangle.length - 1;k >= 0;--k){
        let currentLine = triangle[k];
        for (let i = 0; i < currentLine.length; i++){
            let curr_value = currentLine[i];
            if(isPrime(curr_value)){
                sum_values[k][i] = 0;
            }else if(k === triangle.length - 1){
                sum_values[k][i] = currentLine[i];   
            }else{
                if(i !== 0){
                    sum_values[k][i] = Math.max(sum_values[k][i],curr_value + sum_values[k + 1][i-1]); // left down diagonal
                }                
                sum_values[k][i] = Math.max(sum_values[k][i],curr_value + Math.max(sum_values[k + 1][i],sum_values[k + 1][i + 1]));// check with down value as well as right down diagonal
            }
        }
    }

    return sum_values[0][0];
}

function createEmptyTriangleStructure(triangle){
    let sum = [];
    for(let i=0;i < triangle.length; ++ i){
        sum[i] = [];
        for(let j = 0;j < triangle[i].length; ++ j){
            sum[i][j] = 0;
        }
    }
    return sum;
}

const myArray = [
                    [1],
                    [8, 4],
                    [2, 6, 9], 
                    [8, 5, 9, 3]
                ];
let theTriangle = [
                        [215],
                        [193, 124],
                        [117, 237, 442],
                        [218, 935, 347, 235],
                        [320, 804, 522, 417, 345],
                        [229, 601, 723, 835, 133, 124],
                        [248, 202, 277, 433, 207, 263, 257],
                        [359, 464, 504, 528, 516, 716, 871, 182],
                        [461, 441, 426, 656, 863, 560, 380, 171, 923],
                        [381, 348, 573, 533, 447, 632, 387, 176, 975, 449],
                        [223, 711, 445, 645, 245, 543, 931, 532, 937, 541, 444],
                        [330, 131, 333, 928, 377, 733, 17, 778, 839, 168, 197, 197],
                        [131, 171, 522, 137, 217, 224, 291, 413, 528, 520, 227, 229, 928],
                        [223, 626, 34, 683, 839, 53, 627, 310, 713, 999, 629, 817, 410, 121],
                        [924, 622, 911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233]
                    ];

console.log(maximumTrianglePathSum(myArray));
console.log(maximumTrianglePathSum(theTriangle));

• 你的代码有很多问题。所以我改变了很多东西，我会试着解释我在这里做什么。
• isPrime()检查一个数字是否是素数（1也照顾）。
• if请参阅处理许多极端情况的第一个条件。在那，如果第一行的第一个数字不是素数，我们会返回，0因为您从顶部开始并且想要在非素数上行走。
• 现在，我们创建一个sum_values数组来存储每一行​​的总和。该数组的结构triangle与所有位置的初始化0相同createEmptyTriangleStructure()。
• 现在，我们从下到上遍历您的三角形（这是您的想法）。
• 如果我们在三角形行中遇到一个素数，我们将该位置设置为0in，sum_values因为我们不能从那里移动到下方。
• 如果我们正在遍历三角形中的最后一行，即else if(k === triangle.length - 1)，那么我们将它们设置为原样，因为在此下方没有行。
• 最后，您被允许进行 3 次移动 =>左下（对角线）、下、右下（对角线） => i - 1、i、i + 1。

• 所以，[k + 1][i - 1]是down left，[k + 1][i]是down，[k + 1][i + 1]是down right。

• 因此，最后，我们max在所有这些中取值并将其设置为当前位置的值[k][i]。

• 最后，我们返回[0][0]最终值。这是一个经典的动态规划问题。

• 这可以在空间方面进一步优化。当前的空间复杂度为O(n^2)，但我们可以将其减少到O(n)，我将其留给您作为练习。