Lee前端技术栈

题目：给定两个数组，编写一个函数来计算它们的交集。

分析：这是一个较为基础且常见的题，方法很多，比如：双指针法，去重法，二分查找法等：

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

var intersection = function(nums1, nums2) {
    let arr = []
    for (let i =0;i<nums1.length;i++) {
        for (let j=0;j<nums2.length;j++) {
            if (arr.indexOf(nums1[i]) === -1
                && arr.indexOf(nums2[j]) ===-1
                    && nums1[i] === nums2[j]) {
                arr.push(nums2[j])
            }
        }
    }
    return arr
}
intersection([1,2,2,1], [2,2])  //  [2]
intersection([4,9,5], [9,4,9,8,4])  //  [4,9]

运行结果： 执行用时：596 ms, 在所有 JavaScript 提交中击败了5.22的用户
内存消耗：38 MB, 在所有 JavaScript 提交中击败了99.13%的用户
可以看到双指针法的时间复杂度较高，而空间复杂度低。

1
2
3
4
5

var intersection = function(nums1, nums2) {
    return [...new Set(nums1)].filter(n => nums2.includes(n))
}
intersection([1,2,2,1], [2,2])  //  [2]
intersection([4,9,5], [9,4,9,8,4])  //  [4,9]

先用new Set()对nums1去重，再过滤，这种方法本人认为局限性较大。

That’s all!

题目：给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

分析：看题目，直接就想到了哈希方式。统计字符出现的次数。

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

var containsNearbyDuplicate = function(nums, k) {
    let obj = {}
    for (let i = 0;i < nums.length;i++) {
       if (obj[nums[i]] !== undefined &&
            i - obj[nums[i]] <= k) {
           return true
       }
       obj[nums[i]] = i
    }
    return false
};
containsNearbyDuplicate([1,2,3,1], 3) // true
containsNearbyDuplicate([1,2,3,1,2,3], 2) // false

That’s all!

题目：给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

分析：这个题应该是比较简单的，哈希方式，统计字符出现的次数这个思路即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

var containsDuplicate = function(nums) {
    if (nums.length < 2) return false
    let map = {}
    let isTrue = false
    for (let i = 0;i<nums.length;i++) {
        if (!map.hasOwnProperty(nums[i])) {
            map[nums[i]] = 1
            isTrue = false
        } else {
            isTrue = true
            break
        }
    }
    return isTrue
};
containsDuplicate([1,2,3,1]) // true
containsDuplicate([0,4,5,0,3,6]) // true
containsDuplicate([1,2,3,4]) // false

That’s all!

题目：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

分析：本地中没什么难度，只是要注意的是不要使用额外空间，空间复杂度是O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var reverseString = function(s) {
    let left = 0
    let right = s.length - 1
    while (left <= right) {
        let temp = s[left]
        s[left] = s[right]
        s[right] = temp
        left++
        right--
    }
    return s
};
reverseString(["h","e","l","l","o"])
//  ["o","l","l","e","h"]
reverseString(["H","a","n","n","a","h"])
//  ["h","a","n","n","a","H"]

That’s all!

题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。算法应该具有线性复杂度，并且不使用额外的空间。

解析：在给定的数组中，很有规律，除了只出现一次的元素外，其他的每个元素均只出现俩次，这就让我们想到了异或运算(^)。即，任意数a和0的运算：a⊕a=0;a⊕0=a,所以代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

let singleNumber = nums => {
    if (!nums.length) {
        return
    }
    let m = 0
    for(let i of nums) {
        m ^= i
    }
    return m
}
singleNumber([4,1,2,1,2])   //  4
singleNumber([2,2,1])   //  1

所以本题的思路是非常难的，代码很简单，快补充一下异或运算啊。

题目：给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析：这就是标准的T+1股票，今天买进，只要涨，明天就卖出。

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

let maxProfit = prices => {
    let sum = 0
    for(let i = 0;
        i < prices.length;i++) {
            if (prices[i+1] > prices[i]) {
                sum += prices[i+1] - prices[i]
            }
        }
    return sum
}
maxProfit([1,2,3,4,5])  //  4
maxProfit([7,1,5,3,6,4])  //  7
maxProfit([7,6,4,3,1])  //  0

