过马路，我对男朋友说，“Darling,我好想去死~”
男朋友拉着我的手：“让我先砍掉你的一条腿好不好？”。
…
早上出门去上班，我磨磨蹭蹭走得很慢，嘴上嘟哝：“Darling，我好想去死~”
“让我先砍掉你的一条腿好不好?”
“为什么你那么执着于砍掉我的腿？”
“没为什么，我就是想砍掉你的一条腿。”
LeetCode:Intersection of Two Linked Lists
题目
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
如果两个链表没有相同尾链，返回null。
两个链表在输出时应保持原来的结构。
链表结构中没有循环。
时间复杂度要求O(n),空间复杂度要求O(1)
思路
先取A，B链的长度，找出哪个是短链，哪个是长链。
然后找到长链尾部和短链长度相同的位置，开始比较它和短链是否相等。
如果当前节点不相等，则两者后移一位继续比较，直到找到第一个相等的节点，记录之。
如果当前节点不相等，但前一个节点相等，说明没有相同的尾链，返回null。
实现
JavaScript:
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
if(headA&&headB){
var node=headA,aLength=1,bLength=1;
while(node.next){
aLength++;
node = node.next;
}
node= headB;
while(node.next){
bLength++;
node=node.next;
}
var pointer1 ,pointer2;
//将ab链截取到尾部位数相同
if(aLength > bLength){
pointer1 = headB;
pointer2 = headA;
for(var i = bLength;i<aLength;i++){
pointer2 = pointer2.next;
}
}else if(aLength<bLength){
pointer1 = headA;
pointer2 = headB;
for(i = aLength;i<bLength;i++){
pointer2 = pointer2.next;
}
}else{
pointer1 = headA;
pointer2 = headB;
}
node = null;
//保留上次比较结果
var sameFlag = false;
while(pointer1){
if(pointer1.val===pointer2.val){
//当前相等，继续比较。
// 如果上次比较不相等，则赋值node，说明是第一个相等的节点
if(!sameFlag){
node = pointer1;
}
sameFlag=true;
pointer1 = pointer1.next;
pointer2 = pointer2.next;
continue;
}
if(pointer1.val!==pointer2.val){
//当前不相等，判断上次比较是否相等。
if(sameFlag){
//上次比较相等，则直接返回null，说明没有相同的尾链
return null;
}else{
//上次比较不相等，则继续比较
pointer1 = pointer1.next;
pointer2 = pointer2.next;
sameFlag=false;
continue;
}
}
}
return node;
}else{
return null;
}
};
页面性能分析工具
LeetCode:Rotate Array
题目来源
有一个数组[1,2,3,4,5],向右移k位，k=3输出[3,4,5,1,2],k=1输出[5,1,2,3,4]
要求时间复杂度线性，空间复杂度可控O(1)
思路
找到每个元素移位后的位置，在新的数组上追一赋值。
实现
JavaScript:
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
//步数是长度的倍数则直接返回
if(k%nums.length===0){
return;
}else{
//取模，拿到真正的步数，因为k可能大于length
var step = k%nums.length;
var result = [];
result.length =nums.length;
for(var i=0;i<nums.length;i++){
//确定每个元素的新的位置
result[(i+step)%nums.length] = nums[i]
}
//重新赋值
for( i=0;i<nums.length;i++){
nums[i] = result[i];
}
}
};
PS：验证虽然通过了，但总感觉有点投机，因为我重新复制了一下这个数组。虽然只用了这一个额外变量，但从空间存储上还是O(n)的。
LeetCode:Maximum Depth of Binary Tree
题目来源
思路
二叉树的最大深度，等于根节点的深度。根节点的深度等于左子树和右子树深度的较大者。
所以这个题可以递归遍历每一个节点的深度。
实现
JavaScript:
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
function findDepth(node,currentDepth){
if(node!==null){
currentDepth++;
//每个节点的深度，等于左深度和右深度的较大者
var leftDepth = findDepth(node.left,currentDepth);
var rightDepth = findDepth(node.right,currentDepth);
return leftDepth>rightDepth?leftDepth:rightDepth;
}else{
return currentDepth;
}
}
//返回根节点的深度
return findDepth(root,0);
};
LeetCode:Plus One
题目来源
有一个数组代表一个非负的数字，求这个数字+1之后的数组。
比如这个数组是[1,2,3,4]它代表数字1234，那么这个数字加1之后是1235。希望得到这个数字代表的数组[1,2,3,5]
思路
从最后一位开始，对当前值+1，如果当前值不为9则正常返回结果。如果当前值为9，则当前值变为0，再递归调用前一位的+1操作。
实现
JavaScript:
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
function plus(digits,i){
if(digits[i]===9){
digits[i]=0;
if(i===0){
var head = [1];
return head.concat(digits);
}else{
return plus(digits,i-1);
}
}else{
digits[i] = digits[i]+1;
return digits;
}
}
return plus(digits,digits.length-1);
};
PS：上面的代码性能不是很好，肯定有更好的算法的。
LeetCode:Single Number
题目来源
有一个都是整型的数组，它除了一个元素只有出现一次之外，其他的都出现了二次。求这个落单的数字。
比如[1,2,3,5,2,1,3]这个数组中5是落单的数字，其他数字都出现了两次。
思路
最先写的是两层for循环来比较是否有相等的。但是提交之后发现Time Limit Exceeded，时间复杂度是n^2。
题目有标注是线性的事件复杂度，而且空间复杂度也是线性级别的,所以递归调用也是不行的。
然后百度了下，发现有人用异或操作来判断。
a ^ b = b ^ a
a ^ a = 0
0 ^ a = a
a ^ b ^ a = a ^ a ^ b = 0 ^ b = b
这样就可以把这个b找出来了。
实现
JavaScript:
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
var result = nums[0];
for(var i = 1; i < nums.length; i++){
result = result ^ nums[i];
}
return result;
}
LeetCode:Power of Two
题目来源
给你一个数字N，求判断它是否是2的次方。比如8是2的3次方，返回true，9不是2的次方，返回false。
思路
这个题目最初想到的是递归除以2。但考虑到2这个数字比较特殊，它的次方在计算机中的位存储也是很特殊的，所以可以试下位操作。
2 : 10
4 : 100
8 : 1000
16: 10000
...
2的X次方，其二进制是1后面跟X个0；而2的X次方减1的二进制都是1.
1 : 1
3 : 11
7 : 111
15: 1111
...
而2^x 和2^x-1 进行位与操作，结果是0.比如8和7
1000
& 0111
-------
0000
那么我们就可以利用这一点来判断一个数是否为2的次方。
实现
JavaScript:
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfTwo = function(n) {
if(n<=0){return false}
return (n&n-1)===0
};
Chrome timeline 检测页面性能
还是先占个坑。
今天要做页面性能优化，终于有机会用到这个了。
二叉排序树的实现
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
/**
* Created by judastree on 15/7/20.
* 二叉排序树
*/
function Node(value, left, right) {
this.value = value;
this.left = left;
this.right = right;
}
function BST() {
this.root = null;
}
BST.prototype = {
add: function (value) {
var n = new Node(value, null, null);
if (this.root == null) {
//根节点为空，直接插入
this.root = n;
return true;
} else {
//根节点不为空，找到匹配的子节点插
var current = this.root;
while (true) {
if (value < current.value) {
//比当前节点小，而且当前节点没有左孩子，直接插入
if (current.left == null) {
current.left = n;
break;
} else {
//当前节点有左孩子，往下遍历，再和左孩子比较
current = current.left;
}
} else if (value > current.value) {
//大于当前节点，而且当前节点没有右孩子，直接插入
if (current.right == null) {
current.right = n;
break;
} else {
//当前节点有右孩子，往下遍历，再和右孩子比较
current = current.right;
}
} else {
//等于的情况，忽略不进行插入
break;
}
}
}
},
//中序遍历
inOrder: function (node, fn) {
if (node) {
if (node.left != null) {
this.inOrder(node.left, fn);
}
fn.call(this, node);
if (node.right != null) {
this.inOrder(node.right, fn);
}
}
},
//先序遍历
preOrder: function (node, fn) {
if (node) {
fn.call(this, node);
if (node.left != null) {
this.preOrder(node.left, fn);
}
if (node.right != null) {
this.preOrder(node.right, fn);
}
}
},
//后序遍历
postOrder: function (node, fn) {
if (node) {
if (node.left != null) {
this.postOrder(node.left, fn);
}
if (node.right != null) {
this.postOrder(node.right, fn);
}
fn.call(this, node);
}
},
//默认调用中序遍历
toArray: function () {
var result = [];
this.inOrder(this.root, function (node) {
result.push(node.value);
});
return result;
},
toString: function () {
return this.toArray().toString();
}
};
var bst = new BST();
bst.add(4);
bst.add(8);
bst.add(3);
bst.add(7);
bst.add(1);
bst.add(2);
console.log("中序遍历：");
console.log(bst.toString());
console.log("先序遍历");
var preResults = [];
bst.preOrder(bst.root, function (node) {
preResults.push(node.value);
});
console.log(preResults.toString());
console.log("后序遍历");
var postResults = [];
bst.postOrder(bst.root, function (node) {
postResults.push(node.value);
});
console.log(postResults.toString());
PS: 边参考别人的，写了一个小时。