11 - 算法 I - Githubissues

Linjiayu6 commented 4 years ago

1- 深度优先和广度优先搜索实现 TODO

题外话: React 和 Vue都是深度优先遍历
深拷贝和浅拷贝

Linjiayu6 commented 4 years ago

2- 扁平化 + 去重 + 排序 / 迭代实现扁平化

var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]

第一种实现

//  扁平化
let result = []
var flatten = array => {
  array.forEach((item) => {
    if (Object.prototype.toString.call(item) === '[object Array]') {
      flatten(item)
    } else {
      result.push(item)
    }
  })
  return result
}
var flat = flatten(arr)

/**
 * 去重 new Set, 转数组
 * 1. [... new Set([1, 2, 2]]
 * 2. Array.from(new Set([1, 2, 2]))
 */
var unique = [...new Set(flat)]
console.log(unique)

// 升序
result = unique.sort((a, b) => a - b)
console.log(result)

array.flat(Infinity) 拍平深度
new Set() 去重
Array.from 转为数组
sort((a, b) => a - b)排序

第二种实现 🔥🔥🔥🔥🔥

// Infinity 拍平深度
Array.from(new Set(arr.flat(Infinity))).sort((a, b) => a - b)

第三种实现 toString() 🔥🔥🔥🔥🔥

array.toString() 将数组变成string, 在字符串分割处理

"1,2,2,3,4,5,5,6,7,8,9,11,12,12,13,14,10"

[...new Set(arr.toString().split(',').sort((a, b) => a - b))].map(data => parseInt(data))

迭代方式扁平化

✨ arr.length > 0 这里总不注意

var arr = [1, 2, [3, 4, 5, [6, 7], 8], 9, 10, [11, [12, 13]]]
var result = []
while (arr && arr.length > 0) {
  var data = arr.shift()
  if (Array.isArray(data)) {
    arr = data.concat(arr)
  } else {
    result.push(data)
  }
}

console.log(result)

Linjiayu6 commented 4 years ago

3 - 合并处理

'A3'.indexOf('3')
'A3'.replace('3', '')

第一版


let a1 =  ['A1', 'A2', 'B1', 'B2', 'C1', 'C2', 'D1', 'D2']
let a2 = ['A', 'B', 'C', 'D'].map((item) => item + 3)
var result = a1.concat(a2).sort().map( => d.indexOf('3') > -1 ? d.replace('3', '') : d)

第二版

/**
 * 两个数组合并成一个数组
 * 请把两个数组 ['A1', 'A2', 'B1', 'B2', 'C1', 'C2', 'D1', 'D2'] 和 ['A', 'B', 'C', 'D']
 * 合并为 ['A1', 'A2', 'A', 'B1', 'B2', 'B', 'C1', 'C2', 'C', 'D1', 'D2', 'D']
 */

var arr1 = ["A1", "A2", "B1", "B2", "C1", "C2", "D1", "D2"]
var arr2 = ["A", "B", "C", "D"]

function merge () {
  // 先将所有的值后面加上 '3' 
  arr2.map(item => item + '3')
  // 两个数组合并, 排序, sort是按照 A, A1, A2, B, B1, ... 方式排序
  // 因为前面加上了'3',  A1, A2, A3, B1, ...
  var result = arr1.concat(arr2).sort().map(str => {
    if (str.indexOf('3') > -1) { // 'A3'.indexOf('3') replace掉
      str = str.replace('3', '')
    }
    return str
  })
  return result
}

merge()

Linjiayu6 commented 4 years ago

4- 输出 0-9 你能想到的方法异步值按照顺序输出?

for (var i = 0; i< 10; i++){ setTimeout(() => console.log(i) , 1000) }

本质: 异步流程，再执行i会丢失

1. setTimeout 第三个参数作为回调函数的参数传入

for (var i = 0; i< 10; i++) {
        // function (i)  不要忘记
    setTimeout(function (i) { console.log(i) }, 1000, i)
}

2. 绑定当前作用域, 将值传入

for (var i = 0; i< 10; i++) {
        const fn = function (i) { console.log(i) }
    setTimeout(fn.bind(Object.create(null), i), 1000)
}

3. IIFE 函数自己执行, 将值传入

for (var i = 0; i< 10; i++) {
   (function (i) {
    setTimeout(function () { console.log(i) }, 1000)
  })(i)
}

4. 利用 let 块级作用域

for (let i = 0; i< 10; i++) {
     setTimeout(() => console.log(i), 1000)
}

// 同上
for (let i = 0; i< 10; i++) {
  let _i = i
  setTimeout(() => console.log(_i), 1000)
}

Linjiayu6 commented 4 years ago

5 - 打印?

// 下面代码中 a 在什么情况下会打印 1？
var a = ?;
if(a == 1 && a == 2 && a == 3){
    console.log(1);
}

隐式转换, == 是toString方法的转换, 每次判断+1 就可以通过了。

var a = {
  i: 1,
  toString: function () { return a.i ++ }
}
if(a == 1 && a == 2 && a == 3){
    console.log(1);
}

Linjiayu6 commented 4 years ago

6 - 实现一个 sleep 函数

sleep(1000) 意味着等待1000毫秒

1. Promise 实现

2. 回调实现

function sleep (timer) {
  return new Promise(resolve => {
    setTimeout(() => {
      resolve(timer)
    }, timer)
  })
}

sleep(2000).then(timer => console.log(timer + ' success'))

// 2. 回调实现
function sleep (timer, cb) {
  setTimeout(() => {
    cb && cb(timer)
  }, timer)
}

sleep(1000, (timer) => console.log(timer + ' success'))

3. Generator

fn().next().value.then...