没什么好说的。That’s all!

我们知道在react中，setState是调用频率非常高的一个函数。

setState在默认情况下是异步的

我们知道setState的调用是非常频繁的，那么如果setStates是同步执行，那么就意味着只要调用setState就会修改state,而state的变化，就会直接启动diff算法，从而重新渲染页面，这在性能方面的消耗实在是太过夸张。但是如果是异步执行，那么在多次setState之后，将这些操作一起合并执行。降低性能消耗成为可能。

同步情况下的setState

在setTimeout和原生事件中，setState是同步执行的。

调用setState会发生什么

调用setState之后首先会将传入setState的参数和原来的state进行合并，得到新的state，那么这样state就被更新了，因为state的更新就会引起页面的重新渲染，所以，会调用触发所谓的调和过程，react的就以相对高效的方式来自动计算出新旧dom的差异，根据差异最小化来重新构建页面。

曾经的react

react技术栈的迭代是非常快的，但是版本16也许是一次革命性的迭代。从版本16开始，react的底层由stack算法转变为fiber算法，大大提高了性能。而在16.8之后react又新增了hooks的概念。在老版本的react中，开发者所开发的大多都是class组件和少部分的函数组件，对于函数组件来说，它仅仅只是一个纯UI的展示组件，只能接受props，而不能有自己的state。而对于class组件来说，问题也是不少：组件状态复用艰难，让人无奈的this问题，高阶组件和函数组件的嵌套层次太深，复杂组件变得难以理解，以及难以记忆的生命周期等问题很让人头大。

Hooks能做点什么

总的来说Hooks的出现就是为了解决这些问题而产生的：

• useState函数可以初始化状态，为函数组件赋予了状态；
• useEffect函数代替了之前的生命周期函数，接受包含命令式，可能有副作用代码的函数；
• useContext接受上下文对象，并返回上下文对象，让深嵌套的组件通信变的简单；
• useReducer 是useState的代替方案，接受类型为state，action => newState的reducer，并返回与dispatch方法配对的当前状态；
• useCallback返回一个记忆的memoried版本，该版本仅在其输入发生改变时才会更改，尤其是很好的解决了函数需要绑定this这一问题；
• useMemo一个纯记忆函数
• useRef返回一个可变的ref对象，其.current对象被定义为初始化传递的参数
• …

Hooks的实现原理

React会维护俩个链表，一个是currentHook，另外一个是WorkInProgressHook,每一个节点类型都是Hooks，每当hooks函数被调用，react就会创建一个hooks对象，并挂在链表的尾部，函数组件之所以能做一些类组件不能做的事儿，就是因为hook对象，函数组件的状态，计算值，缓存等都是交给hook去完成的，这样组件通过Fiber.memoizedState属性指向hook链表的头部来关联hook对象和当前组件，这样就发挥了hooks的作用。每次调用hooks API的时候，就会首先调用createWorkInProgressHook函数。得到hooks的串联不是一个数组，而是一个链式结构，从根节点workInProgressHook向下通过next进行串联，这也是为什么Hooks不能嵌套使用，不能在条件判断中使用，不能在循环中使用，否则链式就会被破坏。

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

解析：

• 首先给定的是一个有序数组，那么我们直接循环就OK，时间复杂度应该是O(1)
• 题目要求返回的是索引，并不是将目标元素插入到数组的某个位置，这就简单了，并不会对数组做什么操作。那么就可以说是只要发现元素大于等于(>=)目标元素就找到了这个位置,否则就是没有找到这个位置，那么目标值一定是最大值，返回最后一个的下标就OK！
• 注意处理边界值。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  let searchInsert = (nums, target) => { let index = 0 for (let i = 0; i < nums.length - 1; i++ ) { if (nums[i] >= target) { index = i break } index = nums.length } return index } searchInsert([1,3,5,6], 5) // 3 searchInsert([1,3,5,6], 2) // 1 searchInsert([1,3,5,6], 0) // 0

  题还是比较简单，但是别让自己的思维走进死胡同，其实对于Javascript来说，有个方法叫reduce，此法也许更简洁。That’s all!

