[Array&Hashing] Boison Solution Note

---

Array&Hashing Easy(7/7)

歸納方法論在 LeeCode: Array 類型筆記 (Easy)

1. Contains Duplicate

//  BEST
function hasDuplicates(nums) {
    return new Set(nums).size !== nums.length
}

//  EASY O(N^2)
function hasDuplicates(nums) {
    return nums.some(x => nums.indexOf(x) !== nums.lastIndexOf(x))
}

//  EASY
function hasDuplicates(nums) {
    var keep = []
    for(var i in nums){
        if(keep.indexOf(nums[i])<0){
            keep.push(nums[i])
        } else {
            return true
        }
    }
    return false
}

2. Missing Number

// EASY
var missingNumber = function(nums) {
  for(let i = 0; i <= nums.length; i++){
     if(!nums.some(x => x === i)){
       return i
     }
  }
}


// BEST
var missingNumber = function(nums) {
    let sum = 0;
    for(let i=0;i<nums.length;i++){
        sum += i+1-nums[i]
    }
    return sum;
}

3. Find All Numbers Disappeared in an Array

// EASY TC:O(N^2) SC:O(N)
var findDisappearedNumbers = function(nums) {
  const arr = []
  for(let i = 1; i <= nums.length; i++){
     if(!nums.some(x => x === i)){
       arr.push(i)
     }
  }
    return arr
}

// GOOD  TC:O(N) SC:O(N)
var findDisappearedNumbers = function(nums) {
  const set = new Set();
  for (let i = 0; i < nums.length; i++) {
    set.add(i + 1);
  }
  for (const num of nums) {
    set.delete(num)
  }
  return [...set]
}

// BEST  TC:O(N) SC:O(N)
var findDisappearedNumbers = function(nums) {
    let resultArr = [];
    for(let i = 0; i < nums.length; i++) {
        let idx = Math.abs(nums[i]) - 1;        
        if(nums[idx] > 0) {
            nums[idx] = -nums[idx];
        }
    }
    
    for(let j = 0; j < nums.length; j++) {
        if(nums[j] > 0) {
            resultArr.push(j+1);
        }
    }
    return resultArr
}

有重複一個數字，就代表有少，重複的數字的位置就是少的那個數字

