算法基礎(chǔ)之簡(jiǎn)單算法

jokester 發(fā)布于2019-08-23 11:53 / 1934人閱讀

摘要：獲取字符串中字符的全排列無(wú)重復(fù)去重回溯查找有環(huán)鏈表的入環(huán)節(jié)點(diǎn)

本文包括簡(jiǎn)單的線性算法和一些數(shù)值計(jì)算，還會(huì)繼續(xù)更新

rgb 和 16進(jìn)制互相轉(zhuǎn)換

function rgb2hex(r,g,b){
  return "#" + ((r<<16)+(g<<8)+b).toString(16);
}
function hex2rgb(str){
  var arr = str.match(/[0-9a-f]{2}/ig);
  return {
    r: parseInt(arr[0], 16),
    g: parseInt(arr[1], 16),
    b: parseInt(arr[2], 16)
  };
}

找出整型數(shù)組中乘積最大的三個(gè)數(shù)

var original_array = [-10, -7, -29, -4, -1, -10, -70];
var result = findMPTN(original_array);
console.log(result);

function findMPTN(arr){    //findMaxiumProductorOfThreeNumbers
  var len = arr.length;
  sorted_arr = arr.sort(function(a,b){return a-b;});
  var pro1 = 1, pro2 = sorted_arr[len - 1];
  for(var i = 1; i <= 3; i++){
    pro1 *= sorted_arr[len - i];
  }
  pro2 *= sorted_arr[0];
  pro2 *= sorted_arr[1];

  return pro1 > pro2 ?
  [sorted_arr[len - 3], sorted_arr[len - 2], sorted_arr[len - 1]] :
  [sorted_arr[0], sorted_arr[1], sorted_arr[len - 1]];
}

判斷大括號(hào)是否閉合

var expression = "{{}}{}{}"
var expressionFalse = "{}{{}";

console.log(isBalanced(expression)); // true
console.log(isBalanced(expressionFalse)); // false
console.log(isBalanced("")); // true

function isBalanced(exp){
  var stack = [];
  var arr = exp.split("");
  var len = arr.length, cur;
  while(cur = arr.shift()){
    if(cur === "{") stack.push(cur);
    if(cur === "}") stack.pop();
  }
  if(stack.length !== 0) return false;
  return true;
}

使用兩個(gè)棧實(shí)現(xiàn)入隊(duì)與出隊(duì)

Array.prototype.enqueue = function(item){
  return this.push(item);
};
Array.prototype.dequeue = function(){
  var tempStack = [];
  var cur, temp;
  while(cur = this.pop()){
    tempStack.push(cur);
  }
  temp = tempStack.pop();
  while(cur = tempStack.pop()){
    this.push(cur);
  }
  return temp;
};

尋找連續(xù)數(shù)組中的缺失的多個(gè)數(shù)

var array = [2, 5, -1, 9, -6, 3, 7];
var result = findLost(array);
console.log(result);

function findLost(arr){
  if(arr.length <= 1) return null;
  var sortedArr = arr.sort(function(a,b){return a-b;});
  var i = sortedArr.shift();
  var cur = sortedArr.shift();
  var result = [];
  do{
    i++;
    if(cur === i) cur = sortedArr.shift();
    else result.push(i);
  }while(cur);
  return result;
}

數(shù)組中元素最大差值計(jì)算

給定某無(wú)序數(shù)組，求取任意兩個(gè)元素之間的最大差值，注意，這里要求差值計(jì)算中較小的元素下標(biāo)必須小于較大元素的下標(biāo)。

var array = [7, 8, 4, 9, 9, 15, 3, 1, 10];
var result = findLargestDifference(array);
console.log(result);
function findLargestDifference(arr){
  var min = arr[0];
  var diff = 0;
  for(var i = 1, len = arr.length; i < len; i++){
    if(arr[i] < min){
      min = arr[i];
      continue;
    }
    if(arr[i] - min > diff){
      diff = arr[i] - min;
    }
  }
  return diff;
}

數(shù)組中元素乘積

