lanbos'blog

js的简单算法(二)

通过一些博客和《啊哈!算法》了解js的栈,队列

队列问题

队列的定义:队列是一种特 殊的线性结构,它只允许在队列的首部(head)进行删除操作,这称为“出队”,而在队列 的尾部(tail)进行插入操作,这称为“入队”。当队列中没有元素时(即 head==tail),称为 空队列

《啊哈!算法》中的一道题,大体意思是有一串密码规则为:首先将第 1 个数删除,紧接着将第 2 个数放到 这串数的末尾,再将第 3 个数删除并将第 4 个数放到这串数的末尾,再将第 5 个数删除…… 直到剩下最后一个数,将最后一个数也删除。按照刚才删除的顺序,把这些删除的数连在一 起就是这串密码,加密的数字为:“6 3 1 7 5 8 9 2 4”。书中阐述了基本思路,引入两个变量head(剩余数组的第一个元素)和tail(剩余数组的最后一个元素的下一个位置)通过移动head和tail的数值来生成新的数组。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var qqArray = [6, 3, 1, 7, 5, 8, 9, 2, 4];
var sisRight = function(arr) {
var head = 0;
var tail = arr.length;
var results = [];
while (head < tail) {
results.push(arr[head]);
head++;
arr[tail] = arr[head];
tail++;
head++;
}
return results;
}
sisRight(qqArray); //[6, 1, 5, 9, 4, 7, 2, 8, 3]

栈的概念

“栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。表尾为栈顶(top),表头为栈底(bottom),不含元素的空表为空栈。栈又称为后进先出(last in first out)的线性表。”

概念很抽象,大致可模拟理解为只允许一端push和pull的数组。还是通过《啊哈!算法》中的题来理解,题目是判断一个字符串是不是回文字符串(“所谓回文字符 串就是指正读反读均相同的字符序列,如“席主席”、“记书记”、“aha”和“ahaha”均是回 文,但“ahah”不是回文”)。思路是利用回文字符串中心对称的特点来进行解题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var loopStr = "ahaha";
var ifLoopStr = function(str) {
var len = str.length;
var mid = len / 2 - 1;
var backMid = Math.round(len / 2);
var top = -1;
var s = [];
for (var i = 0; i <= mid; i++) {
top++;
s.push(str[i]);
}
for (var j = backMid; j < len; j++) {
if (str[j] != s[top]) {
return false;
}
top--;
}
if (top == -1) {
return true;
} else {
return false;
}
}
console.log(ifLoopStr(loopStr));//true

纸牌游戏–小猫钓鱼(栈和队列综合问题)

游戏规则:游戏的规则是这样的:将一副扑克牌平均分成两份,每人拿一份。q1先拿出手中的 第一张扑克牌放在桌上,然后q2也拿出手中的第一张扑克牌,并放在q1刚打出的扑克牌 的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即35啊哈!算法可将两张相同的牌及其中间所夹的牌全部取走,并依次放到自己手中牌的末尾。当任意一人 手中的牌全部出完时,游戏结束,对手获胜。
关键代码逻辑是,建一个作为标记的book数组,长度等于所有牌面的最大数字,然后在其中用0和1存储桌面上是否有出现的牌面。具体代码比较有意思,这里用js模拟了一下。(两人手里各有6张牌,牌面最大为9;q1手里牌是:2, 4, 1, 2, 5, 6;q2手里牌是:3, 1, 3, 5, 6, 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
var q1 = {
data: [2, 4, 1, 2, 5, 6],
head: 0,
tail: 6
}
var q2 = {
data: [3, 1, 3, 5, 6, 4],
head: 0,
tail: 6
}
var cardNum = 9;

function playcard(q1, q2, cardNum) {
// init
var _book = [];
var _s = {
data: [],
top: 0
}
var _t = null;
// init s
for (var i = 0; i < cardNum; i++) {
_book.push(0);
}
// start play
while (q1.head < q1.tail && q2.head < q2.tail) {
// q1 put card
_t = q1.data[q1.head];
if (_book[_t] == 0) { //q1 continu put
q1.head++;
_s.top++;
_s.data[_s.top] = _t;
_book[_t] = 1;
} else { //q1 collect cards
q1.head++;
q1.data[q1.tail] = _t;
q1.tail++;
while (_s.data[_s.top] != _t) {
_book[_s.data[_s.top]] = 0;
q1.data[q1.tail] = _s.data[_s.top];
q1.tail++;
_s.top--;
}
}
// q2 put card
_t = q2.data[q2.head];
if (_book[_t] == 0) { //q2 continu put
q2.head++;
_s.top++;
_s.data[_s.top] = _t;
_book[_t] = 1;
} else { //q2 collect cards
q2.head++;
q2.data[q2.tail] = _t;
q2.tail++;
while (_s.data[_s.top] != _t) {
_book[_s.data[_s.top]] = 0;
q2.data[q2.tail] = _s.data[_s.top];
q2.tail++;
_s.top--;
}
}
}
// win or lose
if (q2.head == q2.tail) {
console.log("q1 win and his cards:");
var _results = [];
for (var i = q1.head; i <= q1.tail - 1; i++) {
_results.push(q1.data[i]);
}
console.log(_results);
if (_s.top > 0) {
var deskR = [];
for (var i = 1; i <= _s.top; i++) {
deskR.push(_s.data[i]);
}
console.log("cards on desk:" + deskR);
} else {
console.log("desk empty");
}
} else {
console.log("q2 win and his cards:");
var _results = [];
for (var i = q2.head; i <= q2.tail - 1; i++) {
_results.push(q2.data[i]);
}
console.log(_results);
if (_s.top > 0) {
var deskR = [];
for (var i = 1; i <= _s.top; i++) {
deskR.push(_s.data[i]);
}
console.log("cards on desk:" + deskR);
} else {
console.log("desk empty");
}
}
console.log("end");
}
playcard(q1, q2, cardNum);