{{video https://www.youtube.com/watch?v=4eVksgi9vIc&t=327s}}

4. Single Number

// EASY TC:O(N^2) SC:O(1)
var singleNumber = function(nums) {
    for(let i of nums){
        if(nums.indexOf(i) === nums.lastIndexOf(i)){
          return i
        }
    }
}

// GOOD TC:O(N) SC:O(N)
var singleNumber = function(nums) {
    let set = new Set(nums)
    let sum = 0
    for (i of set){
      sum += i
    }
    sum = sum * 2
    for (j of nums){
      sum -= j
    }
    return sum 
}

// BEST
var singleNumber = function(nums) {
    let singleEl = nums[0];
    for (let i = 1; i < nums.length; i++) {
        singleEl ^= nums[i];
    }
    return singleEl;
}

XOR 位元運算子

5. Convert 1D Array Into 2D Array

// EASY
var construct2DArray = function(original, m, n) {
    if(original.length !== m*n) return []
    let arr = []
    while(m){
        while(arr.length !== n){
            arr.push(original[0])
            original.shift(original[0])   
        }
        original.push(arr)
        arr = []
        m--
    }
    return original
}

// BEST
var construct2DArray = function(original, m, n) {
    const arr = []
    let nextIdx = 0
    if(m*n !== original.length) return arr
    for(let i = 0; i < m; i++) {
        arr.push(original.slice(nextIdx, nextIdx+n));
        nextIdx += n;
    }
    return arr;
}

6. 242. Valid Anagram

// EASY TC:O(N) SC:O(1)
var isAnagram = function(s, t) {
    if(s.length !== t.length) return false  
    let note = {}    
    for(element of s){
        if(note[element] === undefined){
            note[element] = 1            
        } else {
            note[element] += 1
        }
    }    
    for(element of t){
        if(note[element] === 0 || note[element] === undefined) return false        
        note[element] -= 1
    } 
    return true
}

// BEST TC:O(N) SC:O(1)
var isAnagram = function(s, t) {
    let alpha = new Array(26).fill(0)
    for (let i = 0; i < s.length; i++) {
        alpha[s.charCodeAt(i) - 97]++
    }
    for (let i = 0; i < t.length; i++) {
        alpha[t.charCodeAt(i) - 97]--
    }
    return alpha.every(i => i === 0)
};

// BEST TC:O(N) SC:O(1)
const CHARS_NUMBER = 256
var isAnagram = function(s, t) {
    if (s.length !== t.length) return false
    const charCount1 = new Array(CHARS_NUMBER).fill(0);
    const charCount2 = new Array(CHARS_NUMBER).fill(0);
    for (let i = 0; i < s.length; i++) {
      const code1 = s.charCodeAt(i)
      const code2 = t.charCodeAt(i)
      charCount1[code1]++
      charCount2[code2]++
    }
    for (let i = 0; i < charCount1.length; i++) {
    	if (charCount1[i] !== charCount2[i]) return false;
    }
    return true
}

// BEST TC:O(N) SC:O(1)
var isAnagram = function(s, t) {
    if(s.length !== t.length) return false;
    const map1 = new Map()
    const map2 = new Map()
    s.split('').forEach((c)=>{
      map1[c] =  map1[c] + 1 || 1; 
    }) 
    t.split('').forEach((c)=>{
      map2[c] =  map2[c] + 1 || 1; 
    })
    for(let item in map1){
        if(map1[item] !== map2[item]) return false;
    }
    return true
}


// BEST TC:O(N) SC:O(1)
var isAnagram = function(s, t) {
    if(s.length !== t.length) return false
    const map = new Map()
    s.split('').forEach((c)=>{
      map[c] =  map[c] + 1 || 1
    }) 
    for(item of t){
        if(!(map[item] > 0)) return false
        map[item] -= 1
    }
    return true
}

// BEST TC:O(N) SC:O(1)
var isAnagram = function(s, t) {
    if(s.length !== t.length) return false
    const map = new Map()
    s.split('').forEach((c)=>{
      map[c] =  map[c] + 1 || 1
    }) 
    for(item of t){
        if(!(map[item] > 0)) return false
        map[item] -= 1
    }
    return true
}

7. Two Sum

// EASY TC:O(N^2) SC:O(1)
var twoSum = function(nums, target){
    for(let i=0;i<=nums.length-1;i++){
        for(let j=1+i;j<=nums.length-1;j++){
            if(nums[i]+nums[j] === target) return [i,j] 
        }
    }
}

// BEST TC:O(N) SC:O(N)
function twoSum(nums, target){
    let lookup = {}
    for(let i = 0; i < nums.length; i++) {
        let difference = target - nums[i]
        if(lookup[difference] || lookup[difference] === 0) return [lookup[difference], i]
        lookup[nums[i]] = i
    }
}

// BEST TC:O(N) SC:O(N)
var twoSum = function(nums, target) {
    let lookup = {}
    for(let i = 0; i < nums.length; i++) {
        let difference = target - nums[i]
        if(lookup[difference] !== undefined) return [lookup[difference], i]
        lookup[nums[i]] = i
    }
}

// BEST TC:O(N) SC:O(N)
var twoSum = function(nums, target) {
    let lookup = {}
    for(let i = 0; i < nums.length; i++) {
        let difference = target - nums[i]
        if(lookup[difference] >= 0) return [lookup[difference], i]
        lookup[nums[i]] = i
    }
}

---

Array&Hashing Medium(5/5)

1. 49. Group Anagrams

// BEST/EASY
var groupAnagrams = function(strs) {
  let hashTable = {}, str = ''
  for (var i = 0; i < strs.length; i++) {
    str = strs[i].split('').sort().join('')
    if (!hashTable[str]) hashTable[str] = []
    hashTable[str].push(strs[i])
  }
  return Object.values(hashTable)
}

// BEST
var groupAnagrams = function(strs) {
  const map = new Map()  
  for (let str of strs) {
    const key = shuffle(str)
    if (!map.has(key)) map.set(key, [])
    map.get(key).push(str)
  }
  return Array.from(map.values())
}

const shuffle = (str) => {
  const arr = new Array(26).fill(0)  
  for (let char of str) {
    const curr = char.charCodeAt() - 'a'.charCodeAt()
    arr[curr]++
  }  
  return arr.join('-')
}

// BEST 
var groupAnagrams = function(strs) {
  const hashTable = {}
  for (let str of strs) {
    const key = shuffle(str)
    if (!hashTable[key]) {
      hashTable[key] = [str];
    } else {
      hashTable[key].push(str);
    }
  }
  return Object.values(hashTable)
}

const shuffle = (str) => {
  const arr = new Array(26).fill(0)  
  for (let char of str) {
    const curr = char.charCodeAt() - 'a'.charCodeAt()
    arr[curr]++
  }  
  return arr.join('-')
}

2. 347. Top K Frequent Elements

// EASY
function getKeyByValue(object, value) {
  return Object.keys(object).find(key => object[key] === value);
}

var topKFrequent = function(nums, k) {
    const map = {}
    let value = [], arr = []
    for(num of nums){
        map[num] =  map[num] + 1 || 1; 
    }
    value = Object.values(map)
    for(let i=1;i<=k;i++) {
        arr.push(getKeyByValue(map, Math.max(...Object.values(map))))
        map[getKeyByValue(map, Math.max(...Object.values(map)))] = 0
    }
    return arr
}

// BEST
    let res = [], map = new Map()
    nums.forEach(n => map.set(n, map.get(n) + 1 || 1))
    let sortedArray = [...map.entries()].sort((a, b) => b[1] - a[1])
    for(let i = 0; i < k; i++) {
        res.push(sortedArray[i][0])
    }
    return res

3. 238. Product of Array Except Self

// BEST
var productExceptSelf = function(nums) {
  let product = 1, result = []
  for (let i=0;i<=nums.length-1;i++) {
    result[i] = product
    product *= nums[i]
  }
  product = 1
  for (let i=nums.length-1;i>=0;i--) {
    result[i] *= product
    product *= nums[i]
  }  
  return result
}
productExceptSelf([1,2,3,4])  //  [24,12,8,6]

/*
[1,          2,          3,           4          ]

左邊往右生長最多到   nums[length - 2]:3   留一個空缺
[1,          1*1,        1*1*2,       1*1*2*3    ] 
右邊往左生長最多到   nums[1]         :2   留一個空缺
[1*4*3*2,    1*4*3       1*4,         1          ] 

[1*1*4*3*2,  1*1*1*4*3,  1*1*2*1*4,   1*1*2*3*1  ]
[24,         12,         8,           6          ]
*/

4. 128. Longest Consecutive Sequence

// EASY&BEST
var longestConsecutive = function(nums) {
  if(nums.length === 0) return 0
  if(nums.length === 1) return 1
  nums = nums.sort((a, b) => a-b)
  let len = 1, lenArr = []  
  for(let i=1;i<=nums.length-1;i++) {
    if(nums[i] === nums[i-1]+1){
      len++
      if(i === nums.length-1) lenArr.push(len)
    } else if (nums[i] !== nums[i-1]) {
      lenArr.push(len)
      len = 1
    } else if (nums[i] === nums[i-1]) {
      if(i === nums.length-1) lenArr.push(len)
    }
  }
  return Math.max(...lenArr)
}


// GOOD&BEST
var longestConsecutive = function(nums) {
   let max = 0
   nums = new Set(nums)
   for (let num of nums) {
      let big = num
      let small = num
      while (nums.delete(big + 1)) big++
      while (nums.delete(small - 1)) small--
      const diff = big - small + 1
      if (max < diff) max = diff
   }
   return max
}

longestConsecutive([2, 1, 5, 0,-3, 3, -2])

/*
big 和 small 每次同時記錄起始位置
一個往上走，一個往下走，最後紀錄兩者差距


[-3, -2, 0, 1, 2, 3, 5]
[0, 1, 2, 3]
4

[-3, -2, 0, 1, 2, 3, 5]
big=-3,  small=-3,  max=0
[-3, 0, 1, 2, 3, 5]
big=-2,  small=-3,  max=0
[-3, 0, 1, 2, 3, 5]
big=-2,  small=-3,  max=0,    diff=1
[-3, 0, 1, 2, 3, 5]
big=-2,  small=-3,  max=1,    diff=1
[-3, 0, 1, 3, 2, 5]
big=0,   small=0,   max=1,    diff=1
[-3, 0, 3, 2, 5] ←
big=1,   small=0,   max=1,    diff=1
[-3, 0, 3, 5] ←
big=2,   small=0,   max=1,    diff=1
[-3, 0, 5] ←
big=3,   small=0,   max=1,    diff=1
[-3, 0, 5]
big=3,   small=0,   max=1,    diff=4
[-3, 0, 5]
big=3,   small=0,   max=4,    diff=4
[-3, 0, 5]
big=5,   small=5,   max=4,    diff=1
*/

5. Encode and Decode Strings

// BEST
var decodeString = function(s) {
    let mulStack = [], strStack = [], num = 0, res = ''
    for (const c of s) {   
        if (!isNaN(c)) {  
            num = num * 10 + (c - '0')
        } else if (c == '[') {  
            strStack.push(res)
            mulStack.push(num) 
            res = '' 
            num = 0
        } else if (c == ']') {  
            res = strStack.pop() + res.repeat(mulStack.pop())
        } else {                   
            res += c
        }
    }
    return res;
}

decodeString('2[a]3[b4[c]]e')

/*
e
ce
cccce
bcccce
bccccbccccbcccce
abccccbccccbcccce
aabccccbccccbcccce

     ,mulStack=[   ],strStack=[        ],num=0,res=''
c='2',mulStack=[   ],strStack=[        ],num=2,res=''
c='[',mulStack=[2  ],strStack=[        ],num=0,res=''
c='a',mulStack=[2  ],strStack=[        ],num=0,res='a'
c=']',mulStack=[   ],strStack=[        ],num=0,res='aa'
c='3',mulStack=[   ],strStack=[        ],num=3,res='aa'
c='[',mulStack=[3  ],strStack=['aa'    ],num=0,res=''
c='b',mulStack=[3  ],strStack=['aa'    ],num=0,res='b'
c='4',mulStack=[3  ],strStack=['aa'    ],num=4,res='b'
c='[',mulStack=[3,4],strStack=['aa','b'],num=0,res=''
c='c',mulStack=[3,4],strStack=['aa','b'],num=0,res='c'
c=']',mulStack=[3  ],strStack=['aa'    ],num=0,res='bcccc'
c=']',mulStack=[   ],strStack=[        ],num=0,res='aabccccbccccbcccc'
c='e',mulStack=[   ],strStack=[        ],num=0,res='aabccccbccccbcccce'
*/

[第三週] JavaScript - 把你對 isNaN 的不滿都說出來

NaN : 全名為 Not a Number ，屬於全域物件，代表不是數字

isNaN('3')   // false
isNaN( 3 )   // false
isNaN('s')   // true