Lee前端技术栈

单向链表

链表的定义：链表是由一组节点组合而成的集合，每个节点都使用一个对象的引用指向他的后继。指向另一个节点的引用叫做链。链表靠他们相互之间的关系进行引用。所以对于链表的操作也很简单，既，查找，删除，插入等。只是改变元素的指向关系即可。
实现链表：

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
43
44
45
46

function Node (item) {
    //  element保存节点上的数据
    this.element = item
    //  next表示指向下一个节点的链
    this.next = null
}
function Llist () {
    //  链表的头
    this.header = new Node('head')
    //  查找链表元素
    this.find = find
    //  向链表中插入元素
    this.insert = insert
    //  删除链表的某一个元素
    this.remove = remove
}
function find (item) {
    //  拿到列表的头节点
    let currNode = this.header
    while(currNode !== item) {
        //  如果当前节点不是要找的节点
        //  就指向下一个节点
        currNode = currNode.next
    }
    return currNode
}
function insert (newItem, oldItem) {
    //  先找到要在插入元素的前一个元素
    let currNode = this.find(oldItem)
    const newNode = Node(newItem)
    //  前一个元素指向新节点
    currNode.next = newNode
    //  新元素指向之前元素的下一个
    newNode.next = currNode.next
}
function remove (item) {
    //  首先要找到前一个元素
    var currNode = this.header
    while (!(currNode ===  null) &&
        currNode.next.element !== item) {
            currNode = currNode.next
        }
    if (!(currNode.next === null)) {
        currNode.next = currNode.next.next
    }
}

双向链表

双向了链表较单项链表而言，双向链表比单向链表要多一个属性，就是前驱。这样在删除元素的时候，就不需要再查找前一个元素了。也就是说，每个元素总有一个属性，指向了他的前一个元素。

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
43

function Node (item) {
    this.element = item
    this.next = null
    this.previous = null
}
function Llist () {
    this.header = new Node('head')
    this.find = find
    this.remove = remove
    this.insert = insert
    //  查找最后一个元素
    this.findLast = findList
}
function find (item) {
    let currNode = this.header
    while (!(currNode.element === item)) {
        currNode = currNode.next
    }
    return currNode
}
function insert (newElement, item) {
    let curr = this.find(item)
    let newNode = new Node(newElement)
    curr.next = newNode
    newNode.next = curr.next
    newNode.previous = curr
}
function remove (item) {
    let curr = this.find(item)
    if (!(curr.next === item)) {
        curr.previous.next = curr.next
        curr.next.previous = curr.previous
        curr.next = null
        curr.previous = null
    }
}
function findLast (item) {
    let curr = this.header
    while (!(curr.next === item)) {
        curr = curr.next
    }
    return curr
}

循环链表

循环链表和单向链表很相似，唯一的区别就是循环链表的头节点的next属性指向自己。

1
2
3
4
5
6
7

function Llist (item) {
    this.header = new Node(item)
    this.header.next = this.header
    .
    .
    .
}

That’s all!

我们之前说过React是一个组件至上的技术栈，所以，组件之间的通信就是大家关注的话题。主要有以下几种：

父子组件

父子组件的传值通过props来实现。

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

var parent = () => {
    let name = "I'm Lee!"
    return (
        <div>
            <Child name="{name}"/>
        </div>
    )
}

var child = (props) => {
    return (
        <div>
            {
                props.name
            }
        <div>
    )
}

子父组件

子父组件的通信主要是通过callback来实现。

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

var parent = () => {
    const onChildClick = (item) => {
        console.log(item) //    点我
    }
    return (
        <div>
            <Child callback={onChildClick}/>
        </div>
    )
}

var child = props => {
    return (
        <div>
            <button onClick={ props.callback('点我') }>点我</button>
        </div>
    )
}

父孙组件

父孙组建有俩中方式：

• 以父子组件传值的方式，层层向下传递；
• context上下文的方式：

  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

  const context = createContext() var parent = () => { const [count, setCount] = useState(0) return ( <div> <context.Provider value={ count }> <Child /> </context.Provider> </div> ) } var child = () => { return ( <div> <Son /> </div> ) } var son = () => { return ( <context.Consumer> { count => <p>{count}</p> } </context.Consumer> ) }

  无关(兄弟)组件

  非嵌套关系的组件通信主要有以下三种方式：
• 兄弟组件，可以通过找到共同的父组件，通过父子，子父组件的方式实现通信
• 可以通过redux, mobx, recoil等全局状态库来实现全局状态管理
• 可以通过自定义事件（发布订阅）

队列的定义：队列其实应该是属于列表的一种，又像是俩个栈拼接形成一样来存储有序数据。队列是一种先进先出的数据结构，就像是公交车一样，前门上车后门下车.所以对于队列的操作最主要的就是俩种：对列尾部插入，队列头部删除。既入队和出对。

