我遇到了一個演算法問題，我不知道如何原則上解決它，因為我沒有找到任何可以在這里使用的演算法。也許有人可以幫助我。
任務：有一個拉丁字符陣列。陣列中的每個字符都可以替換為任意整數。替換后，所有相同的字符也將替換為相同的數字。有沒有可能讓陣列值的總和等于k？
輸入：
- array - 拉丁字符陣列，0<length(array)<20, sub_array[i]="x" | "是" | “z”
- k - 要得到的陣列之和的值，0<k<150
輸出：布林值——可以或不能使陣列陣列的值之和等于k
示例（飛鏢）：
var array = ["x", "x", "x", "y", "z"];
var k = 10;
print(getResult(array, k)); // return true, because [2, 2, 2, 3, 1]
uj5u.com熱心網友回復：
觀察：給定nx、my 等，通過將 x、y、... 值中的任何一個更改 1，總和只能以 GCD(n, m, ...) 為增量更改，其中 GCD 是最大公約數（可以用歐幾里得演算法找到）。
k因此，只有當是其數量 GCD 的倍數時，才能滿足條件。
注意：這假設 x, y, ... 可能不是唯一的，并且可能是負數
uj5u.com熱心網友回復：
首先，您可以遍歷陣列并計算“x”、“y”和“z”的出現次數。我將這些計數稱為 x、y 和 z。那么問題就變成了：
你能找到整數 a、b 和 c，使得 a * x b * y c * z = k。
如果數字可以是負數，那么它相對簡單：如果 k % gcd(x, y, z) = 0 是可能的（忽略 0，所以如果 x 為 0 則 k % gcd(y, z) = 0）。換句話說，只有當你可以制作 gcd(x, y, z) 的倍數并且 k 不是這些數字的倍數時，才有可能失敗。
如果 a、b 和 c 必須是非負數，那么它會變得有點復雜。我們正在處理貨幣 x、y 和 z 的硬幣問題。如果 k % gcd(x, y, z) != 0 則永遠不可能。現在我們可以通過將 k, x, y 和 z 除以 gcd(x, y, z) 來簡化問題。之后，我們可以通過使用 Frobenius 數來查看是否可以輕松實作：
n = 2：所有數字 > x * y - x - y 都可以構建
n = 3：可以構建所有數字 > sqrt(3 * x * y * z)
如果 k 小于該值，我們可以檢查是否可以使用硬幣問題的常見動態規劃解決方案來構建 k。
當然，您必須處理一些邊緣情況。例如 k = 0 或者如果只給出一個數字，那么它就是 k % x = 0。
uj5u.com熱心網友回復：
這是一個簡單的解決方案，它適用于以下假設：
- 一個數字最多可以分配給一個字符
- 至少有一個字符只出現一次
function findNumbers([s,sum]) { // count occurences of characters:
let ar1 = Object.entries(s.split("").reduce((a, c) => (a[c] = (a[c] || 0) 1, a), {}))
.sort((a, b) => b[1] - a[1]); // sort: most frequent characters first
// assign interger values to each character (starting with 1 ...
let ar2=ar1.map(([c, n], i) =>{ // c: character, n: occurences, i: index
sum-=n*(i 1);
return [c, i 1<ar1.length? i 1: ar1.length sum]
});
return [Object.fromEntries(ar2),ar2.pop()[1]>ar2.pop()[1]]; // add a results flag to each solution: true/false
}
let res=[["xxxyz",10],["ghijjk",17],["abcabcabd",12],["abccdef",18],["abcd",9]].map(findNumbers)
console.log(res) // true, true, false, false, false顯然，這是一個快速的鏡頭。我還沒有檢查最不常見的字符是否只出現一次。它當然需要更多的改進，但它已經很快地表明了具有正整數的解決方案是否可能。如果最后一個數字不大于倒數第二個，則找不到合適的數字并false回傳標志。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/417558.html
標籤：