几个js算法题

打印Fibonacci数列

function Fibonacci(num) {
 if(num === 0) {
  return 0;
 }else if(num === 1) {
  return 1;
 }else{
  return arguments.callee(num -2) + arguments.callee(num -1); 
 }
 
}
for(var i=0;i<5;i++){ // 0 1 1 2 3
 console.log(Fibonacci(i));
}

trim

function trim(str) {
 var start = 0, end = 0;
 // 去除左边的空格
 for (var i = 0, len = str.length; i < len; i++) {
  if (str[i] != " ") {
   start = i;
   break;
  }
 }
 
 // 去除右边的空格
 for (var len = str.length - 1, j = len; j > 0; j--) {
  if (str[j] != " ") {
   end = j;
   break;
  }
 }
 
 // 如果需要的话，去除中间的超过一个的空格
 str = str.substring(start, end + 1)
 var result = "";

 for (var k = 0, len = str.length; k < len; k++) {
  if (str[k] == str[k + 1] && str[k] == " ") {
   continue;
  } else {
   //result += str[k]; 用concat效率更高
   result = result.concat(str[k]);
  }
 }

 return result;
}

function trim2(str) {
 return str.replace(/^\s*|\s*$/g, "");
}

var str = "  a       b c d  ";
console.log(trim(str)); // a b c d

冒泡排序

function BubbleSort(arr) {
 var temp = 0;
 for (var i = 0, len = arr.length; i < len; i++) {
  for ( j = i; j < len; j++) {
   if (arr[i] > arr[j]) {
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
   }
  }
 }
 return arr;
}

var arr = [1, 0, 15, 5, 10, 3];
console.log(BubbleSort(arr));

一种快速排序，不过有缺陷，重复的数字没算在内，想解决的话只能再写一个数组来记录重复的数组和重复的次数

function quicksort(arr){
 var temp=[],result=[];
 for(var i=0, len=arr.length;i<len;i++){
  temp[arr[i]]=true;
 }
 
 console.log(temp.length); //89
 console.log(temp[1]); //true
 console.log(temp[4]); //undefined
 for(var j=0,len2=temp.length;j<len2;j++){
  if(temp[j]){
   result.push(j);
  }
 } 
 return result;
}
var arr = [3,5,1,2,10,88,10,25,66];
console.log(quicksort(arr)); // [1, 2, 3, 5, 10, 25, 66, 88]

十进制转十六进制，十六进制转十进制

function Dec2Hex(num) {
 var a = Dec2HexAction(num);
 var out = "";
 for ( i = a.length - 1; i >= 0; i--) {
  out += a.charAt(i);
 }
 return out;
}

function Dec2HexAction(num) {
 var out = '';
 var out2 = '';
 var a = num % 16;
 //取余
 var b = Math.floor(num / 16);
 //取商
 a = getHex(a);
 if (b > 16)
  out += a.toString() + Dec2HexAction(b);
 else
  out += a.toString() + getHex(b).toString();
 return out;
}

function getHex(num) {
 if (num == '10')
  return 'A';
 if (num == '11')
  return 'B';
 if (num == '12')
  return 'C';
 if (num == '13')
  return 'D';
 if (num == '14')
  return 'E';
 if (num == '15')
  return 'F';
 return num;
}

/* 十六进制转成十进制 */
function Hex2Dec(num) {
 return eval('0x' + num);
}

console.log(Dec2Hex(15)); //0F
console.log(Hex2Dec("0f")); //15

链表相邻元素翻转，如a->b->c->d->e->f-g，翻转后变为：b->a->d->c->f->e->g

function rotate(list){
 var temp="";
 for(var i=0,len=list.length;i<len;i++){
  if(i%2 ==0 && list[i+1]){
   temp=list[i];
   list[i]=list[i+1];
   list[i+1]=temp;
  }
 }
 return list;
}
var list = ["a","b","c","d","e","f","g"];
console.log(rotate(list));

字符串移动（字符串为*号和26个字母的任意组合，把*号都移动到最左侧，把字母移到最右侧并保持相对顺序不变），要求时间和空间复杂度最小

function shift(str){
 var result = "", count=0;
 for(var i=0,len=str.length;i<len;i++){
  if(str[i]=="*"){
   count+=1;
   str = (str.substring(0,i)) + (str.substring(i+1,len));
  }
 }
 for(var j=0;j<count;j++){
  str = "*" +str;
 }
 return str;
}
var str="abc*de*f*";
console.log(shift(str)); // ***abcdef

查找数组中和最大的子序列时间复杂度O（n）

function maxSum(arr){
 var sum=0, tempSum=0, begin=0, end=0;
 var result = [];
 
 for(var i=0,len=arr.length;i<len;i++){
  if(tempSum>0){
   tempSum = tempSum + arr[i];
  }else{
   tempSum=arr[i];
   begin=i;
  }
  
  if(tempSum>sum){
   sum=tempSum;
   end=i;
  }
 }
 console.log(begin);
 console.log(end);
 return sum;
}

var arr = [2,-3,9,3,-3];
console.log(maxSum(arr)); //2,3,12
arr = [-1,3,6,-9,2,-5,-1,9,4,-3];
console.log(maxSum(arr)); //7,8,13