算法

算法

实现千位分隔符

function numberWithCommas(x) {
  x = x.toString();
  var pattern = /(-?\d+)(\d{3})/;
  while (pattern.test(x)) x = x.replace(pattern, "$1,$2");
  return x;
}
numberWithCommas(12312124545); //'12,312,124,545'
numberWithCommas(123121245.45); //'123,121,245.45'

冒泡排序

function bubbleSort(arr) {
    for(let i=0; i<arr.length; i++) {
        for(let j=1; j<arr.length-i; j++) {
            if(arr[j] < arr[j-1]) {
                let temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
    return arr;
}
console.log(bubbleSort([3, 2, 1, 4, 5])); // [1, 2, 3, 4, 5]

选择排序

function selectionSort(arr) {
    for(let i=0; i<arr.length; i++) {
        let min = i;
        for(let j=i+1; j<arr.length; j++) {
            if(arr[j] < arr[min]) {
                min = j;
            }
        }
        let temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
    return arr;
}
console.log(selectionSort([3, 2, 1, 4, 5])); // [1, 2, 3, 4, 5]

插入排序

function insertionSort(arr) {
    for(let i=1; i<arr.length; i++) {
        let current = arr[i];
        let j = i - 1;
        while(j >= 0 && arr[j] > current) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = current;
    }
    return arr;
}
console.log(insertionSort([3, 2, 1, 4, 5])); // [1, 2, 3, 4, 5]

快速排序

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for(let i=0; i<arr.length; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([3, 2, 1, 4, 5])); // [1, 2, 3, 4, 5]

归并排序

function mergeSort(arr) {
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length/2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let result = [];
    while(left.length && right.length) {
        if(left[0] < right[0]) {
            result.push(left.shift())
        }else{
            result.push(right.shift())
        }
    }

    while(left.length) {
        result.push(left.shift())
    }

    while(right.length) {
        result.push(right.shift())
    }

    return result;
}

二分查找

function bSearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

求数组的交集并集差集

let nums1 = [1, 2, 3];
let nums2 = [2, 3, 4, 5];

// 求交集
function intersection(nums1, nums2) {
  return nums1.filter((item) => {
    return new Set(nums2).has(item);
  });
}

console.log(intersection(nums1, nums2));

// 求并集
function sumSet(nums1, nums2) {
  return [...new Set([...new Set(nums1), ...new Set(nums2)])];
}
console.log(sumSet(nums1, nums2));

// 求差集
function differenceSet(nums1, nums2) {
  return nums1
    .filter((item) => !new Set(nums2).has(item))
    .concat(nums2.filter((item) => !new Set(nums1).has(item)));
}

console.log(differenceSet(nums1, nums2));

实现方法rotate(arr, k)，第一个参数为数组，第二个参数为非负数，将数组向右移动 k 步

function rotate(arr, num) {
    let len = arr.length;
    num = num%len;
    return arr.slice(num).concat(arr.splice(0, num));
}

let arr = [1, 2, 3, 4];
rotate(arr, 2);

给定一个字符串 str，返回字符串中字母顺序最大的并且同时在字符串中出现大写和小写的字母，不存在返回~

function printBigLetter(str) {
    let arr = str.split('');
    arr.sort((a, b) => {return b.charCodeAt() - a.charCodeAt()})
    let index = 0;
    while(arr[index].charCodeAt() > 90) {
        // 找大写，如果arr[i].charCodeAt()<90就不再循环
        if(arr.join("").lastIndexOf(arr[index].toUpperCase()) !== -1) {
            return arr[index].toUpperCase();
        }
        index++;
    }
    return '~'
}

回文括号 {[({[]})]}，[{)]

function palindromeBrackets(str) {
    let arr = str.split('');
    let stack = [];
    let obj = {'(' : ')', '{' : '}', '[' : ']'};
    for(let i=0; i<arr.length; i++) {
        if(arr[i] === '(') {stack.push(obj[arr[i]])}
        else if(arr[i] === '{') {stack.push(obj[arr[i]])}
        else if(arr[i] === '[') {stack.push(obj[arr[i]])}
        else if(arr[i] !== stack[stack.length-1] || stack.length===0) return false;
        else stack.pop();
    }
    // 如果栈中还有值，说明左边括号多，返回false
    if(stack.length > 0) {
        return false;
    }
    return true;
}