近期遇到的計(算)算(法)題及解(JavaScript)

以下是近期遇到的三個計(算)算(法)題... 提到這些問題的時候簡單理了下思路，後面又以JavaScript程式碼實現並順便記個筆記...

至於是什麼場景下遇到這些題的麼... ：)

問題一：從無序數組裡取出M個值，總和為N，得出一個解即可

給出思路：

1. 遞迴直到長度為M為止，得出陣列子集；

2. 對得出的陣列子集進行計算，如果相加的和等於N(如果設定容差T，則相加的和與N的差距小於容差T)，則將子集資料存入combArr；

2.1. 預設只取第一個值，取到後跳出迴圈；

2.2. 如果設定取所有結果，則繼續迴圈求之後的子集。

程式碼如下：

const arr = [14, 30, 38, 15, 34, 20, 10, 5, 35, 32, 27, 11, 9, 50, 21, 29, 3, 47, 26, 39, 18, 17, 40, 37, 49, 23, 22, 43, 33, 1, 24, 8, 16, 12, 25, 28, 48, 2, 41, 44, 45, 46, 4, 13, 42, 36, 31, 19, 6, 7];
// 引數陣列數量總和容差是否取全部結果
function getCombination(array, count, sum, tolerance, allResult) {

const combArr = [];
const $tolerance = isNaN(tolerance) ? 0 : tolerance;

if (!count || isNaN(count)) {;
return combArr.push([]), combArr;
}

// 是否取所有結果
let getAllResult = false;

const generateIdxComb = ($originArray, $count, $array) => {
if ($count === 0) {
const $sum = $originArray.reduce((a, b) => a + b);
if (Math.abs(sum - $sum) <= $tolerance) {
combArr.push($originArray);
if (allResult) {
getAllResult = true;
}
}
return;
}
for (let i = 0, len = $array.length; i <= len - $count; i++) {
if (combArr.length && !getAllResult) {
break;
}
generateIdxComb($originArray.concat($array[i]), $count - 1, $array.slice(i + 1));
}
}

// 遞迴取子集
(generateIdxComb)([], count, array);
return combArr;
}
getCombination(arr, 3, 21);
// output [[14, 5, 2]]
getCombination(arr, 3, 21, 0, true);
// output [[14, 5, 2],[14, 3, 4],...]27個組合

問題一的擴充套件，揹包問題：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高

const arr = '[{weight: 1,price: 15}, {weight: 3,price: 12}, {weight: 5,price: 16}, {weight: 6,price: 9}, {weight: 7,price: 18}, {weight: 9,price: 11}]';
// 陣列 數量 限定值
function getMaxComb(array, count, sum) {
let combArr = [];
let totalPrice = 0;

if (!count || isNaN(count)) {;
return combArr;
}

const generateIdxComb = ($originArray, $count, $array) => {
if ($count === 0) {
const $sumWeight = $originArray.reduce((a, b) => a + b.weight, 0);
if ($sumWeight <= sum) {
const $totalPrice = $originArray.reduce((a, b) => a + b.price, 0);
if ($totalPrice > totalPrice) {
totalPrice = $totalPrice;
combArr = $originArray;
}
};
return;
}
for (let i = 0, len = $array.length; i <= len - $count; i++) {
generateIdxComb($originArray.concat($array[i]), $count - 1, $array.slice(i + 1));
}
}

// 遞迴取子集
(generateIdxComb)([], count, array);

return combArr;
}
getMaxComb(arr, 3, 17);
// output [{"weight":1,"price":15},{"weight":5,"price":16},{"weight":7,"price":18}]

問題二：取一串字串裡的最長迴文

關於這個問題，理了2種思路，一種是空間換時間的，但是在瀏覽器跑1W以上長度的字串就導致瀏覽器奔潰；下面程式碼中的是另外一種，在瀏覽器跑了個10000長度字串的時間為200ms不到。兩種方法在nodejs端皆可用，前者效率是後者的10倍左右，所以...就直接貼了效率較佳的程式碼。

先給出思路：

1. 考慮到迴文長度奇偶的區別，預先處理字串，中間加_連線；

2. 以字串做迴圈，分別以當前索引的字元為中心將兩邊的值做比較，如果是迴文，則返回迴文長度的1/2；

3. 如果迴文長度大於當前存的最長迴文長度變數的值，則更新最長迴文長度變數和最長迴文中心索引值變數；

