lintcode

按照难易程度排序后刷题，并没有讲究最佳算法，只是单纯实现。有的没有验证，重在思想，若有疑问请留言。 632.在二叉树中寻找值最大的节点并返回。

// function Tree(data){ // this.data = data, // this.left = null, // this.right = null // } // Tree.prototype = { // insert:function(obj){ // if(obj.data < this.data){ // if(this.left!=null){ // this.left.insert(obj); // }else{ // this.left=obj // } // }else{ // if(this.right!=null){ // this.right.insert(obj); // }else{ // this.right=obj // } // } // // }, // arr:[], // show:function(){ // this.arr.push(this.data); // if(this.left!=null){ // this.left.show() // } // if(this.right!=null){ // this.right.show() // } // } // } // var root = new Tree(10); // var arr=[]; // for(var i=5;i<12;i++){ // var obj = new Tree(i); // arr.push(obj); // } // arr.forEach(function(item,index,arr){ // root.insert(item) // }) // root.show(); // var min = Math.min.apply(null,root.arr) // console.log(root,root.arr,min);

366.斐波那契数列

// // function fbnq(n){ // fbnq.count++; // if(arguments.callee.store[n-1]!=undefined){ // return arguments.callee.store[n-1] // }else{ // var result = fbnq(n-1)+fbnq(n-2); // arguments.callee.store.push(result); // return result; // } // } // fbnq.store=[1,1];//缓存思想，记录每次结果，再次使用时无需计算 // fbnq.count=0; //记录计算所需次数 // console.log(fbnq(5),fbnq.count); // fbnq.count=0; // console.log(fbnq(5),fbnq.count);

454.矩形类

// // function Rect(width,hegiht){ // this.width = width, // this.hegiht = height // } // Rect.prototype.getArea=function(){ // return this.width * this.height // } // 452.删除列表中的元素，给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5 // function delOne(arr,num){ // arr.forEach(function(ele,index,arr){ // if(ele == num){ // arr.splice(index,1) // } // }) // return arr // } // var arr = delOne([1,2,3,3,3,5],4) // console.log(arr);

463.排序

// // for (var i = 0; i < arr.length - 1; i++) { // var flag = true; // for (var j = 0; j < arr.length - 1 - i; j++) { // if (arr[j] > arr[j + 1]) { // var temp = arr[j]; // arr[j] = arr[j + 1]; // arr[j + 1] = temp; // flag = false; // } // } // if (flag==true) { // break; // } // }

457.二分法查找。在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1

// // var arr=[1,3,7,10,12,14,14,20]; // getIndex.index = 0; // function getIndex(arr,num,min,max){ // var min = min||0, // max = max||arr.length-1; // if(num<arr[min]||num>arr[max]){ // getIndex.index = -1; // }else{ // if(num == arr[min]){ // getIndex.index = min; // }else if(num == arr[max]){ // getIndex.index = max; // }else{ // var crtIndex = Math.ceil((min + max)/2); // if(crtIndex == max){ // getIndex.index = -1; // }else { // if(num == arr[crtIndex]){ // getIndex.index = crtIndex; // // }else if(num > arr[crtIndex]){ // min = crtIndex; // arguments.callee(arr,num,min,max); // }else{ // max = crtIndex; // arguments.callee(arr,num,min,max); // } // // } // } // } // return getIndex.index; // } // var index = getIndex(arr,7); // console.log(index);

1.给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符

// // function getSum(){ // var arrList = []; // Array.prototype.forEach.call(arguments,function(ele,index,arr){ // var arr = new Array(ele); // arrList = arrList.concat(arr);console.log(arrList); // }) // return arrList.length; // } // console.log(getSum(1,1,1))

569.各位相加,给出一个非负整数 num，反复的将所有位上的数字相加，直到得到一个一位的整数。

// // function positionAdd(num){ // var arr = num.toString().split(""),sum=0; // if(arr.length>1){ // sum = arr.reduce(function(pre,curr,index,arr){ // return parseInt(pre) + parseInt(curr); // }) // if(sum>9){ // sum = arguments.callee(num); // }else{ // return sum; // } // }else{ // sum = parseInt(arr[0]); // } // return sum; // } // var sum = positionAdd(parseInt(1)); // console.log(sum);

167.链表求和

// function Chain(data){ // this.data = data; // this.next = null; // } // Chain.prototype = { // insertNext:function(obj) { // if(this.next != null) { // this.next.insertNext(obj); // } else { // this.next = obj; // } // }, // toArray:function(){ // var arr = []; // arr.push(this.data); // if(this.next != null){ // var arr1 = this.next.toArray(); // arr = arr.concat(arr1); // } // return arr; // }, // gain:function(obj1,obj2) { // var arr1 = obj1.toArray(); // var arr2 = obj2.toArray(); // arr1.forEach(function(ele,index,arr) { // arr1[index] = ele + arr2[index]; // }) // return this.toChain(arr1); // }, // toChain:function(arr) { // var result = new Chain(arr.shift()); // arr.forEach(function(ele,index,arr) { // var chainItem = new Chain(ele); // result.insertNext(chainItem); // }) // return result; // } // }

93.判断两个二叉树是平衡二叉树

