標籤: LeetCode

Javascript 刷 LeetCode 學演算法 – 搜尋 Linear Search, Binary Search

Published on 由Sasa撰寫發表留言

Linear Search

時間複雜度：O(n)



744. Find Smallest Letter Greater Than Target


撞到語法不夠熟悉的問題，原本嘗試在 forEach 中 return 和 break，發現不適用
這種情況適合改用 for loop or every 等等其他方法，可參考以下文章

https://masteringjs.io/tutorials/fundamentals/foreach-break


Binary Search

時間複雜度： O log(n)

適用情境：在一個已排序的陣列中，找出其中特定的值

實作關鍵：遞迴or無窮迴圈，雙指標、中值
=> 設立雙指標、中值，並在查找的過程中不斷移動邊界

367. Valid Perfect Square

延伸閱讀：

取中值的公式

直觀來說會寫

int mid = (low + high)/2;

但這篇文章提到建議改寫

int mid = low + (high – low)/2;

原因是超過最大正整數時，會溢位，這時候取的中值就會是錯的

But if we calculate the middle index like this means our code is not 100% correct, it contains bugs.

That is, it fails for larger values of int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value(231 – 1 ).

The sum overflows to a negative value and the value stays negative when divided by 2.


Reference from geeksforgeeks

Javascript刷LeetCode – 520, substring()

Published on 由Sasa撰寫發表留言

題目：520. Detect Capital

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

  1. All letters in this word are capitals, like “USA".
  2. All letters in this word are not capitals, like “leetcode".
  3. Only the first letter in this word is capital, like “Google".

Otherwise, we define that this word doesn’t use capitals in a right way.

 


var detectCapitalUse = function(word) {
if(word === word.toLowerCase() || word === word.toUpperCase()){
return true;
}else if(word[0] === word[0].toUpperCase() && word.substring(1) === word.substring(1).toLowerCase()){
return true;
}else{
return false;
}
};

view raw

leetCode520.js

hosted with ❤ by GitHub

JS中的字串可當作char[]，直接操作[]

substring( startIndex, [endIndex])
The substring() method returns the part of the string between the start and end indexes, or to the end of the string.

參考：

[JavaScript] 手把手一起入門（二） – 變數 & 基本操作

Javascript刷LeetCode – 242

Published on 由Sasa撰寫發表留言

題目：242. Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

一開始寫，
卡在要怎麼完全比對兩個陣列，
所以查到使用JSON.stringify()。
後來查到，其他答案，利用陣列在串連回字串（ join() ）去比對，
感覺更直觀了！


var isAnagram = function(s, t) {
let s_ary = s.split('');
let t_ary = t.split('');
return JSON.stringify(s_ary.sort()) == JSON.stringify(t_ary.sort());
};
var isAnagram = function(s, t) {
if(s.length != t.length) return false;
let s_ary = s.split('').sort();
let t_ary = t.split('').sort();
return s_ary.join('') == t_ary.join('');
};

view raw

LeetCode242v1.js

hosted with ❤ by GitHub

但是運行時間還是很慢，
因此繼續尋找更加解，

注意到以下解法：


var isAnagram = function(s, t) {
if(s.length != t.length) return false;
let tb = {};
for(let i = 0 ; i < s.length ; i++){
let letter = s[i];
if(tb[letter]){
tb[letter]++;
}else{
tb[letter] = 1;
}
}
for(let i = 0 ; i< t.length ; i++){
let letter = t[i];
if(tb[letter]){
tb[letter]–;
}else{
return false;
}
if(tb[letter] < 0 ){
return false;
}
}
return true;
};

view raw

LeetCode242v2.js

hosted with ❤ by GitHub

覺得很不錯的思維，
根本不需要sort或是用物件記錄住兩方出現的次數，
直接利用一個物件以++記錄s的出現次數，再以–扣掉t出現的次數，
就可以得到解了！

Javascript刷LeetCode – 387, 雙指標遍歷: indexOf , lastIndexOf ; ES6新類型 map 與 set；for of

Published on 由Sasa撰寫發表留言

題目：387. First Unique Character in a String
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

解題思維：

先建立hashTable，再Seacrch
參考：詳細動畫可見：leetCode solution
一開始，我是使用object去紀錄每個字母出現的次數，但到後面要search時發現一個問題


var firstUniqChar = function(s) {
var ary = s.split('');
var counter = {};
for(var i = 0; i< ary.length; i++){
if(!(ary[i] in counter)){
counter[ary[i]] = 1;
}else{
counter[ary[i]] += 1;
}
}
console.log(counter);
Object.keys(counter).map(function(key,index){
if(counter[key] === 1){
return key;
}else{
return -1;
}
})
for(var j = 0 ; j < counter.lenght ; j++){
console.log(counter[j]);
}
};
var a = firstUniqChar("leetcode");
console.log(a);

view raw

leetCode387wrong.js

hosted with ❤ by GitHub

[object Object] {
c: 1,
d: 1,
e: 3,
l: 1,
o: 1,
t: 1
}

原本儲存進去的key順序亂掉了！
經過一番survey後得知，
Object的key會根據不同瀏覽器被自動排序，是不可依靠的
要控制key的順序，建議使用Array

參考：
https://stackoverflow.com/questions/47727428/axios-stop-automatic-sorting-of-objects-based-on-keys

 

 

但是我覺得object很難直接用[]操作，很麻煩～～～
再繼續survey後，發現ES6出了新的資料型態：

映射的實作
Map v.s. Set

根據MDN的定義：
Map and Set objects contain elements which are iterable in the order of insertion.
key會根據插入的順序

A Map object is a simple key/value map and can iterate its elements in insertion order.