4. 當字串長度減去迴圈中心小於最長迴文長度變數，則說明以右邊字元為中心的迴文不會比當前獲得的最長迴文長了，就不用繼續浪費計算資源了。

程式碼如下：

function getLongestPalindrome($value) {

// 考慮到迴文長度是偶數的情況
value = $value.split('').join('_');
// 存最長迴文長度 (其實是長度的1/2；從doCkeck中可以看出，返回的僅是迴圈的值)
let longestPalindromeLen = 0;
// 存最長迴文的中心索引值
let palindromeCenter = 0;
// 陣列長度
const len = value.length;

// 迴文檢測
function doCheck(idx, value) {
let i = 0;
for (; i <= idx; i++) {
if (value[idx - i] !== value[idx + i]) {
break;
}
}
// 注意這裡返回的是 i - 1，所以其實取到的是迴文長度的1/2
return i - 1;
}

// 遍歷陣列
for (let i = 0; i < len; i++) {
// 省掉後續的一些判斷，因為這時候以右邊字元為中心的迴文長度已經小於等於最長迴文了
if (len - i < longestPalindromeLen) {
break;
}
const checkResult = doCheck(i, value);
if (checkResult && checkResult > longestPalindromeLen) {
longestPalindromeLen = checkResult;
palindromeCenter = i;
}
}

// 組成結果
let str = value.slice(palindromeCenter - longestPalindromeLen, palindromeCenter + longestPalindromeLen + 1).replace(/_/g, '');

return str;
}

getLongestPalindrome('aba');
// output 'aba'
getLongestPalindrome('adaceebdsdbeecabd');
// output 'aceebdsdbeeca'
getLongestPalindrome('abbac');
// output 'abba'
getLongestPalindrome('12345678765432');
// output '2345678765432'

1-30 - 15 - 34 - 23
|||||
20 -6- 8- 27 - 19
|||||
35 -11 - 9- 21 - 7
|||||
29 -3- 50 - 18 - 10

先給出思路：

1-31 - 46- 80- 103
|||||
21 -37 - 54- 107 - 126
|||||
56 -67 - 76- 128 - 135
|||||
85 -88 - 138 - 156 - 166

156 > 135， 得出 右
138 > 128， 得出 右
88 > 76，得出 右
85 > 67，得出 右
85之後只能向上反推，得出3個下
給出結果： 下下下右右右右

const arr = [
[1, 30, 15, 34, 23],
[20, 6, 8, 27, 19],
[35, 11, 9, 21, 7],
[29, 3, 50, 18, 10]
];

function calcPath(matrix) {

// 存相加的值用
const bestPathSum = [];
for (let i = 0; i < matrix.length; i++) {
bestPathSum.push([]);
}

// 求路徑過程，如 1-2-33個數當中只有2個"-"，可得路徑過程 = 路徑長度 - 1
let bestPathValue = [];
const RIGHT = '右';
const DOWN = '下';
let goDownLen = matrix.length - 1;
let goRightLen = matrix[0].length - 1;

// 二維陣列計算，取最大值作為儲存
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[i].length; j++) {
// 第一步設定第一個值作為基礎
if (i === 0 && j === 0) {
bestPathSum[i][j] = matrix[i][j];
} else if (i === 0) {
// 第一個陣列往右計算
bestPathSum[i][j] = bestPathSum[i][j - 1] + matrix[i][j];
} else if (j === 0) {
// 多個數組以第一個值往下計算
bestPathSum[i][j] = bestPathSum[i - 1][j] + matrix[i][j];
} else {
// 除索引 0 外的其他值計算
bestPathSum[i][j] = Math.max(bestPathSum[i - 1][j], bestPathSum[i][j - 1]) + matrix[i][j];
}
}
}

// 輸出路徑
for (let i = goDownLen + goRightLen; i > 0; i--) {
if (goDownLen === 0) {
goRightLen--;
bestPathValue.push(RIGHT);
} else if (goRightLen === 0) {
goDownLen--;
bestPathValue.push(DOWN);
} else {
if (bestPathSum[goDownLen][goRightLen - 1] > bestPathSum[goDownLen - 1][goRightLen]) {
goRightLen--;
bestPathValue.push(RIGHT);
} else {
goDownLen--;
bestPathValue.push(DOWN);
}
}
}

const result = {
bestPath: bestPathValue.reverse().join('-'),
maxValue: bestPathSum[bestPathSum.length - 1][bestPathSum[0].length - 1]
}

return result;
}
calcPath(arr);
// output {bestPath: "下-下-下-右-右-右-右", maxValue: 166}