2017年7月于長(zhǎng)城

一、如下是一個(gè)tree樹的實(shí)現(xiàn)，寫出結(jié)果：

var s=[];
var arr=s;
    for(var i=0;i<3;i++){
    var pusher = {
        value: "item"+i
        },tmp;
     if(i!==2){
        tmp = []
        pusher.children = tmp
    }
    arr.push(pusher);
    arr = tmp;  // arr做了一個(gè)對(duì)象指針的移動(dòng)，等于上一個(gè)children
}
console.log(s[0]);

// {
      value: "item0",
      children:[
           {
             value: "item1",
             children:[{
                 value: "item2"
             }]
            }
      ]
  }

二、查找如下有序數(shù)組中31出現(xiàn)的位置，最快的查找方法是什么，JavaScript怎么實(shí)現(xiàn)？

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

對(duì)于一個(gè)已經(jīng)排好序的數(shù)組，最快定位的方法是二分查找

function find (arr, item) {
    var low = 0;  //設(shè)定下標(biāo)
    var high = arr.length - 1; // 設(shè)定上標(biāo)
    while (high >= low) {
        var mid = Math.floor((low + high) / 2);   //二分查找的關(guān)鍵
        if (arr[mid] === item) {
            return mid;
        }else if (arr[mid] > item) {
             high = mid;
        } else if (arr[mid] < item){
            low = mid;
        } 
    }
    return  -1;
}

三、 用JavaScript實(shí)現(xiàn)數(shù)組的快速排序：

快速排序過程只需要三步：

• 1、在數(shù)據(jù)集中，選擇一個(gè)元素作為“基準(zhǔn)”(pivot)。（基準(zhǔn)值可以任意選擇，但是選擇中間的值比較容易理解）
• 2、所有小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊；所有大于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的右邊。
• 3、對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。
  使用js數(shù)組方法及遞歸

function quickSort(arr) {
   if(arr.length <= 1) return arr;
   var index = Math.floor(arr.length / 2);
   var key = arr.splice(index, 1)[0];
   var left = [],right = [];
   arr.forEach(function(v){
       v <= key ? left.push(v) : right.push(v);
   });
   return quickSort(left).concat([key], quickSort(right));
}

四、寫出單向鏈表和雙向鏈表的添加和刪除操作的實(shí)現(xiàn)過程。

單向鏈表的添加：

function insert(newElement, item){
    var newNode = new Node(newElement);  // 新建一個(gè)節(jié)點(diǎn)
    var current = this.find(item);   //找到item的位置(current在js中是引用，類似于C語(yǔ)言指針)
    newNode.next = current.next;  //將新節(jié)點(diǎn)的后繼指向item的后繼
    current.next = newNode;  // 修改item節(jié)點(diǎn)的后繼指向新節(jié)點(diǎn)
}

單向鏈表的刪除：

// 首先要找到刪除元素的上一個(gè)節(jié)點(diǎn)
function findPrevious (item) {
    var currentNode = this.head;
    while (!(currentNode.next === null) && (currentNode.element !== item)) {
    return currentNode;
    }
}

function remove (item) {
    var prevNode = this.findPrevious(item);
    var currentNode = this.find(item); // 查找到當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)
    if (!(prevNode.next === null)) {
        prevNode.next = prevNode.next.next; //待刪除節(jié)點(diǎn)的前驅(qū)的后繼 指向 原本待刪除節(jié)點(diǎn)的后繼
        currentNode.next = null; // 釋放節(jié)點(diǎn)，防止內(nèi)存泄漏
    }
}

雙向列表的添加：

// 插入節(jié)點(diǎn)，注意插入的鏈指向
function insert(newElement, item){
    var newNode = new Node(newElement);  // 新建一個(gè)節(jié)點(diǎn)
    var current = this.find(item);   //找到item的位置
    newNode.next = current.next;  //將新節(jié)點(diǎn)的后繼指向item的后繼
        newNode.previous = current;
        current.next = newNode;
        if (newNode.next !== null) {
                newNode.next.previous = newNode; // 將item原本的位置的前驅(qū)指向新節(jié)點(diǎn)
        }
}

雙向鏈表的刪除：

