A+ Leetcode 討論整理 week1

本週主要針對三種資料結構String、Array、Object來進行相關練習,並搭配幾題Leetcode上的題目作為範例,重點為如何解析題目背後的邏輯思維,故將相關的知識整理成筆記呈現。

Javascript Data Type

常見String的method: fromCharCode(), charCodeAt(), concat(), includes(), indexOf(), localeCompare(), match(), repeat(), replace(), search(), slice(), split(), substring(), toLowerCase(), toUpperCase(), trim()

Array(陣列)、Object(物件) — Mutable(可變的)、Object Type(物件型別)、Call by reference(傳址參考):指向記憶體的位址

常見Array的method:from(), isArray(), concat(), entries(), every(), fill(), filter(), find(), findIndex(), forEach(), includes(), indexOf(), join(), map(), pop(), push(), reduce(), reverse(), shift(), slice(), some(), sort(), splice(), unshift()

常見Object的method:assign(), create(), defineProperties(), defineProperty(), entries(), freeze(), keys(), hasOwnProperty(), values()

String vs Array — 記憶體所佔的空間複雜度O(1) vs O(n)

Array vs Object — 有順序(index) vs 無順序(key-value pairs -> Hash Table/Hash Map 的一種)

如何複製Array和Object,避免call by reference的問題 — Array: slice, spread operator([…])、Object:淺拷貝(assign)&深拷貝(JSON.stringify() <-> JSON.parse())

#412 Fizz Buzz

But for multiples of three, it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

方法一(暴力解):。分別判斷15的倍數、5的倍數、3的倍數所對應的字詞,其餘的數字則轉為字串,最終放入陣列並輸出。

/**
* @param {number} n
* @return {string[]}
*/
var fizzBuzz = function(n) {
const result = [];
for(let i = 1; i <= n; i++) {
if(i % 3 === 0 && i % 5 === 0) {
result.push("FizzBuzz");
} else {
if(i % 5 === 0) {
result.push("Buzz");
} else if(i % 3 === 0) {
result.push("Fizz");
} else {
result.push(i.toString());
}
}
}

return result;
};

方法二(String Concatenation字串串接):不一樣的地方是只要判斷是否為3的倍數跟五的倍數,如果為15的倍數的話,字串會自然地串在一起

/**
* @param {number} n
* @return {string[]}
*/
var fizzBuzz = function(n) {
let ans = [];
for (let i = 1; i <= n; i++) {
let str = '';
if (i % 3 === 0) {
str += 'Fizz';
}
if (i % 5 === 0) {
str += 'Buzz';
}
if (!str) {
str = i + '';
}
ans.push(str);
}
return ans;
};

Javascript字串轉陣列&陣列轉字串 — parseInt()、Number()、+s & n.toString()、String(n)、n + “”

方法三(Hash Table):建立一個物件分別存數字及其對應的字詞,在遍歷1到n的過程中,同時遍歷該物件,判斷該數字能否被物件中存的數整除,再依序做字串串接

/**
* @param {number} n
* @return {string[]}
*/
var fizzBuzz = function(n) {
const result = [];
const mappings = {
'3': 'Fizz',
'5': 'Buzz'
};

for(let i = 1; i <= n; i++) {
let str = '';
for(let num in mappings) {
if(i % parseInt(num, 10) === 0) {
str += mappings[num];
}
}
if(!str) {
str += i + '';
}
result.push(str);
}

return result;
};

方法四(較少程式碼):運用三元運算子來判斷

/**
* @param {number} n
* @return {string[]}
*/
var fizzBuzz = function(n) {
const result = [];
let str = '';

for(let i = 1; i <= n; i++) {
str = ((i % 3 === 0 ? 'Fizz' : '') + (i % 5 === 0 ? 'Buzz' : '')) || i + '';
result.push(str);
}

return result;
};

#1 Two Sum

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

方法一(暴力解):跑雙重迴圈,判斷每兩個值相加是否等於目標值,最終回傳兩個值的index值

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for(var i = 0; i < nums.length; i++) {
for(var j = i + 1; j < nums.length; j++) {
if(nums[i] + nums[j] === target) {
return [i, j];
}
}
}
};

