metroluffy / fe-learning Goto Github PK

View Code? Open in Web Editor NEW

16.0 4.0 1.0 153 KB

前端基础知识点以及经验整理

leetcode leetcode-solutions leetcode-javascript javascript interview interview-questions frontend

fe-learning's Issues

剑指offer —— 青蛙跳台阶问题

点击查看原文
 点击查看原题

题目

一只青蛙一次可以跳上$1$级台阶，也可以跳上$2$级台阶。求该青蛙跳上一个 $n$级的台阶总共有多少种跳法。

答案需要取模 $1e9+7$（$1000000007$），如计算初始结果为：$1000000008$，请返回 $1$。

提示：$n$ 的取值为 $[0, 100]$

解题思路

令 $n$ 级台阶的跳法为 $Sn$，
当 $n$ 为 $0$ 时，$S\mathop{{}}\nolimits_{{0}} = 1$
当 $n$ 为 $1$ 时，$S\mathop{{}}\nolimits_{{1}} = 1$
当 $n$ 为 $2$ 时，$S\mathop{{}}\nolimits_{{2}} = 2$
当 $n$ 为 $3$ 时，$S\mathop{{}}\nolimits_{{3}} = 3$
当 $n$ 为 $4$ 时，$S\mathop{{}}\nolimits_{{4}} = 5$
...
当台阶数为 $n$ 时，$S\mathop{{}}\nolimits_{{n}}=S\mathop{{}}\nolimits_{{n - 1}}+S\mathop{{}}\nolimits_{{n-2}}\text{（}n \ge 2\text{）}
$

第一版代码

根据上面推出的状态转移方程，我们很容易写出如下代码

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    if (n === 0 || n === 1) {
        return 1
    }
    const mod = 1000000007
    const res = [1, 1]
    for (let i = 2; i <= n; i++) {
        res[i] = (res[i - 1] + res[i - 2]) % mod
    }
    return res[n]
};

优化代码

在上面的代码中我们发现，res[i] 取决于 res[i - 1] 和 res[i - 2]，所以我们大可不必使用数组，直接改用三个变量也能将代码实现：

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    if (n === 0 || n === 1) {
        return 1
    }
    const mod = 1000000007
    let first = 1
    let second = 1
    let res = 0
    for (let i = 2; i <= n; i++) {
        res = (first + second) % mod
        first = second
        second = res
    }
    return res
};

哨兵节点的应用-从移除链表元素说起

移除链表元素

题目

203. 移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

题解

问题看起来很简单，可以如此考虑：

选择要删除节点的前一个结点 prev
将 prev 的 next 设置为要删除结点的 next 即可

实现如下：

var removeElements = function(head, val) {
    let curr = head;
    while (curr !== null) {
      let temp = curr
      curr = curr.next;
      if (curr && curr.val === val) temp.next = curr.next;
    }
    return head
};
/**
* input: [1,2,6,3,4,5,6], 6
* output: [1,2,3,4,5] // pass
*
* // 待删除元素在表头的情况
* input: [6,1,2,3,4,5,6], 6
* output: [6,1,2,3,4,5] // failed
*
* // 待删除元素重复的情况
* input: [1,2,3,6,6,4,5,6], 6
* output: [1,2,3,6,4,5] // failed
*/

可以看到当元素在链表中间仅出现一次时，以上代码运行良好，但是面对待删除元素在表头或者重复出现时，就搞不定了。因为我们要选中待删除节点的前一个节点来完成删除，从而忽略了当前节点。你也可以画图分析一下原因。

那么解决思路就是保存前一个节点的引用，同时判断当前节点是否待删除即可。如何做？增加一个哨兵节点。这里所谓的哨兵节点，其实就是给链表增加一个伪头，让一个指针指向它，然后随当前指针一起遍历。

LeetCode官方题解：哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    let sentinel = new ListNode(-1);
    sentinel.next = head;
    let prev = sentinel, curr = head;
    while (curr !== null) {
      if (curr.val === val) prev.next = curr.next;
      else prev = curr;
      curr = curr.next;
    }
    return sentinel.next
};

更详细的题解（带图）：移除链表元素-LeetCode官方题解

题目

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

解题思路

暴力法

直接将数字转成二进制格式，然后计算 $1$ 的个数。
PS：String 的 toString 方法可以转换进制，利用这点我们少写点代码……

代码

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    const str = n.toString(2)
    const N = str.length
    let res = 0
    for (let i = 0; i < N; i++) {
        if (str[i] == 1) {
            res++
        }
    }
    return res
}

位运算

以输入的数字是 $9$ 为例子（二进制为 1001），每次与 $1$ 进行按位与运算，如果结果为 $1$ 说明最低位为 $1$，否则为 $0$；每次做完按位与运算就将数字右移，直到数字为0为止。

代码

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let res = 0
    while (n) {
        if (n & 1) {
            res++
        }
        n >>= 1
    }
    return res
};

实现Promise.all及finally

实现Promise.all

也算是常备知识点，理解这几个常用API的概念。

Promise.all

Promise.all(iterable) 方法返回一个 Promise 实例，此实例在 iterable 参数内所有的 promise 都“完成（resolved）”或参数中不包含 promise 时回调完成（resolve）；如果参数中 promise 有一个失败（rejected），此实例回调失败（reject），失败的原因是第一个失败 promise 的结果。

Promise._all = (iterable) => {
  return new Promise(function(resolve, reject) {
    if (!Array.isArray(iterable)) {
      return reject(new TypeError('arguments must be an array'));
    }
    var resolvedCounter = 0;
    var remaining = iterable.length;
    var resolvedValues = new Array(remaining);
    for (var i = 0; i < remaining; i++) {
      (function(i) {
        Promise.resolve(iterable[i]).then(function(value) {
          resolvedCounter++
          resolvedValues[i] = value
          if (resolvedCounter == remaining) {
            return resolve(resolvedValues)
          }
        }, function(reason) {
          return reject(reason)
        })
      })(i)
    }
  })
}

多提一嘴 Promise.allSettled，它会返回一个在所有给定的 promise 已被决议或被拒绝后决议的
promise ，并带有一个对象数组，每个对象表示对应的 promise 结果。通俗点，相较于 all，他会等所有的任务跑完才返回，即便某个任务失败。

Promise.race

Promise.race(iterable) 方法返回一个 promise，一旦迭代器中的某个 promise 解决或拒绝，返回的 promise 就会解决或拒绝。

Promise._race = (iterable)=>{
  return new Promise((resolve, reject) => {
    for (const p of iterable) {
      Promise.resolve(p).then(resolve).catch(reject)
    }
  })
}

Promise.finally