function* sleep (timer) {
  yield new Promise(resolve => setTimeout(() => {
    resolve(timer)
  }, timer))
}

sleep(2000)
.next().value // next执行, data.value 返回的是promise
.then(timer => console.log(timer + ' success'))

var g = sleep(2000)
g.next().value.then(console.log)

4. Async Await

async function sleep (timer) {
  let data = await new Promise(resolve => setTimeout(() => { resolve(timer) }, timer))
  console.log(data)
  return data // 必须用return 才能用then
}

sleep(2000)
.then(timer => console.log(timer + ' success'))

// 或者
var result = await sleep(2000)
console.log('result: ', result)

Linjiayu6 commented 4 years ago

7 - 实现 (5).add(3).minus(2) 功能

Number


Number.prototype.add = function (num) {
// console.log(this) // Number{5}
return this.valueOf() + num
}

Number.prototype.minus = function (num) { return this.valueOf() - num }

Linjiayu6 commented 4 years ago

8 - 冒泡 + 改进版本 ✨多练几遍 TODO


/**
 * 冒泡
 * [3, 4, 1, 2]
 * 每次把最大的值, 冒泡到最后面
 * 1. [3, 1, 2, 4]
 * 2. [1, 2, 3, 4]
 * 3. [1, 2, 3, 4]
 */
function bubbleSort (arr) {
  for (let i = 0; i < arr.length; i++) {
    let num = 0
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        num += 1
        var temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
    // 遍历一次没有再交换的则结束
    if (num === 0) {
      return arr
    }
  }
  return arr
}

bubbleSort([3, 4, 1, 2])

Linjiayu6 commented 4 years ago

9 - 某公司 1 到 12 月份的销售额存在一个对象里面 ✨ 没有一次过 TODO

Array.from({ length: 12 }) // 长度为12的数组, 值为 [undefined, undefined, undefined, ....]

Array.from({ length: 12 }).map((_, i) => obj[i + 1] || null)

/**
 * { 1:222, 2:123, 5:888}
 * 请把数据处理为如下结构: [222, 123, null, null, 888, null, null, null, null, null, null, null]
 */

var month = { 1:222, 2:123, 5:888}
var result = []
for (let i = 0; i < 12; i ++) {
  result.push(null)
}

Object.keys(month).forEach(item => result[item - 1] = month[item])

Linjiayu6 commented 4 years ago

10 - 要求设计 LazyMan 类 🔥🔥🔥🔥🔥

LazyMan('Tony').eat('lunch').sleep(10).eat('dinner');
LazyMan('Tony').eat('lunch').eat('dinner').sleepFirst(5).sleep(10).eat('junk food');
将所有事件串行起来, 通过this.next 来调用
队列的概念: shift() 移出去 unshift() 从头输入进去 http://muyiy.cn/question/program/56.html

思路:
任务有异步和同步, 任务如何串联起来执行?
xxx.xxxx.xxx 每个函数通过this返回, 将任务连接, 放到队列后
最后利用 宏队列或微队列特性, 滞后执行

// LazyMan('Tony');
// // Hi I am Tony

// LazyMan('Tony').sleep(10).eat('lunch');
// // Hi I am Tony
// // 等待了10秒...
// // I am eating lunch

// LazyMan('Tony').eat('lunch').sleep(10).eat('dinner');
// // Hi I am Tony
// // I am eating lunch
// // 等待了10秒...
// // I am eating diner

// LazyMan('Tony').eat('lunch').eat('dinner').sleepFirst(5).sleep(10).eat('junk food');
// // Hi I am Tony
// // 等待了5秒...
// // I am eating lunch
// // I am eating dinner
// // 等待了10秒...
// // I am eating junk food

class _LazyMan {
    constructor (name) {
        this.name = name
        this.queue = [] // 队列内容注册
        this._init()
        // 等到所有同步注册任务完事儿后, 我们再执行队列里的内容
        // 用宏任务 或 微任务处理
        Promise.resolve().then(() => this._next())
        // 或 setTimeout(() => this._next(), 0)
        return this
    }

    _init () {
        console.log('Hi I am ' + this.name)
    }

    eat (food) {
        const fn = () => {
            console.log('I am eating ' + food)
            this._next() // 执行下一个任务
        }
        this.queue.push(fn) // 先把任务放到队列里面, 等到所有注册完再去执行
        return this
    }

    // 异步任务的统一处理
    _async (delay) {
        return () => new Promise(resolve => {
            setTimeout(() => resolve(delay), delay * 1000)
        }).then(data => {
            console.log('等待了' + data + '秒')
            this._next() // 执行下一个任务
        })
    }

    // 异步的任务
    sleep (delay) {
        this.queue.push(this._async(delay))
        return this
    }

    // 该异步任务会插到最前面
    sleepFirst (delay) {
        this.queue.unshift(this._async(delay))
        return this
    }

    _next () {
        if (this.queue && this.queue.length > 0) {
            const task = this.queue.shift() // 从头移出来一个任务 执行
            task && task()
        }
    }

}

const LazyMan = (name) => new _LazyMan(name)
LazyMan('Tony').eat('lunch').eat('dinner').sleepFirst(5).sleep(10).eat('junk food');

Linjiayu6 commented 4 years ago

11 - 给定两个数组，写一个方法来计算它们的交集

[ ] 349. 两个数组的交集
[x] 350. 两个数组的交集 II

1. 数据字典 + 计数

