算法题目

[wuxianqiang]

整数反转

function revese (x) {
  let rev = 0
  while (x !== 0) {
    console.log(x)
    if (rev < Number.MIN_VALUE / 10 || rev > Number.MAX_VALUE / 10) {
      return 0
    }
    let digit = x % 10
    x = Math.floor(x / 10)
    rev = rev * 10 + digit
  }
  return rev
}

字符串反转

var reverseString = function(s) {
    const n = s.length;
    for (let left = 0, right = n - 1; left < right; ++left, --right) {
        [s[left], s[right]] = [s[right], s[left]];
    }
};

两数只和等于target

function total(nums, target) {
  let map = new Map()
  map.set(nums[0], 0)
  for (let i = 1; i < nums.length; i++) {
    let x = target - nums[i]
    if (map.has(x)) {
      return [i, map.get(x)]
    }
    map.set(nums[i], i)
  }
}

两数只和等于target，给定的是有序数组

// 双指针
function twoSum (numbers, target) {
  let left = 0;
  let right = numbers.length - 1
  while (left < right) {
    if (numbers[left] + numbers[right] === target) {
      return [left, right]
    }
    if (numbers[left] + numbers[right] < target) {
      left++
    } else {
      right--
    }
  }
  return [-1, -1]
}

罗马数字转换

function change (s) {
  let sum = 0;
  let i;
  for (i = 0; i < s.length - 1; i++) {
    sum += getValue(s[i + 1]) > getValue(s[i]) ? -getValue(s[i]) : getValue(s[i])
  }
  // 处理最后一个字符
  sum += getValue(s[i])
  return sum
}

console.log(change('IV'))

最长公共前缀

//  纵向扫描法
function longestCommonPrefix(strs) {
  if (strs == null || strs.length == 0) {
    return ''
  }
  for (let i = 0; i < strs[0].length; i++) {
    let c = strs[0][i]
    for (let j = 1; j < strs.length; j++) {
      console.log(strs[j][i], c)
      if (i === strs[j].length || strs[j][i] !== c) {
        return strs[0].substring(0, i)
      }
    }
  }
  return strs[0]
}

// 二分查找

function longestCommonPrefix(strs) {
  if (strs == null || strs.length == 0) {
    return ''
  }
  let minLength = Number.MAX_VALUE
  for (let i = 0; i < strs.length; i++) {
    minLength = Math.min(minLength, strs[i].length)
  }
  let low = 0;
  let high = minLength
  while (low < high) {
    let mid = (high + low) >> 1
    if (isCommonPrefix(strs, mid)) {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
  return strs[0].substring(0, low)
}

function isCommonPrefix(strs, length) {
  let str0 = strs[0].substring(0, length)
  let count = strs.length
  for (let i = 1; i < count; i++) {
    let str = strs[i]
    for (let j = 0; j < length; j++) {
      if (str0[j] !== str[j]) {
        return false
      }
    }
  }
  return true
}

console.log(longestCommonPrefix(['12121212', '12', '1234']))

删除数组中重复的项目

//  双指针
function removeDuplicates( nums) {
  let n = nums.length
  if (n === 0) {
    return 0
  }
  let fast = 1
  let slow = 1
  while (fast < n) {
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow] = nums[fast]
      ++slow
    }
    ++fast
  }
  return slow
}

移除元素，删除数组中指定的重复元素

var removeElement = function(nums, val) {
  let left = 0, right = nums.length;
  while (left < right) {
      if (nums[left] === val) {
          nums[left] = nums[right - 1];
          right--;
      } else {
          left++;
      }
  }
  return left;
};

搜索插入位置