Set objects are collections of values. You can iterate its elements in insertion order. A value in a Set may only occur once; it is unique in the Set‘s collection.
每個數值只會唯一不重複

參考：
http://www.jstips.co/zh_cn/javascript/map-to-the-rescue-adding-order-to-object-properties/

 

再搭配一個新的語法： for of 便可快速的遍歷map

根據MDN定義：
The for...of statement creates a loop iterating over iterable objects, including: built-in String, Array, Array-like objects (e.g., arguments or NodeList), TypedArray, Map, Set, and user-defined iterables.

參考：
http://www.webhek.com/post/javascript-loop-foreach-for-in-for-of.html

 


var firstUniqChar = function(s) {
var counter = new Map();
for(let word of s){
if(word === undefined)
break;
if(!(counter.has(word))){
counter.set(word,1);
}else{
counter.set(word,counter.get(word)+1);
}
}
for(let [key,value] of counter){
if(counter.get(key) === 1){
return s.search(key);
}
}
return -1;
};
var a = firstUniqChar("leetcode");

view raw

leetCode387v1.js

hosted with ❤ by GitHub

注意map元素操作的語法
map.get(element);
map.has(element);

String.search()
searches a string for a specified value, and returns the position of the match.
字串中尋找特定的字元，並返回其索引

 

上面的方法提交會過，但是總覺得太過攏長，
因此立刻去google尋找更佳解，
結果就找到了以下更漂亮簡短的解法！
參考：https://blog.vancel.in/leetcode-387-first-unique-character-in-a-string/


var firstUniqChar = function(s) {
for(let w of s){
if(s.indexOf(w) === s.lastIndexOf(w))
return s.indexOf(w);
}
return -1;
};

view raw

leetCode387v2.js

hosted with ❤ by GitHub

利用雙指標的思維

指標i由左邊開始確認，指標j由右邊開始確認，
分別i++ , j– , 直到相撞，
若相撞，表示兩邊出發都只有遇到同一個值，也就是唯一值。

左指標，利用indexOf()
The indexOf() method returns the index within the calling String object of the first occurrence of the specified value, starting the search at fromIndex. Returns -1 if the value is not found.
從左到右，直到找到第一個相符的字元

右指標，利用lastIndexOf()
The lastIndexOf() method returns the index within the calling String object of the last occurrence of the specified value, searching backwards from fromIndex. Returns -1 if the value is not found.
從左到右，直到找到最後一個相符的字元

參考：
https://blog.csdn.net/xiaobangsky/article/details/48313243

使用Javascript刷LeetCode – 657

Published on 由Sasa撰寫發表留言

657. Robot Return to Origin

題目：
There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.

Note: The way that the robot is “facing" is irrelevant. “R" will always make the robot move to the right once, “L" will always make it move left, etc. Also, assume that the magnitude of the robot’s movement is the same for each move.
先上解法：


/**
* @param {string} moves
* @return {boolean}
*/
var judgeCircle = function(moves) {
var x = 0 , y = 0;
var ary = moves.split('');
for(var i = 0; i< ary.length ; i++){
switch(ary[i]){
case 'R':
x += 1;
break;
case 'L':
x -= 1;
break;
case 'U':
y -= 1;
break;
case 'D':
y += 1;
break;
}
}
return (x == 0 && x === y) ? 1 : 0;
};

view raw

leetCode657.js

hosted with ❤ by GitHub

Note:

原本看到題目，講到x,y軸就直覺地使用了陣列來記憶位置，但後來看了其他人的解法，發現用兩個變數記錄即可，想想也是，用陣列有點太大材小用了。

看到python解寫到，return x==y==0
感覺很直觀，因此想要照用，結果不小心掉入js的隱型強制轉型(Implicit convert)的陷阱，卡了一下。
x==y 為true , typeof: boolean
true == 0 , true被強制轉型為1, 因此答案會是 1 == 0 為 false

參考：
https://stackoverflow.com/questions/22980471/how-does-a-b-c-comparison-work-in-javascript

https://ithelp.ithome.com.tw/articles/10201512

Javscript刷LeetCode – 709 , 相關：ASCII , Unicode

Published on 由Sasa撰寫發表留言

簡解：使用內建函式


var toLowerCase = function(str) {
return str.toLowerCase();
};

view raw

leetCode709v1.js

hosted with ❤ by GitHub

複雜解：不使用內建函式，利用字母的Unicode碼


var toLowerCase = function(str) {
var ary = str.split('');
for(var i = 0 ; i < ary.length ; i++){ if(ary[i] >= 'A' && ary[i] <= 'Z'){
var code = ary[i].<strong>charCodeAt</strong>(0) + 32;
ary[i] = String.<strong>fromCharCode</strong>(code);
}
}
var newStr = ary.join('');
return newStr;
};

view raw

leetCode709v2.js

hosted with ❤ by GitHub

//大小寫英文的code號碼相差32

ASCII ：
ASCII（American Standard Code for Information Interchange，美國訊息交換標準代碼）是一套基於英文字母的字符編碼系統。
最後一次更新為1986年。

Unicode :
Unicode（中文：萬國碼、國際碼、統一碼、單一碼）是電腦科學領域裡的一項業界標準。它對世界上大部分的文字系統進行了整理、編碼，使得電腦可以用更為簡單的方式來呈現和處理文字。
目前最新的版本為2019年5月公布的12.1.0

Unicode字元列表：
https://zh.wikipedia.org/wiki/Unicode%E5%AD%97%E7%AC%A6%E5%88%97%E8%A1%A8#%E6%8B%89%E4%B8%81%E5%AD%97%E6%AF%8D
包含並沿用ASCII列表

參考：
http://www.ruanyifeng.com/blog/2007/10/ascii_unicode_and_utf-8.html
前往 Medium.com 檢視