// nums1 = [1, 2, 2, 1] nums2 = [2, 2] 返回 [2, 2]
function match (nums1, nums2) {
  var dictionary = {}
  for (let i = 0; i < nums1.length; i++) {
    if (dictionary[nums1[i]]) {
      dictionary[nums1[i]] += 1
    } else {
      dictionary[nums1[i]] = 1
    }
  }
  var result = []
  nums2.forEach(d => {
    if (dictionary[d] && dictionary[d] > 0) {
      result.push(d)
      dictionary[d] -= 1
    }
  })
  return result
}

match([1, 2, 2, 1, 2], [2, 2])

2. 匹配

function match (nums1, nums2) {
  var i = 0 // nums1
  var result = []
  while (i < nums1.length && nums2 && nums2.length > 0) {
    if (nums2.indexOf(nums1[i]) > -1) {
      nums2 = nums2.slice(nums2.indexOf(nums1[i]) + 1)
      result.push(nums1[i])
    }
    i += 1
  }
  return result
}

// 0.7.21 写的
function jiaoji(nums1, nums2) {
    var result = []
    while (nums2.length > 0) {
        var data = nums2.shift()
        if (nums1.indexOf(data) > - 1) {
            result.push(data)
            nums1.splice(nums1.indexOf(data), 1)
        }
    }
    return result
}

Linjiayu6 commented 4 years ago

12 - 如何设计实现无缝轮播 TODO

http://muyiy.cn/question/program/63.html

实现原理是 1 -> 2 -> 3 -> 4 在图像切换的时候, 切换到4, 后面没有元素的, 讲道理是1的现实。
通过赋值 1, 4的图片
4假 -> 真1 -> 2 -> 3 -> 真4 -> 1假
在 4 -> 1假 这种过度效果中, 做到无缝, 等到1浮现后, 再切换为真1

Linjiayu6 commented 4 years ago

13 - 随机数生成 + 排序 + 重组 + 顺序在一起 🔥

http://muyiy.cn/question/program/67.html

/**
 * 随机创建数组
 * 1. Array.from({ length: 个数 }): [undefined, undefined, ...]
 * 2. 随机数取整数 Math.floor(Math.random() * base) base = 100 基于0 - 100的随机数创建
 */
var createList = (length, base = 100) => Array.from({ length }).map(() => Math.floor((Math.random() * base)))

// 排序
var list = createList(10, 100).sort((a, b) => a - b)

// 去重
list = Array.from(new Set(list))

// 连着的放在一起
var sequence = list => {
    var result = []
    var temp = []
    list.forEach(d => {
        if (temp && temp.length === 0) {
            temp.push(d)
        } else {
            if (temp[temp.length - 1] + 1 === d) { // 如果连续就放到暂存栈中
               temp.push(d)
            } else {
                result.push(temp) // 不连续直接输出
                temp = [d]
            }
        }
    })
    result.push(temp)
    return result
}

Linjiayu6 commented 4 years ago

14 - 大小写转换 ✨ 没及时做出来 TODO

function fn (string) {
  let result = ''
  for (let i = 0; i < string.length; i++) {
    var s = string[i] 
    result += s === s.toUpperCase() ? s.toLowerCase() : s.toUpperCase()
  }
  return result
}

正则表达式

string.replace(/(\w)/g, (s) => s === s.toUpperCase() ? s.toLowerCase() : s.toUpperCase())

str.replace(/[a-zA-Z]/g, a => a.toUpperCase() === a ? a.toLowerCase() : a.toUpperCase())

Linjiayu6 commented 4 years ago

15 - 实现一个字符串匹配算法 🔥

从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置 http://muyiy.cn/question/program/71.html

1 - S.match(T) api方式match

'stringsubsss'.match('sub')
类数组 { 0: sub, index: 6 .... } index 第6个字符串开始是匹配的

function _match (S, T) {
    var index = S.match(T).index
    return index ? index : 0
}
_match('eabced', 'ed')

2 - S.search(T) const _math = (S, T) => S.search(T)

3. - indexOf('') + slice

function match(S, T) {
    if (S.length < T.length) return -1;
    if (S.indexOf(T[0]) < 0) return -1;
    var pos = S.indexOf(T[0]);
    return S.slice(pos, pos + T.length) === T ? pos : -1;
}

match('qasxffff', 'fff');

Linjiayu6 commented 4 years ago

16 - Proxy 实现简单的数据绑定 ✨多练习 TODO

- 问题在于: onclick ✨ 写不明白

<html>

<body>
  <div id="key">0</div>
  <!-- onclick="increase()" 这个地方竟然错了 -->
  <button onclick="increase()">increase</button>
  <button onclick="decrease()">decrease</button>

  <script>
    const data = { count: 0 }

    const proxy = new Proxy(data, {
      set: function (obj, property, value) {
        obj[property] = value
        console.log('set', obj)
        render(value)
      },

      get: function (obj, property) {
        return obj[property]
      }
    })

    function render (value) {
      document.getElementById('key').innerHTML = value
    }

    function increase () {
      proxy.count += 1
    }

    function decrease () {
      proxy.count -= 1
    }
  </script>
</body>
</html>

Linjiayu6 commented 4 years ago

17 - 算法题「旋转数组」

189. 旋转数组

1 - slice

// list.slice(0, key) 截取值是 0, 1, .... key - 1
var rotate = function(nums, k) {
    var len = nums.length
    if (len === 0 || len === 1 || k === 0) return nums
    k = k > len ? k : k % len
    nums = nums.slice(len - k).concat(nums.slice(0, len - k))
    return nums
};

2 - 原地不动交换类型

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    var len = nums.length
    if (len === 0 || len === 1 || k === 0) return nums
    k = k > len ? k : k % len

    // 原地不动类型
    for (let i = 0; i < k; i++) {
        // var data = nums.splice(len - 1, 1) // 这个ok, 但是会超时 从队尾删除
        var data = nums.pop() // 从队尾删除
        nums.unshift(data) // 从队头增加
    }

    return nums
};

