如果有喜歡我的文章歡迎關注
野生的前端工程師

30Day Leecodeing Callenge ,第一週挑戰 ！！

總結第一周的題目心得與解析,有兩個技巧

1.Hashmap

javascript 的 hashmap 就是應用Object的索引值存跨索引值得值

1.Single Number
6.Group Anagrams
7.Counting Elements

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

就是從陣列兩端開始走訪,直到兩端交錯。

可參考：
4.Move Zeroes

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

思維：
歸納出不快樂數比對輸入數字
判斷數字拆開相乘的數是不是快樂數,然後再判斷是否快樂。

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
};