【JavaScript】フロントエンドに必須のコード整理(leetcodeの問題解を含む)

もっとleetcodeの問題は私のgithubの上にあります.ここをクリックして、また更新し続けます.
一般的なデータ構造とアルゴリズム
これらのコードはすべてleetcodeの上でACテーマになりました.
二分割検索

const binarySearch = function (nums, target) {
  if(nums === null || nums.length === 0) {
    return -1
  }
  let left = 0,
    right = nums.length - 1
  while(left <= right) {
    let middle = left + Math.floor((right - left) / 2)
    if(target < nums[middle]) {
      right = middle - 1
    } else if(target > nums[middle]) {
      left = middle + 1
    } else {
      return middle
    }
  }
  return -1
}

二叉の木は再帰前の順序で遍歴しません.

//     
/**
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

var preorderTraversal = function(root) {
  if(!root) return []
  let result = []
  let stack = []
  stack.push(root)
  while(stack.length) {
    let current = stack.pop()
    result.push(current.val)
    if(current.right) {
      stack.push(current.right)
    }
    if(current.left) {
      stack.push(current.left)
    }
  }
  return result
};

二叉の木は再帰的ではない中、順番に巡回します.

var inorderTraversal = function(root) {
   let result = []
   let stack = []
   while(root !== null) {
    stack.push(root)
    root = root.left
   }
   while(stack.length) {
     let current = stack.pop()
     result.push(current.val)
     current = current.right
     while(current) {
       stack.push(current)
       current = current.left
     }
   }
   return result
};

二叉の木は再帰しないで、順番に巡回します.

var postorderTraversal = function (root) {
  if (!root) return []
  let result = []
  let head = root   //           
  let current = null  //          
  let stack = [head]
  while (stack.length !== 0) {      //      ，     
    current = stack[stack.length - 1]  //        current 
    if (current.left && head !== current.left && head !== current.right) { //       
      stack.push(current.left)   
    } else if (current.right && head !== current.right) { //         
      stack.push(current.right) 
    } else {
      result.push(stack.pop().val)
      head = current
    }
  }
  return result
};

二叉の木の階層は巡回して、列の広さを優先的に遍歴します.

var levelOrder = function (root) {
  if (root === null) {
    return [];
  }
  //            (   )
  let queue = [],
    result = []
  queue.push(root)
  while (queue.length !== 0) {
    //            
    let level = [] //        
    let size = queue.length //    size
    for (let i = 0; i < size; i++) {
      node = queue.shift()
      level.push(node.val)
      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }
    result.push(level)
  }
  return result
};

二叉の木の最大の高さを求めます.

      function fn(root) {
    return maxDepth(root)
  }

  //     ：   root             
  function maxDepth(root) {
    //     
    if(root === null) {
      return 0
    }
    //     
    let leftHeight = maxDepth(root.left)
    let rightHeight = maxDepth(root.right)
    return Math.max(leftHeight, rightHeight) + 1
  }

判定リターン文字列

var isPalindrome = function(s) {
    let length = s.length
    if(length === 0 || length === 1) return false
    let left = 0, right = length - 1
    while(left < right) {
      if(s[left++] != s[right--]) {
        return false
      }
    }
    return true
};

泡の並べ替え

 //    ，    ，                  ，        ，        
  bubbleSort = function (array) {
    var length = array.length
    for (var i = 0; i < length; i++) {
      for (var j = 0; j < length - 1 - i; j++) {
        if (array[j] > array[j + 1]) {
         swap(array, j, j + 1)
        }
      }
    }
  }

クイックソート

function quickSort(array) {
  let left = 0, 
    right = array.length - 1
    index

  if (array.length > 1) {
    //index                    
    index = partition(array, left, right)
    if (left < index - 1) {
      quickSort(array, left, index - 1)
    }
    if (index < right) {
      quickSort(array, index, right)
    }
  }
}

function partition(array, left, right) {
  let point = array[Math.floor((right + left) / 2)] //       
  let i = left,
    j = right
  while (i <= j) {
    while (array[i] < point) {
      i++
    }
    while (array[j] > point) {
      j--
    }
    if (i <= j) {
         swap(array, i, j )
      i++
      j--
    }
  }
  return i
}

並べ替えを選択

  //    ，              ，          
   function selectSort(array) {
     let length = array.length,
      minIndex
      for(let i = 0; i < length; i++) {
        minIndex = i
        for(let j = 0; j 

JavaScript常用コード
シシシシシシシシシシシシシシシシシシシ菚関数の手ぶれと節流を防ぎます.

//    

function fn() {}
var cd = false  //cd false        

button.onclick = function() {
  if(!cd) {  
    cd = true
    setTimeout(()=> {
      fn()
      cd = false
    }, 3000)
  }
}

//  
function fn() {}
var timeId = null
button.onclick = function () {
  if(timeId) { //           
    window.clearTimeout(timeId)
  }
  timeId = setTimeout(() => {
    fn()
    timeId = null
  }, 5000)
}

再帰的に深度コピーを実現する

var deepCopy = function(obj) {
    if (typeof obj !== 'object') return;
    var newObj = obj instanceof Array ? [] : {};
    for (var key in obj) {
        if (obj.hasOwnProperty(key)) {
            newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
        }
    }
    return newObj;
}

シングルモード

let Single = (function() {
  let _instance = null
  function init(props) {
    return {
      publickMethod: function(){

      },
      value: props.value
    }
  }
  return function(props) {
    if(!_instance) {
      _instance = init(props)
    }
    return _instance
  }
})()
let instance = Single({value: 10})

購読モードを公開

  //      
  let Observer = function() {
    _message = {}
    return {
      //                ，                  
      on(type, callback) {
        if(_message[type]) {
          _message[tyep] = [callback]
        } else {
          _message[tyep].push(callback)
        }
      },
      //    
      emit(type, args) {
        if(!_message[type]) {
          return 
        }
        let events = {
          type,
          args: args || {}
        }
        let length = _message[type].length
        for(let i = 0; i < length; i++) {
          _message[type][i].call(this, events)
        }
      },
      //             
      remove(type) {
        if(_message[type]) {
          delete _message[type]
        }
      },
      once(type, callback) {
        on(type, (args) => {
          callback(args)
          remove(type)
        })
      }
    }
  }