题目：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。
分析：看到这个题，第一反应应该就是选择排序的思想。是的没有错。采用prices[i]和后面的每一个元素做对比。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

let maxProfit = prices => {
    //  取第一个元素为最小值
    let sum = prices[0]
    let po = 0
    for (let i = 1;
            i < prices.length; i++) {
        if (prices[i] < sum) {
            sum = prices[i]
        }
        po = prices[i] - sum > po ? 
            (prices[i] - sum) : po
    }
    return po
}
maxProfit([7,1,5,3,6,4])    // 5
maxProfit([7,6,4,3,1])    // 0

空间复杂度为O(1),时间复杂度为O(1),但是请考虑下面的代码是不有问题。

1
2
3
4
5
6
7
8
9
10
11
12

let maxProfit = prices => {
    let pr = 0
    for (let i = 0;i < prices.length - 1;i++) {
        for (let j = i+1;j < prices.length;j++) {
            if (prices[j]>prices[i]) {
                let sum = prices[j] - prices[i]
                if (sum > pr) pr = sum
            }
        }
    }
    return pr
}

请写下你的见解！

题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

分析：看到这个题，其实我们就直接想到了，统计给定数组中元素出现次数的问题。所以照着这个方向做就OK！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

let majorityElement = (nums) => {
    let obj = {}
    let arr = []
    nums.forEach(n => {
        if (!obj.hasOwnProperty(n)) {
            obj[n] = 1
        } else {
            obj[n]++
        }
    })
    for (let key in obj) {
        if (obj[key] > (nums.length)/2) {
            arr.push(key)
        }
    }
    return arr
}
majorityElement([3,2,3])    //  3
majorityElement([2,2,1,1,1,2,2])    //  2

其实，思路就是哈希表+排序方式，That’s all!

题目：给你一个字符串 s，由若干单词组成，单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词，请返回 0 。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

分析：此题中唯一需要注意的就是空字符串的问题，包括，一个空字符串，或者最后有一个空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var lengthOfLastWord = (s) => {
    //  先将字符串通过空转化成数组
    let arr = s.split(' ')
    let len = 0
    //  注意i>=0
    for (let i = arr.length - 1;
            i >= 0;i--) {
        //  判断后面第一个不是空
        if (arr[i]) {
            len = arr[i].length
            break
        }
    }
    return len
}
lengthOfLastWord("hello world ") // 5
lengthOfLastWord(" ") // 0

较为简单，That’s all!

题目：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。本题中将空字符串,标点符号定义为有效回文字符串。

分析：注意这里的坑。