Linjiayu6 commented 4 years ago

18 - 回文数判定打印出 1 - 10000 之间的所有对称数 TODO

http://muyiy.cn/question/program/81.html

1 - 回文判断

function match (base = 100) {
    let result = []
    for (let i = 1; i <= base; i++) {
        if (i < 10) continue
        let str = i.toString()
        let re_str = str.split('').reverse().join('') // 回文判断
        if (str === re_str) {
            result.push(i)
        }
    }
    return result
}

2 - 数学归纳

/**
 * 1. 个数肯定都是
 * 2. 十位数 11 的倍数
 * 3. 101, 111, 121 ...
 *    - 101 * i + n * 10 (n = 0 ~ 9)
 *    - 101 * 2 * i + n * 10
 * 
 * 4. 1001, 1111, 1221 ...
 *    - 1001 * i + n * 110
 *    - 1001 * 2 * i + n * 110
 */

function fn () {
    let result = []
    for (let i = 1; i < 10; i++) {
        result.push(i) // 1位数所有都是 
        result.push(i * 11) // 十位数 11倍数
        for (let j = 0; j < 10; j++) {
            result.push(i * 101 + j * 10)
            result.push(i * 1001 + j * 110)
        }
    }
    return result
}

fn()

Linjiayu6 commented 4 years ago

19 - 移动零 TODO

283. 移动零

测试用例注意[0, 0, 1]

var moveZeroes = function(nums) {
    var _len = nums.length
    if (_len === 0 || _len === 1) return nums

    var _zeronums = 0
    var i = 0
    while (i < _len - _zeronums) {
        if (nums[i] === 0) {
            nums.splice(i, 1)
            nums.push(0)
            _zeronums += 1
            // * 总错: i不会进位, 是根据当前位置再做判断 [0, 0, 1]
        } else {
            i += 1
        }
    }
    return nums
};

这么做就是错的一遍遍的错 ❌ 测试用例注意[0, 0, 1]

