算法

[cristinazhou]

1、repeat 方法
const repeatFunc = repeat(console.log, 4, 3000)
repeatFunc("hellworld"); // 会输出 4次 helloworld, 每次间隔3秒
function repeat(func, times, wait) {
    var timer = null;
    var count = 0;

    return function () {
        const context = this;
        const args = arguments;

        const func1 = function () {
            if (count === times) {
                clearTimeout(timer);
                return;
            }
            count++;
            timer = setTimeout(() => {
                func.apply(context, args);
                func1();
            }, wait)
        }
        func1();
    }
}

2、event 发布订阅
class Event {

    constructor() {
        this.eventMap = {}
    }

    on (eventName, func) {
        if(this.eventMap[eventName]) {
            this.eventMap[eventName].push(func)
        } else {
            this.eventMap[eventName] = [func]
        }
    }

    off (eventName, func) {
        if(this.eventMap[eventName]) {
            this.eventMap[eventName] = this.eventMap[eventName].filter(cb => cb!== func)
        }
    }

    once(eventName, callback) {
        const onceCallback = data => {
            callback(data)
            this.off(eventName, onceCallback)
        }
        this.on(eventName, this.onceCallback)
    }

    trigger(eventName, data) {
        if(this.eventMap[eventName]) {
            this.eventMap[eventName].forEach(callback => {
                callback(data)
            })
        }

    }
}

3、对象深拷贝
const isObject = (obj) => typeof obj === 'object'

function deepClone(obj, map = new WeakMap()) {

    if(!isObject(obj)) return obj

    if(map.has(obj)) return map.get(obj)
    const newObj = Array.isArray(obj) ? [] : {}
    map.set(obj, newObj)
    Reflect.ownKeys(obj).forEach(key => {
        newObj[key] =  isObject(obj[key]) ? deepClone(obj[key], map) : obj[key]
    })
    return obj
}
const b = { c: 3 }
const a = { a : 1, b: b}
const cloneA = deepClone(a)
console.info(cloneA)

4、判断回文字符串
function isHuiwen(str) {
    let arr = str.split('')
    for(let i =0 ; i< arr.length/2 + 1; i++) {
        if(arr[i] !== arr[arr.length - 1-i]) {
            return false
        } else {
            continue
        }
    }
    return true
}
let a = 'abba'
let b = 'acdca'
let c = 'favdkoll'
console.info(isHuiwen(a))
console.info(isHuiwen(b))
console.info(isHuiwen(c))

5、函数 防抖 ，函数节流
function debounce(fn, wait) {
    let timer = null
    return function() {
        clearTimeout(timer)
        timer = setTimeout(() => {
            fn.apply(this, arguments)
        }, time)
    }

}

// 节流函数
function throttle(fn, wait) {

    let flag = true
    return function() {

        if(!flag) return
        flag = flag
        setTimeout(() => {
            fn.apply(this, arguments)
            flag = true
        }, time)
    }

}

6、全排列
// abc  , abc,acb,bac,bca,cab,cba 
function getGroup(str) {
    const arr = str.split('')
    const result = [] 

    function dfs(temp) {
        if (temp.length === arr.length) { 
            result.push(temp)
            return
        }
        for (let i = 0; i < arr.length; i++) { 
            if (!temp.includes(arr[i])) { 
                dfs([...temp, arr[i]])
            }
        }
    }
    dfs([])
    return result

}

7、数组拍平
// 数组拍平 arr = [1,2, ['3', '4' , '5', [6, [7, 8], 9, 10]]]
function flat(arr) {
    const result = []

    for (let i = 0; i < arr.length; i++) { 
        if (Array.isArray(arr[i])) {
            result.push(...flat(arr[i]))
        } else { 
            result.push(arr[i])
        }
    }
    return result
}
function flatten(arr) {
    return arr.reduce((a, b) => {
      // return Array.isArray(b) ? a.concat(flatten(b)) : a.concat(b);
      return a.concat(Array.isArray(b) ? flatten(b) : b);
    }, []);
  };
let arr = [1,2, ['3', '4' , '5', [6, [7, 8],9, 10]]]
let res1 = flat2(arr)
console.info('res1',res1)

8、逗号分割
// 1234567.90    1,234,567.90
function slove(num) {
    const arr = num.toString().split('.')
    const part1 = arr[0].split('')
    const part2 = arr[1]
    let res = ''

    part1.reverse().forEach((value, index) => { 
        if (index !== 0 && index % 3 === 0) {
            res = value + ',' + res
        } else { 
            res = value + '' + res
        }

    })
    return res+ '.' + part2

}

let num1 = 1234567.90
// let res1 = slove(num1)
// console.info('res1', res1)