function remove (item) {
    var currentNode = this.find(item);
    if (!(currentNode === null)) {
        currentNode.previous.next = currentNode.next; // 刪除節(jié)點(diǎn)的前驅(qū)的后繼，指向刪除節(jié)點(diǎn)的后繼
        currentNode.next.previous = currentNode.previous; //刪除節(jié)點(diǎn)的后繼的前驅(qū)，指向刪除節(jié)點(diǎn)的前驅(qū)
        currentNode.next = null; // 釋放節(jié)點(diǎn)，防止內(nèi)存泄漏
        currentNode.previous = null;
    } else {
        currentNode.previous.next = null; // 尾節(jié)點(diǎn)的前驅(qū)的后繼指向null
        currentNode.previous = null; // 釋放尾節(jié)點(diǎn)
    }
}

五、用代碼實(shí)現(xiàn)二叉搜索樹，寫出相關(guān)方法查找最小值。

//定義節(jié)點(diǎn)
function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
}

// 插入值
function insert (data) {
    var n = new Node(data, null, null); // 定義一個(gè)新節(jié)點(diǎn)
    if(this.root === null) {
        this.root = n;
    } else {
        var current = this.root;
        var parent;
        while (true) {
            parent = current;
            if (data < current.data) {
                current = current.left; // 比當(dāng)前值小就放左邊
                if (current === null) {
                    parent.left = n;
                    break;
                }
            } else {    // 比當(dāng)前值大就放右邊
                current = current.right;
                if(current === null){
                    parent.right = n;
                    break;
                }
            }
        }
    }
}

// 找最小值
function getSmallest (root) {
    // 一直往左子樹上去找，找到?jīng)]有左節(jié)點(diǎn)即找到了最小值
    var current = this.root || root;
    while (!(current.left === null)) {
        current = current.left;
    }
    return current;
}

六、編寫一個(gè)方法，求一個(gè)字符串的字節(jié)長(zhǎng)度：

(一個(gè)英文字符占1個(gè)字節(jié)，一個(gè)中文字符占2個(gè)字節(jié))

function getBytes(str) {
        var len = str.length;
        var bytes = len;
        for (var i = 0; i< len; i++) {
                if (str.charCodeAt(i) >= 128) {     // 如果判斷是中文字符就+1
                        bytes++;
                }
        }
        return bytes;
}

七、找出一個(gè)正數(shù)數(shù)組的最大差值：

function getDifference(arr) {
        var minValue = arr[0];
        var maxDifference = 0;
        for (var i = 0; i < arr.length; i++) {
                var current = arr[i];
                minValue = Math.min(minValue, current);    // 用一個(gè)臨時(shí)變量存較小的值
                var difference = current - minValue;
                maxDifference = Math.max(maxDifferent, potential);
        }
        return maxDifference;
}

ES6擴(kuò)展運(yùn)算符

function getDifference(arr){
    var max = Math.max(...arr);  // 找出最大值
    var min = Math.min(...arr);   // 找出最小值
    return max - min;
}

數(shù)組sort排序

function getDifference(arr){
    var arr = arr.sort();
        var min = arr[0];
        var max = arr[arr.length-1];
        return maxDifference = max - min;
}

八、判斷一個(gè)單詞是否是回文：

（如mamam）

function isPalindrome(str) {
    var len = str.length;
    var start = Math.ceil(len / 2);
    while (start < len) {
        if(str[start] !== str[len - start - 1]) {
            return false;
        };
        start++;
    }
    return true;
}

九、數(shù)組去重：

function unique(arr) {
    var result = [];

    arr.forEach(function(v){
        if(result.indexOf(v) < 0) {
            result.push(v);
        }
    });
    return result;
}

十、計(jì)算字符串中出現(xiàn)次數(shù)最多的字母及次數(shù)：

function findMaxDuplicate(str){
    if (str.length === 1) return str;
    
    var charObj = {};
    for(var i=0; i<str.length; i++){
        if(!charObj[str.charAt(i)]){
            charObj[str.charAt(i)] = 1;
        } else {
            charObj[str.charAt(i)] += 1;
        }
    }
    var maxChar = '',
    maxValue = 1;
    for(var k in charObj) {
        if (charObj[k] >= maxValue) {
            maxChar = k;    
            maxValue = charObj[k];
        }
    }
    return '出現(xiàn)次數(shù)最多的是：'+ maxChar +',一共'+charObj[maxChar]+'次'
}

十一、寫一個(gè)isPrime()函數(shù)，當(dāng)其為質(zhì)數(shù)時(shí)返回為true，否則返回false。

(質(zhì)數(shù)：大于1且只能被1和它本身整除的數(shù))

