Data Structure(JS)

发表于 | 更新于 | 分类于 | | 阅读次数 |

一、数据结构

1、数组

1) 创建数组：

1
2
3
4
5
6
7
8
var daysOfWeek = new Array();
var daysOfWeek = new Array(7);
var daysOfWeek = new Array('Sun', 'Mon', 'Tue', 'Wed', 'Thurs', 'Fri', 'Sat');
var daysOfWeek = [];
var daysOfWeek = ['Sun', 'Mon', 'Tue', 'Wed', 'Thurs', 'Fri', 'Sat'];
console.log(daysOfWeek);

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
var numbers = [1,2,3];
//加到末尾------
numbers[numbers.length] = 4;
numbers.push(5,6); //可以push一至多个元素到数组末尾
//加到首位------
//从后往前遍历，挨个后移覆盖，第一个元素空出填新元素
for(var i = numbers.length; i >= 0; i--){
    numbers[i] = numbers[i - 1];
}
numbers[0] = -1;
//unshift
numbers.unshift(-2, -3);//可以unshift一至多个元素。把整个参数当一个数组整体插入，最后结果-2在-3的前面
//删除末尾元素-----
numbers.pop();
//删除首位元素-----
//从前往后遍历，挨个前移覆盖，数组长度不变，最后一个元素为undefined,注意访问该数组时就要遍历条件i < numbers.length - 1
for(var i = 0; i < numbers.length; i++){
    numbers[i] = numbers[i + 1];
}
//shift真正删除 数组长度减1
numbers.shift(); 
//删除任意位置的任意个元素-------
numbers.splice(5,3);//删除从索引5开始的3个元素
//添加任意个元素到任意位置
numbers.splice(5,0,2,3,4);//添加的第一个元素(2)索引为5

3) 多维数组

1
2
3
matrix3x3x3.length //第一维长度
matrix3x3x3[i].length //第二维长度
matrix3x3x3[i][j].length //第三维长度

4). 数组方法

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
//数组合并。参数可传元素、数组、对象
var newArr = arr1.concat(0, 1, arr2);
//every迭代器 如果isEven函数对数组每一项都返回true，则返回true。
numbers.every(isEven);//isEven函数事先定义好
//some迭代器  如果数组中有一个元素能返回true，则返回true.
numbers.some(isEven);
//forEach迭代器
numbers.forEach(function(){});
//返回返回每个元素的运行结果的map迭代器
var myMap = numbers.map(isEven); 
//返回运行结果为true的元素组成的数组 filter迭代器
var evenNumbers = numbers.filter(isEven);
//reduce迭代器
numbers.reduce(function(previous, current, index){ //累加数组求和
    return previous + current;
});
//搜索和排序
numbers.reverse(); //对原数组反序
numbers.sort(); //默认当字符串排序:看ASCII码，大写字母码小
numbers.sort(function(a, b){ //写sort的比较函数时，返回负数说明第一个参数排在前面。
    return a - b; //升序
    //return b - a; //降序
});
numbers.indexOf(10);//元素10第一次出现的索引，没有返回-1
numbers.lastIndexOf(10);//元素10最后一次出现的索引，没有返回-1
numbers.toString(); //返回一个字符串，用逗号连接
numbers.join('-'); //该方法常用于编解码后发到服务器

  • 关于 valueOf(), typeof(), instanceof

var arr = [1,2,3];//数组的valueOf()全等于自身
类型 | arr | arr.valueOf()
—|—|—
typeof() | object | object
instanceof Object | true | true
instanceof Array | true | true

var bool = false; //全等
类型 | bool | bool.valueOf()
—|—|—
typeof() | boolean | boolean
instanceof Object | false | false
instanceof Boolean | false | false

