【笔试面试】算法与数据结构


阅读数:   

经典算法

排序

背包问题

普通算法

题目1:找出重复元素

数字 1~1000 放在含有 1001 个元素的数组中，其中只有唯一的一个元素值重复，其他数字均只出现一次。设计一个算法，将重复元素找出来，要求每个数组元素只能访问一次。

解答：根据异或运算的性质可知，当相同元素异或时，其运算结果为0；当相异元素异或时，其运算结果为非0；任何数与0进行异或运算，其运算结果为该数。本题中，正好可以使用到此方法，即将数组里的元素逐一进行异或运算，得到的值再与数字1,2,3,…,N进行异或运算，得到的最终结果即为所求的重复元素。

以数组[1,3,4,2,5,3]为例，(1^3^4^2^5^3)^(1^2^3^4^5) = (1^1)^(2^2)^(3^3^3)^(4^4)^(5^5) = 3

代码如下：

1
2
3
4
5
6
7
8
function findDup (arr) {
  if (!arr || arr.length < 1) return -1
  const len = arr.length
  let result = 0
  for (let i = 0; i < len; i++) result ^= arr[i]
  for (let i = 1; i < len; i++) result ^= i
  return result
}

题目2:数组最大最小值

给定数组[a1,a2,a3,…,an]，要求找出数组中的最大和最小值。假设数组中的值各不相同

解答：

1
2
3
// array 是数组[a1,a2,a3,…,an]
const max = Math.max.apply(null, array)
const min = Math.min.apply(null, array)

题目3:洗牌函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 获取一个在[min, max]的整数 
function getRandomNumber(min, max) {
     // [0, 1) -> [0, max-min+1) -> [min, max+1) -> [min, max]
     return Math.floor(Math.random() * (max - min + 1) + min);
 }

// 实现洗牌函数
function shuffle(arr) {
    // 浅拷贝
    let _arr = arr.slice();

    for(let i = 0; i < _arr.length; i++) {
        const j = getRandomNumber(0, i);
        [_arr[i], _arr[j]] =  [_arr[j], _arr[i]];
    }
    return _arr;
}

export shuffle;

题目4:数组扁平化

有一个数组，其值为 [1,[2,[3,4,2],2],5,[6]] ，如何才能输出 [1,2,3,4,2,2,5,6] ?

1
2
const arr =  [1,[2,[3,4,2],2],5,[6]] 
arr.toString().split(',').map(value => +value)

题目4:创建递增数组

不用循环语句（for while等）来创建一个长度为n的数组，每个元素的值等于它的索引

解答：代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 方法一：
function arrayGenerator(n){
    return Array(n).join('1').split('').map((item, index) => index)
}

// 方法二：ES6
function arrayGenerator(n){
    return [...new Array(len).keys()]
}

// 下面列举一个错误的方法
function arrayGenerator(n){
    let arr = []
    arr.length = 50  // 或者arr[49] = 1这种增加数组长度的方法
    arr = arr.map((item, index) => index)  // map不执行，因为iterator为空
    // // 验证(说明，该方式可以迭代Array, TypedArray, String, Map, Set)
    // const arrIterator = arr[Symbol.iterator]()
    // arrIterator.next() // {value: undefined, done: true}
}

数据结构

链表

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
// 链表结点
function node(id, name) {
    this.id = id  // 结点id
    this.name = name // 结点数据
    this.next = null // 下一个结点
}

// 单链表
function linkList(id, name) {
    this.header = new node(id, name)  // 链表头结点(平时工作中，这里一般是存储一些链表的相关信息)
}

// 生成测试数据
function generatorDemoList(arr){
    const lists = new linkList()
    const array = arr || [1,3,1,5,5,7]
    array.forEach((item, index) => {
        lists.addLink(new node(index,item))
    })
    return lists
}

linkList.prototype = {
    // 添加节点数据
    addLink: function(node){ 
        let current = this.header
        while(current.next != null) {
            if(current.next.id > node.id) break // 这里可以根据实际情况定义
            current = current.next
        }
        node.next = current.next
        current.next = node
    },
    // 删除节点数据
    removeLink: function(node){ 
        let current = this.header
        while(current.next != null) {
            if(current.next.id === node.id) break
            current = current.next
        }
        current.next = node.next
        node.next = null
    },
    // 清空链表
    clear: function(){ 
        this.header = null
    },
    // 获取链表
    getLinkList: function(){ 
        let current = this.header 
        if(current === null || current.next === null) return console.log("链表为空")
        let txt = ""
        while(current.next !== null) {
            txt += current.next.name
            if(current.next.next === null) {
                break
            } else {
                txt += "-->"
            }
            current = current.next
        }
        console.log(txt)   
    },
    // 对链表进行逆序
    reverse: function(){
        let header = this.header 
        if(header === null || header.next === null) return console.log("链表为空")
        let pre = null // 前驱节点
        let cur = null // 当前节点
        let next = null // 后继节点
        // 把链表的首节点变成尾节点
        cur = header.next 
        next = cur.next
        cur.next = null
        pre = cur
        cur = next
        // 使当前遍历到的结点cur指向其前驱节点
        while(cur.next != null) {
            next = cur.next
            cur.next = pre
            pre = cur
            cur = cur.next
            cur = next
        }
        // 最后一个结点指向倒数第二个结点
        cur.next = pre
        // 链表头结点指向原来链表的尾结点
        header.next = cur
    },
    // 删除无序单链表中重复的结点（双重for循环找到重复结点删除）
    removeDup: function(){
        let header = this.header
        if(header === null || header.next === null) return 
        let outerCur = header.next // 外层循环指针
        let innerCur = null // 内层缓和指针
        let innerPre = null // innerCur的前驱节点
        let temp = null // 用来指向被删除结点的指针
        for(;outerCur != null; outerCur = outerCur.next) {
            for(innerCur = outerCur.next, innerPre = outerCur; innerCur !== null;) {
                // 找打重复的结点并删除
                if(outerCur.name == innerCur.name) {
                    tmp = innerCur
                    innerPre.next = innerCur.next
                    innerCur = innerCur.next
                } else {
                    innerPre = innerCur
                    innerCur = innerCur.next
                }
            }
        }
    },
    // 找出链表倒数第K个结点(设置两个指针，一个指针比另外一个先前移K步，当前面的指针指向null时，后面的指针指向的就是我们要找的元素)
    findLastK: function(k){
        let header = this.header
        if (k <= 0 || header === null || header.next === null) return

        let slow = null
        let fast = null
        slow = fast = header.next
        for(let i = 0; i < k; i++) {
            fast = fast.next
        }
        while(fast !== null) {
            slow = slow.next
            fast = fast.next
        }
        return slow
    }
}

