我無法通過這個編碼挑戰：代碼挑戰：https : //www.codewars.com/kata/550f22f4d758534c1100025a/train/javascript
因為我的代碼太慢了。我不確定我的代碼的哪一部分導致了問題。這就是為什么我需要幫助來優化它。
function dirReduc(arr){
if (arr.length === 0 || arr.length === 1) return [];
let lengthTracker = arr.length;
for (let i = 0; i < arr.length; i ) {
if (lengthTracker > arr.length) {
lengthTracker = arr.length;
i = 0;
}
switch(arr[i]) {
case "NORTH":
arr[i-1] === "SOUTH"? arr.splice(i-1,2) :
arr[i 1] === "SOUTH"? arr.splice(i,2) : null
break;
case "SOUTH":
arr[i-1] === "NORTH"? arr.splice(i-1,2) :
arr[i 1] === "NORTH"? arr.splice(i,2) : null
break;
case "EAST":
arr[i-1] === "WEST"? arr.splice(i-1,2) :
arr[i 1] === "WEST"? arr.splice(i,2) : null
break;
case "WEST":
arr[i-1] === "EAST"? arr.splice(i-1,2) :
arr[i 1] === "EAST"? arr.splice(i,2) : null
break;
}
i===arr.length-1? i=0:null
}
return arr;
}
uj5u.com熱心網友回復：
拼接可能很昂貴。我們可以形成一個回圈，假設函式已經正確地減少了串列的下一部分：
function matches(a, b){
return (a == "NORTH" && b == "SOUTH") ||
(b == "NORTH" && a == "SOUTH") ||
(a == "EAST" && b == "WEST") ||
(b == "EAST" && a == "WEST");
}
function f(A, i=0){
if (i == A.length)
return [];
const rest = f(A, i 1);
const [head,...tail] = rest;
if (head){
if (matches(A[i], head))
return tail;
else
return [A[i]].concat(rest);
}
return [A[i]];
}
uj5u.com熱心網友回復：
我看到這有幾個問題。首先，正如我在評論中提到的，拼接長陣列的成本很高，并且會使您的演算法O(n^2). 簡單而快速的方法是使用讀取點和寫入點一次將元素復制到一個單元格中，只需跳過湮滅，然后在最后使用一次拼接來修剪末尾未復制的單元格陣列。這樣就可以了O(n)。
其次，您的代碼正在向前和向后尋找匹配項，這既不必要又可能令人困惑。最后，不需要 aswitch (...)因為所有分支都做同樣的事情。
這是我將如何使用您的代碼來完成此操作，更改上述內容并在評論中注明。
function dirReduc(arr){
if (arr.length === 0 || arr.length === 1) return [];
let lengthTracker = 0; // the write-point
for(let i = 0; i < arr.length; i ) { // i is the read-point
if(lengthTracker == 0) {
// if no output, copy readpoint and advance write-point
arr[lengthTracker] = arr[i];
lengthTracker ;
} else {
// replaces switch()
if (((arr[lengthTracker-1] === "NORTH") && (arr[i] === "SOUTH"))
|| ((arr[lengthTracker-1] === "SOUTH") && (arr[i] === "NORTH"))
|| ((arr[lengthTracker-1] === "EAST") && (arr[i] === "WEST"))
|| ((arr[lengthTracker-1] === "WEST") && (arr[i] === "EAST"))) {
lengthTracker--; // annihilate by decrementing the writepoint
} else {
// copy readpoint to after writepoint and advance
arr[lengthTracker ] = arr[i];
}
}
}
//trim the array to only include what was written
arr.splice(lengthTracker);
return arr;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335890.html
標籤：javascript 算法
上一篇：在O(n)中查找并排序n個值陣列中的log2(n)最小值和log2(n)最大值
下一篇：計算字串中字符出現的次數？