function isPrime(number) {
    if (typeof number !== 'number' || !Number.isInteger(number)) {
        return false;
    } 
    if (number < 2) {
        return false;
    } else if (number === 2) {
        return true;
    } else if (number % 2 === 0) {
        return false;
    }
    var squareRoot = Math.sqrt(number); // 求平方根
    for(var i = 3; i <= squareRoot; i += 2) {
        if (number % i === 0) {
            return false;
        }
    }
    return true;
}

十二、對(duì)下列字符串進(jìn)行排序，按照字符串中的數(shù)字排序：

"hell2o wor5ld Compa1y T4est 3abc"
1.首先對(duì)給定字符串根據(jù)空格進(jìn)行分割，畢竟數(shù)組比字符串更容易操作。
2.接著制定排序規(guī)則，哪個(gè)單詞中包含的數(shù)字更大，排名就靠后。
3.然后，用數(shù)組的sort方法，傳入排序規(guī)則匿名函數(shù)，進(jìn)行定制排序。
4.最后，將sort后的數(shù)組進(jìn)行聚合，返回字符串。

function FindNumber(str){  
    for(var i=0;i<str.length;i++){  
        var chr = str.charAt(i);  
        if(!isNaN(chr)){  
            return parseInt(chr);  
        }  
    }  
}  
  
function Order(words){  
    return words.split(" ").sort(function(a,b){  
        return findNumber(a) - findNumber(b); 
    }).join(" ");  
}  

十三、寫一個(gè)flat函數(shù)將如下一個(gè)多層嵌套數(shù)組輸出成字符串。

輸入：['a', ['b', 'c'], 1, 2, ['d', 'e'], 'f', 3, 4]
輸出：a, b, c, 1, 2, d, e, f, 3, 4

方法一：遞歸方法

var arr = ['a', ['b', 'c', ['d']], 1, 2, ['e', 'f'], 'g', 3, 4];
function flat (arr) {
      var result = [];
      var each = function (arr) {
            arr.forEach(item => {
                  if (item instanceof Array) {
                       each(item);
                   } else {
                       result.push(item);
                   }
            });
       }
       each(arr);
       return result.join(',');
}

flat(arr);

方法二：toString格式轉(zhuǎn)換

var arr = ['a', ['b', 'c', ['d']], 1, 2, ['e', 'f'], 'g', 3, 4];

Array.prototype.toString = function () {
    return this.join(',');  // 這里this就是arr數(shù)組
}

var flat = function (arr) {
    return arr + '';
}

flat(arr);

十四、將1234567 變成 1,234,567，即千分位標(biāo)注

// 方法一：
function exchange(num) {
     num = String(num); // 轉(zhuǎn)成字符串
    if (num.length <= 3) {
        return num;
    }

    num = num.replace(/\d{1,3}(?=(\d{3})+$)/g, (v) => {
        return v + ',';
    });
    return num;
}

exchange(1234567)  // 1,234,567

// 方法二
function format(num){  
   num = String(num); // 數(shù)字轉(zhuǎn)字符串  
  var str=""; // 字符串累加  
  for(var i = num.length - 1, j=1; i>=0; i--, j++){  
      if(j%3 == 0 && i !== 0){ // 每隔三位加逗號(hào)，過濾正好在第一個(gè)數(shù)字的情況  
          str+=num[i]+","; // 加千分位逗號(hào)  
          continue;  
      }  
      str+=num[i]; // 倒著累加數(shù)字
  }  
  return str.split('').reverse().join(""); // 字符串=>數(shù)組=>反轉(zhuǎn)=>字符串 
}

十五 、有100格臺(tái)階，可以跨1步可以跨2步，一共有多少種走法：

(本質(zhì)是斐波那契數(shù)列)

function step(){
    this.n1 = 1;
    this.n2 = 2;
    this.total = 100;
    this.getFunction = getFunction;
}

var Stairs = new step();

function getFunction(){
    for(i=2; i<this.total;i++){
        res = this.n1 + this.n2;
        this.n1 = this.n2;
        this.n2 = res;
    }
    return res;
}

var totalStairs = Stairs.getFunction();
console.log(totalStairs);

// 方法二：
function fib(n) {
  let array = new Array(n + 1).fill(null)
  array[0] = 0
  array[1] = 1
  for (let i = 2; i <= n; i++) {
    array[i] = array[i - 1] + array[i - 2]
  }
  return array[n]
}

十六、多維數(shù)組問題
1、多維數(shù)組轉(zhuǎn)一維數(shù)組：

let arr = ['a', ['b', 'c'], 1, 2, ['d', 'e'], 'f', 3, 4]
arr.concat.apply([], arr)  // ["a", "b", "c", 1, 2, "d", "e", "f", 3, 4]