# [Array&Hashing] Boison Solution Note
---
## Array&Hashing Easy(7/7)
歸納方法論在 [LeeCode: Array 類型筆記 (Easy)](./LeeCode%3A%20Array%20%E9%A1%9E%E5%9E%8B%E7%AD%86%E8%A8%98%20(Easy)%2047c98687-3a1a-42d4-88fc-5442457a7871.md "LeeCode: Array 類型筆記 (Easy)")
### 1. [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/)
```bash
// 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](https://leetcode.com/problems/missing-number/)
```javascript
// 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](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/)
```javascript
// 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](https://leetcode.com/problems/single-number/)
```javascript
// 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](https://leetcode.com/problems/convert-1d-array-into-2d-array/)
```javascript
// 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](https://leetcode.com/problems/valid-anagram/)**
```javascript
// 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](https://leetcode.com/problems/two-sum/)
```javascript
// 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 ](https://leetcode.com/problems/group-anagrams/)
```javascript
// 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](https://leetcode.com/problems/top-k-frequent-elements/)**
```javascript
// 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](https://leetcode.com/problems/product-of-array-except-self/)**
```javascript
// 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](https://leetcode.com/problems/longest-consecutive-sequence/)**
```javascript
// 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](https://leetcode.cn/problems/decode-string/submissions/)
```javascript
// 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 的不滿都說出來](https://yakimhsu.com/project/project_w3_Javasciprt_NaN.html)
`NaN` : 全名為 Not a Number ，屬於全域物件，代表不是數字
```javascript
isNaN('3') // false
isNaN( 3 ) // false
isNaN('s') // true
```
Sign in with Wallet
Connect another wallet