var newBool = new Boolean(false); //相等不全等
类型 | newBool | newBool.valueOf()
—|—|—
typeof() | object | boolean
instanceof Object | true | false
instanceof Boolean | true | false
因为newBool是用Boolean new出来的,Boolean继承自Object

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
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
//创建栈
function Stack(){
    var items = [];
    
    this.push = function(element){
        items.push(element);
    };
    
    this.pop = function(){
        return items.pop();
    };
    
    this.peek = function(){
        return item[items.length - 1];
    };
    
    this.isEmpty = function(){
        return items.length == 0;
    };
    
    this.size = function(){
        return items.length;
    };
    
    this.clear = function(){
        items = [];
    };
    
    this.print = function(){
        console.log(items.toString());
    };
}
//应用：十进制转二进制，只看整数部分（除以2取余，逆序排列）；小数部分是乘2取整，顺序排列
function divideBy2(decNumber){
    var remStack = new Stack(),
        rem, binaryString = '';
        
    while(decNumber > 0){
        rem = Math.floor(decNumber % 2); //余数为rem
        remStack.push(rem);
        decNumber = Math.floor(decNumber / 2);
    }
    
    while(!remStack.isEmpty()){
        binarString += remStack.pop().toString();
    }
    
    return binaryString;
}
//十进制转二、八、十六进制的通用代码
function baseConverter(decNumber, base){
    var remStack = new Stack(),
        rem, 
        baseString = '',
        digis = '0123456789ABCDEF';
        
    while(decNumber > 0){
        rem = Math.floor(decNumber % base); //余数为rem
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base);
    }
    
    while(!remStack.isEmpty()){
        baseString += digits[remStack.pop()];
    }
    
    return baseString;
}
//用栈平衡括号(ES6实现)
function parenthesesChecker(symbols){
    let stack = new Stack(),
        balanced = true,
        index = 0,
        symbol, top,
        opens = "([{",
        closers = ")]}";
    while (index < symbols.length && balanced){
        symbol = symbols.charAt(index);
        if (opens.indexOf(symbol) >= 0){
            stack.push(symbol);
            console.log('open symbol - stacking ${symbol}');
        } else {
            console.log('close symbol ${symbol}');
            if (stack.isEmpty()){
                balanced = false;
                console.log('Stack is empty, no more symbols to pop and compare');
            } else {
                top = stack.pop();
                //if (!matches(top, symbol)){
                if (!(opens.indexOf(top) === closers.indexOf(symbol))) {
                    balanced = false;
                    console.log('poping symbol ${top} - is not a match compared to ${symbol}');
                } else {
                    console.log('poping symbol ${top} - is is a match compared to ${symbol}');
                }
            }
        }
        index++;
    }
    if (balanced && stack.isEmpty()){
        return true;
    }
    return false;
}
console.log(parenthesesChecker('{([])}')); //true
console.log(parenthesesChecker('{{([][])}()}')); //true
console.log(parenthesesChecker('[{()]')); //false
//汉诺塔问题
function towerOfHanoi(n, from, to, helper){
    if (n > 0){
        towerOfHanoi(n-1, from, helper, to);
        to.push(from.pop());
        console.log('-----');
        console.log('Source: ' + from.toString());
        console.log('Dest: ' + to.toString());
        console.log('Helper: ' + helper.toString());
        towerOfHanoi(n-1, helper, to, from);
    }
}
var source = new Stack();
source.push(3);
source.push(2);
source.push(1);
var dest = new Stack();
var helper = new Stack();
towerOfHanoi(source.size(), source, dest, helper);
source.print();
helper.print();
dest.print();