var lists = generatorDemoList()
console.log("链表逆序前：")
console.log(lists.getLinkList())
console.log("链表逆序后：")
lists.reverse()
console.log(lists.getLinkList())
console.log("清空链表……\n\n")
lists.clear()

var lists = generatorDemoList()
console.log("删除重复结点前：")
console.log(lists.getLinkList())
console.log("删除重复结点后：")
lists.removeDup()
console.log(lists.getLinkList())
console.log("清空链表……\n\n")
lists.clear()

var lists = generatorDemoList()
console.log("链表为：")
console.log(lists.getLinkList())
console.log("链表倒数第4个元素结点是：")
console.log(lists.findLastK(4).name)
console.log("清空链表……\n\n")
lists.clear()

栈和队列

在 JavaScript 中，栈和队列可以用数组去表示。

1
2
3
4
5
6
var arr = [1,2,3,4,5]

arr.unshift(0)
arr.push(6)
arr.shift()
arr.pop()

二叉树

我这里有另外一篇介绍是链表二叉树的文章（https://www.ionluo.cn/blog/posts/6121effd.html）

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// 二叉树的结点
function BinaryTree(value, left, right) {
    this.value = value || null // 结点值
    this.left = left // 左子树结点
    this.right = right // 右子树结点
}

// 遍历打印的值
let printTxt = ''

BinaryTree.prototype = {
    /*
     * 检测当前节点是否是叶子结点
     * @return boolean 当结点非空并且有两个空的子树时为true，否则为false
     */
    isLeaf() {
        return !this.isEmpty() && this.left.isEmpty() && this.right.isEmpty()
    },
    // 检测结点是否为空
    isEmpty() {
        return this.value === null
    },
    // 读取结点值
    getValue() {
        if (this.isEmpty()) return false
        return this.value
    },
    // 给结点指定值
    attachValue(obj) {
        if (!this.isEmpty()) return false
        this.value = obj
        this.left = new BinaryTree()
        this.right = new BinaryTree()
    },
    // 删除结点值，使得结点为空
    detachValue() {
        if (!this.isLeaf()) return false
        this.value = null
        this.left = null
        this.right = null
        return this.value
    },
    // 读取左子树
    getLeft() {
        if (this.isEmpty()) return false
        return this.left
    },
    // 读取右子树
    getRight() {
        if (this.isEmpty()) return false
        return this.right
    },
    // 前序遍历
    preorderTraversal() {
        if (this.isEmpty()) return 
        printTxt += ' ' + this.getValue()
        this.getLeft().preorderTraversal()
        this.getRight().preorderTraversal()
    },
    // 中序遍历
    inorderTraversal() {
        if (this.isEmpty()) return 
        this.getLeft().inorderTraversal()
        printTxt += ' ' + this.getValue()
        this.getRight().inorderTraversal()
    },
    // 后序遍历
    postorderTraversal() {
        if (this.isEmpty()) return 
        this.getLeft().postorderTraversal()
        this.getRight().postorderTraversal()
        printTxt += ' ' + this.getValue()
    },
    // 当前结点值与传入的值做比较
    compare(value){
        return value - this.getValue()
    },
    // 给二叉排序树插入指定的值
    insert(value) {
        if (this.isEmpty()) return this.attachValue(value)
        const diff = this.compare(value)
        if(diff < 0){
            this.getLeft().insert(value)
        } else if (diff > 0) {
            this.getRight().insert(value)
        }
    }
}

const arr = [1,2,3,4,5,6,7,8,9,10]
console.log("数组join：", arr.reduce((accumulator, current, index, array) => {
    return accumulator + " " + current
}))

const root = new BinaryTree()
// 将有序数组arr放入二叉树中
function setTree(arr, root){
    const len = arr.length
    if(len < 2) return root.insert(arr[0])
    const middle = Math.floor(len/2)
    const left = arr.slice(0,middle)
    const right = arr.slice(middle+1)
    root.insert(arr[middle])
    setTree(left,root.left)
    if(len > 2){
        setTree(right, root.right)
    }
}
setTree(arr,root)
root.inorderTraversal()
console.log("数组转换成树的中序遍历结果为：", printTxt)

图

https://blog.csdn.net/qq_38689395/article/details/106983342

1

本文作者： ionluo
本文链接： http://www.ionluo.cn/blog/posts/8b6308d0.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
知识共享许可协议

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true