finally() 方法返回一个 Promise。在 promise 结束时，无论结果是 fulfilled 或者是 rejected，都会执行指定的回调函数。这为在 Promise 是否成功完成后都需要执行的代码提供了一种方式。

这避免了同样的语句需要在 then() 和 catch() 中各写一次的情况。

Promise.prototype._finally = function (callback) {
  var constructor = this.constructor;
  return this.then(
    function(value) {
      // @ts-ignore
      return constructor.resolve(callback()).then(function() {
        return value;
      });
    },
    function(reason) {
      // @ts-ignore
      return constructor.resolve(callback()).then(function() {
        // @ts-ignore
        return constructor.reject(reason);
      });
    }
  );
};

用箭头函数美化一下：

Promise.prototype._finally = function (callback) {
  let constructor = this.constructor;
  return this.then(
    value  => constructor.resolve(callback()).then(() => value),
    reason => constructor.resolve(callback()).then(() => constructor.reject(reason))
  );
};

参考文档

微信面试题 LazyMan

要求实现一个函数，需要满足以下功能

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.sleepTime = 0
        this.sleepFirstTime = 0
        this.taskList = []
        console.log(`Hi I am ${this.name}`);
        setTimeout(() => {
            this.next()
        }, 0)
    }
    next() {
        var fn = this.taskList.shift();
        fn && fn();
    }
    eat (f) {
        var that = this;
        var fn = (function (n) {
            return function () {
                console.log(`I am eating ${n}`)
                that.next();
            }
        })(name);
        this.taskList.push(fn);
        return this;
    }
    sleep (time) {
        var that = this;
        var fn = (function (t) {
            return function () {
                setTimeout(() => {
                    console.log(`等待了${t}秒...`)
                    that.next();
                }, t * 1000);  
            }
        })(time);
        this.taskList.push(fn);
        return this;
    }
    sleepFirst(time) {
        var that = this;
        var fn = (function (t) {
            return function () {
                setTimeout(() => {
                    console.log(`等待了${t}秒...`)
                    that.next();
                }, t * 1000);  
            }
        })(time);
        this.taskList.unshift(fn);
        return this;
    }
}
function LazyMan(name) {
    return new LazyManClass(name);
}

剑指offer —— 重建二叉树

点击查看原文
 点击查看原题

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

解题思路

前序遍历：每次先遍历二叉树的根节点，然后再分别遍历二叉树的左右子树
中序遍历：每次先遍历二叉树的左子树，然后再遍历根节点，最后遍历右子树

结合以上特点，preorder 数组中的第一个值 val 为二叉树的根节点。与之对应的是，我们需要找到 val 在 inorder 数组中的位置 inorderIndex，其中 $[0, inorderIndex - 1]$ 之间的数字分布在左子树，$[inorderIndex + 1, N]$ 之间的数字在右子树；当然，我们还需要找到 preorder 数组中的所有关于左子树的值的分布和所有关于右子树的值的分布，其中 $[1, left + 1]$ 之间的数字分布在左子树，$[right, N]$ 之间的数字分布在右子树。
对于以上推论，我们只要递归的进行下去，这颗树就能被完整的构建出来了。

代码

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (!preorder.length || !inorder.length) {
        return null
    }
    // 根节点的值为 preoder[0]
    const root = new TreeNode(preorder[0])
    // 找到根节点的值在 inorder 中的位置
    // 我们借此来划分 inorder 中分布在左右子树的值
    const inorderIndex = inorder.indexOf(preorder[0])
    // 找到 inorder 中左右子树的边界的值
    // 当然在 preorder 中它们对应左右子树的边界
    // 我们借此来划分 preoder 中分布在左右子树的值
    const left = preorder.indexOf(inorder[inorderIndex - 1])
    const right = preorder.indexOf(inorder[inorderIndex - 1]) + 1
    // 递归构建左右子树
    root.left = buildTree(preorder.slice(1, left + 1), inorder.slice(0, inorderIndex))
    root.right = buildTree(preorder.slice(right), inorder.slice(inorderIndex + 1))
    // 返回结果
    return root
};

N 数之和系列解题模板

解题套路：

直接用哈希表来找（只适合两数之和）
先排序，然后固定首个数字，剩下的交给双指针来找

哈希表解「两数之和」

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

暴力解法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let res = []
    let N = nums.length
    for (let i = 0; i < N; i++) {
        for (let j = i + 1; j < N; j++) {
            if (nums[i] + nums[j] === target) {
              	return [i, j]
            }
        }
    }
    return []
};

时间复杂度：$O(n^2)$
空间复杂度：$O(1)$

显而易见，我们还能再优化一下。

哈希表解法

直接将 num 和对应的下标存到 哈希表 里面，遍历一次 nums，我们只要在 哈希表 里找到 target - num 即可。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map()
    nums.forEach((num, index) => {
      	map.set(num, index)
    })
    nums.forEach((num, index) => {
        let val = target - num
        if (map.has(val)) {
            return [index, map.get(val)]
        }
    })
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

哈希表解法优化

上面我们遍历了两次 nums，其实也可以只遍历一次。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    nums.forEach((num, index) => {
      let val = target - num
      if (map.has(val)) {
      		return [index, map.get(val)]
      }
      map.set(val, index)
    })
  	return []
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

双指针解三（三或三以上）数之和

题目

参考上面的「两数之和」，这里不再赘述。

解法

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums, target) {
    let res = []
    let N = nums.length
    nums.sort((a, b) => a - b)
    for (let i = 0; i < N; i++) {
        // 跳过重复的元素
        if (nums[i] === nums[i - 1]) {
            continue
        }
        let left = i + 1
        let right = N - 1
        // 找到 nums[i] + nums[left] + nums[right] === 0
        // 将结果加到 res 中
        // 过程注意剔除重复的数字
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right]
            if (sum === target) {
                res.push([nums[i], nums[left], nums[right]])
                while (left < right && nums[left] === nums[left + 1]) {
                    left++
                }
                while (left < right && nums[right] === nums[right - 1]) {
                    right--
                }
                left++
                right--
            } else if (sum < target) {
                left++
            } else {
                right--
            }
        }
    }
    return res
};

四数之和

「四数之和」解法如下（跟上面的思路是一样的，只不过是多了一个循环，这里不再注释）：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
  let res = []
  let N = nums.length
  nums.sort((a, b) => a - b)
  for (let i = 0; i < N; i++) {
    if (nums[i] === nums[i - 1]) {
      continue
    }
    for (let j = i + 1; j < N; j++) {
      if (nums[j] === nums[j - 1]) {
        continue
      }
      let left = j + 1
      let right = N - 1
      while (left < right) {
        let sum = nums[i] + nums[j] + nums[left] + nums[right]
        if (sum === target) {
          res.push([nums[i], nums[j], nums[left], nums[right]])
          while (left < right && nums[left] === nums[left + 1]) {
            left++
          }
          while (left < right && nums[right] === nums[right - 1]) {
            right--
          }
          left++
          right--
        } else if (sum < target) {
          left++
        } else {
          right--
        }
      }
    }
  }
}