// 先行断言
function format_with_regex(number) {
    return !(number + '').includes('.')
      ? // 就是说1-3位后面一定要匹配3位
        (number + '').replace(/\d{1,3}(?=(\d{3})+$)/g, (match) => {
          return match + ',';
        })
      : (number + '').replace(/\d{1,3}(?=(\d{3})+(\.))/g, (match) => {
          return match + ',';
        });
  }
  console.log(format_with_regex(1243250.990));

9、最长无重复子串
// s: 'ababdfghbc'
function longestSubStr(str) {

    let map = new Map()
    let max = 0
    let i = 0

    let arr = str.split('')
    for (let j = 0; j < arr.length; j++) { 
        if (map.has(arr[j])) {
            i = map.get(arr[j]) + 1

        } 
        max = Math.max(j - i + 1, max)
        map.set(arr[j], j)

    }
    return max
}
console.info(longestSubStr('ababdfghbc'))
console.info(longestSubStr('bbbbb'))
// pwwkew
console.info(longestSubStr('pwwkew'))

10、小于n的最大数
// 23121   { 2, 4, 9 }   22999
// 23121  { 7 8 9 }  9999
var res = ''
function largestNum(sum, arr) {
    var target = sum + ''
    DFS(0, false, 0, arr, target)
    return res
}
function DFS(index, flag, sum, arr, target) {
    if (index === target.length) {
        res = sum
        return true;
    }
    if(flag){
        return DFS(index+1, true, sum*10 + arr[arr.length-1], arr, target);
    } else {
        let temp = target.charAt(index) - '0';
        for(let i = arr.length-1; i >= 0; i--){
            if(arr[i] === temp){
                if(DFS(index+1, false, sum*10 + arr[i], arr, target)){
                    return true;
                }
            } else if (arr[i] < temp) {
                if(DFS(index+1, true, sum*10 + arr[i], arr, target)){
                    return true;
                }
            }
        }
    }
    // 数组中最小的元素都大于数字该位的值
    if(index !== 0) return false;  // 回溯一步（退回一步）
    else return DFS(index+1, true, sum, arr, target);
}

let res1 = largestNum(23121, [2, 4, 9])
let res2 = largestNum(23121, [7, 8, 9])

console.info('res1', res1)
console.info('res2', res2)

11、岛屿数量
let grid1 = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
]

let grid2 = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let count = 0
    const m = grid.length
    const n = grid[0].length

    for (let i = 0; i < m; i++) { 
        for (let j = 0; j < n; j++) { 
            if (grid[i][j] === "1") {
                solve(i, j)
                count++
            } else { 
                continue
            }

        }
    }

   function solve(i, j) {
        if (i - 1 >= 0 && i - 1 <= m - 1 && grid[i-1][j] === '1') { 
            grid[i - 1][j] = 0
            solve(i-1, j)
        }
        if (j - 1 >= 0 && j - 1 <= n - 1 && grid[i][j-1] === '1') { 
            grid[i][j-1] = 0
            solve(i, j-1)
        }
        if (i + 1 >= 0 && i + 1 <= m - 1 && grid[i+1][j] === '1') { 
            grid[i+1][j] = 0
            solve(i+1, j)
        }
        if (j + 1 >= 0 && j + 1 <= n - 1 && grid[i][j+1] === '1') { 
            grid[i][j + 1] = 0
            solve(i, j + 1)
        }
    }
    return count

};

let res1 = numIslands(grid2)
console.info('res1', res1)

12、
// 最长回文子串
// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let dp = [];
    let res = '';
    for (let i = 0; i < s.length; i++) {
        dp[i] = [];
        for (let j = 0; j < s.length; j++) {
            dp[i][j] = 0;
            res = s[j]
        }
        dp[i][i] = true;
    }

      for(let i = s.length -1;i >= 0;i--){
          for(let j = i;j < s.length;j++){
              dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i+1][j-1]);
              if(dp[i][j] && j - i +1 > res.length){
                  res = s.substring(i,j+1);
              }
          }
      }
      return res;

  };

13、最长回文子串的长度
// 输入:s = "abccccdd"
// 输出:7
// 解释:
// 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
/**
 * @param {string} s
 * @return {number}
 */
// var longestPalindrome = function(s) {

// };

// 示例 1：

// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案。
// 示例 2：

// 输入：s = "cbbd"
// 输出："bb"
// leetcode  516. 最长回文子序列 
var longestPalindromeSubseq = function(s) {
  let dp = [];
  for (let i = 0; i < s.length; i++) {
      dp[i] = [];
      for (let j = 0; j < s.length; j++) {
          dp[i][j] = 0;
      }
      dp[i][i] = 1;
  }
  for (let i = s.length - 1; i >= 0; i--) {
    for (let j = i + 1; j < s.length; j++) {
        console.info('i', i)
        console.info('j', j)
          if (s[i] === s[j]) {
              dp[i][j] = dp[i + 1][j - 1] + 2;
          } else {
              dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
          }
      }
  }
  console.info('dp', dp)
  return dp[0][s.length - 1];
};
console.info(longestPalindromeSubseq("bbbab"))
console.info(longestPalindromeSubseq("cbbd"))

