剑指offer--JavaScript版III

51.
请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

1
2
3
4
function isNumeric(s) {
var reg = /^[+-]?(?:(\d+)(\.\d+)?|(\.\d+))([eE][+-]?\d+)?$/;
return reg.test(s);
}

52.
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符”go”时,第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时,第一个只出现一次的字符是”l”。

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
function Init() {
streamNums = [];
streamNumsLen = 256;
streamNumsIndex = 0;
for (var i = 0; i < streamNumsLen; i++) {
streamNums[i] = -1;
}
}

function Insert(ch) {
var code = ch.charCodeAt();
if (streamNums[code] == -1) {
streamNums[code] = streamNumsIndex;
} else if (streamNums[code] >= 0) {
streamNums[code] = -2;
}
streamNumsIndex++;
}

function FirstAppearingOnce() {
result = '';
var ch = '';
var minIndex = Infinity;
for (var i = 0; i < streamNumsLen; i++) {
if (streamNums[i] >= 0 && streamNums[i] < minIndex) {
ch = String.fromCharCode(i);
minIndex = streamNums[i];
}
}
return ch == "" ? '#' : ch;
}

53.
一个链表中包含环,请找出该链表的环的入口结点。

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
function EntryNodeOfLoop(pHead) {
if (!pHead) {
return null;
}
var meeting = meetingNode(pHead);
if (!meeting) {
return null;
}
var nodeLoop = 1;
var node1 = meeting;
while (node1.next != meeting) {
node1 = node1.next;
nodeLoop++;
}
node1 = pHead;
for (var i = 0; i < nodeLoop; i++) {
node1 = node1.next;
}
var node2 = pHead;
while (node1 != node2) {
node1 = node1.next;
node2 = node2.next;
}
return node1;

function meetingNode(node) {
if (!node || !node.next) {
return null;
}
var slow = node.next;
var fast = slow.next;
while (fast && slow) {
if (fast === slow) {
return fast;
}
slow = slow.next;
fast = fast.next;
if (fast) {
fast = fast.next;
}
}
return null;
}
}

54.
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->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
function deleteDuplication(pHead) {
if (!pHead) {
return null;
}
var tempHead = new ListNode(-1);
tempHead.next = pHead;
var preNode = tempHead;
var curr1 = preNode.next;
var curr2 = curr1.next;
while (curr1) {
if (!curr2 || curr2.val !== curr1.val) {
if (curr1.next !== curr2) {
clear(curr1, curr2);
preNode.next = curr2;
} else {
preNode = curr1;
}
curr1 = curr2;
if (curr2) {
curr2 = curr2.next;
}
} else {
if (curr2) {
curr2 = curr2.next;
}
}
}
return tempHead.next;

function clear(node, stop) {
var temp;
while (node !== stop) {
temp = node.next;
node.next = null;
node = temp;
}
}
}

55.
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function GetNext(pNode) {
if (!pNode) {
return pNode;
}
if (pNode.right) {
pNode = pNode.right;
while (pNode.left) {
pNode = pNode.left;
}
return pNode;
} else if (pNode.next && pNode.next.left == pNode) {
return pNode.next;
} else if (pNode.next && pNode.next.right == pNode) {
while (pNode.next && pNode.next.left != pNode) {
pNode = pNode.next;
}
return pNode.next;
} else {
return pNode.next;
}
}

56.
请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function isSymmetrical(pRoot) {
if (!pRoot) {
return true;
}
return symmetrical(pRoot, pRoot);
function symmetrical(node1, node2) {
if (!node1 && !node2)
return true;
if (!node1 || !node2)
return false;
if (node1.val != node2.val)
return false;
return symmetrical(node1.left, node2.right) && symmetrical(node1.right, node2.left);
}
}

57.
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

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
function Print(pRoot) {
var res = [];
if (!pRoot) {
return res;
}
var que = [];
que.push(pRoot);
var flag = false;
while (que.length > 0) {
var vec = [];
var len = que.length;
for (var i = 0; i < len; i++) {
var tmp = que.shift(); //front
vec.push(tmp.val);
if (tmp.left)
que.push(tmp.left);
if (tmp.right)
que.push(tmp.right);
}
if (flag) {
vec.reverse();
}
res.push(vec);
flag = !flag;
}
return res;
}

58.
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function Print(pRoot) {
var res = [];
if (!pRoot) {
return res;
}
var que = [];
que.push(pRoot);
while (que.length > 0) {
var vec = [];
var len = que.length;
for (var i = 0; i < len; i++) {
var tmp = que.shift(); //front
vec.push(tmp.val);
if (tmp.left)
que.push(tmp.left);
if (tmp.right)
que.push(tmp.right);
}
res.push(vec);
}
return res;
}

59.
请实现两个函数,分别用来序列化和反序列化二叉树

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
function Serialize(pNode) {
var str = [];
ser(pNode);
for (var i = str.length - 1; i >= 0; i--) {
if (str[i] !== '#') {
break;
}
str.pop();
}
return str.join();
function ser(node) {
if (!node) {
str.push('#');
return;
}
str.push(node.val);
ser(node.left);
ser(node.right);
}
}
function Deserialize(str) {
var index = -1;
var len = str.length;
if (index >= len) {
return null;
}
var arr = str.split(",");
var head = des();
return head;
function des(node) {
index++;
if (arr[index] && arr[index] !== '#') {
var temp = new TreeNode(arr[index]);
node = temp;
node.left = des();
node.right = des();
}
return node;
}
}

60.
给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function KthNode(pRoot, k) {
if (!pRoot || !k) {
return null;
}
return KthCore(pRoot);
function KthCore(node) {
var target = null;
if (node.left) {
target = KthCore(node.left);
}
if (!target) {
if (k === 1)
target = node;
k--;
}
if (!target && node.right)
target = KthCore(node.right);
return target;
}
}

