ackuikui
首页文章专栏随笔记录
基础方法(必会)10种排序栈(计算器)hash表(统计字母次数)滑窗，双指针二分查找前缀和-缓存矩阵乘法递归分治贪心动态规划回溯DFS 搜索 BFS 搜索树

算法

使用语言 JavaScript ，排序，二分查找，滑窗，前缀和，回溯，贪心，动规，广搜

基础方法(必会)

  • 循环
    • for 
      let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
  if (arr[i] == 2) {
    continue;
  }
  if (arr[i] == 4) {
    break;
  }
  console.log(arr[i]);
}
    • while 
      let i = 11; // 10
while (i > 0) {
  if (i > 6) {
    i -= 3;
  } else {
    i -= 2;
  }
  console.log(i);
  if (i == 3) {
    break;
  }
}
  • 数组
    • [1,2,3].join(',')
    • [1].concat([2]), [1].concat([2], [3,4])
    • [1,2].slice(), [1,2].slice(1), [...arr]
    • [2,4,3].sort(), ['aa','b','ac','aab'].sort()
    • arr=[1,2,3,4],arr.splice(1,2), arr=[1,2,3,4],arr.splice(1,0,3)
    • [].push(9), [].unshift(2), [2].shift(), [9].pop()
    • reverse()
    • new Array(10).fill(0), new Array(10).fill([]).map(v=>[])
    • [a,b] = [b,a]
    • [...new Set([2,3,2])]
    • [2,3,2,4].filter(v=>v>2)
    • sum=0,[2,3,2,4].forEach((v,i)=> sum+=v)
    • sum = [2,3,4].reduce((tmp,v) => tmp+v, 1)
  • 字串
    • 'abc'.length
    • 'abcdef'.slice(1,3) bc
    • 'abcdef'.substr(1,2) bc
    • 'abcdef'.substring(1,3) bc
    • 'abcdef'.substring(4, 1) bcd
    • 'abcdef'.slice(1,-2) bcd
    • '11'.padStart(8,0) 前补齐8
  • 数
    • (123.115).toFixed(2), (123.125).toFixed(2), 123.11, 123.13
    • Math.round(22.50) 23
    • Math.sqrt(9)
    • Math.max(2,3)
    • Math.ceil(1.2)
    • Math.floor(1.8)
    • Math.floor(Math.random() * 6) + 3
  • ASICC
    • String.fromCharCode(65) A
    • 'a'.charCodeAt() 97
  • 进制
    • parseInt('11', 2) 3
    • parseInt('FF', 16) 255
    • (3).toString(2) 11
  • 位运算
    • 5>>1 二分下取整数
    • n & 1 == 0 偶数
  • 正则
    • '12as23s'.match(/\d/)
    • /\d/.test('aaas2'), /\w+/.test('aaas2'), /[b-d]/.test('aab22')

字串,数组(大数加法)

    let arr1 = '123'.split('').reverse()
    let arr1 = '456'.split('').reverse()
    let maxLen = Math.max( arr1.length, arr2.length)
    let result = []
    for(let i = 0; i < maxLen; i++){
        let a = Number(arr1[i]) || 0
        let b = Number(arr2[i]) || 0
        let v = (result[i] || 0) + a + b
        result[i] = v % 10
        if(v > 9){
            result[i+1] = 1
        }
    }
    console.log(result.reverse().join(''))

去重排序（明明的随机数）

let result = [... new Set(arr.sort((a, b) => {return a - b}))]

进制(存储1的个数)

let s = Number('4').toString(2)
console.log(s.replaceAll('0','').length)

正则(字符串最后一个单词的长度)

line.replace(/^.*\s(\w+)$/g, '$1').length
// slice lastIndexOf(' ')

递归（质数因子）

输入：180 输出：2 2 3 3 5

let arr = []
function getMin(num){
    let max = Math.floor(Math.sqrt(num))
    for(let i = 2; i <= max; i++){
        if(num % i == 0){
            num = num / i
            arr.push(i)
            getMin(num)
            break;
        } else if(i == max) {
            arr.push(num)
        }
    }
}
getMin(line)
console.log(arr.join(' '))

10种排序

10 种排序

  • 冒泡
  • 选择
  • 插入
  • 希尔
  • 归并
  • 快排
  • 堆
  • 桶
  • 计数
  • 基数

栈(计算器)

let strArr = '2+2*[3+4]'.split('')
let arr = []
for (let i = 0; i < strArr.length; i++) {
    let v = strArr[i];
    let ch = '['
    if (v == "]") {
        let a = [];
        while (v != ch) {
            v = arr.pop();
            if (v != ch) {
                a.unshift(v);
            }
        }
        let r = eval(a.join(""));
        arr.push(r);
    } else {
        arr.push(v);
    }
}
console.log(arr.join(""))

hash表(统计字母次数)

let str = 'abasseacdesa'
let obj = {}
for(let i = 0; i< str.length; i++){
    let k = str[i]
    obj[k] = (obj[k] || 0) + 1
}
console.log(obj['a'])

滑窗，双指针

最长无重复子串

