30Day LeetCoding Callenge — Week1
30-Day Leecodeing Callenge ,第一週挑戰 ！！
藉由此活動，我想更深入去瞭解JavaScript的演算法思維，目標是訓練出腦海中能觀想出演算法模型。
總結這週的技巧，有兩個值得注意的演算法。
1.Hashmap
javascript 的 hashmap 就是應用Object的索引值存跨索引值得值
可參考
大致觀念是這樣：
let arr = ['a','b','c']
let hashmap = {}
for(let i = 0; i < arr.length ; i++){
if(arr[i] = 'a') arr[arr[i]] = 1
}
// hashmap = { {'a': 1} }
2.two pointers
就是從陣列兩端開始走訪,直到兩端交錯
可參考：
GreeksforGreeks — Two Pointers Technique
let i = 0
let j = arr.length
while(i < j){
if(condition){
dosomething
}
i++
j--
}
題目
1.Single Number
說明：找出陣列中不重複的數字
Example 1:
Input: [2,2,1] Output: 1
Example 2:
Input: [4,1,2,1,2] Output: 4
思維：
我的解法是先累計每個數字的數目，然後再找數目唯一的數字
先用Object 紀錄最後再轉Array 處理，算是蠻常用到的技巧
Answer:
var singleNumber = function(nums) {
let temp = {}
nums.map(num => {
if(!temp[num]){
temp[num] = 1
}else{
temp[num] +=1
}
})
return Object.keys(temp).find(key => 1 === temp[key])
};
2. Happy Number
說明：判斷是否為快樂數
Example:
Input: 19 Output: true Explanation: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
思維：
- 歸納出不快樂數比對輸入數字
- 判斷數字拆開相乘的數是不是快樂數,然後回到1.判斷是否快樂
Answer：
var isHappy = function(n) {
let answer = false
let notHappy = [4,,16,37,58,89,145,42,20]
let num = n
while(notHappy.indexOf(num) === -1){
if(num ===1){
answer = true
break
}else{
let list = num.toString().split("")
let sum = 0
let newNum = list.map((a)=>{
return sum += Math.pow(a,2)
})
num = sum
}
}
return answer
};
3.Maximum Subarray
說明：找出陣列中連續加總最大和
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
思維：
這題目有點抽象,首先先找出最大值,然後加總為負數則設為0
我後來想想如果最大和是負數該怎麼辦？如果是這樣的話那最大值應該就是最大和了，
所以小於0就等於0比較像是連續陣列的斷點，用這樣想比較好懂
Answer：
var maxSubArray = function(nums) {
let max = Math.max(...nums)
let num = 0
for(let i = 0 ; i < nums.length ; i++){
num += nums[i]
if(num > max) max = num
if(num < 0) num = 0
}
return max
};
4.Move Zeroes
說明：把所有0移到最後面
Example:
Input: [0,1,0,3,12] Output: [1,3,12,0,0]
思維：
題目有提示適合用two pointer , two pointer 是簡單好用的演算法
看題目就可以知道,這個演算法就是從兩頭開始比對直到交錯為止,
陣列右邊(尾端)是放0得地方,所以遇到0就向左走
陣列左邊(頭端)是移動0的地方,所以用splice(i,1)切掉0,在push(0)
Answer：
var moveZeroes = function(nums) {
let i = 0
let j = nums.length - 1
while(i < j ){
if(nums[j] === 0) j--
if(nums[i] === 0) {
nums.splice(i,1)
nums.push(0)
}else{
i++
}
}
};
5.Best Time to Buy and Sell Stock II
說明：股票陣列中找出最大收益和
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
思維：
這題沒有很複雜,題目有說明都是單次交易所以只要當天比隔天還低就是賺
Answer：
var maxProfit = function(prices) {
let i = 0
let j = prices.length
let sumProfit = 0
while(i < j-1 ){
let profit = 0
if(prices[i] < prices[i+1] ){
profit = prices[i+1]- prices[i]
}
sumProfit += profit
i++
}
return sumProfit
};
6.Group Anagrams
說明：找出字母一樣的單字並分類
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
思維：
這題難在於輸入跟輸出的陣列是非對稱的,所以有時要嘗試 hashmap
string.split(‘’).sort()則是用來判斷是否同類
Answer:
var groupAnagrams = function(strs) {
let hash = {
}
strs.map(s =>{
let temp = ""
let math = s.split('').sort()
if(temp !== math) temp = math
if(temp === math){
if(hash[math]){
hash[math].push(s)
}else{
hash[math] = [s]
}
}
})
return (Object.values(hash))
};
7.Counting Elements
說明：計算陣列中存在 n+1 的數。
Example 1:
Input: arr = [1,2,3] Output: 2 Explanation: 1 and 2 are counted cause 2 and 3 are in arr.
Example 2:
Input: arr = [1,1,3,3,5,5,7,7] Output: 0 Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.
Example 3:
Input: arr = [1,3,2,3,5,0] Output: 3 Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.
Example 4:
Input: arr = [1,1,2,2] Output: 2 Explanation: Two 1s are counted cause 2 is in arr.
思維：hashmap的變形應用
- 找出有沒有n+1的數,並累計有幾個
- 再找一次陣列中的值有幾個符合n+1
- 累加hashmap裡面符合n+1的數量
Answer：
var countElements = function(arr) {
let hash = {}
arr.map(num => {
if(!hash[num +1 ]){
hash[num +1 ] = 1
} else{
hash[num +1 ] += 1
}
})
let index = Object.keys(hash).filter((h,i) =>{
return arr.some(a =>{
return a == h
})
})
let answer = 0
index.map((i) =>{
answer += hash[i]
})
return answer
};