3、队列

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
//普通队列
function Queue(){
    var items = [];
    
    this.enqueue = function(element){
        items.push(element);
    };
    
    this.dequeue = function(element){
        return items.shift();
    };
    
    this.front = function(){
        return items[0];
    };
    
    this.isEmpty = function(){
        return items.length == 0;
    };
    
    this.size = function(){
        return items.length;
    };
    
    this.print = function(){
        console.log(items.toString());
    };
}
//优先队列:按优先级从小到达（从高到底）排序；优先级相同的插入早的在前面。
function PriorityQueue(){
    var items = [];
    
    function QueueElement(element, priority){
        this.element = element;
        this.priority = priority;
    }
    
    this.enqueue = function(element, priority){
        var queueElement = new QueueElement(element, priority);
        
        if(this.isEmpty()){
            items.push(queueElement);
        }else{
            var added = false;
            for(var i = 0; i < items.length; i++){
                if(queueElement.priority < items[i].priority){//数字越小优先级越高
                    items.splice(i, 0, queueElement);
                    added = true;
                    break;
                }
            }
            if(!added){
                items.push(queueElement);
            }
        }
    }
}
//循环队列-击鼓传花
function hotPotato(nameList, num){
    var queue = new Queue();
    
    for(var i = 0; i < nameList.length; i++){
        queue.enqueue(nameList[i]);
    }
    
    var eliminated = '';
    while(queue.size() > 1){
        for(var i = 0; i < num; i++){
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();
        console.log(eliminated + "out!");
    }
    return queue.dequeue();
}

4、链表

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
//普通链表
function LinkedList(){
    var Node = function(element){ //节点辅助类
        this.element = element;
        this.next = null;
    };
    
    var length = 0;
    var head = null;
    
    this.append = function(element){
      var node = new Node(element),
        current;
        
        if(head == null){
            head = node;
        }else{
            current = head;
            
            //循环列表，直到找到最后一项
            while(current.next){
                current = current.next;
            }
            current.next = node;
        }
        length++;
    };
    
    this.removeAt(position){
        //检查越界
        if(position > -1 && position < length){
            var current = head,
                previous,
                index = 0;
            
            //移除第一项
            if(position == 0){
                head = current.next;
            }else{
                while(index < position){
                    previous = current;
                    current = current.next;
                    index++;
                }//跳出循环时，index == position,current为position处的节点
                
                previous.next = current.next;
            }
            length--;
            return current.element;
        }else{
            return null;
        }
    };
    
    this.insert = function(position, element){
        if(position > -1 && position < length){
            var node = new Node(element),
                current = head,
                previous,
                index = 0;
            
            if(position == 0){
                node.next = current;
                head = node;
            }else{
                while(index < position){
                    previous = current;
                    current = current.next;
                    index++;
                }
                node.next = current;
                previous.next = node;
            }
            length++;
            
            return true;
        }else{
            return false;
        }
    };
    
    this.toString = function(){
        var current = head,
            string = '';
            
        while(current){
            string += "," + current.element;
            current = current.next;
        }
        
        return string.slice(1); //不显示第一个","
    };
    
    this.indexOf = function(element){
        var current = head,
            index = 0;
        
        while(current){
            if(element === current.element){
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    };
    
    this.remove = function(element){
        var index = this.indexOf(element);
        return this.removeAt(index);
    };
    
    this.isEmpty = function(){
        return length === 0;
    };
    
    this.size = functi;on(){
        return length;
    };
    
    this.getHead = function(){//head是LinkedList的私有变量，在类的外部实现循环访问列表时通过该方法获取head
        return head;
    };
}
//双向链表
function DoublyLinkedList(){
    var Node = function(element){
        this.element = element;
        this.next = null;
        this.prev = null;
    };
    
    var length = 0;
    var head = null;
    var tail = null;
    
    this.insert = function(position, element){
        if(position >= 0 && position <= length){
            var node = new Node(element),
                current = head,
                previous,
                index = 0;
            
            if(position == 0){ //如果在第一个位置插入
                if(!head){
                    head = node;
                    tail = node;
                }else{
                    node.next = current;
                    current.prev = node;
                    head = node;
                }
            }else if(position === length){ //如果在末尾插入
                current = tail;
                current.next = node;
                node.prev = current;
                tail = node;
            }else{ //如果在不是首尾的中间插入
               while(index < position){
                   previous = current;
                   current = current.next;
                   index++;
               } 
               node.next = current;
               previous.next = node;
               
               current.prev = node;
               node.prev = previous;
            }
            length++;
            return true;
        }else{
            return false;
        }
    };
    
    this.removeAt = function(position){
        if(position > -1 && position < length){
            var current = head,
                previous,
                index = 0;
                
            if(position === 0){ //如果删除第一项
                head = current.next;
                
                if(length === 1){ //如果链表就只有一项,删除后要更新tail
                    tail = null;
                }else{
                    head.prev = null;
                }
            }else if(position === length - 1){ //如果删除最后一项
                current = tail;
                tail = current.prev;
                tail.next = null;
            }else{
                while(index < position){
                    previous = current;
                    current = current.next;
                }
                
                previous.next = current.next;
                current.next.prev = previous;
            }
            length--;
            return current.element;
        }else{
            return null;
        }
    };
}
//循环链表 tail.next = head; head.prev = tail;
function CircularLinkedList(){
    var Node = function(element){
        this.element = element;
        this.next = null;
    };
    
    var length = 0;
    var head = null;
    
    this.append = function(element){
         var node = new Node(element),
            current;
            
        if(head == null){
            head = node;
        }else{
            current = head;
            
            while(current.next != head){ //这里不同 最后一个节点不为null而是指向head
                current = current.next;
            }
            current.next = node;
        }
        
        node.next = head; //最后记得将添加到末尾的节点指向head
        length++;
    };
    
    this.removeAt = function(position){
        if(position > -1 && position < length){
            var current = head,
                previoius,
                index = 0;
                
            if(position == 0){//移除第一项注意改变末尾几点的指向
                while(current.next !== head){
                    current = current.next;
                }
                head = head.next;
                current.next = head;
            }else{
                while(index < position){
                    previous = current;
                    current = current.next;
                    index++;
                }
                previous.next = current.next;
            }
            length--;
            
            return current.element;
        }else{
            return null;
        }
    };
    
    this.insert = function(position, element){
        if(position >= 0 && position < length){
            var node = new Node(element),
                current = head,
                previous,
                index = 0;
            
            if(position === 0){ //如果在第一个位置添加，比普通链表复杂：要注意原链表是否为空
                if(!head){
                    head = node;
                    node.next = head; //添加后链表长度为1
                }else{
                    node.next = current;
                    while(current.next != head){
                        current = current.next;
                    }
                    head = node;
                    current.next = head;
                }
            }else{
                while(index < position){ //应该不用考虑在最后插入，有append
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            length++;
            return true;
        }else{
            return false;
        }
    };
    
    this.toString = function(){
        var current = head,
            s = current.element; //如果s的初始化不为空，直接赋值为第一个元素
        
        while(current.next != head){
            current = current.next; //并且如果这两句的顺序
            s += ',' + current.element;
        }
        
        return s.toString(); //这样就不需要slice(1)了
    };
    
    this.indexOf = function(element){
        var current = head,
            index = -1;
        //check first item
        if (element == current.element){
            return 0;
        }
        index++;
        //check in the middle of the list
        while(current.next !== head){
            if (element == current.element){
                return index;
            }
            current = current.next;
            index++;
        }
        //check last item
        if (element == current.element){
            return index;
        }
        return -1;
    };
    this.remove = function(element){
        var index = this.indexOf(element);
        return this.removeAt(index);
    };
    
    this.isEmpty = function(){
        return length === 0;
    };
    
    this.size = function() {
        return length;
    };
    
    this.getHead = function(){
        return head;
    };
}

5、集合

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
function Set(){
    var items = {}; //使用对象表示集合
    
    this.has = function(value){
        return value in items;
    };
    
    //更好的实现方式
    this.has = function(value){
        return items.hasOwnProperty(value);
    };
    
    this.add = function(value){
        if(!this.has(value)){
            items[value] = value; //同时作为键和值保存
            return true;
        }
        return false;
    };
    
    this.remove = function(value){
        if(this.has(value)){
            delete items[value];
            return true;
        }
        return false;
    };
    
    this.clear = function(){
        items = {};
    };
    
    this.size = function(){
        return Object.keys(items).length;
    };
    
    this.sizeLegacy = function(){
        var count = 0;
        for(var prop in items){
            if(items.hasOwnProperty(prop)){ //避免计算原型的属性
                ++count;
            }
        }
        return count;
    ;
    
    this.values = function(){ //Chrome Firefox
        return Object.keys(items);
    };
    
    this.valuesLegacy = function(){
        var keys = [];
        for(var key in items){
            keys.push(key);
        }
        return keys;
    };
    
    this.union = function(otherSer){ //求并集
        var unionSet = new Set();
        
        var values = this.values();
        for(var i = 0; i < values.length; i++){
            unionSet.add(values[i]);
        }
        
        values = otherSet.values();
        for(var i = 0; i < values.length; i++){
            unionSet.add(values[i]);
        }
        
        return unionSet;
    };
    
    this.intersection = function(otherSet){
        var intersectionSet = new Set();
        
        var values = this.values();
        for(var i = 0; i < values.length; i++){
            if(otherSet.has(values[i])){
                intersectionSet.add(values[i]);
            }
        }
        
        return intersectionSet;
    };
    
    this.difference = function(otherSet){//不存在与otherSet中的元素
        var differenceSet = new Set();
        
        var values = this.values();
        for(var i = 0; i < values.length; i++){
            if(!otherSet.has(values[i])){
                differenceSet.add(values[i]);
            }
        }
        reutrn differenceSet;
    };
    
    this.subset = function(otherSet){//检测是不是otherSet的子集
        if(this.size() > otherSet.size()){
            return false;
        }else{
            var values = this.values();
            for(var i = 0; i < values.length; i++){
                if(!otherSet.has(values[i])){
                    return false;
                }
            }
            return true;
        }
    };
}

6、字典和散列表

字典

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 Dictionary(){
    var items = {};
    
    this.has = function(key){
        return key in items;
    };
    
    this.set = function(key, value){
        items[key] = value;
    };
    
    this.remove = function(key){
        if(this.has(key)){
            delete items[key];
            return true;
        }
        return false;
    };
    
    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    };
    
    this.values = function(){
        var values = [];
        for(var k in items){
            if(this.hasOwnProperty(k)){
                values.push(items[k])
            }
        }
    };
    
    //clear size keys方法与Set一样
    
    this.getItems = function(){
        return items;
    };
}

散列表

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
function HashTable(){
    var table = [];
    
    var loseloseHashCode = function(key){
        var hash = 0;
        for(var i = 0; i < key.length; i++){
            hash += key.charCodeAt(i); //ASCII码相加
        }
        return hash % 37;//为了得到比较小的数值，做除法取余
    };
    
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        console.log(position + ' - ' + key);
        table[position] = value;
    };
    
    this.get = function(key){
        return table[loseloseHashCode(key)];
    };
    
    this.remove = function(key){
        table[loseloseHashCode(key)] = undefined;
    };
    
    //------------------处理冲突------------------
    //方法一：分离链接：
    var ValuePair = function(key, value){
        this.key = key;
        this.value = value;
        
        this.toString = function(){
            return '[' + this.key + ' - ' + this.value + ']';
        };
    };
    //重写put get remove
    this.put = function(key, value){
        var position = loseloseHashCode[key];
        
        if(table[position] == undefined){
            table[position] = new LinkedList();
        }
        table[position].append(new ValuePair(key, value));
    };
    
    this.get = function(key){
        var position = loseloseHashCode[key];
        
        if(table[position] !== undefined){
            //遍历链表来寻找键/值
            var current = table[position].getHead();
            
            while(current.next){//第一个(只有一个节点时)和最后一个节点不会进入循环
                if(current.element.key === key){
                    return current.element.value;
                }
                current = current.next;
            }
            
            //检查元素在链表第一个或最后一个节点的情况
            if(current.element.key === key){
                return current.element.value;
            }
        }
        return undefined;
    };
    
    this.remove = function(key){
        var position = loseloseHashCode(key);
        if(table[position] !== undefined){
            var current = table[position].getHead();
            while(current.next){ //同上 不包括第一个节点(只有一个节点时)和最后一个节点
                if(current.element.key === key){
                    table[position].remove(current.element);
                    if(table[position].isEmpty()){//注意链表是否为空
                        table[position] = undefined;
                    }
                    return true;
                }
                current = current.next;
            }
            
            //检查是否为第一个或最后一个元素
            if(current.element.key === key){
                table[position].remove(current.element);
                if(table[position].isEmpty()){
                    table[position] = undefined;
                }
                return true;
            }
        }
        return false;
    };
    
    //方法二：线性探查 需要重写put get remove
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        
        if(table[position] == undefined){
            table[position] = new ValuePair(key, value);
        }else{
            var index = ++position;
            while(table[index] != undefined){
                index++;
            }
            table[index] = new ValuePair(key, value);
        }
    };
    
    this.get = function(key){
        var position = loseloseHashCode(key);
        
        if(table[position] !== undefined){
            if(table[position].key === key){
                return table[position].value;
            }else{
                var index = ++position;
                while(table[index] !== undefined && table[index] && table[index].key !== key){
                    index++;
                }
                if(table[index] && table[index].key === key){
                    return table[index].value;
                }
            }
        }
        return undefined;
    };
    
    this.remove = function(){
        同上，只是把return table[index].value都改为table[position] = undefined;
    }
    
    //更好的散列函数：插入和检索元素的时间更短，较低的冲突可能性
    var djb2HashCode = function(key){
        var hash = 5381;//初始化赋值一个质数
        for(var i = 0; i < key.length; i++){
            hash = hash * 33 + key.charCodeAt(i);//魔力数+ASCII码
        }
        return hash % 1013; //1013：随机数，比散列表大小要大一些
    }
}

7、树

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
//BinarySearchTree 二叉搜索树
function BinarySearchTree(){
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    };
    
    
    var root = null;
    
    this.insert = function(key){
        var newNode = new Node(key);
        
        if(root == null){
            root = newNode;
        }else{
            insertNode(root, newNode);
        }
    };
    
    var insertNode = function(node, newNode){ //辅助函数，私有
        if(newNode.key < node.key){
            if(node.left == null){
                node.left = newNode;
            }else{
                insertNode(node.left, newNode);
            }
        }else{
            if(node.right == null){
                node.right = newNode;
            }else{
                insertNode(node.right, newNode);
            }
        }
    };
    
    this.inOrderTraverse = function(callback){ //访问者模式 ??
        inOrderTraverseNode(root, callback);
    };
    
    var inOrderTraverseNode = function(node, callback){
        if(node !== null){
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    };
    
    this.preOrderTraverse = function(callback){
        preOrderTraverseNode(root, callback);
    };
    
    var preOrderTraverse = function(node, callback){
        if(node != null){
            callback(node.key);
            preOrderTraverseNode(node.left, callback);
            preOrderTraverseNode(node.right, callback);
        }
    };
    
    this.postOrderTraverse = function(callback){
        postOrderTraverseNode(root, callback);
    };
    
    var postOrderTraverseNode = function(node, callback){
        if(node != null){
            postOrderTraverseNode(node.left, callback);
            postorderTraverseNode(node.right, callback);
            callback(node.key);
        }
    };
    
    this.min = function(){
        return minNode(root);
    };
    
    var minNode = function(node){
        if(node){
            while(node && node.left !== null){ //沿着树的左边遍历
                node = node.left;
            }
            return node.key;
        }  
        return null;
    };
    //求最大值类似 沿着树的右边遍历
    
    //搜索特定值
    this.search = function(key){
        return searchNode(root, key);
    };
    
    var searchNode = function(node, key){
        if(node == null){
            return false;
        }
        if(key < node.key){
            return searchNode(node.left, key);
        }else if(key > node.key){
            return searchNode(node.right, key);
        }else{
            return true;
        }
    };
    
    //移除特定节点
    this.remove = function(key){
        roo = removeNode(root, key);
    };
    
    var removeNode = function(node, key){
        if(node == null){
            return null;
        }
        if(key < node.key){
            node.left = removeNode(node.left, key);//更新左子树
            return node;
        }else if(key > node.key){
            node.right = removeNode(node.right, key);//更新右子树
            return node;
        }else{ //找到了要删除的键
            //第一种情况：一个叶节点
            if(node.left === null && node.right === null){
                node = null;
                return node;
            }else if(node.left === null){//第二种情况：一个只有一个子节点的节点
                node = node.right;
                return node;
            }else if(node.right === null){
                node = node.left;
                return node;
            }
            //第三种情况：一个有两个子节点的节点
            var aux = findMinNode(node.right);//与求最小值类似，只不过不是返回节点的值而是返回节点
            node.key = aux.key;
            node.right = removeNode(node.right, aux.key);
            return node;
        }
    };
}
//AVL树：自平衡二叉搜索树。查找、插入和删除在平均和最坏情况下都是O(log n)。
//插入的数据有序时，普通的二叉搜索树会左右层数相差非常大，甚至最后变成链表的形式，影响查找效率。AVL树会好很多。
function AVLTree() {
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    };
    var root = null;
    this.getRoot = function(){
        return root;
    };
    var heightNode = function(node) {
        if (node === null) {
            return -1;
        } else {
            return Math.max(heightNode(node.left), heightNode(node.right)) + 1;
        }
    };
    var rotationLL = function(node) {
        var tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        return tmp;
    };
    var rotationRR = function(node) {
        var tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        return tmp;
    };
    var rotationLR = function(node) {
        node.left = rotationRR(node.left);
        return rotationLL(node);
    };
    var rotationRL = function(node) {
        node.right = rotationLL(node.right);
        return rotationRR(node);
    };
    var insertNode = function(node, element) {
        if (node === null) {
            node = new Node(element);
        } else if (element < node.key) {
            node.left = insertNode(node.left, element);
            if (node.left !== null) {
                if ((heightNode(node.left) - heightNode(node.right)) > 1){
                    if (element < node.left.key){
                        node = rotationLL(node);
                    } else {
                        node = rotationLR(node);
                    }
                }
            }
        } else if (element > node.key) {
            node.right = insertNode(node.right, element);
            if (node.right !== null) {
                if ((heightNode(node.right) - heightNode(node.left)) > 1){
                    if (element > node.right.key){
                        node = rotationRR(node);
                    } else {
                        node = rotationRL(node);
                    }
                }
            }
        }
        return node;
    };
    this.insert = function(element) {
        root = insertNode(root, element);
    };
    var parentNode;
    var nodeToBeDeleted;
    
    //--------removeNode看不懂------------
    var removeNode = function(node, element) {//node表示在哪棵AVL树上删除，element表示删除哪个值
        if (node === null) {
            return null;
        }
        parentNode = node;
        if (element < node.key) {
            node.left = removeNode(node.left, element);
        } else {
            nodeToBeDeleted = node;
            node.right = removeNode(node.right, element);
        }
        if (node === parentNode) { //remove node
            if (nodeToBeDeleted !== null && element === nodeToBeDeleted.key) {
                if (nodeToBeDeleted === parentNode) {
                    node = node.left;
                } else {
                    var tmp = nodeToBeDeleted.key;
                    nodeToBeDeleted.key = parentNode.key;
                    parentNode.key = tmp;
                    node = node.right;
                }
            }
        } else { //do balancing
            if (node.left === undefined) node.left = null;
            if (node.right === undefined) node.right = null;
            if ((heightNode(node.left) - heightNode(node.right)) === 2) {
                if (element < node.left.key) {
                    node = rotationLR(node);
                } else {
                    node = rotationLL(node);
                }
            }
            if ((heightNode(node.right) - heightNode(node.left)) === 2) {
                if (element > node.right.key) {
                    node = rotationRL(node);
                } else {
                    node = rotationRR(node);
                }
            }
        }
        return node;
    };
    this.remove = function(element) {
        parentNode = null;
        nodeToBeDeleted = null;
        root = removeNode(root, element);
    };
}
//红黑树：可以进行高效的中序遍历
//堆积树

8、图

  • 几个术语：度，路径，简单路径（不包含重复定点），环，连通图（图中每两个顶点之间都存在路径），有向图，无向图，强连通图（图中没量个顶点之间在双向上都存在路径）
  • 图的表示：邻接矩阵，邻接表，关联矩阵
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
function Graph(){
    var vertices = []; //存储顶点
    var adjList = new Dictionary(); //存储邻接表。键-值：顶点-邻接顶点数组
    
    this.addVertex = function(v){
        vertices.push(v);
        adjList.set(v, []);
    };
    
    this.addEdge = function(v, w){
        adjList.get(v).push(w);
        adjList.get(w).push(v);
    };
    
    this.toString = function(){
        var s = '';
        for(var i = 0; i < vertices.length; i++){
            s += vertices[i] + ' -> ';
            var neighbors = adjList.get(vertices[i]);
            for(var j = 0; j < neighbors.length; j++){
                s += neighbors[j] + ' ';
            }
            s += '\n';
        }
        return s;
    };
    
    //图的遍历
    //DFS：深度优先遍历：用栈存储待访问节点。顶点沿着路径被探索，存在新的相邻顶点就去访问。
    //BFS：广度优先遍历：用队列存储待访问节点。
    
    var initializeColor = function(){
        var color = [];
        for(var i = 0; i < vertices.length; i++){
            color[vertices[i]] = 'while'; //未访问过
        }
        return color;
    }
    
    this.bfs = function(v, callback){
        var color = initializeColor(),
            queue = new Queue();
        queue.enqueue(v);
        
        while(!queue.isEmpty()){
            var u = queue.dequeue(),
                neighbors = adjList.get(u);
            color[u] = 'grey';//经过队列了但是没有探索其相邻节点
            for(var i = 0; i < neighbors.length; i++){
                var w = neighbors[i];
                if(color[w] === 'white'){
                    color[w] = 'grey';
                    queue.enqueue(w);
                }
            }
            color[u] = 'black';//其相邻节点已全部探索完毕且该节点已出队列
            if(callback){
                callback(u);
            }
        }
    };
    
    //bfs应用：给定源顶点v，找出对每个顶点u，u和v之间的最短路径距离（以边的数量计）
    this.BFS = function(v){
        var color = initializeColor(),
            queue = new Queue(),
            d = [], //从v到u的距离d[u]
            pred = []; //前溯点pred[u]，用来推导出从v到其他每个顶点的最短路径
        queue.enqueue(v);
        
        for(var i = 0; i < vertices.length; i++){
            d[vertices[i]] = 0;
            pred [vertices[i]] = null;
        }
        
        while(!queue.isEmpty()){
            var u = queue.dequeue(),
                neightbors = adjList.get(u);
            color[u] = 'grey';
            for(var i = 0; i < neighbors.length; i++){
                var w = neibors[i];
                if(color[w] === 'white'){
                    d[w] = d[u] + 1;
                    pred[w] = u; //意即w是u的neighbors中的一个，因u的neighbors而进入队列
                    queue.enqueue(w);
                }
            }
            color[u] = 'black'; 
        }
        return {
            distances: d,
            predecessors: pred
        };
    };
    
    //测试：
    var graph = new Graph();
    var myVertices = ['A','B','C','D','E'];
    for(var i = 0; i < myVertices.length; i++){
        graph.addVertex(myVertices[i]);
    }
    graph.addEdge('A','B');
    graph.addEdge('A','C');
    graph.addEdge('A','D');
    graph.addEdge('B','E');
    var shortestPathA = graph.BFS(myVertices[0]);
    
    //求出A到各点最短路径长度后，利用前溯点数组构建从源顶点到其他各点的路径：
    var fromVertex = myVertices[0];//myVertices数组是用于测试的图的第一个顶点
    for(var i = 1; i < myVertices.length; i++){
        var toVertex = myVertices[i],
            path = new Stack();//路径用栈表示，因为下面是反向前溯，到时候就可以正向打印
        for(var v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]){
            path.push(v);
        }
        path.push(fromVertex);
        var s = path.pop();
        while(!path.isEmpty()){
            s += ' - ' + path.pop();
        }
        console.log(s);
    };
    
    this.dfs = function(callback){
        var color = initializeColor();
        for(var i = 0; i < vertices.length; i++){
            if(color[vertices[i]] === 'white'){
                dfsVisit(vertices[i], color, callback);
            }
        }
    };
    
    var dfsVisit = function(u, color, callback){
        color[u] = 'grey';
        if(callback){
            callback(u);
        }
        var neighbors = adjList.get(u);
        for(var i = 0; i < neighbors.length; i++){
            var w = neighbors[i];
            if(color[w] === 'white'){
                dfsVisit(w, color, callback);
            }
        }
        color[u] = 'black';
    };
    
    //改进的DFS
    var time = 0;
    this.DFS = function(){
        var color = initializeColor(),
            d = [], //顶点u的发现时间d[u]
            f = [], //顶点被标注为black，u的完成探索时间f[u]
            p = []; //顶点u的前溯点p[u]
        time = 0;
        
        for(var i = 0; i < vertices.length; i++){
            d[vertices[i]] = 0;
            f[vertices[i]] = 0;
            p[vertices[i]] = 0;
        }
        for(i = 0; i < vertices.length; i++){
            if(color[vertices[i]] === 'white'){
                DFSVisit(vertices[i], color, d, f, p);
            }
        }
        return {
            discovery: d,
            finished: f,
            predessors: p
        };
    };
    
    var DFSVisit = function(u, color, d, f, p){
        console.log('discovered: ' + u);
        color[u] = 'grey';
        d[u] = ++time;
        var neighbors = adjList.get(u);
        for(var i = 0; i < neighbors.length; i++){
            var w = neighbors[i];
            if(color[w] === 'white'){
                p[w] = u;
                DFSVisit(w, color, d, f, p);
            }
        }
        color[u] = 'black';
        f[u] = ++time;
        console.log("explored: " + u);
    };
    
    //改进后的DFS应用：拓扑排序，安排事情按照先后顺序发生（只用于有向无环图）：按照完成时间倒序排序。
}

单源正权值的最短路径问题：dijkstra算法。计算一个节点到其他所有节点的最短路径

image

image

二、排序算法

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
function ArrayList(){
    var array = [];
    
    this.insert = function(item){
        array.push(item);
    };
    
    this.toString = function(){
        return array.join();
    };
    
    //后面的swap都要根据这里的相应修改，应该把数组也传进来，直接在数组上修改。
    var swap = function(arr, i, j) {
        var tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    };
    
    //冒泡排序
    this.bubbleSort = function(){
        var length = array.length;
        for(var i = 0; i < length; i++){
            for(var j = 0; j < length - 1; j++){
                if(array[j] > array[j + 1]){
                    swap(array[j], array[j + 1]);
                }
            }
        }
    };
    
    //改进的冒泡排序(1)：从内循环减去外循环中已跑过的轮数，避免内循环中不必要的比较
    this.modifiedBubbleSort = function(){
        var length = array.length;
        for(var i = 0; i < length; i++){
            for(var j = 0; j < length - i - 1; j++){
                if(array[j] > array[j + 1]){
                    swap(array[j], array[j + 1]);
                }
            }
        }
    };
    
    //选择排序：找到最小值放在第一位，再找第二小的值放在第二位。。。
    this.selectionSort = function(){
        var length = array.length,
            indexMin;
        for(var i = 0; i < length - 1; i++){
            indexMin = i;
            for(var j = i; j < length; j++){
                if(array[indexMin] > array[j]){
                    indexMin = j;
                }
            }
            if(i != indexMin){
                swap(array[i], array[indexMin]);
            }
        }
    };
    
    //插入排序:假设第一项已经排序了，接下来它和第二项比较，将前两位排好序；接着第三项往前比较，排序前三项......
    this.insertionSort = function(){
        var length = array.length,
            j, temp;
        for(var i = 1; i < length; i++){
            j = i;//j为当前要排的数的索引
            temp = array[i]; //temp为当前要排的数
            while(j > 0 && array[j - 1] > temp){
            //每次都比较它前面的，不行就后退，同时j也后退，保持j后面的永远比j处的大；再继续看它前面的，直到找到比它小的就不后移了，直接填坑
                array[j] = array[j - 1];
                j--;
            }
        }
    };
    
    //归并排序：Firefox的Array.prototype.sort用归并排序实现。
    //分治思想(=>要递归)，将原始数组切分成小数组，直到每个小数组只有一个位置，接着将小数组归并成较大数组，直到最后只有一个排序完毕的大数组。
    this.mergeSort = function(){
        array = mergeSortRec(array);
    };
    var mergeSortRec = function(array){ //分治，递归
        var length = array.length;
        if(length === 1){ //递归终止条件。即数组长度为1时，不再分了。
            return array;
        }
        var mid = Math.floor(length / 2),
            left = array.slice(0, mid),
            right = array.slice(mid + 1, length);
        
        return merge(mergeSortRec(left), mergeSortRec(right));
    };
    
    var merge = function(left, right){ //负责合并和排序小数组来产生大数组
        var result = [],
            il = 0,
            ir = 0;
        
        while(il < left.length && ir < right.length){
            if(left[il] < right[ir]){
                result.push(left[il++]);
            }else{
                result.push(right[ir++]);
            }
        }
        
        while(il < left.length){
            result.push(left[il++]);
        }
        while(ir < right.length){
            result.push(right[ir++]);
        }
        
        return result;
    };
    
    //快速排序：Chrome的Array.prototype.sort使用快速排序实现
    this.quickSort = function(){
        quick(array, 0, array.length - 1);
    };
    
    var quick = function(array, left, right){
        var index;
        
        if(array.length > 1){
            index = partition(array, left, right);
            
            if(left < index - 1){
                quick(array, left, index - 1);
            }
            if(index < right){
                quick(array, index, right);
            }
        }
    };
    
    var partition = function(array, left, right){ //划分
        var pivot =  array[Math.floor((left + right) / 2)],
            i = left,
            j = right;
        
        while(i <= j){
            while(array[i] < pivot){
                i++;
            }
            while(array[j] > pivot){
                j--;
            }
            if(i <= j){
                swapQuickSort(array, i, j);
                i++;
                j--;
            }
        }
        return i; //每次划分结束后，索引i的值处在了它应该在的位置
    };
    
     var swapQuickSort = function(array, index1, index2){ //array也要传进来，划分之后左右均为小数组
         var tmp = array[index1];
         array[index1] = array[index2];
         array[index2] = tmp;
     };
}
//利用额外的空间的快速排序
/*
大致分三步：
1、找基准（一般是以中间项为基准）
2、遍历数组，小于基准的放在left，大于基准的放在right
3、递归
*/
var a = [2,4,5,63,4,5,63,2,4,43];
 
function quicksort(arr)
{
    if (arr.length == 0)
        return [];
        
    
    var left = new Array();  
    var right = new Array();
    var pivot = arr[0];
 
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
           left.push(arr[i]);
        } else {
           right.push(arr[i]);
        }
    }
 
    return quicksort(left).concat(pivot, quicksort(right));
}
console.log(quicksort(a));
//改进的冒泡排序(2)
var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];
function bubbleSort(a)
{
    var swapped;
    do {
        swapped = false; //标记 如果某一轮执行完毕后没有发生交换，则可以直接退出循环，排序结束
        for (var i = 0; i < a.length-1; i++) {
            if (a[i] > a[i+1]) {
                swap(a[i], a[i+1]);
                swapped = true;
            }
        }
    } while (swapped);
}
bubbleSort(a);
console.log(a);