給定某無(wú)序數(shù)組，要求返回新數(shù)組 output ，其中 output[i] 為原數(shù)組中除了下標(biāo)為 i 的元素之外的元素乘積，要求以 O(n) 復(fù)雜度實(shí)現(xiàn)：

var firstArray = [2, 2, 4, 1];
var secondArray = [0, 0, 0, 2];
var thirdArray = [-2, -2, -3, 2];

console.log(productExceptSelf(firstArray)); // [8, 8, 4, 16]
console.log(productExceptSelf(secondArray)); // [0, 0, 0, 0]
console.log(productExceptSelf(thirdArray)); // [12, 12, 8, -12]

function productExceptSelf(arr){
  var result = [];
  var pro = 1;
  var len = arr.length;
  for(var i = 0; i < len; i++){
    result.push(pro);
    pro *= arr[i];
  }
  pro = 1;
  for(i = len - 1; i >= 0; i--){
    result[i] *= pro;
    pro *= arr[i];
  }
  return result;
}

數(shù)組扁平化

var arr = [1,2,[1,3,[2,[2,3,3],[2,5]]],[6,3]];

//傳統(tǒng)方式
function flat(arr,result=[]){
  if(arr.constructor !== Array) return [arr];
  var length = arr.length;
  arr.forEach(function(item){
    if(item.constructor !== Array) result.push(item);
    else result = flat(item, result);
  });
  return result;
}
var flatted = flat(arr);
console.log(flatted);          //[1, 2, 1, 3, 2, 2, 3, 3, 2, 5, 6, 3]

//優(yōu)雅方式
var arr=[1,3,4,5,[6,[0,1,5],9],[2,5,[1,5]],[5]];
var flatter = arr => arr.reduce((a, b) => a.concat(Array.isArray(b) ? flatter(b) : b), []);
console.log(flatter(arr));        //[1, 2, 1, 3, 2, 2, 3, 3, 2, 5, 6, 3]

//另一個(gè)方法，簡(jiǎn)單但有副作用：把數(shù)組內(nèi)的值全部轉(zhuǎn)換成了字符串類型
var flatten = a => a.join().split(",");
console.log(flatten(arr));     //["1", "2", "1", "3", "2", "2", "3", "3", "2", "5", "6", "3"]

查找字符串中出現(xiàn)次數(shù)最多的字符及數(shù)量

"ababccdeaeajxac".split("").sort().join("").match(/(w)1*/g).reduce(function(a,b){ return a.length > b.length ? a : {char: b[0], length: b.length};}, {char: "", length: 0});       //{char: "a", length: 5}

字符串查找

String.prototype.indexOf = String.prototype.indexOf || function(str){
  if(str.length > this.length) return -1;
  var len = 0;
  var _this = this.split(""), str = str.split("");
  var lenA = str.length, this_len = this.length;
  var temp;
  for(var i = 0, j = 0; j < lenA; i = 0, j = temp + 1, len = 0){
    debugger;
    while(str[i] !== _this[j] && j < this_len){
      j++;
    }
    temp = j;
    while(str[i] === _this[j] && j < this_len){
      len++;
      i++;
      j++;
    }
    if(len === lenA) return temp;
  }
  return -1;
}

字符串查找(KMP 算法)

String.prototype.indexOf = String.prototype.indexOf || function(str){
  var next = [];
  var n = this.length;
  var m = str.length;
  calcNext(str,next);
  for (var i = 0,q = 0; i < n; ++i){
      while(q > 0 && str[q] != this[i])
          q = next[q-1];
      if (str[q] === this[i]){
          q++;
      }
      if (q === m){
          return i - m + 1;
      }
  }
  return -1;


  function calcNext(str){
    var m = str.length;
    next[0] = 0;
    for(var q = 1, k = 0; q < m; ++q){
        while(k > 0 && str[q] != str[k])
            k = next[k-1];
        if (str[q] == str[k]){
            k++;
        }
        next[q] = k;
    }
  }
}

查看鏈表是否有環(huán)