function insert (arr, num) {
  let left = 0
  let right = arr.length - 1
  let ans = right
  while (left < right) {
    let mid = (left + right) >> 1
    let target = arr[mid]
    if (target >= num) {
      ans = mid
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  console.log(ans)
}

二叉树的中序遍历

var inorderTraversal = function(root) {
    const res = [];
    const inorder = (root) => {
        if (!root) {
            return;
        }
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);
    return res;
};

合并已排序的数组

function mergeArray(first, sec) {
  var temp = []
  var t = 0

  var i = 0
  var j = 0
  var k
  // 取较短的数组开始loop
  var mid = (first.length <= sec.length) ? first.length - 1 : sec.length - 1
  while (i <= mid && j <= mid) {
    //关键的逻辑在于这行
    k = (first[i] < sec[j]) ? first[i++] : sec[j++]
    //过滤重复元素
    if (t > 0 && k == temp[t - 1]) {
      continue
    }
    temp[t++] = k
  }

  // 将first数组中剩余的元素追加到temp
  while (i <= first.length - 1) {
    k = first[i++]
    if (t > 0 && k == temp[t - 1]) continue
    temp[t++] = k
  }
  // 将sec数组中剩余的元素追加到temp
  while (j <= sec.length - 1) {
    k = sec[j++]
    if (t > 0 && k == temp[t - 1]) continue
    temp[t++] = k
  }

  return temp
}

console.log(mergeArray([1, 2, 3], [2, 3, 4, 6]))

合并二叉树

    function mergeTrees(t1, t2) {
      if (t1 == null)
        return t2;
      if (t2 == null)
        return t1;
      t1.value += t2.value;
      let left = mergeTrees(t1.left, t2.left);
      if (left) {
        t1.left = left
      }
      let right = mergeTrees(t1.right, t2.right);
      if (right) {
        t1.right = right
      }
      return t1;
    }
    console.log(mergeTrees(rootA, rootB))

判断对称二叉树

function isSymmetric (root) {
  return isMirror(root, root)
}

function isMirror (t1, t2) {
  if (t1 == null && t2 == null) return true;
  if (t1 == null || t2 == null) return false;
  return (t1.value === t2.value) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right)
}

console.log(isSymmetric(node1))

二叉树翻转

function reverse(node) {
  if (node != null) {
    let temp = node.left;
    node.left = node.right;
    node.right = temp;
    reverse(node.left);
    reverse(node.right);
  }
}

二叉树的最大深度

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

二叉树的最小深度

function minDepth (root) {
  if (root === null) {
    return 0
  }
  return 1 + Math.min(minDepth(root.left), minDepth(root.right))
}

将有序数组转换为二叉树

// 尽量构建一个平衡二叉树，使元素均匀分布
function solution(nums) {
  function TreeNode(value) {
    this.value = value
    this.left = null
    this.right = null
  }
  function arrayToBST(nums, start, end) {
    if (end < start) {
      return null
    }
    let mid = (start + end) >> 1
    let root = new TreeNode(nums[mid])
    root.left = arrayToBST(nums, start, mid - 1)
    root.right = arrayToBST(nums, mid + 1, end)
    return root
  }
  return arrayToBST(nums, 0, nums.length - 1)
}

console.log(solution([-10, -3, 0, 5, 9]))

路径总和

function hasPathSum (root, sum) {
  if (root === null) {
    return false
  }
  let node = [root]
  let value = [root.value]
  while (node.length) {
    let now = node.pop()
    let temp = value.pop()
    if (temp === sum) {
      return true
    }
    if (now.left && now.left !== null) {
      node.push(now.left)
      value.push(now.left.value + temp)
    }
    if (now.right && now.right !== null) {
      node.push(now.right)
      value.push(now.right.value + temp)
    }
  }
  return false
}

计算买卖股票的最佳时机

function maxProfix (prices) {
  if (!prices) {
    return 0
  }
  let min_price = Number.MAX_VALUE // 记录最小的股值
  let max_profit = 0; // 最大的利润
  for (let i = 0; i < prices.length; i++) {
    let p = prices[i]
    if (p < min_price) {
      // 当前股值小于最小股值时，记录到最小股值里面
      min_price = p
    }
    if (p - min_price > max_profit) {
      // 当前利润大于最大利润时，记录到最大利润值里面
      max_profit = p - min_price
    }
  }
  return max_profit
}

let arr = [7, 1, 5, 3, 6, 4]
console.log(maxProfix(arr))

判断回文字符串

// 双指针
function isPaindrome(s) {
  if (!s) {
    return true
  }
  let left = 0
  let right = s.length - 1
  while (left < right) {
    if (s[left] !== s[right]) {
      return false
    }
    left++
    right--
  }
  return true
}

console.log(isPaindrome('abba'))

只出现一次的数字

function singleNumber (nums) {
  // 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次
  let set = new Set()
  for (let i = 0; i < nums.length; i++) {
    let current = nums[i]
    if (set.has(current)) {
      set.delete(current)
    } else {
      set.add(current)
    }
  }
  console.log(set)
}

console.log(singleNumber([1, 2, 2, 3, 3]))

二叉树先序遍历

function preorderTrvaersal (root) {
  function preorder (root, res) {
    if (root === null) {
      return
    }
    res.push(root.value)
    preorder(root.left, res)
    preorder(root.right, res)
  }
  let res = []
  preorder(root, res)
  return res
}

二叉树后续遍历

function postorderTrvaersal (root) {
  function postorder (root, res) {
    if (root === null) {
      return
    }
    postorder(root.left, res)
    postorder(root.right, res)
    res.push(root.value)
  }
  let res = []
  postorder(root, res)
  return res
}

阶乘后的零

function trailingZeroes (n) {
  // 先计算阶乘
  function sum (num) {
    if (num <= 1) {
      return 1
    } else {
      return num * sum(num - 1)
    } 
  }
  // 再计算零
  let count = sum(n)
  let zero_count = 0
  while (count % 10 === 0) {
    zero_count += 1
    count /= 10
  }
  return zero_count
}

console.log(trailingZeroes(5))

计数质数 质数的定义：在大于 11 的自然数中，除了 11 和它本身以外不再有其他因数的自然数

const isPrime = x => {
  for (let i = 2; i * i <= x; i++) {
    if (x % i === 0) {
      return false
    }
  }
  return true
}

function countPrimes (n) {
  let ans = 0
  for (let i = 2; i < n; i++) {
    ans += isPrime(i)
  }
  return ans
}

丑数 若 n 是丑数，则 n 可以写成 n = 2^a 3^b 5^c

var isUgly = function(n) {
    if (n <= 0) {
        return false;
    }
    const factors = [2, 3, 5];
    for (const factor of factors) {
        while (n % factor === 0) {
            n /= factor;
        }
    }
    return n == 1;
};

存在重复元素

var containsDuplicate = function(nums) {
    const set = new Set();
    for (const x of nums) {
        if (set.has(x)) {
            return true;
        }
        set.add(x);
    }
    return false;
};

用队列实现栈 栈是一种后进先出的数据结构，元素从顶端入栈，然后从顶端出栈。 队列是一种先进先出的数据结构，元素从后端入队，然后从前端出队。

// 队列 shift首部删除 unshift 首部添加

// 栈 push 添加， pop 删除

class MyStack {
  constructor () {
    this.queue1 = []
    this.queue2 = []
  }
  push (x) {
    this.queue2.push(x)
    while (this.queue1.length) {
      this.queue2.push(this.queue1.shift())
    }
    let temp = this.queue1
    this.queue1 = this.queue2
    this.queue2 = temp
  }
  pop () {
    return this.queue1.shift()
  }
}

const stack = new MyStack()
stack.push(88)
stack.push(99)
console.log(stack.pop())
console.log(stack.queue1)

进制转换

function mulBase(num, base) {
  var s = [];
  do {
    s.push(num % base);
    num = Math.floor(num /= base);
  } while (num > 0);
  var converted = "";
  while (s.length > 0) {
    converted += s.pop();
  }
  return converted;
}

实现栈

function Stack() {
  this.dataStore = [];
  this.top = 0;
  this.push = push;
  this.pop = pop;
  this.peek = peek;
  this.clear = clear;
}
function push(element) {
  this.dataStore[this.top++] = element;
}
function pop() {
  return this.dataStore[--this.top];
}

function peek() {
  return this.dataStore[this.top - 1];
}

function length() {
  return this.top;
}

function clear() {
  this.top = 0;
}

let stack = new Stack()
stack.push(1)
stack.push(2)
stack.clear()

汇总区间

function summaryRanges (nums) {
  let ret = []
  let i = 0
  let n = nums.length;
  while (i < n) {
    let low = i;
    i++
    while (i < n && nums[i] === nums[i - 1] + 1) {
      i++
    }
    let high = i - 1;
    let temp = ['' + nums[low]]
    // 每次遇到相邻元素之间的差值大于 11 时
    if (low < high) {
      temp.push('->')
      temp.push('' + nums[high])
    }
    ret.push(temp.join(''))
  }
  return ret
}

console.log(summaryRanges([1,2,3, 6,7,8]))

2的幂

var isPowerOfTwo = function(n) {
    return n > 0 && (n & (n - 1)) === 0;
};

二叉搜索树的最近公共祖先

//p 和 q 的最近公共祖先就是从根节点到它们路径上的「分岔点」
function lowestCommon (root, p, q) {
  let ancestor = root
  while (true) {
    if (p.value < ancestor.value && q.value < ancestor.value && ancestor.left) {
      // 如果当前节点的值大于 p 和 q 的值，说明 p 和 q 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
      ancestor = ancestor.left
    } else if (p.value > ancestor.value && q.value > ancestor.value && ancestor.right) {
      // 如果当前节点的值小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；
      ancestor = ancestor.right
    } else {
      break
    }
  }
  return ancestor
}

有效的字母异位词 t 是 ss 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 ss 和 tt 分别排序，看排序后的字符串是否相等即可判断

var isAnagram = function(s, t) {
    return s.length == t.length && [...s].sort().join('') === [...t].sort().join('')
};

二叉树的所有路径

function binaryTree (root) {
  let paths = []
  let construct_paths = (root, path) => {
    if (root) {
      path += root.value.toString()
      if (root.left === null && root.right === null) {
        paths.push(path)
      } else {
        // 当前节点不是叶子节点，继续递归
        path += '->'
        construct_paths(root.left, path)
        construct_paths(root.right, path)
      }
    }
  }
  construct_paths(root, '')
  return paths
}

各位相加

function addDigits(num) {
  return (num - 1) % 9 + 1;
}

缺失数字

function missingNumber (nums) {
  // [0, 1, 2]
  nums.sort((a, b) => a - b)
  // 判断n出现在末位
  if (nums[nums.length - 1] !== nums.length) {
    return nums.length
  }
  // 判断0出现在首位
  if (nums[0] !== 0) {
    return 0
  }
  for (let i = 1; i < nums.length; i++) {
    let expectedNum = nums[i - 1] + 1
    if (nums[i] !== expectedNum) {
      return expectedNum
    }
  }
  return -1
}

移动零

function mmoveZeroes(nums) {
  let n = nums.length
  let left = 0
  let right = 0
  while (right < n) {
    if (nums[right]) {
      swap(nums, left, right)
      left++
    }
    right++
  }
}

function swap(arr, a, b) {
  if (a === b) {
    return
  }
  let temp = arr[a]
  arr[a] = arr[b]
  arr[b] = temp
}

let arr = [1, 2, 3]
mmoveZeroes(arr)
console.log(arr)

3 的幂 找出数字 n 是否是数字 b 的幂的一个简单方法是，n%3 只要余数为 0，就一直将 n 除以 b。

function isPowerOfThree(n) {
  if (n < 1) {
      return false;
  }

  while (n % 3 == 0) {
      n /= 3;
  }

  return n == 1;
}

完全平方根

function isPerfectSquare (num) {
  if (num < 2) {
    return true
  }
  let left = 2
  let right = num / 2
  let guessSquared;
  while (left <= right) {
    x = (left + right) >> 1
    guessSquared = x * x;
    if (guessSquared === num) {
      return true
    }
    if (guessSquared > num) {
      right = x - 1
    } else {
      left = x + 1
    }
  }
  return false
}

中序遍历，二叉树最小绝对值差

function getMin (root) {
  let ans = Number.MAX_VALUE
  let pre =  -1;
  const dfs = (root) => {
    if (root === null) {
      return
    }
    dfs(root.left)
    if (pre === -1) {
      pre = root.value
    } else {
      ans = Math.min(ans, root.value - pre)
      pre = root.value
    }
    dfs(root.root)
  }
  dfs(root)
  return ans;
}

判断一颗树是另一颗树的子树

function isSubtree(s, t) {
  function dfs (s, t) {
    if (s === null) {
      return false
    }
    return check(s, t) || dfs(s.left, t) || dfs(s.right, t)
  }
  function check (s, t) {
    if (s === null && t === null) {
      return true
    }
    if (s === null || t === null || s.value !== t.value) {
      return false
    }
    return check(s.left, t.left) && check(s.right, t.right)
  }
  return dfs(s, t)
}

根据二叉树创建字符串

function tree2str(t) {
  if (t === null) {
    return ''
  }
  if (t.left === null && t.right === null) {
    return t.value + ''
  }
  if (t.right === null) {
    return t.value + '(' + tree2str(t.left) + ')'
  }
  return t.value + '(' + tree2str(t.left) + ')(' + tree2str(t.right) + ')'
}

寻找数组中的中心索引

function pivotIndex (nums) {
  const total = nums.reduces((a, b) => a + b, 0)
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    if (2 * sum + nums[i] === total) {
      return i
    }
    sum += nums[i]
  }
  return -1
}