那么对于 $N$ 数之和，我们只要利用一下 DFS 就可以解决了，参考以下代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var nSum = function(nums, target) {
    const helper = (index, N, temp) => {
        // 如果下标越界了或者 N < 3 就没有必要在接着走下去了
        if (index === len || N < 3) {
            return
        }
        for (let i = index; i < len; i++) {
            // 剔除重复的元素
            if (i > index && nums[i] === nums[i - 1]) {
                continue
            }
            // 如果 N > 3 的话就接着递归
            // 并且在递归结束之后也不走下边的逻辑
            // 注意这里不能用 return
            // 否则循环便不能跑完整
            if (N > 3) {
                helper(i + 1, N - 1, [nums[i], ...temp])
                continue
            }
            // 当走到这里的时候，相当于在求「三数之和」了
            // temp 数组在这里只是把前面递归加入的数组算进来
            let left = i + 1
            let right = len - 1
            while (left < right) {
                let sum = nums[i] + nums[left] + nums[right] + temp.reduce((prev, curr) => prev + curr)
                if (sum === target) {
                    res.push([...temp, nums[i], nums[left], nums[right]])
                    while (left < right && nums[left] === nums[left + 1]) {
                        left++
                    }
                    while (left < right && nums[right] === nums[right - 1]) {
                        right--
                    }
                    left++
                    right--
                } else if (sum < target) {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    let res = []
    let len = nums.length
    nums.sort((a, b) => a - b)
    helper(0, 4, [])
    return res
};

总而言之，要点是：先排序，然后把循环降低到两个之后，利用双指针来找最后两个值。

将数字转换为人民币单位格式

请根据面向对象编程的**，设计一个类型 Cash用于表达人民币，使得：

class Cash {
}
const cash1 = new Cash(105)
const cash2 = new Cash(66)
const cash3 = cash1.add(cash2)
const cash4 = Cash.add(cash1, cash2)
const cash5 = new Cash(cash1 + cash2)

console.log(`${cash3}`, `${cash4}`, `${cash5}`)
// 1元7角1分 1元7角1分 1元7角1分

实现Lodash函数系列（一）：_.get

题目

/**
 * object (Object): 要检索的对象。
 * path (string): 要获取属性的路径。
 * [defaultValue] (*): 如果解析值是 undefined ，这值会被返回。
 */
function _get(object, path, default) {

}

实现类似 lodash 的 get 函数，根据 object对象的path路径获取值。如果解析 value 是 undefined 会以 defaultValue 取代。

示例：

const object = { 'a': [{ 'b': { 'c': 3 } }] };

_get(object, 'a[0].b.c');
// => 3

_get(object, 'a.b.c', 'default');
// => 'default'

实现

function _get (source, path, defaultValue = undefined) {
  // 将数组格式的路径转化成dot格式的，再拆分成key数组
  // a[0].b -> a.0.b -> ['a', '0', 'b']
  const paths = path.replace(/\[(\d+)\]/g, '.$1').split('.')
  let result = source
  for (const p of paths) {
    result = Object(result)[p] // null 与 undefined 取属性会报错, 用Object包装一下
    // if (result === undefined) {
    //    return defaultValue
    // }
  }
  return result || defaultValue
}

参考文档

如何实现类似 lodash 的 get

手写eventbus

eventbus实际上就是一个发布订阅模式、也用到了闭包，在回答类似问题的时候都可以提及

class Eventbus {
    constructor () {
        this.eventbus = {}
    }
    /**
     * 事件发布
     * @param {*} name 事件名字
     * @param {*} slef 自身作用域
     * @param {*} cb 回掉函数
     */
    $on(name,slef,cb) {
        let tuple = [slef,cb]
        if (Object.prototype.hasOwnProperty.call(this.eventbus, name)){
            this.eventbus[name].push(tuple)
        } else {
            this.eventbus[name] = [tuple]
        }
    }
    /**
     * 触发事件
     * @param {*} name 事件名字
     * @param {*} data 数据
     */
    $emit(name,data) {
        if (Object.prototype.hasOwnProperty.call(this.eventbus, name)) {
            let cbs = this.eventbus[name]
            // console.log(this.eventbus)
            cbs.map(item=>{
                let [slef, cb] = [item[0], item[1]]
                cb.call(slef, data)
            })
        }
    }

    /**
     * 取消事件
     * @param {*} name 事件名字
     * @param {*} fn 取消事件的回调
     */
    $off(name, fn) {
        if (Object.prototype.hasOwnProperty.call(this.eventbus, name)) {
            fn()
            delete this.eventbus[name]
        } 
    }

    /**
     * 当前事件被触发后只执行一次
     * @param {*} name 
     * @param {*} slef 
     * @param {*} fn 
     */
    $once(name, slef,fn) {
        let that = this
        function onceOn (data){
            fn.call(slef,data)
            console.log(that.eventbus[name])
            that.eventbus[name] = that.eventbus[name].filter(item=>{
                return item[0] !== slef  
            })
        }
        this.$on(name, slef, onceOn)
    }
}

实现字符串反转

题目

实现一个字符串反转：输入：www.toutiao.com.cn 输出：cn.com.toutiao.www

要求：1.不使用字符串处理函数 2.空间复杂度尽可能小

实现

要实现字符串反转，应用双指针前后交换位置即可，这里需要注意字符串是基本类型，需要先转换成字符数组，反转后再拼接回去即可。

// 方法一, 不合题意，却可以大致整理出思路

function _swap(s) {
    return s.split('.').reverse().join('.')
}

// swap('www.toutiao.com.cn')
// "cn.com.toutiao.www"

// 分别实现上述函数

function split(s, op='') {
    let sa = [], ss = ''
    for(let si = 0; si < s.length; si++){
        if(s[si] === op){
            sa.push(ss);ss = ''
        } else {
            ss+= s[si]
        }
    }
    if(ss) sa.push(ss)
    return sa
}

function join(sa, op=',') {
    let s = '', l = 0
    while(l < sa.length) {
        s += sa[l] + (l == sa.length - 1 ? '' : op)
        l++
    }
    return s
}

function swap(s){
    if(!s) return ''
    s = split(s,'.')
    let i = 0, j = s.length - 1;
    while(i < j) {
        let t = s[i]
        s[i] = s[j]
        s[j] = t
        i++;
        j--;
    }
    return join(s, '.')
}

// swap('www.toutiao.com.cn')
// "cn.com.toutiao.www"

你也可以考虑在单次遍历中实现，空间复杂度应该差不多。

关于async和await的“同步”

题目

要求看代码写输出。

function wait(){
  return new Promise(resolve =>
    setTimeout(resolve, 10*1000)
  )
}
async function func1() {
  console.time('time-func1')
  const x = await wait()
  const y = await wait()
  const z = await wait()
  console.timeEnd('time-func1')
}
async function func2() {
  console.time('time-func2')
  const x = wait()
  const y = wait()
  const z = wait()
  await x
  await y
  await z
  console.timeEnd('time-func2')
}
func1()
func2()

/** 输出如下
 * time-func2：10002.4ms
 * time-func1: 32261.5ms
 */

解析

async、await语法糖让我们可以把Promise的异步回调处理写出“同步”的方式，即代码看起来是同步并且整洁很多，但其目的是简化使用多个 promise 时的同步行为，并非是真同步。

await 表达式会暂停当前 async function 的执行，等待 Promise 处理完成。若 Promise 正常处理(fulfilled)，其回调的resolve函数参数作为 await 表达式的值，继续执行 async function。

如此相邻的两个 await wait() 会形成继发关系（串行）。要写成并发方式，~~可以如 func2函数所示用变量先缓存Promise，再一起执行~~，或者你也可以使用 Promise.all / Promise.allSettled，没有依赖关系的函数最好让它们同时触发。

注意：Promise.all 有短路效应，如果参数中 promise 有一个失败（rejected），此实例回调失败（reject），失败的原因是第一个失败 promise 的结果。

async function func3() {
  console.time('time-func3')
  await Promise.all([wait(),wait(),wait()])
  console.timeEnd('time-func3')
}
func3()
// time-func3: 10455.867919921875ms

更多请参见: MDN-async function

CSS绘制常见的图形

利用border相关属性。

三角形

.triangle {
    width: 0;
    height: 0;
    border-right: 50px solid transparent;
    border-top: 50px solid blue;
    border-left: 50px solid transparent;
}

梯形

.trapezoid {
  width:100px;
  height:0;
  border-right: 50px solid transparent;
  border-bottom: 50px solid blue;
  border-left: 50px solid transparent;
}

扇形

其实就是三角形加了一个border-radius:50%

.sector {
    width: 0;
    height: 0;
    border-right: 50px solid transparent;
    border-top: 50px solid blue;
    border-left: 50px solid transparent;
    border-radius: 50%;
}

箭头

如代码，就是两个三角形叠起来，再用定位做个offset（控制线的粗细），方向还是border相关属性控制的。

.arrow{
    position:relative;
}
/*黑色三角形   */
.arrow:before{
    content: "";
    display: block;
    position: absolute;
    top: 50%;
    right: 0;
    width: 0;
    height: 0;
    border:10px solid;
    border-color: transparent transparent transparent #000;
}
/*背景色三角形*/
.arrow:after{
    content: "";
    display: block;
    position: absolute;
    top: 50%;
    right: 1px;
    width: 0;
    height: 0;
    border:10px solid;
    border-color: transparent transparent transparent #fff;
}

椭圆

.oval {
    width: 200px;
    height: 100px;
    background: red;
    -moz-border-radius: 100px / 50px;
    -webkit-border-radius: 100px / 50px;
    border-radius: 100px / 50px;
}

树形数据结构扁平化

编写两个函数，实现如下两个数据结构互相转换

const data = {
  a: {
    b: {
      c: {
        dd: 'abcdd'
      }
    },
    d: {
      xx: 'adxx'
    },
    e: 'ae'
  }
}
const output = {
  'a.b.c.dd': 'abcdd',
  'a.d.xx': 'adxx',
  'a.e': 'ae'
}

实现一个repeat函数

题目

实现一个repeat函数，每次间隔时间调用被包裹的函数，重复指定的次数

function repeat (func, times, wait) {
  // ...
}
// 调用
const repeatFunc = repeat(console.log, 4, 500)
repeatFunc('hello~')
// 输出
// hello~ // * 4 by interval 500ms

实现

延长setTimeout的时间

function repeat (func, times, wait) {
  if (typeof func !== 'function') throw Error('The first param for repeat is not a function!')
  return (...args) => {
    for (let i = 0; i < times; i++) {
      setTimeout(() => {
        console.log(new Date())
        func.apply(null, args)
      }, (i + 1) * wait)
    }
  }
}

借助Promise实现一个sleep函数

function sleep (wait) {
  return new Promise((resolve, reject) => {
    setTimeout(() => {
      resolve(window.performance.now())
    }, wait)
  })
}

function repeat (func, times, wait) {
  if (typeof func !== 'function') throw Error('The first param for repeat is not a function!')
  return async (...args) => {
    for (let i = 0; i < times; i++) {
      console.log(await sleep(wait))
      func.apply(null, args)
    }
  }
}

以上点了一些思路，抛砖引玉，仅供参考。

将list数据转换成树形结构

题目

以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换成树形结构，要求尽可能降低时间复杂度。parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：

// 原始 list 如下
let list =[
    {id:1,name:'部门A',parentId:0},
    {id:2,name:'部门B',parentId:0},
    {id:3,name:'部门C',parentId:1},
    {id:4,name:'部门D',parentId:1},
    {id:5,name:'部门E',parentId:2},
    {id:6,name:'部门F',parentId:3},
    {id:7,name:'部门G',parentId:2},
    {id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);

// 转换后的结果如下
let result = [
    {
      id: 1,
      name: '部门A',
      parentId: 0,
      children: [
        {
          id: 3,
          name: '部门C',
          parentId: 1,
          children: [
            {
              id: 6,
              name: '部门F',
              parentId: 3
            }, {
              id: 16,
              name: '部门L',
              parentId: 3
            }
          ]
        },
        {
          id: 4,
          name: '部门D',
          parentId: 1,
          children: [
            {
              id: 8,
              name: '部门H',
              parentId: 4
            }
          ]
        }
      ]
    },
  ···
];

思路

使用Map保存id和对象的映射，循环list，根据parentId在Map里取得父节点，如果父节点有children属性，就直接push当前的子节点，如果没有就添加children属性。

function convert(list) {
	const res = []
	const map = new Map()
        list.forEach(el => {
            map.set(el.id, el);
        });
	for (const item of list) {
		if (item.parentId === 0) {
			res.push(item)
			continue
		}
                // 获取引用，设置子节点
		if (map.has(item.parentId)) {
			const parent = map.get(item.parentId)
			parent.children = parent.children || []
			parent.children.push(item)
		}
	}
	return res
}
// 关键：Map保存引用关系
// test
// map.get(1) === res[0] // true

JS实现函数无限操作

题目

用Javascript实现一个无限极函数，形如：

operator (1)(2)(3) => f(x)...;
operator (1)(2)(3)() => 6;

注意：执行operator的时候如果最后不是以()结尾（如operator (1)(2)），则这个结果会一直缓存到闭包里。如果下次直接operator (3)(4)的话结果是10.因为他会累加之前的结果。如果你不想这样，那可以通过加()消费缓存的结果。

实现

闭包的一个应用。

function add(x, y) {
    if (isNaN(+x)) {
        x = 0;
    }
    if (isNaN(+y)) {
        y = 0;
    }
    return x + y;
}
var operator = (function(op) {
    let result = null;
    return function (x) {
        if (x) {
            result = op(x, result);
            return arguments.callee; // 在严格模式下无效, 你可以给定函数一个名字
        } else {
            let ret = result;
            result = null;
            return ret;
        }
    }
})(add);

记一次字节前端笔试

字节跳动前端面经

其他与个人项目相关的就不说了，直接来看笔试题。

题目

看代码写输出

var result = [];
var a = 3;
var total = 0;
function foo(a) {
  var i = 0;
  // 注意这里的i后置加
  for (; i < 3; i++) {
    result[i] = function() {
      total += i * a;
      console.log(total);
    }
  }
}

foo(1);
result[0](); // 3
result[1](); // 6
result[2](); // 9

如果将 var i = 0 改为 let, 输出是否会变化

不会，这里 i 是定义在foo函数作用域内的。

注解：

用闭包来解释这题会更好，因为i是定义在foo函数作用域里的，result数组里的函数运行时相当于从foo函数作用域外引用i、a变量，这个时候foo循环已经退出了，i因为后置加的存在在退出循环以后等于3，a因为参数传入为1，所以输出就是3、6、9。如果这里参数不指定a的话，就会直接沿着作用域链往上查找到定义在全局作用域的a = 3，最后结果为9、18、27。如果foo不传入参数，a还是在foo函数作用域，相当于写了一条 var a; // undefined，最后输出三个NaN。

二进制加法

实现一个二进制加法，输入输出均为二进制字符串

function binaryAdd(num1: string, num2: string): string {
  // TODO
}
//Example
binaryAdd('1010', '111') // '10001'

leetcode原题，二进制求和

和链表求和、字符串加法差不多，进位进入第二次运算即可，计算完成如进位有余记得补位

function addBinary(a,b) {
    let ans = '', carry = 0
    let pa = a.length-1;
    let pb = b.length-1;
    while (pa >=0 || pb >= 0) {
        const sum = Number(a[pa] || 0) + Number(b[pb] || 0) + carry
        carry = Math.floor(sum / 2);
        ans = sum % 2 + ans
        pa--;
        pb--;
    }
    if(carry !== 0) ans = '1' + ans
    return  ans
}

实现一个带并发限制的异步队列

实现一个带并发限制的异步调度器Scheduler，保证同时运行的任务最多有两个。完善代码中Scheduler类，使得以下程序能正确输出

class Scheduler {
  add(promiseCreator) {
    // TODO
  }
  // TODO
}
const timeout = (time) => new Promise(resolve => {
  setTimeout(resolve, time)
})
const scheduler = new Scheduler();
const addTask = (time, order) => {
  scheduler.add(() => timeout(time))
    .then(() => console.log(order))
}

addTask(1000, '1')
addTask(500, '2')
addTask(300, '3')
addTask(400, '4')
// output: 2 3 1 4
// 一开始，1、2两个任务进入队列
// 500ms时，2完成，输出2，任务3进队
// 800ms时，3完成，输出3，任务4进队
// 1000ms时，1完成，输出1
// 1200ms时，4完成，输出4

// 实现如下
class Scheduler {
  constructor () {
    this.tasks = [] // 任务缓冲队列
    this.runningTask = [] // 任务队列
  }

  // promiseCreator 是一个异步函数，return Promise
  add (promiseCreator) {
    return new Promise((resolve, reject) => {
      promiseCreator.resolve = resolve
      if (this.runningTask.length < 2) {
        this.run(promiseCreator)
      } else {
        this.tasks.push(promiseCreator)
      }
    })
  }

  run (promiseCreator) {
    this.runningTask.push(promiseCreator)
    promiseCreator().then(() => {
      promiseCreator.resolve()
      // 删除运行完的任务
      this.runningTask.splice(this.runningTask.findIndex(promiseCreator), 1)
      if (this.tasks.length > 0) {
        this.run(this.tasks.shift())
      }
    })
  }
}

小结

字节还是很考基础，面了两次下来感觉最大的问题就是这块，平时实践较多但是深度不够，比如第三题那个带并发限制的异步队列，读完题后没有较好的思路。

如果单纯从准备面试的角度，除开基础知识预备，算法题这些，JS这块可以关注一下事件循环、作用域、原型链继承，再就是各种花式异步操作等等。

实现简单的并发请求控制

题目

请实现以下的函数，可以批量请求数据，所有的URL地址在urls参数中，同时可以通过 max 参数控制请求的并发度，当所有请求结束之后，需要执行 callback 回调函数。发请求的函数可以直接使用 fetch 即可

function sendRequest(urls: sring[],max:number,callback:()=>void){
    //TODO
}

实现

这里收藏网上一个比较好的实现。

function sendRequest(urls, max, callback) {
  const len = urls.length;
  let idx = 0;
  let counter = 0;

  function _request() {
    // 有请求，有通道
    while (idx < len && max > 0) {
      max--; // 占用通道
      fetch(urls[idx++]).finally(() => {
        max++; // 释放通道
        counter++;
        if (counter === len) {
          return callback();
        } else {
          _request();
        }
      });
    }
  }
  _request();
}

二叉树的路径

整理

一般地，处理二叉树路径相关的问题，使用递归更直观，诸如输出二叉树所有的路径、路径和或者左/右叶子节点之和等等，以下举几个例子。

题一

给定一个二叉树，返回所有从根节点到叶子节点的路径。

257. 二叉树的所有路径

最直观的方法是使用递归。在递归遍历二叉树时，需要考虑当前的节点和它的孩子节点。如果当前的节点不是叶子节点，则在当前的路径末尾添加该节点，并递归遍历该节点的每一个孩子节点。如果当前的节点是叶子节点，则在当前的路径末尾添加该节点后，就得到了一条从根节点到叶子节点的路径，可以把该路径加入到答案中。

作者：LeetCode

// 二叉树节点等实现略去
function constructPath(node, path, collection) {
    if(node !== null) {
        path += node.val
      	// 叶子结点，将路径加入答案集合
        if(node.left === null && node.right === null) {
            collection.push(path)
        } else {
            path += '->'
            // 处理左右节点
            constructPath(node.left, path, collection)
            constructPath(node.right, path, collection)
        }
    }
}
const binaryTreePaths = function(root) {
    if(root === null) return []
    const collection = []
    constructPath(root, '', collection)
    return collection
};

题二

很容易关联到另一题，求根到叶子节点数字之和。在此题中，二叉树的每条路径都作为一个数字，求和，所以处理方法也可以类似，构建路径数字，最后遍历求和。

function constructPath(node, path, collection) {
    if(node !== null) {
        path += node.val
        if(node.left === null && node.right === null) {
            collection.push(path)
        } else {
            constructPath(node.left, path, collection)
            constructPath(node.right, path, collection)
        }
    }
}
var sumNumbers = function(root) {
    if(root === null) return 0
    const collection = []
    constructPath(root, '', collection)
    return collection.reduce((pre, curr) => pre+= Number(curr), 0)
};

实现要先把数字转字符串最后遍历转回来，效率略低，可以放到每次遍历中去累加：

const helper = (root, cur, ans) => {
    if(root !== null) {
        cur = cur*10 + root.val
        if (root.left === null && root.right === null) {
          ans.num += cur
        } else {
          helper(root.left, cur, ans)
          helper(root.right, cur, ans)
	}
    }
}
const sumNumbers = function(root) {
    if(!root) return 0
    let ans = {
        num: 0
    }
    helper(root, 0, ans)
    return ans.num
};

题三

404. 左叶子之和

function mapLeftLeaves(root,isLeft) {
    if (root == null) return 0;
    if (isLeft && root.left == null && root.right == null) return root.val;
    return mapLeftLeaves(root.left,true) + mapLeftLeaves(root.right, false);
}
const sumOfLeftLeaves = function(root) {
    if(root === null) return 0
    return mapLeftLeaves(root, false)
};

或者使用迭代，效率更高

const sumOfLeftLeaves = function(root) {
    if(!root) return 0
    const stack = [root]
    let ans = 0
    // 借助栈实现先序遍历
    while(stack.length > 0) {
        let cur = stack.pop()
        if(cur.right) stack.push(cur.right)
        if(cur.left) stack.push(cur.left)
      	// 处理左叶子结点
        if(cur.left && !cur.left.left && !cur.left.right) ans += cur.left.val
    }
    return ans
};

以上。

将JS对象表示的DOM结构渲染为真实DOM树

题目

要求写一个函数将以下调用渲染成真实DOM

var el = require('./element')

var ul = el('ul', {id: 'list'}, [
  el('li', {class: 'item'}, ['Item 1']),
  el('li', {class: 'item'}, ['Item 2']),
  el('li', {class: 'item'}, ['Item 3'])
])

var ulRoot = ul.render()
document.body.appendChild(ulRoot)

实现

// element.js
function Element (tagName, props, children) {
  this.tagName = tagName
  this.props = props
  this.children = children
}
// 将函数调用转为JS对象表达的DOM结构
module.exports = function (tagName, props, children) {
  return new Element(tagName, props, children)
}

// render方法
Element.prototype.render = function () {
  // 根据tagName构建真实节点
  var el = document.createElement(this.tagName)
  var props = this.props
  // 设置节点的DOM属性
  for (var propName in props) {
    var propValue = props[propName]
    el.setAttribute(propName, propValue)
  }

  var children = this.children || []
  // 递归处理子节点
  children.forEach(function (child) {
    var childEl = (child instanceof Element)
      ? child.render() // 如果子节点也是虚拟DOM，递归构建DOM节点
      : document.createTextNode(child) // 如果字符串，只构建文本节点
    el.appendChild(childEl)
  })

  return el
}

参考

深度剖析：如何实现一个 Virtual DOM 算法

一般DP问题的快速解

思路

一个是找出问题的一个一个子“ 状态”，再一个就是建立“ 状态转移方程”（就是所谓的“ 递推关系式”），可以手写枚举几个结果出来找关系推出式子，然后先递归写法，再向迭代写法的方向优化空间复杂度。

“ 循环还是递归”，这只是实现的办法而已，不是动态规划的本质；再比如空间换时间，把子问题的解答结果（就是上面说的子“ 状态”）存放起来，减少重复计算，这也是优化的办法，也并非动态规划本质。

实现

// 伪代码
function helper(data,map, ...params) {
    // 递归终止条件
    // for example
     if(param === xxx) return xx
    // 缓存key
    // for example，如二维问题
     const key = `${i}-${j}`
    // 获取缓存
    if(map.has(key)) {
        return map.get(key)
    }
    // 根据状态转移方程计算
    const result = helper(data, map,...params)
    // 缓存计算结果
    map.set(key, result)
    return result
}
function minPathSum(grid) {
    const map = new Map()
    return helper(grid, map, ...initParam)
};

斐波那契数列

让我们从最简单的斐波那契数列开始，一般问题会让求取数列的某一项，并有

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

其中关于 F(N)的表达式就是此问题的递推关系式，当然从斐波那契数列(0,1,1,2,3,5,8....)也可以推出, 符合上述思路，子问题就是单个数由其前一项和前两项相加求和而来。那么可以有：

// f(i) = f(i - 1) + f(i - 2)
function helper(i,map) {
    // 递归终止条件
    // for example
    if(i < 2) return i
    // 获取缓存, 一维问题的key直接用参数即可
    if(map.has(i)) {
        return map.get(i)
    }
    // 根据状态转移方程计算
    const result = helper(i - 1, map) + helper(i - 2, map)
    // 缓存计算结果
    map.set(i, result)
    return result
}
function fib(N) {
    const map = new Map()
    return helper(N, map)
};

/** test
 * fib(0) = 0
 * ...
 * fib(50) = 6765 // passed
 */

一般教程都会拿上述例子作为函数记忆化的例子。上述解法思路也差不多就是递推关系式+缓存。

以上解法的时间复杂度：O(N)，空间复杂度：O(N)，内存中使用的堆栈大小。空间复杂度还可以优化，因为我们只需要前两个状态。

先把实现方法改写为迭代写法：

function fib(N) {
    if(N < 2) return N
    const dp = [1, 1]
    for(let i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[N-1]
}

这里使用数组来缓存结果，保存了从1~N的结果，优化之：

function fib(N) {
    if (N <= 1) return N
    let current = 0, prev1 = 1, prev2 = 1;

    for (let i = 2; i <= N; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

如此，我们就做到了O(1)的空间复杂度。

零钱兑换

来看一个稍难的问题，零钱兑换, 典型的背包问题。

我们先拿出分别一枚硬币，从总额减去币值的消耗，作为一种方案（+1），然后重复该过程，拿每种硬币去凑剩余的余额，从方案中选出最小数量即可。

根据思路可以得出：

f(0) = 0, //金额为0不能由硬币组成
f(n > 0) = min{f(n−coin)+1∣coin∈coins}

具体思路参见：零钱兑换-官方题解

// 递归方程式
// f(i) = min(f(i - cost in costs)) + 1
function helper(amount, coins, map) {
    // 金额消耗完毕，递归终止
    if(amount <= 0) return 0
    // 获取缓存
    if(map.has(amount)) {
        return map.get(amount)
    }
    // 根据状态转移方程计算
    const re = []
    for (let i of coins ) {
        const t = amount - i
        if( t >= 0) re.push(helper(t, coins, map))
    }
    const result = Math.min(...re) + 1
    // 缓存计算结果
    map.set(amount, result)
    return result
}
function coinChange(coins, amount) {
    const map = new Map()
    const result = helper(amount, coins, map)
    return result === Infinity ? -1 : result
};

同样可以改写成迭代写法：

function coinChange(coins, amount) {
  const dp = new Array(amount+1).fill(Infinity)
  dp[0] = 0
  for (let coin of coins ) {
    for (let i = 1; i <= amount; i++) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1)
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

总结

一般错误出现在递归边界设置错误或者递推关系式上，如果遇到爆栈等问题，可以从这两方面着手。

递归写法最接近关系式，更容易写出求解，故作为快速解的一个思路。但是学习不应以结果为导向，要更关注过程，例如递归写法的时间复杂度也可以根据问题类型进行优化，或用迭代写法来优化空间复杂度等等。

题目

动态规划题目参见：动态规划-Leetcode

TODO

补充其他动规类型，如二维问题

判断二叉树是否相同/对称/子树

判断二叉树是否相同/对称

题目

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

100. 相同的树

思路

处理二叉树的问题，递归比较直观，逐级判断节点是否一致即可。

实现

const isSameTree = (p, q) => {
    if(p == null && q == null) 
        return true;
    if(p == null || q == null) 
        return false;
    if(p.val != q.val) 
        return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

也可以借助队列通过迭代来实现，每棵树分别一个队列，相同位置的节点逐级入队，再出队判断即可。

const isSameTree = (p, q) => {
    const queue1 = [];
    const queue2= [];
    queue1.push(q);
    queue2.push(p);
    while (queue1.length > 0){
        const tempQ = queue1.shift();
        const tempP = queue2.shift();
      	// 判断逻辑是一样的 
        if (tempQ === null && tempP === null) continue;
        if (tempQ === null || tempP === null) return false;
        if(tempP.val !== tempQ.val) return false;
        queue1.push(tempQ.left);
        queue1.push(tempQ.right);
        queue2.push(tempP.left);
        queue2.push(tempP.right);
    }
    return true;
}

类似的应用还有判断一棵树B是否为另一棵树A的子树，如果根节点相同则从根节点判断，如果不相同则递归判断A的左子树、右子树是否包含B。

面试题26. 树的子结构

var isSubStructure = function(A, B) {
    let result = false;
    // 边界条件，因题不同
    if(A != null && B != null){
        if(A.val  == B.val)
            result = isSameTree(A,B);
        if(!result)
            result = isSubStructure(A.left, B);
        if(!result)
            result = isSubStructure(A.right, B);
    }
    return result
};

类似的题

想到一道类似的题，检查一棵二叉树是否对称，101. 对称二叉树

const isSymmetric = root => {
    const q = [];
    q.push(root);
    q.push(root);
    while (q.length > 0) {
        const t1 = q.shift();
        const t2 = q.shift();
        if (t1 == null && t2 == null) continue;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        q.push(t1.left);
        q.push(t2.right);
        q.push(t1.right);
        q.push(t2.left);
    }
    return true;
};

这里每次都检验对称位置的节点是否相同，然后再把其子节点按对称的顺序入队，思路上也是模拟人手工遍历。

字符串相加和相乘

字符串相加

题目

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。不能直接将输入的字符串转换为整数形式。

415. 字符串相加

实现

模拟笔算加法，逐位相加

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
function addStrings (num1, num2) {
    let i = num1.length - 1,j = num2.length - 1
    let carry = 0
    let ans = ''
    while(i >= 0 || j >= 0) {
        // 考虑进位的相加，长度不同的数字，取不到则标0
        const sum = (Number(num1[i]) || 0) + (Number(num2[j]) || 0) + carry
        // 进位处理
        carry = Math.floor(sum / 10)
        ans = sum % 10 + ans
        i--;
        j--
    }
    // 如果有未处理的进位
    if(carry > 0) ans = '1'+ ans
    return ans
};

类似的题

同样四则运算，来看下字符串相乘，字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

// 与字符串加法类似，模拟笔算乘法-竖版乘法
function multiply (num1, num2) {
    // 如有一方为 0 直接返回 0 作为结果
    if(num1 === '0' || num2 === '0') return '0'
    // 用于保存结果及进位
    let res = Array(num1.length + num2.length).fill(0)
    // 逐位相乘
    for (let i = num2.length - 1; i >= 0; i--) {
        let n1 = Number(num2[i]);
        for (let j = num1.length - 1; j >= 0; j--) {
            let n2 = Number(num1[j]);
            // 单数相乘+进位
            let sum = res[i + j + 1] + n1 * n2;
            res[i + j + 1] = sum % 10;
            // 保存进位
            res[i + j] += Math.floor(sum / 10);
        }
    }
    let ans = ''
    for (let i = 0; i < res.length; i++) {
        if (i == 0 && res[i] == 0) continue;
        ans+=res[i];
    }
    return ans
};

flex相关属性的计算方法

flex属性的计算方法

这里主要是flex-grow、flex-shrink，分别对应在空间有剩余时的分配、空间不足时的收缩

flex-grow

剩余空间按flex-grow指定的值比例分配即可

举个例子，父容器的宽度为600，两个子项A(300, 1)、B(200, 2)，求具体宽度：

剩余宽度为100

子项增长宽度A = 100 * 1/3 = 33.333, 则实际宽度 = 333.333
子项增长宽度B = 100 * 2/3 = 66.667, 则实际宽度 = 266.667

Demo

flex-shrink

子项收缩宽度 = 子项收缩比例 *溢出宽度
子项收缩比例 = (子项宽度* 收缩系数) / 所有子项的(宽度  *收缩系数)之和

* 收缩系数指flex-shrink的值

举个例子，父容器的宽度为600，两个子项A(500, 2)、B(400, 1)，求具体宽度：

溢出宽度为300

子项收缩比例A = (500 *2) / (500 × 2 + 400 × 1) ≈ 0.71
子项收缩比例B = (400* 1) / (500 × 2 + 400 × 1) ≈ 0.29

子项收缩宽度A = 300 * 0.71 = 213, 则实际宽度 = 287
子项收缩宽度B = 300 * 0.29 = 87, 则实际宽度 = 313

* 实际宽度略有出入，与收缩比例取整有关

关键在于收缩比例的计算，和flex-grow不一样

Demo

CSS实现一个响应式布局

题目

请用CSS实现一个1行4列占满宽度的布局，每个子项要求有 1px 的黑色边框。当设备宽度小于 720px 时，布局变换为2行2列，当设备宽度小于 360px 时，布局变换为4行1列。

<div class="container">
  <div class="item"></div>
  <div class="item"></div>
  <div class="item"></div>
  <div class="item"></div>
</div>

实现

使用 flex 布局，搭配 MediaQuery 实现响应式

html,
body {
  margin: 0;
  padding: 0;
}

.container {
  display: flex;
  flex-direction: row;
  flex-wrap: wrap;
  /* 以上两项可以简写为 flex-flow属性 */
}

.item {
  height: 100px;
  box-sizing: border-box;
  border: 1px solid black;
  flex: 0 0 25%
}
@media screen and (max-width: 720px) {
  .item {
    flex: 0 0 50%
  }
}

@media screen and (max-width: 360px) {
 .item {
    flex: 0 0 100%
  }
}

也可以使用grid布局

.container {
  display: grid;
  grid-template-columns: repeat(4, 1fr);
}
@media screen and (max-width: 720px) {
  .container {
    grid-template-columns: 1fr 1fr;
  }
}

@media screen and (max-width: 360px) {
  .container {
    grid-template-columns: 1fr;
  }
}

可以通过以下链接调试：

https://codepen.io/liusw/pen/WNQaarP

京东面经

CSS：

垂直居中的方式
移动端的适配方案，1px的线如何画
BFC，原因，渲染机制
清除浮动的方法
输入URL，浏览器的渲染机制（很深，深入dom渲染（dom2，dom3），css渲染）
eventloop（宏任务和微任务）

js和框架

跨域和解决方案
网络安全（具体措施和解决方案，最好项目中用到）
VUE如何把tempale模版编译成VDOM树的
diff算法的过程和复杂度
vue和react的区别.
项目最难的点，怎么解决的
webpack用过多少，多深，做过哪些优化
vue的dom如何变异的（指令，dom树）
vue的响应式原理（watcher创建和分配）$nextTick如何实现和原理

后端和网络编程

http的三次握手的具体过程
用到了https吧，谈谈对https了解
KOA用过，说一下中间件原理
说一下浏览器缓存机器，304的状态码表示什么含义

汇总区间

题目

给定一个无重复元素的有序整数数组，返回数组区间范围的汇总。

示例 1:

输入: [0,1,2,4,5,7]
输出: ["0->2","4->5","7"]
解释: 0,1,2 可组成一个连续的区间; 4,5 可组成一个连续的区间。

汇总区间

题解

双指针，假设为 i，j，i 位于开始，j 逢 +1 后移，否则生成序列。

function summaryRanges (nums) {
    const ans = []
    for (let i = 0, j = 0; j < nums.length; ++j) {
        // 判断下一位是否为当前值+1，注意边界
        if (j + 1 < nums.length && nums[j + 1] == nums[j] + 1)
            continue;
        // 否则生成序列
        if (i == j)
            ans.push(nums[i] + "");
        else
            ans.push(nums[i] + "->" + nums[j]);
        i = j + 1;
    }
    return ans
};

实现一个深克隆函数

思路

要求实现一个深克隆的函数。

对于引用类型，例如常见的Object，都是通过引用指向同一块堆内存，因此无法直接赋值的方式拷贝一个对象。有一些方法可以实现浅克隆，例如通过遍历的方式复制每一个属性，或者使用 Object.assign / Object.create，对于数组对象，可以使用 Array.prototype.slice 方法，这里不深究，主要来看下深克隆。

一般地，我们可以使用JSON序列化的方式完成拷贝，缺点是：

无法实现对函数、RegExp等特殊对象的克隆
对象有循环引用,会报错
会抛弃对象的constructor,所有的构造函数会指向Object
...

那么常见的方式就是递归遍历复制属性，需要处理的就是上述几种情况。

实现

function deepClone(obj) {
  // 应对循环引用设置的缓存
  const objs = new WeakMap()

  function helper(obj) {
    if (obj === null) return null
    if (typeof obj !== 'object') return obj // 值类型直接返回即可

    let child
    // 获取被克隆对象的类型
    const type = Object.prototype.toString.call(obj)
    // 处理特殊对象
    switch(type) {
      case '[object Array]':
        // 处理数组对象
        child = []
        break
      case '[object RegExp]':
        // 对正则对象做特殊处理
        child = new RegExp(obj.source, obj.flags)
        if(obj.lastIndex) child.lastIndex = obj.lastIndex
        break
      case '[object Date]':
        // 对Date对象做特殊处理
        child = new Date(parent.getTime())
        break
      default:
        // 这里没有处理Map、Set， 下述方式无法处理这两者
        // 获取对象原型
        proto = Object.getPrototypeOf(parent)
        child = Object.create(proto)
        break
    }
    // 处理循环引用
    // 这里也可以用数组来缓存
    if(objs.has(obj)) {
      return objs.get(obj)
    }
    objs.set(obj, obj)

    // 递归遍历属性
    for (let i in obj) {
      child[i] = helper(obj[i])
    }
    return child
  }

  return helper(obj)
}

metroluffy / fe-learning Goto Github PK

fe-learning's Issues

题目

解题思路

第一版代码

优化代码

移除链表元素

题目

题解

更多一点

题目

解题思路

暴力法

代码

位运算

代码

实现Promise.all

Promise.all

Promise.race

Promise.finally

参考文档

微信面试题 LazyMan

题目

解题思路

代码

哈希表解「两数之和」

题目

暴力解法

哈希表解法

哈希表解法优化

双指针解三（三或三以上）数之和

题目

解法

四数之和

实现Lodash函数系列（一）：_.get

题目

实现

参考文档

实现字符串反转

题目

实现

关于async和await的“同步”

题目

解析

三角形

梯形

扇形

箭头

椭圆

实现一个repeat函数

题目

实现

将list数据转换成树形结构

题目

思路

JS实现函数无限操作

题目

实现

字节跳动前端面经

题目

看代码写输出

二进制加法

实现一个带并发限制的异步队列

小结

题目

实现

二叉树的路径

整理

题一

题二

题三

将JS对象表示的DOM结构渲染为真实DOM树

题目

实现

参考

一般DP问题的快速解

思路

实现

斐波那契数列

零钱兑换