let s = 'pwwkew'
let start = 0
let end = 1
let max = 0
while(end <= s.length){
    let tmp = s.substring(start, end)
    let index = tmp.indexOf(s[end])
    if(index == -1){
        end ++
    } else {
        start += index + 1
    }
    max = Math.max(max, tmp.length)
}
console.log(max)

二分查找

    // let nums = [1, 3, 5, 6]
    // let target = 2
    if (target < nums[0]) {
        return 0
    } else if (target > nums[nums.length - 1]) {
        return nums.length
    }

    let start = 0
    let end = nums.length - 1
    let mid = 0
    while (start <= end) {
        mid = (start + end) >> 1
        if (nums[mid] == target) {
            start = mid
            break
        } else if (nums[mid] > target) {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return start

前缀和-缓存

let arr = [34,24,53,22,64,42,63,32]
let cache = [arr[0]]
for(let i = 1; i<arr.length; i++){
   cache[i] = cache[i-1] + arr[i]
}
let sum = fn(cache, 2,4)
console.log(sum) // 86

function fn(cache, i,j){
  return cache[j] - cache[i]
}

矩阵乘法

矩阵乘法 3x2 * 2x1 = 3x1

x1 x2   y1    x1y1 + x2y2
x3 x4 * y2  = x3y1 + x4y2
x5 x6         x5y1 + x6y2
```js
for (let i = 0; i < x; i++) {
    for (let j = 0; j < z; j++) {
        for (let yi = 0; yi < y; yi++) {
            result[i][j] += arrA[i][yi] * arrB[yi][j];
        }
    }
}

递归分治

贪心

  • 中心下标（左右和-相等）
    let sum = nums.reduce((t, v) => t + v, 0)

    let tmp = 0
    return nums.findIndex(v => { tmp += v; return sum + v == tmp * 2 })
  • 心算挑战(最大k个和-为偶数)
    let cards = [1,10,5,2,9]
    let cnt = 4
    cards.sort((a, b) => b - a)

    let arr1 = [0]
    let arr2 = [0]

    cards.forEach((v, i) => {
        if (v % 2 == 0) {
            arr2.push(arr2[arr2.length - 1] + v)
        } else {
            arr1.push(arr1[arr1.length - 1] + v)
        }
    })
    let max = 0
    for (let k = 0; k < arr1.length; k += 2) {
        if (0 <= cnt - k && cnt - k < arr2.length) {
            max = Math.max(max, arr1[k] + arr2[cnt - k])
        }
    }
    return max
  • 跳跃游戏 贪心
    let nums = [3,2,1,0,4]
    
    let max = nums[0]
    let t = 0
    if(max >= nums.length-1) {
        return true
    }
    for(let i =0 ; i<=max; i++ ){
        t = nums[i] + i 
        if(t > max){
            max = t
            if(max >= nums.length-1){
                return true
            }
        }
    }
    return false

动态规划

  • 最长递增子序列，
    numsi > 前面的某个numsj, 则dpi = dpj + 1, i的长度为j的最大+1
    //  nums [10,  9, 2, 5, 3, 7, 101, 18]
    //  DP   [1,  1,  1, 2, 2, 3, 4,   4]
    let dp = new Array(nums.length).fill(1)
    let max = 1
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1
            }
        }
        if (dp[i] > max) {
            max = dp[i]
        }
    }
    console.log(max)
    return max

回溯

  • 全排列
    // [1, 2, 3]
    let tmp = []
    let result = []
    function back(arr) {
        if (tmp.length == nums.length) {
            result.push(tmp.slice())
            return
        }
        for (let i = 0; i < arr.length; i++) {
            let _arr = arr.slice()
            let v = _arr.splice(i, 1) // 每次抽取一个，剩下的再排列
            // tmp包含arr[i], 不用开辟_arr内存， used[i] = true;
            tmp.push(v[0])
            back(_arr)
            tmp.pop()
        }
    }
    back(nums)
    console.log(result)
    return result

DFS 搜索 BFS 搜索

  • 广度优选（200. 岛屿数量）沉岛
    let row = grid.length
    let col = grid[0].length
    let sum = 0
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid[i][j] == '1') {
                sum += 1
                // 四周-沉岛
                change(i, j)
            }
        }
        // console.log(grid)
    }
    return sum
    
    function change(i, j) {
        if (i < 0 || i >= row || j < 0 || j >= col) {
            return
        }
        grid[i][j] = 0
        if (grid[i][j + 1] == '1') {
            change(i, j + 1)
        }
        if (grid[i][j - 1] == '1') {
            change(i, j - 1)
        }
        if (grid[i + 1] && grid[i + 1][j] == '1') {
            change(i + 1, j)
        }
        if (grid[i - 1] && grid[i - 1][j] == '1') {
            change(i - 1, j)
        }
    }

树

  • (113.路径总和 II)
    let result = []
    let arr = []
    let sum = 0
    function getVal(nod) {
        if(!nod){
            return
        }
        arr.push(nod.val)
        sum += nod.val // -= 透传剩余
        if (!nod.left && !nod.right) {
            if (sum == targetSum) {
                result.push(arr.slice())
            }
        } else {
            if (nod.left) {
                getVal(nod.left)
            }
            if (nod.right) {
                getVal(nod.right)
            }
        }
        arr.pop()
        sum -= nod.val
    }
    getVal(root)
    // console.log(result)
    return result