如何在陣列樹模式生成器中支持256個沒有null的值？-有解無憂

我喜歡這個問題的答案，它是如此有創意和強大。我將它翻譯為支持 256 個值而不支持空陣列，并且樹/陣列shape生成似乎有效。然而，我被困在編碼基數函式是如何作業的，以及如何翻譯它，因為現在POSSIBLE_SHAPE_LIST只有 9 個元素而不是 16 個。給定索引，如何getPath在樹結構中適當地放置值的路徑？這是完整的代碼：

const POSSIBLE_SHAPE_LIST = [1, 2, 4, 8, 16, 32, 64, 128, 256]
const CODE_LIST = collect()

console.log(CODE_LIST.join('\n'))
console.log(getPath(28, 21))

function getPath(size, i) {
  let code = CODE_LIST[size - 1]
  let limit = POSSIBLE_SHAPE_LIST[code % POSSIBLE_SHAPE_LIST.length]

  if (i < limit) {
    return [i]
  }

  for (let sub = 1; sub < 6; sub  ) {
    i -= limit
    code /= 9
    limit = POSSIBLE_SHAPE_LIST[code % POSSIBLE_SHAPE_LIST.length]
    if (i < limit) {
      return [sub, i]
    }
  }
}

function collect() {
  let codes = []

  for (let n = 1; n <= 256; n  ) {
    let shapeNumbers = shape(n)
    let code = encode(shapeNumbers)
    codes.push(code)
  }

  return codes
}

function encode(shapeNumbers) {
  let code = 0

  for (let i = shapeNumbers.length - 1; i >= 0; i--) {
    code = code * POSSIBLE_SHAPE_LIST.length   POSSIBLE_SHAPE_LIST.indexOf(shapeNumbers[i])
  }

  return code
}

/**
 * Returns number of atomic entries,
 * followed by data-size(s) of subarrays
 */

function shape(n) {
  let p = greatestPowerOf2(n);
  if (p >= n) {
    // The only cases where there are no subarrays
    return [n];
  }

  // Try with one subarray
  for (let sub = 2; sub < n && sub <= 256; sub *= 2) {
    let top = n - sub   1;
    p = greatestPowerOf2(top);
    if (p >= top) {
      return [p - 1, sub];
    }
  }

  // Try with two subarrays
  for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
    for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
      let top = n - sub1 - sub2   2;
      if (top < 0) break;
      p = greatestPowerOf2(top);
      if (p >= top) {
        return [p - 2, sub1, sub2];
      }
    }
  }

  // Try with three subarrays
  for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
    for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
      for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
        let top = n - sub1 - sub2 - sub3   3;
        if (top < 0) break;
        p = greatestPowerOf2(top);
        if (p >= top) {
          return [p - 3, sub1, sub2, sub3];
        }
      }
    }
  }

  // Try with four subarrays
  for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
    for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
      for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
        for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
          let top = n - sub1 - sub2 - sub3 - sub4   4;
          if (top < 0) break;
          p = greatestPowerOf2(top);
          if (p >= top) {
            return [p - 4, sub1, sub2, sub3, sub4];
          }
        }
      }
    }
  }

  // Try with five subarrays
  for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
    for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
      for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
        for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
          for (let sub5 = 2; sub5 <= sub4; sub5 *= 2) {
            let top = n - sub1 - sub2 - sub3 - sub4 - sub5   5;
            if (top < 0) break;
            p = greatestPowerOf2(top);
            if (p >= top) {
              return [p - 5, sub1, sub2, sub3, sub4, sub5];
            }
          }
        }
      }
    }
  }

  // Try with 6 subarrays
  for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
    for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
      for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
        for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
          for (let sub5 = 2; sub5 <= sub4; sub5 *= 2) {
            for (let sub6 = 2; sub6 <= sub5; sub6 *= 2) {
              let top = n - sub1 - sub2 - sub3 - sub4 - sub5 - sub6   6;
              if (top < 0) break;
              p = greatestPowerOf2(top);
              if (p >= top) {
                return [p - 6, sub1, sub2, sub3, sub4, sub5, sub6];
              }
            }
          }
        }
      }
    }
  }

  // Try with 7 subarrays
  for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) {
    for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
      for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
        for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
          for (let sub5 = 2; sub5 <= sub4; sub5 *= 2) {
            for (let sub6 = 2; sub6 <= sub5; sub6 *= 2) {
              for (let sub7 = 2; sub7 <= sub6; sub7 *= 2) {
                let top = n - sub1 - sub2 - sub3 - sub4 - sub5 - sub6 - sub7   7;
                if (top < 0) break;
                p = greatestPowerOf2(top);
                if (p >= top) {
                  return [p - 7, sub1, sub2, sub3, sub4, sub5, sub6, sub7];
                }
              }
            }
          }
        }
      }
    }
  }

  throw new Error(n)
}

function greatestPowerOf2(n) {
  return n >= 256 ? 256 : n >= 128 ? 128 : n >= 64 ? 64 : n >= 32 ? 32 : n >= 16 ? 16 : n >= 8 ? 8 : n >= 4 ? 4 : n >= 2 ? 2 : 1;
}

它不應該記錄（在最后）[21]，它應該記錄類似遵循此處[14, 1]列出的模式的內容。我在原始答案的翻譯中做錯了什么？

uj5u.com熱心網友回復：

有兩個問題需要解決：

POSSIBLE_SHAPE_LIST = [1, 2, 4, 8, 16, 32, 64, 128, 256]僅列出表示子陣列的可能值，但并未列出形狀表示中第一個元素的所有可能值，即不在嵌套陣列中的原子值的數量。這個數字不一定是 2 的冪。例如，大小 28 的形狀是 [12, 4, 4, 4]，這意味著有 3 個大小為 4 的子陣列，但也有 12 個頂級槽。那 12 不是 2 的冪，但仍然需要編碼。
code /= 9將執行浮點除法（與 Java 不同）。而且，那個 9 不應該被硬編碼，因為你有一個常數。

所以寫：code = Math.floor(code / POSSIBLE_SHAPE_LIST.length)

為了解決第一個問題，我建議將collect功能分成幾個步驟：

收集所有形狀而不編碼它們
收集這些形狀中使用的不同數字并將其分配給POSSIBLE_SHAPE_LIST
執行這些形狀的編碼。

所以腳本可以從這個開始：

let shapes = collectShapes(); // Step 1
const POSSIBLE_SHAPE_LIST = getUsedNumbers(shapes); // Step 2
console.log(POSSIBLE_SHAPE_LIST);  // Demonstrate that list has 35 instead of 9 values
const CODE_LIST = shapes.map(encode); // Step 3

console.log(CODE_LIST.join('\n'));
console.log("the shape for size 28 is ", shapes[27]); // for debugging
console.log(getPath(28, 21)); // [3, 1]

function getUsedNumbers(shapes) {
  const usedNumberSet = new Set([1,2,4,8,16,32,64,128,256]);
  for (const shapeNumbers of shapes) {
    usedNumberSet.add(shapeNumbers[0]);
  }
  // Not really necessary to sort, but it is a nice-to-have
  return [...usedNumberSet].sort((a, b) => a - b); 
}

function collectShapes() {
  let shapes = [];
  for (let n = 1; n <= 256; n  ) {
    shapes.push(shape(n));
  }
  return shapes;
}

注意：我習慣用分號結束陳述句，因為我不想依賴于自動分號插入演算法。

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424320.html

標籤：javascript 数组算法

上一篇：為什么n^2被認為是一種時間復雜度，而n/2不是？[復制]

下一篇：n-1比較的最佳運行時間？