方法二(Hash Table):跑一個迴圈,判斷目標數目標數減去當前的數是否存在於物件中,存在的話則返回當前的index值及存放於物件中以減去的數為key的value值,否則將當前的數作為key值、index作為value值存放於物件中

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var map = {};

for(var i = 0; i < nums.length; i++) {
var val = nums[i];

if(map[target - val] >= 0) {
return [map[target - val], i];
} else {
map[val] = i;
}
}
};

#371 Sum of Two Integers

方法一(暴力解):從1遍歷至b取絕對值,查看b是否大於或等於0,並依次將a做遞增或遞減

/**
* @param {number} a
* @param {number} b
* @return {number}
*/
var getSum = function(a, b) {
for (let i = 1; i <= Math.abs(b); i++) {
b >=0 ? a++ : a--;
}
return a;
};

位元 AND(a & b) — 當兩運算元的該位置皆為 1 時,回傳值的該位置為 1

位元 XOR(a ^ b) — 當兩運算元的該位置恰好一者為 1 時,回傳值的該位置為 1

左移 (a << b)—將 a 的二進位表示法左移 b (< 32) 位元,右側補 0

  0  00        1  10
+ 1 10 ^ + 1 10 &
---------- ------------
1 10 10 << 1
2 100

方法二(位元運算):將兩數轉換為二進位並進行運算,當不需要進位時可以直接回傳 a ^ b,需要進位時透過(a & b)並向左位移一位(<<1),每一次遞迴算出新的進位值

/**
* @param {number} a
* @param {number} b
* @return {number}
*/
var getSum = function(a, b) {
if(b === 0) return a;
let sum = a ^ b;
let carry = (a & b) << 1;
return getSum(sum, carry);
};

#344 Reverse String

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

方法一(未符合題目要求空間複雜度O(1)):宣告一個額外的陣列,利用迴圈遍歷字串s,並從最後面開始一個個將字元放入陣列中

/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
var result = [];
for(var i = s.length-1; i >= 0; i--){
result.push(s[i]);
}
return result;
};

方法二(暴力解):首先將陣列轉成字串,再遍歷陣列將每個字元替換成字串中依序由後面往前遞減的字元

/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
let str = s.join('');
for(let i = 0; i < s.length; i++){
s[i] = str[s.length-i-1];
}
return;
};

方法三(half loop):只要跑一半的陣列,將陣列中的字元頭尾兩兩作交換

/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
let len = s.length-1;
for(let i = 0; i < len / 2; i++){
const tmp = s[i];
s[i] = s[len-i];
s[len-i] = tmp;
}

return s;
};

變數兩兩交換

var a = 1, b = 2, tmp;
tmp = a;
a = b;
b = tmp;
let a = 1, b = 2;
[a, b] = [b, a]
--------------------------
//下方兩個僅適用兩數為正的
var a = 1, b = 2;
a = a + b; // a = 3, b = 2
b = a - b; // a = 3, b = 1
a = a - b; // a = 2, b = 1
var a = 1, b = 2; // 二進位制:a = 0001, b = 0010
a = a ^ b; // 計算結果:a = 0011, b = 0010
b = a ^ b; // 計算結果:a = 0011, b = 0001
a = a ^ b; // 計算結果:a = 0010, b = 0001

方法三(two pointers):利用雙指針的方式,一個指針從頭,另一個指針從尾巴開始算,兩兩指針依序遞增及遞減來縮小範圍

/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
let low = 0;
let high = s.length - 1;

while(low < high){
[s[low], s[high]] = [s[high], s[low]]
high--;
low++;
}
return;
};

方法四(recursion):利用遞迴的方式不斷的呼叫自身函式,透過每一次的呼叫來達成範圍縮小

/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
var reverseStringHelper = function(left, right) {
if(left >= right) return;
[s[left], s[right]] = [s[right], s[left]];
return reverseStringHelper(left + 1, right - 1);
};
return reverseStringHelper(0, s.length - 1);
};