var swap = function (nums, i, j) {
    var temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

var moveZeroes = function(nums) {
    if (nums.length < 1) return nums
    var zeros = 0
    for (let i = 0; i < nums.length - zeros; i++) {
        if (nums[i] === 0) {
            for (let j = i; j < nums.length - 1 - zeros; j ++) {
                swap(nums, j, j + 1)
            }
            zeros += 1
        }
    }
    return nums
};

Linjiayu6 commented 4 years ago

20 -请实现一个 add 函数 🔥🔥🔥🔥🔥

http://muyiy.cn/question/program/84.html

1 - curry 实现 🔥🔥🔥🔥🔥 TODO

function add (...args1) {
    var store = args1
    function fn (...args2) {
        if (args2.length === 0) {
            return store.reduce((a, b) => a + b, 0)
        }
        store = store.concat(args2)
        return fn
    }
    return fn
}
add(1, 2, 3)()
add(1)(2)(3)()
add(1)(2, 3)()

2 - toString实现

/**
 *  add(1); // 1
    add(1)(2); // 3
    add(1)(2)(3); // 6
    add(1)(2, 3); // 6
    add(1, 2)(3); // 6
    add(1, 2, 3); // 6
 */

function add () {
    // 1. 对参数进行汇总入栈
    let params = Array.prototype.slice.call(arguments, 0)
    function addArgs (...args) {
        params = params.concat(args)
        return addArgs
    }
    // 2. 这里是重点 直接可以读到toString  转换方法
    addArgs.toString = () => params.reduce((a, b) => a + b, 0)
    return addArgs
}

Linjiayu6 commented 4 years ago

21 - 两数之和

1. 两数之和

👧 forEach是没有办法停止的, 就是不要用forEach

function add (arr, target) {
  var map = {}
  for (let i = 0; i < arr.length; i ++) {
    var data = arr[i]
    if (map[target - data]) {
      return [map[target - data], i]
    }
    map[data] = i
  }
  return []
}

Linjiayu6 commented 4 years ago

22 - 在输入框中如何判断输入的是一个正确的网址

直接 new URL(xxx) 判断

function isUrl (url) {
    try {
        new URL(url)
        return true
    } catch (error) {
        return false
    }
}

Linjiayu6 commented 4 years ago

23 - 把原始 list 转换成树形结构猿辅导挂的题 🔥🔥🔥🔥🔥 TODO

http://muyiy.cn/question/program/88.html

Linjiayu6 commented 4 years ago

24 - 实现模糊搜索结果的关键词高亮显示 TODO

http://muyiy.cn/question/program/90.html

Linjiayu6 commented 4 years ago

25 - 实现一个函数 fn 找出链条中所有的父级 id TODO

https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/143

Linjiayu6 commented 4 years ago

26 - 两个有序数组的中位数 TODO

http://muyiy.cn/question/program/93.html

Linjiayu6 commented 4 years ago

27 - 逆序还必须是递归方式 TODO

用 JavaScript 写一个函数，输入 int 型，返回整数逆序后的字符串。如：输入整型 1234，返回字符串“4321”。要求必须使用递归函数调用，不能用全局变量，输入函数必须只有一个参数传入，必须返回字符串

// 1234
function reverse(num) {
    let result = ''
    let string = num.toString() // 转为string
    if (string.length === 0 || string.length === 1) return string

    function fn (string, i) {
        if (i === -1) return result
        result += string[i]
        return fn(string, i - 1)
    }

    return fn(string, string.length - 1)
}

Linjiayu6 commented 4 years ago

28 - 修改以下 print 函数，使之输出 0 到 99，或者 99 到 0 TODO

*只能修改 setTimeout 到 Math.floor(Math.random() 1000 的代码**
Math.floor(Math.random() * 1000) 这里时间不同的, 如何输出的是 i 内容?

// 如何求解?
function print(n){
    setTimeout(() => {
      console.log(n);
    }, Math.floor(Math.random() * 1000));
}
for(var i = 0; i < 100; i++){
    print(i);
}

1 - 自执行, 不管异步 🔥

function print(n){
    // 自执行 (n => fn)(n)
    setTimeout(((n) => {
        console.log(n);
      })(n), Math.floor(Math.random() * 1000));
}
for(var i = 0; i < 100; i++){
    print(i);
}

2 - 时间都统一处理, 加个0

function print(n){
    setTimeout(() => {
      console.log(n);
    }, 0 * Math.floor(Math.random() * 1000));
}
for(var i = 0; i < 100; i++){
    print(i);
}

Linjiayu6 commented 4 years ago

29 - 不用加减乘除求7倍

http://muyiy.cn/question/program/102.html

左移运算 << 1
2 2 2 + 1

function seven (num) {
    let result = num
    // for (let i = 0; i < 3; i++) {
    //     result = result << 1
    // }
    result = result << 3
    return result - num
}

Linjiayu6 commented 4 years ago

30 - 模拟实现一个 localStorage

/**
 * getItem
 * setItem
 * clear
 * removeItem
 * key
 * length
 */
class LocalStorage {
  constructor () {
    this.LS = {}
  }
  getItem (key) {
    return this.LS[key] || null
  }
  setItem (key, value) {
    this.LS[key] = value
  }
  clear () {
    this.LS = {}
  }
  removeItem (key) {
    delete this.LS[key]
  }
  key () {
    return Object.keys(this.LS)
  }
  length () {
    return Object.keys(this.LS).length
  }
}

// 挂在到 window下
window.LS = new LocalStorage()

LS.setItem('a', { a : 1})
LS.getItem('a')
LS.setItem('b', { b : 1})
LS.setItem('a', document.body)
LS.getItem('a')
LS.length()
LS.key()
LS.clear()

Linjiayu6 commented 4 years ago

31 - 模拟实现一个 localStorage & 过期时间

new Date().valueOf() 当前时间
Date.now() 当前时间

/**
 * new Date() Wed Jul 15 2020 10:37:16 GMT+0800 (China Standard Time)
 * new Date().valueOf() 当前时间 1594780608433
 * Date.now() 当前时间 1594780615144
 */

class LS {
  constructor () {
    this.cache = new Map() // key, value
    this.date = new Map() // key, date 当超过时间, 则清除 cache里内容
  }

  setItem (key, value, time) {
    this.date.set(key, time)
    this.cache.set(key, value)
    console.log(this.date)
    console.log(this.cache)
  }

  getItem (key) {
    this.check(key)
    return this.cache.get(key) || - 1
  }

  delete (key) {
    this.cache.delete(key)
  }

  check (key) {
    // 时间验证
    if (this.date.has(key)) {
      // 时间存进去是 number类型
      if (Date.now() > this.date.get(key)) {
        this.cache.delete(key)
        this.date.delete(key)
        return false // 已经删除
      }
      return true // 可以继续用
    }
    return false
  }

  clear () {
    this.cache.clear()
    this.date.clear()
  }
}

window.cache = new LS()
window.cache.setItem('a', 'aaaaa', Date.now() + 10000) // 当前时间加上10s后过期
window.cache.getItem('a') // 当前时间加上10s后过期

Linjiayu6 commented 4 years ago

32 - 获取地址栏查询参数方式

1. 又臭又长版本

function fn (url) {
  var params = url.split('?')[1]
  if (params) {
    params = params.split('&')
    var result = ''
    for (let i = 0; i < params.length; i ++) {
      if (params[i].indexOf('elective') > -1) {
        result = params[i]
        break
      }
    }
    result = result.split('=')[1]
    return result ? result.split(',') : []
  }
  return []
}

fn('https://www.xx.cn/api?keyword=&level1=&local_batch_id=&elective=&local_province_id=33')

2. new URL() 获取

function fn (url, key) {
  // search: ?keyword=&level1=&local_batch_id=&elective=800,700&local_province_id=33
  // searchParams.get(key) 获取
  return new URL(url).searchParams.get(key) // 800,700
}

fn('https://www.xx.cn/api?keyword=&level1=&local_batch_id=&elective=800,700&local_province_id=33', 'elective')

3. 正则表达 🔥🔥🔥🔥🔥

var str = 'https://www.baidu.com/auth?a=1&bizId=310015,7801&b=3'
// 目标所有参数匹配: 前可能有?(匹配)=(匹配)后可能有&
var pattern = /\??(\w+)=(\w+)\$?/g
str.match(pattern) // ["?a=1", "bizId=310015", "b=3"]

// 模式匹配 (字母数字 多次)=(字母数字 多次) 但是没有匹配到, 内容
var pattern = /(\w+)=(\w+)/g
str.match(pattern) // ["a=1", "bizId=310015", "b=3"]

var pattern = /(\w+)=(\w+)(,\w+)?/g
str.match(pattern) // ["a=1", "bizId=310015,7801", "b=3"]

var pattern = /(bizId)=(\w+)(,\w+)?/g
str.match(pattern) // ["bizId=310015,7801"]

function fn () {
  var str = 'https://www.xx.cn/api?keyword=&level1=&local_batch_id=&elective=800,700&local_province_id=33'
  var pattern = /elective=(\w*)(,\w+)?/g
  var data = str.match(pattern) // ["elective="] ["elective=800"] ["elective=800,700"]
  if (data) {
    return data[0].split('=')[1].split(',')
  }
  return []
}

Linjiayu6 commented 4 years ago

33 - 考虑到性能问题，如何快速从一个巨大的数组中随机获取部分元素

http://muyiy.cn/question/program/107.html

Linjiayu6 commented 4 years ago

34 - 输入 '1, 2, 3, 5, 7, 8, 10'

// 输出 '1~3, 5, 7~8, 10'

function fn(str) {
  // 输入 '1, 2, 3, 5, 7, 8, 10'
  // 输出 '1~3, 5, 7~8, 10'
  var arr = str.split(',').map(d => Number(d)).sort((a, b) => a - b);
  var result = [];
  var j = 0;
  // 这里是等于, 总错
  for (let i = 1; i <= arr.length; i++) {
    if (arr[i] !== arr[i - 1] + 1) {
      if (i - 1 === j) {
        result.push(arr[j].toString());
      } else {
        result.push(arr[j] + '~' + arr[i - 1]);
      }
      j = i;
    }
  }
  return result;
}
fn('1, 2, 3, 5, 7, 8, 10');

Linjiayu6 commented 4 years ago

35 - 形式转换

var entry = {
  a: {
    b: {
      c: {
        dd: 'abcdd'
      }
    },
    d: {
      xx: 'adxx'
    },
    e: 'ae'
  }
}

// 要求转换成如下对象
var output = {
  'a.b.c.dd': 'abcdd',
  'a.d.xx': 'adxx',
  'a.e': 'ae'
}

function fn (entry, prefix = '', result = {}) {
  Object.keys(entry).forEach(id => {
    var data = entry[id]
    prefix = prefix ? prefix + '.' + id : id
    // 类型判断
    if (Object.prototype.toString.call(data) === '[object Object]') {
      fn(data, prefix, result)
    } else {
      result[prefix] = data
    }
  })
  return result
}

fn(entry)

Linjiayu6 commented 4 years ago

36 - 形式转换 II

http://muyiy.cn/question/program/112.html

Linjiayu6 commented 4 years ago

37 - 有基本类型和引用类型的数组去重


// [123, "meili", "123", "mogu", 123] => [123, "meili", "123", "mogu"]
// [123, [1, 2, 3], [1, "2", 3], [1, 2, 3], "meili"] => [123, [1, 2, 3], [1, "2", 3], "meili"]
// [123, {a: 1}, {a: {b: 1}}, {a: "1"}, {a: {b: 1}}, "meili"] => [123, {a: 1}, {a: {b: 1}}, {a: "1"}, "meili"]

function fn (list) {
  var map = new Map()
  // 基本类型过滤掉
  list = [...new Set(list)]

  // 引用类型过滤
  /**
   * JSON.stringify([1, "2", 3]) => "[1,"2",3]"
   * JSON.stringify([1, 2, 3]) => "[1,2,3]"
   */
  list.forEach(value => {
    var key = JSON.stringify(value)
    if (!map.has(key)) {
      map.set(key, value)
    }
  })
  // 转为数组类型
  return [...map.values()]
} 
function fn (list) {
  var map = new Map()
  // 基本类型过滤掉
  list = [...new Set(list)]

  // 引用类型过滤
  /**
   * JSON.stringify([1, "2", 3]) => "[1,"2",3]"
   * JSON.stringify([1, 2, 3]) => "[1,2,3]"
   */
  list.forEach(value => {
    var key = JSON.stringify(value)
    if (!map.has(key)) {
      map.set(key, value)
    }
  })
  // 转为数组类型
  return [...map.values()]
}

Linjiayu6 commented 4 years ago

38 - 找出字符串中连续出现最多的字符和个数

1- 硬写模式

// 'abcaakjbb' => { 'a': 2, 'b': 2 }
// 'abbkejsbcccwqaa' => { 'c': 3 }

/**
 * i, j 指针
 * i和j值相同, 则i不动, 继续 j += 1
 * i和j值不同, 则 j - i 数量返回, i = j, j += 1
 */
function fn (str) {
  var map = new Map()
  var i = 0, j = 1
  var _max = 0 // 暂存最大值

  while (i < str.length && j <= str.length) {
    if (str[i] === str[j]) {
      j += 1
    } else {
      var val = str[i]
      if (map.has(val)) {
        map.set(val, Math.max(map.get(val), j - i))
      } else {
        map.set(val, j - i)
      }
      _max = Math.max(_max, map.get(val))
      i = j
      j += 1
    }
  }

  // 在map基础上 选最大值
  var result = {}
  var values = [...map.values()]
  var keys = [...map.keys()]

  values.forEach((val, i) => {
    if (val === _max) {
      result[keys[i]] = val
    }
  });
  return result
}

fn('abcaakjbb')
fn('abbkejsbcccwqaa')

2 - 正则模式

// 概念
/**
 * 输出: ["a", "b", "c", "a", "11", "aaaa", "k", "j", "bbbbb"]
 * (\w) 所有字符和数组类型, ()代表分组概念
 * \1 代表括号内容匹配, 匹配重现
 * 
 * 该正则 找连续重复
 */
var str = 'abca11aaaakjbbbbb'
str.match(/(\w)\1*/g)

var str1 = 'abacabcxjabc'
str1.match(/(abc)\1*/g) // ["abc", "abc"]

function fn (str) {
  // 字符串连续匹配 ["a", "b", "c", "a", "11", "aaaa", "k", "j", "bbbbb"]
  var arr = str.match(/(\w)\1*/g)
  var arrLen = [] // 每个字符串的长度
  var _maxLen = 0 // 最大长度

  arr.forEach(item => {
    arrLen.push(item.length)
    _maxLen = Math.max(_maxLen, item.length)
  })

  var result = {}
  arrLen.forEach((value, index) => {
    if (value === _maxLen) { result[arr[index][0]] = value }
  })
  return result
}
fn('abbkejsbcccwqaa')

Linjiayu6 commented 4 years ago

39 - 统计 1 ~ n 整数中出现 1 的次数

Linjiayu6 commented 4 years ago

40 - 重复数组转树

Linjiayu6 commented 4 years ago

41 - 扑克牌摆放顺序问题

/**
 * 有一堆扑克牌，将牌堆第一张放到桌子上，再将接下来的牌堆的第一张放到牌底，如此往复；
 * 最后桌子上的牌顺序为： (牌底) 1,2,3,4,5,6,7,8,9,10,11,12,13 (牌顶)；
 * 问：原来那堆牌的顺序，用函数实现
 * 
 * a, b, c, d
 * [a] 单数是 pop
 * [b, a] 双数是 shift
 * [b, a, c] 单数是 pop [c, d]
 * [d, b, a, c] 双数是 shift [d]
 * 倒着推理
 */

// 恢复原来顺序
function reverseToNormal (pocker) {
  var result = []
  while (pocker && pocker.length > 0) {
    var data = null
    if (pocker.length % 2 === 1) { // 奇数
      data = pocker.pop() // 从尾出栈
    } else {
      data = pocker.shift() // 从头出栈
    }
    result.unshift(data)
  }

  // 结果 [7, 6, 8, 5, 9, 4, 10, 3, 11, 2, 12, 1, 13]
  return result
}

reverseToNormal([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13])

/**
 * [a, b, c, d]
 * [], 偶数 => [a]
 * [a], 奇数 => [b, a] unshift(data)
 * [b, a], 偶数 => [b, a, c] push(data)
 * [b, a, c], 奇数 => [d, b, a, c] unshift(data)
 */
function toReverse (pocker) {
  var result = []
  pocker.forEach(data => {
    if (result.length % 2 === 1) { // 奇数
      result.unshift(data)
    } else {
      result.push(data)
    }
  })
  return result
}

toReverse([7, 6, 8, 5, 9, 4, 10, 3, 11, 2, 12, 1, 13])

Linjiayu6 commented 4 years ago

42 - 实现一个 Dialog 类，Dialog可以创建 dialog 对话框，对话框支持可拖拽

Linjiayu6 commented 4 years ago

43 - 用 setTimeout 实现 setInterval，阐述实现的效果与 setInterval 的差异

Linjiayu6 commented 4 years ago

44 - 求两个日期中间的有效日期

Linjiayu6 commented 4 years ago

45 - 颜色排序

/**
 * 在一个字符串数组中有红、黄、蓝三种颜色的球，且个数不相等、顺序不一致，请为该数组排序。
 * 使得排序后数组中球的顺序为:黄、红、蓝。
 * 例如：红蓝蓝黄红黄蓝红红黄红，排序后为：黄黄黄红红红红红蓝蓝蓝
 * 
 * 1. 分桶, 得出每个颜色的内容
 * 2. 桶拼接
 */

// 方案 1
function fn (str) {
  var yellow = [], red = [], blue = []
  for (var i = 0; i < str.length; i++) {
    var data = str[i]
    if (data === '黄') yellow.push(data)
    if (data === '红') red.push(data)
    if (data === '蓝') blue.push(data)
  }
  return yellow.concat(red).concat(blue).join('')
}
fn('红蓝蓝黄红黄蓝红红黄红')

// 方案 2
function fn (str) {
  var yellow = 0, red = 0, blue = 0
  for (var i = 0; i < str.length; i++) {
    var data = str[i]
    if (data === '黄') yellow += 1
    if (data === '红') red += 1
    if (data === '蓝') blue += 1
  }
  // '黄'.repeat(3) = '黄黄黄'
  return '黄'.repeat(yellow) + '红'.repeat(red) + '蓝'.repeat(blue)
}
fn('红蓝蓝黄红黄蓝红红黄红')

// 方案 3
function fn (str) {
  var rule = { '黄': 0, '红': 1, '蓝': 2 }
  // 值小的, 在前面
  return str.split('').sort((a, b) => rule[a] - rule[b]).join('')
}
fn('红蓝蓝黄红黄蓝红红黄红')

Linjiayu6 commented 4 years ago

46 - 链表反转

https://github.com/Linjiayu6/LeetCode/issues/5#issuecomment-660602195

Linjiayu6 commented 4 years ago

47 - 求多个数组之间的交集

1 - reduce

function intersection(...args) {
    // 前面 & 后面 => 新前面(交集) => 新前面 & 后面 => ...
    var result = [...args].reduce((prev, curr) => {
        // 前面根据后面内容, filter保留下来交集内容
        return prev.filter(d => curr.includes(d));
    });
    return [...new Set(result)];
}

intersection([2, 1, 2], [1, 2, 3], [2, 5, 6, 6, 3]); 
intersection([2, 10, 1], [1, 2, 3], [2, 5, 6, 6, 3], [10, 1]);

2 - 不用reduce

function intersection(...args) {
    var result = [...new Set(args[0])];
    for (let i = 1; i < args.length; i++) {
        // result = [1, 2, 3] args[i] = [2, 2, 1] => result 为 [2, 1]
        result = result.filter(data => args[i].includes(data));
    }
    return result;
}

Linjiayu6 commented 4 years ago

48 - 将 '10000000000' 形式的字符串，以每 3 位进行分隔展示 '10.000.000.000' TODO

1 - 字符串匹配

// 将 '10000000000' 形式的字符串，以每 3 位进行分隔展示 '10.000.000.000'
function fn(str) {
    var arr = str.split('').reverse(); // 逆着来
    var i = 0;
    var result = [];
    while (i < arr.length) {
        result.push(arr.slice(i, i + 3).reverse().join(''));
        i += 3;
    }
    return result.reverse().join('.');
}
fn('101000000304');

Linjiayu6 commented 4 years ago

49 - 手写二进制转 Base64（阿里）

Linjiayu6 commented 4 years ago

50 - 二分查找如何定位左边界和右边界

Linjiayu6 commented 4 years ago

51 - 用最简洁代码实现 indexOf 方法

1. match

function _indexOf(S, T) {
    return S.match(T) ? S.match(T).index : -1;
}
_indexOf('abcdesadfafa', '123')
_indexOf('abcdesadfafa', 'desa')
_indexOf('abcdesadfafa', 'ff')

2. slice

function _indexOf(S, T) {
    for (let i = 0; i < S.length; i++) {
        let j = 0;
        if (S[i] === T[j]) {
            if (S.slice(i, i + T.length) === T) return i;
        }
    }
    return -1;
}

3. 基础实现

// arr 或 长string, matchstr, startIndex从指定索引开始, 默认为0
function indexOf (arr, matchstr, startIndex = 0) {
  if (startIndex < 0) return -1
  if (startIndex >= arr.length) return -1

  for (var i = startIndex; i < arr.length; i++) {
    if (arr[i] === matchstr) return i
  }
  return -1
}

_indexOf('stest', 'st'); _indexOf('stest', 'es'); _indexOf('stest', 'tex');

Linjiayu6 / FE-Notes

11 - 算法 I #11

1- 深度优先和广度优先搜索实现 TODO

2- 扁平化 + 去重 + 排序 / 迭代实现扁平化

迭代方式扁平化

✨ arr.length > 0 这里总不注意

3 - 合并处理

4- 输出 0-9 你能想到的方法 异步值按照顺序输出?

5 - 打印?

6 - 实现一个 sleep 函数

1. Promise 实现

2. 回调实现

3. Generator

4. Async Await

7 - 实现 (5).add(3).minus(2) 功能

8 - 冒泡 + 改进版本 ✨多练几遍 TODO

9 - 某公司 1 到 12 月份的销售额存在一个对象里面 ✨ 没有一次过 TODO

10 - 要求设计 LazyMan 类 🔥🔥🔥🔥🔥

11 - 给定两个数组，写一个方法来计算它们的交集

12 - 如何设计实现无缝轮播 TODO

13 - 随机数生成 + 排序 + 重组 + 顺序在一起 🔥

14 - 大小写转换 ✨ 没及时做出来 TODO

15 - 实现一个字符串匹配算法 🔥

16 - Proxy 实现简单的数据绑定 ✨多练习 TODO

17 - 算法题「旋转数组」

1 - slice

2 - 原地不动交换类型

18 - 回文数判定 打印出 1 - 10000 之间的所有对称数 TODO

1 - 回文判断

2 - 数学归纳

19 - 移动零 TODO

这么做 就是错的 一遍遍的错 ❌ 测试用例注意[0, 0, 1]

20 -请实现一个 add 函数 🔥🔥🔥🔥🔥

1 - curry 实现 🔥🔥🔥🔥🔥 TODO

2 - toString实现

21 - 两数之和

22 - 在输入框中如何判断输入的是一个正确的网址

23 - 把原始 list 转换成树形结构 猿辅导挂的题 🔥🔥🔥🔥🔥 TODO

24 - 实现模糊搜索结果的关键词高亮显示 TODO

25 - 实现一个函数 fn 找出链条中所有的父级 id TODO

26 - 两个有序数组的中位数 TODO

27 - 逆序 还必须是递归方式 TODO

28 - 修改以下 print 函数，使之输出 0 到 99，或者 99 到 0 TODO

1 - 自执行, 不管异步 🔥

2 - 时间都统一处理, 加个0

29 - 不用加减乘除 求7倍

30 - 模拟实现一个 localStorage

31 - 模拟实现一个 localStorage & 过期时间

32 - 获取地址栏查询参数方式

33 - 考虑到性能问题，如何快速从一个巨大的数组中随机获取部分元素

34 - 输入 '1, 2, 3, 5, 7, 8, 10'

35 - 形式转换

36 - 形式转换 II

37 - 有基本类型和引用类型的数组去重

38 - 找出字符串中连续出现最多的字符和个数

39 - 统计 1 ~ n 整数中出现 1 的次数

40 - 重复数组转树

41 - 扑克牌 摆放顺序问题

42 - 实现一个 Dialog 类，Dialog可以创建 dialog 对话框，对话框支持可拖拽

43 - 用 setTimeout 实现 setInterval，阐述实现的效果与 setInterval 的差异

44 - 求两个日期中间的有效日期

45 - 颜色排序

46 - 链表反转

47 - 求多个数组之间的交集

48 - 将 '10000000000' 形式的字符串，以每 3 位进行分隔展示 '10.000.000.000' TODO

49 - 手写二进制转 Base64（阿里）

50 - 二分查找如何定位左边界和右边界

51 - 用最简洁代码实现 indexOf 方法

4- 输出 0-9 你能想到的方法异步值按照顺序输出?

18 - 回文数判定打印出 1 - 10000 之间的所有对称数 TODO

这么做就是错的一遍遍的错 ❌ 测试用例注意[0, 0, 1]

23 - 把原始 list 转换成树形结构猿辅导挂的题 🔥🔥🔥🔥🔥 TODO

27 - 逆序还必须是递归方式 TODO

29 - 不用加减乘除求7倍

41 - 扑克牌摆放顺序问题