• 1.忽略大小写，那么就需要统一字符串中每一个字符，要不都答谢大写，要么都小写；
• 2.将空字符串作为有效字符串，那么意味着需要将空字符串,标点符号跳过。
  看代码：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

  var isPalindrome = function(s) { // 将字符串统一转成小写 s = s.toLocaleLowerCase() let left = 0 let right = s.length - 1 let isTrue = false // 只考虑数字和字母，如果不是数字和字母，则跳过 let reg = /^[0-9a-zA-Z]+$/ while (left <= right) { while (!reg.test(s[left]) || !reg.test(s[right])) { if (!reg.test(s[left])) { left++ } if (!reg.test(s[right])) { right-- } } isTrue = s[left] === s[right] if(isTrue) { left++ right-- } else { isTrue = false break } } return isTrue }; isPalindrome('0P') // false isPalindrome('A man, a plan, a canal: Panama') // true isPalindrome('race a car') // false

  Yes, that’s all!

字典的定义：字典是一种以键–值来存储数据的数据结构。但是他的基础是Array,而不是Object.但是字典也是无序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

function Dictionary () {
    //  像字典中添加健--值
    this.add = add
    //  保存数据
    this.dataStore = new Array
    //  查找键值
    this.find = find
    //  删除某一项
    this.remove = remove
    //  统计字典中的属性个数
    this.count = this.count
    //  清空字典
    this.clear = clear
    //  显示字典中所有的项
    this.showAll = showAll
}
function add (key, value) {
    this.dataStore[key] = value
}
function find (key) {
    return this.dataStore[key]
}
function remove (key) {
    delete this.dataStore[key]
}
function count () {
    let n = 0
    for (let key in Object.keys(this.dataStore)) {
        ++n
    }
    return n
}
function clear () {
    Object.keys(this.dataStore).forEach(key => {
        delete this.dataStore[key]
    })
}
function showAll () {
    for (let key in Object.keys(this.dataStore).sort()) {
        console.log(this.dataStore[key])
    }
}

注：字典的实现还是相对比较简单的。但是字典和对象一样，是无序的，需要自己排序。

说到React，版本16将是一个较大的分水岭，尤其是在算法优化方面有了很大的更新，之前是stack算法而之后改成了fiber算法。

stack算法的问题

在react一切都是组建的思想下，多层组建嵌套将会是一个非常常见的操作，那么生命周期的执行将会非常的繁琐。即，

• 挂在阶段：
  constructor
  componentWillMount
  render
  componentDidMount
• 更新阶段
  shouldComponentUpdate
  componentWillUpdate
  render
  componentDidUpdate
  
  从顶层组件一直往下，知道最底层组建，然后再往上，组件的更新阶段也是同理。stack算法底层使用递归，而递归的方式并不会被轻易打断。那么如果组件的嵌套较深，那么递归的运算就会一直在运行，这样，react的渲染一直会占用着浏览器的主线程，这将会花费很长的时间。那么页面中的其他操作就会无法进行，出现页面卡死的现象。

  fiber算法原理

  为了解决stack算法的问题，新版本的react采用了fiber算法，大致是这样做的，就是react将任务分成若干个片段，给每个任务分配一定的时间去执行这个任务，当时间耗尽后，就会检查任务列表中有没有新的或者是优先级更高的任务，如果有执行此任务，如果没有，就继续执行原来的任务。这种方式就是一步渲染的方式。加入fiber的react组件更新分为俩个阶段，以render为界，之前为phase1,之后为phase2。
• phase1阶段
  phase1阶段的生命周期是可中断的。每隔一段时间，就会跳出现有的渲染进程去确定是不是有新的，更重要的任务需要执行，主要是通过requestIdleCallback来构建新的tree，标出重要任务，放入到任务队列中。
• phase2阶段
  phase2阶段的生命周期是不可被中断的。这个阶段就是在render之后执行的，主要就是将phase1阶段的变更一次性的全部更新到DOM上。所以phase1阶段一定是一个完成的任务，否则就会重新再次执行phase1的阶段，这也就导致了某些生命周期可能会执行多次的原因。所以最好保证phase1阶段都做同一件事儿，要不然就会出问题，因此最好都是纯函数。

fiber数据结构

fiber数据结构本质上是一个链表，他有child和sibling属性，指向第一个子节点和相邻兄弟节点，从而构成fiber树，return属性指向其父节点。更新队列updateQueue是一个链表，有first和last属性指向第一个和最后一个update对象，每个fiber结构都有updateQueue属性，指向其更新的队列。每一个fiber都有一个alternate属性开始的时候指向一个自己的clone体，更新的时候会先更新这个alternate,然后通过alternate取代当前的fiber.

关键API–requestIdleCallback

window.requestIdleCallback()方法将浏览器空闲时间段内的调用的函数排队。这使得主事件循环上执行后台和低优先级的工作。而不会影响延迟关键事件，如动画和输入响应。函数一般会按照先进先出的顺序执行。而如果回调函数指定执行超时，则有可能为了超时执行函数而打乱执行顺序，那么就可以在空闲回调函数中调用requestIdleCallback(),以便下一次通过时间循环之前调度另外一个回调。

总结

fiber算法和stack算法，做的优化主要是把任务才拆分成若干个小任务，可以随时控制任务开启和执行，采用异步的方式去执行任务。这样不会丢贞，而stack算法采用递归算法，无法中断，一条道走到黑，因此在动画等要求高的情况下，会出现卡顿现象。