// function Tree(data) { // this.data = data; // this.left = null; // this.right = null; // this.floor = 0; // } // Tree.prototype.insert = function(obj) { // if(obj.data < this.data) { // if(this.left == null) { // this.left = obj; // obj.floor = this.floor + 1; // } else { // this.left.inset(obj); // } // } else { // if(this.right == null) { // this.right = obj; // this.right.floor = this.floor + 1; // } else { // this.right.inset(obj); // } // } // } // Tree.prototype.objMax = function(){ // var arr = []; // if (this == null) { // arr.push(0); // } else { // arr.push(this.data); // if(this.left != null) { // var arr1 = this.left.objMax; // arr = arr.concat(arr1); // } // if(this.right != null) { // var arr1 = this.right.objMax; // arr = arr.concat(arr1); // } // } // return Math.max.apply(null,arr); // } // Tree.prototype.isBanlance = function() { // let flag = false; // let left = this.left; // let right = this.right; // if(Math.abs(left.objMax() - right.objMax())) { // flag = true; // } // return flag; // }

655.返回两数之和

// function sum(num1,num2){ //Array.reduce().call(arguments,function(prev,cur,index,arr){ // raturn prev + cur; // }) // }

66.67.68.69.二叉树前序，中序，后序，层次遍历

// function Tree(data) { // this.data = data; // this.left = null; // this.right = null; // } // Tree.prototype = { // insert: function(obj) { // if(obj.data < this.data) { // if(this.left != null) { // this.left.insert(obj) // } else { // this.left = obj; // } // } else { // if(this.right != null) { // this.right.insert(obj); // } else { // this.right = obj; // } // } // }, // _zxbl: function() { // var arr = []; // if(this.left != null) { // var arr1 = this.left._zxbl(); // arr = arr.concat(arr1); // } // arr.push(this.data); // if(this.right != null) { // var arr2 = this.right._zxbl(); // arr = arr.concat(arr2); // } // return arr; // }, // _qxbl: function() { // var arr = []; // arr.push(this.data); // if(this.left != null) { // var arr1 = this.left._qxbl(); // arr = arr.concat(arr1); // } // if(this.right != null) { // var arr2 = this.right._qxbl(); // arr = arr.concat(arr2); // } // return arr; // }, // _hxbl: function() { // var arr = []; // if(this.left != null) { // var arr1 = this.left._hxbl(); // arr = arr.concat(arr1); // } // if(this.right != null) { // let arr2 = this.right._hxbl(); // arr = arr.concat(arr2); // } // arr.push(this.data); // return arr; // }, // _ccbl:function() { // var obj = {},n = 0; // var arr = []; // arr.push(this); // obj[0] = arr; // function getSon(arr) { // if(arr.length > 0) { // var arr1 = []; // arr.forEach(function(ele,index,arr) { // if(ele.left != null) { // arr1.push(ele.left) // } // if(ele.right != null) { // arr1.push(ele.right) // } // }) // if(arr1.length > 0){ // n++; // obj[n] = arr1; // return arr1; // } // } // } // (function(arr){ // var arr1 = getSon(arr); // if(arr1 != undefined) { // arguments.callee(arr1); // } // }(arr)) // var objResult = {}; // for(var k in obj) { // var arr2 = []; // obj[k].forEach(function(ele,index,arr) { // arr2.push(ele.data); // }) // objResult[k] = arr2; // } // return objResult; // } // } // var root = new Tree(5); // for(var i=0;i<7;i++) { // var data = Math.ceil(10 * Math.random()); // var obj = new Tree(data); // root.insert(obj) // } // var obj = root._ccbl(); // console.log(root,obj);

480.找出二叉树根节点到所有叶子节点的路径

// function Tree(data) { // this.data = data; // this.left = null; // this.right = null; // this.parent = null; // } // Tree.prototype = { // insert: function(obj) { // if(obj.data < this.data) { // if(this.left != null) { // this.left.insert(obj) // } else { // this.left = obj; // obj.parent = this; // } // } else { // if(this.right != null) { // this.right.insert(obj); // } else { // this.right = obj; // obj.parent = this; // } // } // }, // getLeaves:function (){ // var arr = []; // if(this.isLeaf() == true) { // arr.push(this); // } else { // if(this.left != null) { // var arr1 = this.left.getLeaves(); // arr = arr.concat(arr1); // } // if(this.right != null) { // var arr2 = this.right.getLeaves(); // arr = arr.concat(arr2); // } // } // return arr; // }, // isLeaf:function() { // if(this.left == null && this.right == null) { // return true; // } else { // return false; // } // }, // getPath:function(array) { // var obj = {}; // array.forEach(function(ele,index,arr){ // var arr1 = []; // var node = ele; // arr1.push(node); // while(node.parent != null) { // node = node.parent; // arr1.push(node); // } // obj[index] = arr1; // }) // var result = {}; // for(var k in obj) { // var resultArr = []; // obj[k].forEach(function(ele,index,arr){ // resultArr.push(ele.data); // }) // result[k] = resultArr; // } // return result; // } // } // var root = new Tree(5); // for(var i=0;i<7;i++) { // var data = Math.ceil(10 * Math.random()); // var obj = new Tree(data); // root.insert(obj) // } // var arr = root.getLeaves(); // var obj = root.getPath(arr); // console.log(root,obj);

待续。。。