队列实现的属性有：

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

function Queue () {
    //  存储数据
    this.dataStore = []
    //  向队尾push数据
    this.enqueue = enqueue
    //  从队头删除数据
    this.dequeue = dequeue
    //  获取对首元素
    this.front = front
    //  获取队尾元素
    this.back = back
    //  判断对列是不是空
    this.empty = empty
    //  显示队列中的所有元素
    this.toString = toString
}
function enqueue (item) {
    this.dataStore.push(item)
}
function dequeue () {
    this.dataStore.shift()
}
function empty () {
    return !!this.dataStore.length
}
function front () {
    return this.dataStore[0]
}
function back () {
    return this.dataStore[this.dataStore.length - 1]
}
function toString () {
    return this.dataStore.reduce((total, curr) => {
        total += curr
    })
}
//  测试
var queue = new Queue()

注：队列是一种比较重要的数据结构，诸如，排队，排序问题，利用队列将是非常好的解决方式。

React作为当前最为流行的三大前端技术栈之一，备受大家开发者的关注。我们就来讲讲React技术栈的设计初衷是什么？打开React的官网可以醒目的看到一行大字—用于构建用户界面的JavaScript库。这基本就概括了React的核心：构建用户界面。

声明式

React是声明式的编码方式，这使得React构建用户界面变的异常简单，这可以为应用的每一个状态设计简洁的UI视图，当数据改变时，React可以更有效的更新并且正确的渲染组件。以声明式编写UI，可以让代码更加可靠并方便调试。

组件化

组件化应该算是React的又一大特点，React里使用了更加简化的组建模式，它将整个UI上的每一个功能模块定义成组件。然后将小的组件通过组合或者嵌套的方式再构成更大的组件。React组件具有以下特点：

• 可组合：可以将简单的组件组合成复杂的组件
• 可重用：每个组件都是独立的，可以被其他组件调用
• 可维护：组件是独立的，将逻辑和UI封装，可维护性更高
• 可测试：组件的独立性决定了组件更容易测试

一次学习，随处遍写

我认为React最强大的地方就在于一次学习，随处编写。就是说，无论你现在用的是什么技术栈，都可以随时引入React来开发新特性，而不需要重构现在的代码。React同时也支持服务端渲染，或者使用React Native开发原生App。React组件可以映射为对应的原声控件。在输出憝时候，到底输出的是web Dom, Ios，android控件是由平台决定的。

虚拟DOM

当前Web应用越来越广泛。性能方面是一个不得不考虑的问题。传统页面每次刷新页面，都需要手动更新dom,这样性能的消耗是非常大的，因此，React使用虚拟DOM这一JavaScript对象树在每次页面更新后都会重新重新计算虚拟DOM，并且和上一次的虚拟DOM做对比，然后将变化的虚拟DOM更新到真实DOM上。这样就可以大大降低直接更新真是DOM带来的性能消耗。当然React也提供了shouldComponentUpdate这样的生命周期函数，和pureComponent来减少不必要的虚拟DOM的对比，以保证性能。

函数式编程

函数式编程并不是起源于React,但是在我看来一定是扬于React,在新版本的React开发中，React提倡开发者使用函数式编程来开发组件。这样可以减少冗余代码，此外由于组件自身就是函数，更利于测试。

列表的定义：列表是一组有序的数据。其中的元素可以是任意类型。列表一般有的属性为：