function hasCircle(head){   //傳入鏈表頭
  var pos1 = head;
  var pos2 = head;
  while(pos2){
    pos1 = pos1.next;
    pos2 = pos2.next !== null ? pos2.next.next : null;
    if(pos1 === pos2) return true;
  }
  return false;
}

求一個(gè)數(shù)二進(jìn)制中 1 的個(gè)數(shù)

function numberOf1(n){
    if(n < 0){
        n = n >>> 0;
    }
    var arr = n.toString(2).split("");
    return arr.reduce(function(a,b){
        return b === "1" ? a + 1 : a;
    },0);
}

翻轉(zhuǎn)鏈表

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function reverseList(pHead){
    var newHead, temp;
    if(!pHead){
        return null;
    }
    if(pHead.next === null){
        return pHead;
    } else {
        newHead = ReverseList(pHead.next);
    }
    temp = pHead.next;
    temp.next = pHead;
    pHead.next = null;
    temp = null;
    return newHead;
}

判斷是否棧序輸出

例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。

function isPopOrder(pushV, popV){
    if(!pushV.length || !popV.length){
        return false;
    }
    var temp = [];
    var popIndex = 0;
    var len = pushV.length;
    for(var i = 0; i < len; i++){
        temp.push(pushV[i]);
        while(temp.length && temp[temp.length - 1] === popV[popIndex]){
            temp.pop();
            popIndex++;
        }
    }
    return temp.length === 0;
}

獲取字符串中字符的全排列(無(wú)重復(fù))

function permutation(str){
    if(!str || str.length === 0){
        return [];
    }
    var result = [];
    var arr = str.split("");
    var temp = "";
    ordering(arr);
    result = result.filter(function(item, index){  //去重
      return result.indexOf(item) === index;
    });
    return result;

    function ordering(tempArr){
        if(tempArr.length === 0){
            result.push(temp);
            return;
        }
        for(var i = 0; i < tempArr.length; i++){
            temp += tempArr[i];
            insideArr = tempArr.concat();
            insideArr.splice(i,1);
            ordering(insideArr);
            temp = temp.substring(0, temp.length - 1);   //回溯
        }
    }
}

查找有環(huán)鏈表的入環(huán)節(jié)點(diǎn)

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
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;
    }
}

云服務(wù)器 GPU云服務(wù)器 webrtc之vad算法簡(jiǎn)單算法看動(dòng)畫學(xué)算法之:hashtable 最簡(jiǎn)單的算法

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/97631.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

jokester

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

tensorflow怎么下載

閱讀 3016·2023-04-25 17:22
用純css實(shí)現(xiàn)打星星效果（三）

閱讀 1578·2019-08-30 15:54
視覺格式化模型(Visual formatting model)

閱讀 1305·2019-08-30 15:53
移動(dòng)端開發(fā)IOS 6PLUS中表單輸入造成的頁(yè)面高度縮小bug

閱讀 1831·2019-08-30 15:43
快速判斷瀏覽器是否支持特定css、js功能

閱讀 3116·2019-08-29 12:29
字符串replace方法的使用

閱讀 1267·2019-08-26 11:37
vue formData上傳圖片以及其他表單數(shù)據(jù)

閱讀 3310·2019-08-23 18:02
Ajax詳解

閱讀 1644·2019-08-23 14:15

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

算法基礎(chǔ)之簡(jiǎn)單算法

相關(guān)文章

**算法基礎(chǔ)之經(jīng)典算法**

**你需要知道的算法之基礎(chǔ)篇**

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列

發(fā)表評(píng)論

0條評(píng)論

jokester

男|高級(jí)講師

TA的文章

tensorflow怎么下載

用純css實(shí)現(xiàn)打星星效果（三）

視覺格式化模型(Visual formatting model)

移動(dòng)端開發(fā)IOS 6PLUS中表單輸入造成的頁(yè)面高度縮小bug

快速判斷瀏覽器是否支持特定css、js功能

字符串replace方法的使用

vue formData上傳圖片以及其他表單數(shù)據(jù)

Ajax詳解

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

算法基礎(chǔ)之簡(jiǎn)單算法

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！