排序比较

三、查找算法

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
//顺序查找
this.sequentialSearch = function(item){
    for(var i = 0; i < array.length; i++){
        if(item === array[i]){
            return i;
        }
    }
    return -1;
};
//二分查找
this.binarySearch = function(item){
    this.quickSort();
    
    var low = 0,
        high = array.length - 1,
        mid, element;
    
    while(low <= high){
        mid = Math.floor((low + high) / 2);
        element = array[mid];
        if(element < item){
            low = mid + 1;
        }else if(element > item){
            high = mid - 1;
        }else{
            return mid;
        }
    }
    return -1;
};

四、动态规划

能用动态规划解决的著名问题：

  • 背包问题
  • 最长公共子序列
  • 矩阵链相乘
  • 硬币找零

动态规划：将复杂问题分解成更小的相互依赖的子问题(不同于分而治之：分解成相互独立的子问题)

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
function MinCoinChange(coins){
    var cache = {};
    
    this.makeChange = function(amount){
        var me = this;
        if(!amount){
            return [];
        }
        if(cache[amount]){
            return cache[amount];
        }
        var min = [],
            newMin, newAmount;
        for(var i = 0; i < coins.length; i++){
            var coin = coins[i];
            newAmount = amount - coin;
            if(newAmount >= 0){
                newMin = me.makeChange(newAmount);
            }
            //判断newAmount是否有效，minValue是否是最优解，minValue与newAmount是否是合理的值.
            if(newAmount >= 0 && 
            (newMin.length < min.length - 1 || !min.length) &&
            (newMin.length || !newAmount)){
                min = [coin].concat(newMin);//更新最优解
                console.log('new Min ' + min + ' for ' + amount);
            }
        }
        return (cache[amount] = min);
    };
}
var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
console.log(minCoinChange.makeChange(36));
var minCoinChange2 = new MinCoinChange([1, 3, 4]);
console.log(minCoinChange2.makeChange(6));
//贪心算法
function MinCoinChange(coins){
    var coins = coins;
    
    this.makeChange = function(amount){
        var change = [],
            total = 0;
        //从最大面额开始，拿尽可能多的硬币找零。当无法再拿更多这种价值的硬币时，开始拿第二大价值的硬币，依次继续。
        for(var i = coins.length - 1; i >= 0; i--){
            var coin = coins[i];
            while(total + coin <= amount){
                change.push(coin);
                total += coin;
            }
        }
        return change;
    };
}
var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
console.log(minCoinChange.makeChange(36));//与DP算法结果相同
var minCoinChange2 = new MinCoinChange([1, 3, 4]);
console.log(minCoinChange2.makeChange(6));//[4,1,1]，DP=>[3,3]
//贪心算法比DP算法更简单，但它并不总是得到最优解，但是综合来看，它相对执行时间来说，输出了一个可以接受的解。

分享
0%