14、数组的最大区间和
// 考点：动态规划基础算法
// 输出一个 int 型数组的最大连续子数组（所有元素加和最大）各个元素之和​
// # 保证数组中至少有一个正数​

// 例：​

// 输入：{1，2，5，-7，8，-10}​

// 输出：9 (子数组为: {1，2，5，-7，8})
function findRangeMaxSum(arr) { 
    const m = arr.length

    const dp = new Array(m).fill(0)
    dp[0] = arr[0]
    let max = dp[0]

    for (let i = 1; i < m; i++) { 
        dp[i] = dp[i - 1] > 0 ? dp[i - 1] + arr[i] : arr[i]
        if (dp[i] > max) { 
            max = dp[i]
        }
    }

    return max

}

let input1 = [1, 2, 5, -7, 8, -10]
let res1 = findRangeMaxSum(input1)
console.info('res1', res1)

15、大数相加
function addBigNumbers(num1, num2) {
    let sum = ''
    let curry = 0
    let i = num1.length - 1
    let j = num2.length - 1

    while (i >= 0 || j >= 0 || curry > 0) {
        const n1 = +(num1[i] || 0)
        const n2 = +(num2[j] || 0)

        let temp = n1 + n2 + curry
        sum = temp % 10 + sum

        if (temp > 10) {
            curry = 1
        } else { 
            curry = 0
        }
        i--
        j--
    }
    return sum

}
const base62ToDecimal = (str) => {
    const base = 62
    const digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    let len = str.length
    let sum = 0
    let n =0 // 最后一位是0，倒数第二位是1...

    while (len--) {
      let digit = digits.indexOf(str[ len ]) // 获取当前位的10进制数，例如a表示10进制的10，b表示11，c表示12...
      sum += digit * Math.pow(base, n)
      n++
    }
    return sum
}
const decimalToBase62 = (decimal) => {
    const base = 62
    const digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    let result = []

    while (decimal > 0) {
      const remainder = decimal % base // 取余

      result.push(digits[ remainder ]) // 将余数真正对应62进制字符存入数组

      decimal = Math.floor(decimal / base) // 计算商，用于下次计算
    }

    return result.reverse().join('') || '0' // 反转结果
  }

function addBigNumbersBase62(num1, num2) { 
    let a = base62ToDecimal(num1) + ''
    let b = base62ToDecimal(num2) + ''
    let res = addBigNumbers(a, b)
    return decimalToBase62(res)
}

console.log(addBigNumbers('19', '23')) // 42
console.log(addBigNumbers('100', '1024')) // 1124

console.log(addBigNumbersBase62('1a', '2')) // 1124

16、快排
function quickSort(arr) {
       if (arr.length <= 1) {
           return arr;
       }

       const pivot = arr[0];
       const left = [];
       const right = [];

       for (let i = 1; i < arr.length; i++) {
           arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
       }

       return quickSort(left).concat(pivot, quickSort(right));
   }

17、promise 请求并发限制
// 3. 实现一个请求限制（3分钟写完）
function scheduler(max) {
    let queue = [] 
    let count = 0

    const run = () => { 
        if (count < max && queue.length > 0) { 
            const { request, resolve, reject } = queue.shift()
            count++
            request().then(res => { 
                resolve(res)
                count--
                run()
            }).catch(err => { 
                reject(err)
                count--
                run()
            })
        }

    }

    return (request) => { 
        return new Promise((resolve, reject) => {
            queue.push({ request, resolve, reject})
            run()
        })
    }
}

const addRequest = scheduler(2);
const request1 = () => {
  return new Promise((rs) => {
    setTimeout(() => {
        rs(1)
    }, 500)
  })
}
const request2 = () => {
  return new Promise((rs) => {
    setTimeout(() => {
          rs(2)
    }, 800)
  })
}
const request3 = () => {
  return new Promise((rs) => {
    setTimeout(() => {
          rs(3)
    }, 1000)
  })
}
const request4 = () => {
  return new Promise((rs) => {
    setTimeout(() => {
        rs(4)
    }, 1200)
  })
}
addRequest(request1).then((res) => {
  console.log(res);
})
addRequest(request2).then((res) => {
  console.log(res);
});
addRequest(request3).then((res) => {
  console.log(res);
});
addRequest(request4).then((res) => {
  console.log(res);
});