• listSize: 保存列表中元素的个数；
• pos: 列表中当前元素的位置；
• length(): 列表中元素的个数；
• clear(): 清空列表；
• toString(): 返回列表中的元素；
• getElement(): 返回当前位置的元素；
• insert(): 在现有元素的前后插入某个元素；
• append(): 在列表的末尾添加元素；
• find(): 查找列表中的指定元素；
• remove(): 删除列表中的指定元素；
• front(): 将当前元素移动到列表的第一个元素；
• end(): 将当前元素移动到列表的最后一个元素；
• pre(): 将当前元素前移一位；
• next(): 将当前元素后移一位；
• hasNext(): 判断后一位元素；
• hasPre(): 判断前一位元素；
• currPos(): 返回列表的当前位置；
• moveTo(): 将当前元素移动到指定位置；
• contains(): 判断给定的元素是不是包含在列表中。

  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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

  function List () { // 保存在列表中的数据 this.dataStore = [] // 列表的当前位置 this.pos = 0 // 列表的元素个数 this.listSize = 0 this.append = append this. } function append (item) { this.dataStore[this.listSize++] = item } function find (item) { for (let i = 0; i < this.dataStore.length;i++) { if (this.dataStore[i] === item) { return i } } return -1 } function remove (item) { // 先查找到要删除元素的位置 let index = find(item) // 判断是否找到了该元素 if (index > 0) { // splice方法删除找到的元素 this.dataStore.splice(index, 1) // 整个列表的长度减1 --this.listSize return true } return false } function toString () { return this.dataStore } // item 要插入的元素 // after在那个元素后插入 function insert (item, after) { let index = find(after) if (index > 0) { this.dataStore.splice(index + 1, 0, item) ++this.listSize return true } return false } function clear () { delete this.dataStore this.listSize = 0 this.pos = 0 } function contains (item) { for (let i = 0; i < this.dataStore.length; i++) { if (this.dataStore[i] === item) { return true } } return false } function length () { return this.listSize } function front () { this.pos = 0 } function end () { this.pos = this.listSize - 1 } function currPos () { return this.pos } function moveTo (pos) { this.pos = pos } function getElement () { return this.listStore[this.pos] } function pre () { --this.pos } function next () { if (this.pos < this.listSize) { ++this.pos } } function hasNext () { return this.pos < this.listSize } function hasPre () { return this.pos >= 0 } // 测试 let list = new List()

  注：列表的运用看起来和数组区别不是很大，但是这里重要的是运用到像列表中插入元素的方法。

栈的定义：栈是一种特殊的列表,栈内的元素只能通过栈的一端去访问，就是栈顶，所以栈就有了先进后出的特点。也就是说除了栈顶可以访问栈内元素，其他都不可以。一般操作栈的方法有以下三个：

• push(): 将元素押入到栈内；
• pop(): 从栈顶删除一个元素，永久性从栈顶删除；
• peek(): 返回栈顶元素，不删除栈顶元素；
• clear(): 清除栈；
• top：保存栈顶元素。

  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

  function Stack () { // 存储数据的数组 this.dataStore = [] // 栈顶元素 this.top = 0 // 押入栈的方法 this.push = push // 删除栈顶元素的方法 this.pop = pop // 返回栈顶元素的方法 this.peek = peek // 清楚栈的方法 this.clear = clear // 保存栈的长度 this.length = length } function push (item) { this.dataStore[this.top++] = item } function pop (item) { return this.dataStore[this.top--] = item } function peek (item) { return this.dataStore[this.top - 1] } function clear () { this.top = 0 } function length () { return this.top } // 测试 let stack = new Stack()

  注：栈的运用还是有多种，最为典型的如，判断字符串回文，递归计算某个数的阶乘，将一个数制转换成另一种数制。

题目：实现一个strStr()方法，要求strStr有俩个参数，hayStack和needle参数，找出字符串hayStack中needle的位置，并返回这个位置。如果找不到就返回-1.

解析：查找位置，只能双层遍历，依次比对。

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

var strStr = (haystack, needle) => {
    for (let i = 0; i <= haystack.length; i++) {
        let a = i, b = 0
        while (b < needle.length &&
            haystack[a] === needle[b]) {
            a++
            b++
        }
        if (b === needle.length) return i
    }
    return -1
}
strStr('', '')  //  0
strStr('hello', 'll')   //  2
strStr('aaaaa', 'bba')  //  -1

注意：整个代码结构是比较清晰易懂的，但是有几个地地方是需要注意：

• for循环中i是要小于等于（<=）haystack.length,这是因为haystack和needle都可能出现为空的情况；
• 双层循环，要用变量接一下外层循环的变量，这里需要知道的是，双层遍历，外层循环一次，内层循环要全循环完，才能开始外层的第二次循环，以此类推；
• 注意while循环的条件。

That’s all!这就是KMP算法。

题目：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解析：看到这个题，与上一个删除有序数组中的重复元素，很相似，只不过这次要删除的元素被指定了，而且数组也不是有序的，但是实现起来要比之前简单，看代码：

1
2
3
4
5
6
7
8
9
10
11

var removeDuplicates = function(nums, val) {
    if (!nums) return
    let j = 0
    for (let i = 0;i < nums.length; i++) {
        if (nums[i] !== val) {
            nums[j] = nums[j]
        }
        j++
    }
    return j
}

That’s all!

题目：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

分析：给定一个有序的数组，删除重复元素，看到这个条件，我就能突然想到了冒泡排序，那么自然而然的就有了双指针的思路。

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

var removeDuplicates = function(nums) {
    if (!nums) return
    if ( nums && nums.length <= 1) return nums.length
    let i = 0
    let j = 1
    while (j < nums.length) {
        // 如果前一个和后一个不相等
        //  那么就说明这俩个元素不重复，i++
        if (nums[i] !== nums[j]) {
            nums[i+1] = nums[j]
            i++
        }
        j++
    }
    return i+1
};
removeDuplicates([0,0,1,1,1,2,2,3,3,4])
//  5

That’s all!

题目：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

解析：因为括号是成对出现的，所以，我们首先可以判断一下长度，如果是奇数，那么直接返回false。其次，我们很容易就可以想到栈的思想，因为栈的特点是先进后出。所以，我们可以栈的近出，来比对是否是有效字符串。

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

//  通过字典来存储括号对
const dic = {'}': '{', ')': '(', ']': '['}
var isValid = function(s) {
    //  判断字符串是不是奇数
    if (!s || s.length % 2 !==0) return false
    let stack = []
    for (let key of s) {
        //  如果是向右侧的括号押入栈中
        if (key === '{' || key === '(' || key === '[') {
            stack.push(key)
        } else {
            //  如果栈为空，说明括号对缺乏向右侧的半边，返回false
            //  依次出栈与入栈不同，那么就返回false
            if (!stack.length || stack.pop() !== dic[key]) {
                return false
            }
        }
    }
    //  最终如果栈为空，那么字符串是有效的返回true
    return !stack.length
}
isValid('[()]{}')   //  true

注：利用不同数据结构，本题中主要是利用栈结构的原理，相对比较简单。

题目：给定一个数组，其元素是由如果干个字符串组成，那么请找到他们从开始起的最长公共元素，如果没有返回空。例如[‘flower’, ‘flow’, ‘flor’], 则返回flo。
解析：看到这个题，不知道你是不是就想到了十大基础排序中的选择排序的思想，我们只需要通过选择排序的思想比较第一轮即可。比如拿出数组中的第一个元素，然后与后面的相比即可得出结果。

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

var longestCommonPrefix = (arr) => {
    if (!arr) return ''
    if (arr.length <= 1) return arr[0]
    let pod = arr[0]
    for (var i = 0; i < pod.length; i++) {
        let j = 0
        let isTrue = true
        while (j < arr.length) {
            if (arr[j][i] !== pod[i]) {
                isTrue = false
                break
            }
            j++
        }
        if (!isTrue) break
    }
    return pod.substring(0, i)
}

longestCommonPrefix(["flower","flow","flight"])
//  "fl"

注：思想很简单，当然这也是建立在都是LeeCode上简单题的基础上，这里有个坑切记，for循环中变量i不能用let声明，要用var生明。

题目：将罗马数字转为整数，罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。对应结构为：

1
2
3
4
5
6
7
8

字符  数值
I     1
V     5
X     10
L     50
C     100
D     500
M     1000

例如：罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II。下面情况为特殊情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

解析：看到这个题，我突然就想到了选择排序的思想。我们通过记住当前位置的值，比较相邻位置的大小来决定计算方式，是加还是减。就这么简单。

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

const roman = { I:1, V:5, X:10, L:50, C:100, D:500, M:1000 }
var romanToInt = (s) => {
    if (!s) return
    let sum = 0
    let pre = roman[s[0]]
    for (let i = 0; i < s.length; i++) {
        let num = roman[s[i]]
        //  这里为特殊情况说明是左边比右边小
        if (pre < num) {
            sum -= pre
        } else {
            sum += pre
        }
        // 更新pre的值
        pre = num
    }
    sum += pre
    return sum
}
console.log(romanToInt('III')) //    3
console.log(romanToInt('IV')) //    4

That’s all!十大基础算法是重点，这就是九阳神功内功心法，一通百通。

题目：给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

解析：分析题目中的点。

• 负数不是回文数

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

  var isPalindrome = function(x) { x = x.toString() if (!x) return false let isTrue = false let left = 0 let right = x.length - 1 while (left <= right) { isTrue = x[left] === x[right] left++ right-- if (!isTrue) return isTrue } return isTrue };

  That’s all!整体思路就是从俩边向中间循环，只要遇到不相等就跳出循环返回false。

题目：给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−2³¹,  2³¹ − 1] ，就返回 0。

解析：分析题目中的点。

• 整数，可以是正数，也可以是负数，这里需要注意负号；
• 反转后的结果有范围，注意范围，越界返回是0.

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

var reserve = (x) => {
    if (!x) return x
    let neg = x > 0 ? 1 : -1
    let str = ''
    x *= neg
    while (x > 0) {
        str += x % 10
        x = parseInt(x / 10)
    }
    if (str <= -2147483648
        || str >= 2147483647) {
            str = 0
    }
    return str * neg
}
reserve(123)
//  321
reserve(-321)
//  -123
reserve(2147483648)
//  0

注意：这里应该有一个优化的地方，就是越界的比较，其实并不需要比较2³¹次方。

前面说完了十种基础排序，是时候做一个总结了。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。


所以选择方法，还是要选择稳定的，时间复杂度和空间复杂度低的方法。