61.
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var arr = [];
function Insert(num) {
arr.push(num);
arr.sort(function (a, b) {
return a - b;
});
return arr;
}
function GetMedian() {
var mid = Math.floor(arr.length / 2);
if ((arr.length & 1) === 0) {
var n1 = arr[mid];
var n2 = arr[mid - 1];
return (n1 + n2) / 2;
} else {
return arr[mid]
}
}

62.
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,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
function maxInWindows(num, size) {
if (!num || num.length === 0) {
return null;
}
var max = [];
if (num.length >= size && size >= 1) {
var index = [];
for (var i = 0; i < size; ++i) {
while (index.length > 0 && num[i] >= num[index[index.length - 1]])
index.pop();
index.push(i);
}
for (var i = size; i < num.length; ++i) {
max.push(num[index[0]]);
while (index.length > 0 && num[i] >= num[index[index.length - 1]])
index.pop();
if (index.length > 0 && index[0] <= i - size)
index.shift();
index.push(i);
}
max.push(num[index[0]]);
}
return max;
}

63.
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径,但是矩阵中不包含”abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

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
function hasPath(matrix, rows, cols, path) {
var visited = [];
for (var i = 0; i < rows * cols; i++) {
visited[i] = false;
}
var pathLen = 0;
try {
for (var i = 0; i < rows; i++) {
for (var j = 0; j < cols; j++) {
if (core(i, j)) {
return true;
}
}
}
} finally {
visited.length = 0;
}
return false;
function core(row, col) {
if (path.length === pathLen) {
return true;
}
var hasPath = false;
if (row >= 0 && row = 0 && col < cols && matrix[row * cols + col] === path[pathLen] && !visited[row * cols + col]) {
pathLen++;
visited[row * cols + col] = true;
hasPath = core(row - 1, col) + core(row, col - 1)
+ core(row + 1, col) + core(row, col + 1);
if (!hasPath) {
pathLen--;
visited[row * cols + col] = false;
}
}
return hasPath;
}
}

64.
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

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
function movingCount(threshold, rows, cols) {
var visited = [];
for (var i = 0; i < rows * cols; ++i)
visited[i] = false;
var count = movingCountCore(0, 0);
visited.length = 0;
return count;
function getDigitSum(number) {
var sum = 0;
while (number > 0) {
sum += number % 10;
number = Math.floor(number / 10);
}
return sum;
}
function check(row, col) {
if (row >= 0 && row = 0 && col < cols && getDigitSum(row) + getDigitSum(col) <= threshold && !visited[row * cols + col])
return true;
return false;
}
function movingCountCore(row, col) {
var count = 0;
if (check(row, col)) {
visited[row * cols + col] = true;
count = 1 + movingCountCore(row - 1, col)
+ movingCountCore(row, col - 1)
+ movingCountCore(row + 1, col)
+ movingCountCore(row, col + 1);
}
return count;
}
}

手动测试框架

  • 二叉树构造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
function Tree(arr, node, num = 1) {
if (!arr || arr.length === 0) {
return new TreeNode(null);
}
node = node || new TreeNode(arr[num - 1]);
var curr = node;
if (num * 2 - 1 < arr.length && arr[num * 2 - 1]) {
curr.left = new TreeNode(arr[num * 2 - 1]);
Tree(arr, curr.left, num * 2);
}
if (num * 2 < arr.length && arr[num * 2]) {
curr.right = new TreeNode(arr[num * 2]);
Tree(arr, curr.right, num * 2 + 1);
}
return node;
}
// 根据数组生成二叉树
var tree = new Tree([3, 2, 4, 8, 7, null, 10, null, null, 5, 9]);
console.log(tree);
  • 单向链表构造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function ListNode(x) {
this.val = x;
this.next = null;
}
function LinkedList(arr) {
if (!arr || arr.length === 0) {
return new ListNode(null);
}
var head = new ListNode(arr[0]);
var len = arr.length;
var curr = head;
for (var i = 1; i < len; i++) {
var temp = new ListNode(arr[i]);
curr.next = temp;
curr = curr.next;
}
return head;
}
var ll = new LinkedList([3, 2, 4, 8, 7, 10, 5, 9]);
console.log(ll);
  • Node.js 多行输入测试 (如果不能运行请更新浏览器来支持 es6 语法)
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
(function () {
/* Todo: This Array contains the input lines in sequence. Each of the elements is like a line of input. */
var test_lines = ['5', '1 2 3 3 5', '3', '1 2 1', '2 4 5', '3 5 3']; // Do not change the name of this array if you don't like bugs.
/****************************************************************
Todo: Add your code here including the callback function of event 'rl.on()' and
global variables except the statements and definitions of 'readline' and 'rl'.
*****************************************************************/
/* global variables here */
var lines = 1;
/* callback function of 'rl.on()' */
function main(line) { // Do not change the name of this function if you don't like bugs.
var str = line.trim();
console.log('lines', lines++, ':', str);
}
/**************** End of Your Code *****************/
(function () {
var test_len = test_lines.length;
var test_it = gen(test_lines);
var test_val = test_it.next();
while (test_len) {
main(test_val.value);
test_val = test_it.next();
test_len--;
}
function* gen(test_lines) {
var len = test_lines.length;
var i = 0;
while (len) {
yield test_lines[i];
i++;
}
}
}())
}());
文章作者: Monad Kai
文章链接: onlookerliu.github.io/2017/12/27/剑指offer-JavaScript版III/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Code@浮生记
支付宝打赏
微信打赏