我的任務是創建一個 JS 腳本，該腳本能夠在包含長度為 6 的字母字符（僅小寫）的所有排列的陣列上使用二進制搜索找到一個字串 - 表示這種形式的所有字串：
['aaaaaa','aaaaab','aaaaac'.... 'zzzzzx','zzzzzy','zzzzzz']
（陣列中共有 26^6 項）
由于它的大小 - 我無法在本地生成陣列并對其運行常規二進制搜索，我需要能夠在不創建陣列的情況下找到 n/2 位置 (n = 26^6) 的字串。
另一方面 - 我需要在任何字串（'aaaaaa'，'zzzzzz'）到數字之間創建某種一對一的映射，然后我可以制作相反的方式（從數字到字串）除法計算并找到中間字串等等。
最好這應該在 JS/TS 中，因為我想最終用它制作一個節點應用程式。
有任何想法嗎？
uj5u.com熱心網友回復：
你可以做一些像二進制數一樣的事情，我的意思是用 base26 寫數字，然后使用指數在相應的位置找到相應的字母。
let number = (26**6)/2
let exponants = number.toString(26)
let correspondingString = exponants
.split('')
.map(elem => parseInt(elem, 26))
.map(elem => (elem 10).toString(36))
.join('')
console.log(correspondingString);和反向：
let string = 'naaaaa'
let correspondingNumber = string
.split('')
.map(elem => parseInt(elem, 36) - 10)
.map((elem, index) => elem*(26**(5-index)))
.reduce((sum, value)=> sum value, 0)
console.log(correspondingNumber);uj5u.com熱心網友回復：
筆記
該解決方案在某種程度上將問題推廣到更大的數字。與問題相關的數字仍然可以通過標準的 JS 數字型別來容納。
解決方案
您可以a-z使用 JS 的BigInt 物件（任意大小的整數）找到給定數字的表示形式。
如果您正在尋找n/2排序器排列串列中的第 -th 個數字，您可以執行以下操作：
let bn_x = ((26n ** 6n) / 2n) // BigInt notation
, s_x26 = bn_x.toString(26) // Convert in base 26. Digits are represented by 0-9,a-q
, s_atoz // Will hold s_x26 with digits represented by a-z
;
s_atoz =
Array
.from(s_x26) // string -> array of chars (ie. array of single-letter strings)
.map ( c => { // map a-q -> k-z, 0-9 -> a-j
return String.fromCharCode((( c.charCodeAt(0) < 'a'.charCodeAt(0) ) ? (c.charCodeAt(0) ( 'a'.charCodeAt(0) - '0'.charCodeAt(0) )) : ( c.charCodeAt(0) 10 )));
})
.join('') // array of chars -> string
;
console.log(s_atoz);當然，這個具體結果也可以不用計算推匯出來。
反過來，與基本思想類似，但需要注意的是：在撰寫本文時，還沒有可識別基數的 BigInt 建構式，因此需要使用基數構造的基本步驟來組裝數字。
let s_atoz = 'naaaaa'
, abn_x26 =
Array
.from(s_atoz)
.map ( c => {
return BigInt(c.charCodeAt(0) - 'a'.charCodeAt(0));
})
, bn_x = abn_x26.reduce ( (previousValue, currentValue) => {
return BigInt(previousValue) * 26n BigInt(currentValue);
}
, 0n
)
;
console.log(bn_x.toString());uj5u.com熱心網友回復：
如果您只是想在我們的想象陣列中的給定位置找到將出現的字串，我們可以使用這個numberToString函式來計算它：
const n2s = (chars, len = chars .length) => (n) =>
(n < len ? '' : n2s (chars, len) (~~ (n / len)))
chars [n % len]
const fixedN2s = (digits, chars) => (n) =>
n2s (chars) (n) .padStart (digits, chars [0])
const numberToString = fixedN2s (6, 'abcdefghijklmnopqrstuvwxyz')
; [28, 268041553, 202214284, 26 ** 6 / 2] .forEach (
s => console .log (`numberToString (${s}) //=> "${numberToString (s)}"`)
)我們從一個完成大部分作業的輔助函式開始，首先接受我們想要使用的字母表。這里都是小寫字母，但我們可以很容易地想象對“abcde”做同樣的事情。它回傳一個接受數字的函式，然后我們剝離該數字的最后一個“數字：”，將其用作chars最后一個字符的索引，然后對于字串的其余部分，要么回傳一個空字串（在我們的基本情況時n小于我們的字符數）或遞回呼叫的值，該數字被剝離，剩余的數字通過將我們的字符數除以余數來轉移。
我們在一個函式上進行分層，該函式fixedN2s使用一個附加引數呼叫上述函式，該digits引數告訴使用第一個字符預填充的固定位置的數量。也就是說，n2s ('abc...z') (28)會產生'bc'，但我們想用a, 預填充來得到'aaaabc'。
我們使用 pass6和我們的字母表到這個函式來創建numberToString我們的主要函式。
請注意，我們也可以簡單地做相反的事情，就像這個片段：
顯示代碼片段
const s2n = (chars,
encoding = [...chars] .reduce ((a, d, i) => ((a [d] = i), a), {})
) => ([...ss]) => ss .length == 0
? 0
: chars .length * s2n (chars, encoding) (ss .slice (0, -1)) encoding [ss .at (-1)]
const stringToNumber = s2n ('abcdefghijklmnopqrstuvwxyz')
; ['abc', 'woolen', 'random', 'naaaaa'] .forEach (
s => console .log (`stringToNumber ("${s}") //=> ${stringToNumber (s)}`)
)轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498194.html
標籤：javascript 打字稿 算法
上一篇：矩陣中的最大非負積