找出平均對等數
const arr = [-11, 0, 1, 2, 3, 9, 14, 17, 21];
const average = 1.5;
// O(n^2)
const averagePair = (arr, average) => {
const result = [];
for (let i = 0; i <= arr.length; i++) {
for (let j = 0; j <= arr.length; j++) {
const currentItem = arr[i];
const loopItem = arr[j];
// arr是被排序過的且不重複數組, 所已loopItem只能大於currentItem才不會重複
if ((currentItem + loopItem) / 2 === average && loopItem > currentItem) {
result.push([currentItem, loopItem]);
}
}
}
return result;
};
// [ [ -11, 14 ], [ 0, 3 ], [ 1, 2 ] ]
console.log(averagePair(arr, average));
透過此方法雖然能找到答案,但是複雜度為O(N^2),透過Pointer優化此演算法
Pointerc和counter一樣是優化複雜度的一個方法,他們並不是一個正式的名稱
只有在sorted array情況下可以使用,找出最左邊和最右邊數字是否等於要找的值,若超過則代表直過大右邊直要遞減,若加總值小於則代表過小左邊要遞增,若等於代表找到該值,左右值分別增減尋找下個符合條件
const arr = [-11, 0, 1, 2, 3, 9, 14, 17, 21];
const average = 1.5;
const averagePair = (arr, average) => {
let left = 0;
let right = arr.length - 1;
const result = [];
while (right > left) {
const firstItem = arr[left];
const lastItem = arr[right];
const current_average = (firstItem + lastItem) / 2;
if (current_average > average) {
right--;
} else if (current_average < average) {
left++;
} else if (current_average === average) {
result.push([firstItem, lastItem]);
right--;
left++;
}
}
return result;
};
console.log(averagePair(arr, average));
leetcode 2108. Find First Palindromic String in the Array: https://leetcode.com/problems/find-first-palindromic-string-in-the-array/
subsequence是判斷比對字串順序是否符合比對的字串
const subsequence = (subStr, str) => {
const subStrLength = subStr.length;
const strLength = str.length;
let subPointer = 0;
let pointer = 0;
while (pointer < strLength) {
if (subStr[subPointer] === str[pointer]) {
// 比對string條件符合時pointer各++
subPointer++;
pointer++;
} else {
// 不等於時比對的pointer++
pointer++;
}
}
// 如果subPointer的長度符合代表全部都跑完則回傳true
return subPointer === subStrLength;
};
console.log(subsequence('book', 'brooklyn')); // true
console.log(subsequence('hello', 'hello Dear')); // true
console.log(subsequence('abc', 'bac')); // false
console.log(subsequence('abc', 'abc')); // true