前位分割数

var thousandSeparator = function(n) {
    let count = 0;
    let ans = "";
    do {
        let cur = n % 10;
        n = Math.floor(n / 10);
        ans += cur.toString();
        ++count;
        if (count % 3 == 0 && n) {
            ans += '.';
        }
    } while (n);
    return ans.split('').reverse().join('');
};

深度克隆

function deepClone (obj, hash = new WeakMap()) {
  if (obj == null) return obj;
  if (obj instanceof Date) return new Date(obj);
  if (obj instanceof RegExp) return new RegExp(obj);
  if (typeof obj === 'symbol') {
    let desc = obj.description
    return desc ? Symbol(desc) : Symbol()
  }
  if (typeof obj !== 'object') return obj;
  if (hash.has(obj)) return hash.get(obj);
  let cloneObj = new obj.constructor;
  hash.set(obj, cloneObj);
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      cloneObj[key] = deepClone(obj[key]);
    }
  }
  return cloneObj;
}

调度器

//JS实现一个带并发限制的异步调度器Scheduler，保证同时运行的任务最多有两个。完善代码中Scheduler类，使得以下程序能正确输出
class Scheduler {
  constructor() {
    this.awaitArr = [];
    this.count = 0;
  }
  async add(promiseCreator) {
    this.count >= 2 ? await new Promise(resolve => this.awaitArr.push(resolve)) : '';
    this.count++;
    const res = await promiseCreator();
    this.count--;
    this.awaitArr.length && this.awaitArr.shift()();
    return res;
  }
}

const timeout = (time) => new Promise(resolve => {
  setTimeout(resolve, time)
})

const scheduler = new Scheduler()

const addTask = (time, order) => {
  scheduler.add(() => timeout(time)).then(() => console.log(order))
}

addTask(1000, '1')
addTask(500, '2')
addTask(300, '3')
addTask(400, '4')
// output: 2 3 1 4

// 一开始，1、2两个任务进入队列
// 500ms时，2完成，输出2，任务3进队
// 800ms时，3完成，输出3，任务4进队
// 1000ms时，1完成，输出1
// 1200ms时，4完成，输出4

模版字符串

let render = function (str, data) {
  // 模板技术呢，就是替换特殊标签的技术
  let  tpl  =  str.replace(/<%=([\s\S]+?)%>/g, (match, code) => {
    return `' + obj.${code} + '`
  });
  tpl = `let tpl = '${tpl}'\nreturn tpl;`
  console.log(tpl)
  let complied = new Function('obj', tpl);
  return complied(data);
};

let tpl = 'Hello <%=username%>.';
let res = render(tpl, {username: 'Jackson Tian'})
console.log(res) // Hello Jackson Tian.