前端常见算法

1. 冒泡算法

function bubbleSort(arr) {
  var i = 0;
  var j = 9;
  for (i = 1; i < arr.length; i++) {
    for (j = 0; j < arr.length; j++) {
      var temp = 0;
      if (arr[j] > arr[i]) {
        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
      }
    }
  }
  return arr;
}

1. 翻转字符串

思路一: 反向遍历字符串

function reverseString(str) {
  var tmp = "";
  for (var i = str.length - 1; i >= 0; i--) tmp += str[i];
  return tmp;
}

转化成 array 操作

function reverseString(str) {
  var arr = str.split("");
  var i = 0,
    j = arr.length - 1;
  while (i < j) {
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    j--;
  }
  return arr.join("");
}

1. 生成指定长度随机字符串

2. 随机生成验证码

let code = "";
const arr = new Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
const codeLength = 6;
for (var i = 0; i < codeLength; i++) {
  var index = Math.floor(Math.random() * 10);
  console.log("index", index);
  code += arr[index];
}
return code;

1. 数组去重

function unique(arr) {
  var obj = {};
  var result = [];
  for (var i in arr) {
    if (!obj[arr[i]]) {
      obj[arr[i]] = true;
      result.push(arr[i]);
    }
  }
  return result;
}

1. 数组中最大差值

function getMaxProfit(arr) {
  var min = arr[0];
  var max = arr[0];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }
  return max - min;
}
getMaxProfit([2, 3, 10, 11, 23, 34]);

1. 生成斐波那些数列

function getfib(n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n > 1) return getfib(n - 1) + getfib(n - 2);
}
function fibo(len) {
    var fibo = [];
    for (var i = 0; i < len; i++) {
        fibo.push(getfib(i));
    }
    return fibo;
}
`

1. 二分查找法

function binary_search(arr, key) {
    var low = 0,
        high = arr.length - 1;
    while (low <= high) {
        var mid = parseInt((high + low) / 2);
        if (key == arr[mid]) {
            return mid;
        } else if (key > arr[mid]) {
            low = mid + 1;
        } else if (key < arr[mid]) {
            high = mid - 1;
        }
    }
    return -1;
    // 递归
    function binary_search2(arr, low, high, key) {
        if (low > high) return -1;
        var mid = parseInt((low + high) / 2);
        if (key == arr[mid]) {
            return mid;
        } else if (key > arr[mid]) {
            return binary_search2(arr, mid + 1, high, key);
        } else if (key < arr[mid]) {
            return binary_search2(arr, low, mid - 1, key);
        }
    }

1. 实现一个函数, 判断输入是不是回文字符串

1. 斐波那契

let fiber(num){
    let cache = [];
    let fib = function (num) {
        if(num <= 1) return 1;
        return fib(num - 1) + fib(num - 2);
    };
    if(cache[num]){
        return cache[num]
    } else {
       cache[num] =  fib(num);
    }
    return cache[num];
};


// 备忘录形式
let fiber = function(num){
    let cache = [];
    let fib = function (cache, num) {
        if(num <= 1) return 1;
        if(cache[num]){
            return cache[num]
        } else {
           cache[num] = fib(cache,num - 1) + fib(cache, num - 2);;
        }
        return cache[num];
    };
    return fib(cache, num)
};
console.log(fiber(200));

尾递归调用优化

let fib = function (num, num1 = 1, num2 = 1) {
  return num <= 1 ? num2 : fib(num - 1, num2, num1 + num2);
};
// fib(5) => 8

永远只有一个调用记录, 调用函数产生一个调用记录, 最后一步操作 return 把当前函数的计算结果当做参数传递给了下一个自身调用.

1. 判断是不是回文字符串

function isPlalindrome(input) {
  if (typeof input !== "string") return false;
  return input.split("").reverse().join("") === input;
}

// 不使用 api
function isPlalindrome(input) {
  if (typeof input !== "string") return false;
  let i = 0,
    j = input.length - 1;
  while (i < j) {
    if (input.charAt(i) !== input.charAt(j)) return false;
    i++;
    j--;
  }
  return true;
}

1. 不含重复字符串的最长子串的长度

// 解法一: 维护数组:
// 使用一个数组来维护滑动窗口
// 遍历字符串, 判断字符串是否在滑动窗口数组里

* 不在则 push 进数组
* 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
* 然后将 max 更新为当前最长子串的长度

var lengthOfLongestSubstring = function(s) {
    let arr = [], max = 0
    for(let i = 0; i < s.length; i++) {
        let index = arr.indexOf(s[i])
        if(index !== -1) {
            arr.splice(0, index+1);
        }
        arr.push(s.charAt(i))
        //arr.push(s[i])
        max = Math.max(arr.length, max);
    }
    return max
};
console.log(lengthOfLongestSubstring("abcabcbb"));

1. 有效的括号

var isValid = function (s) {
  let map = {
    "{": "}",
    "(": ")",
    "[": "]",
  };
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (map[s[i]]) {
      stack.push(s[i]);
    } else if (s[i] !== map[stack.pop()]) {
      return false;
    }
  }
  return stack.length === 0;
};

这种方式也可以

var isValid = function (s) {
  let map = {
    "{": "}",
    "(": ")",
    "[": "]",
  };
  const arr = [];
  for (var i = 0; i < s.length; i++) {
    if (map[s[i]]) {
      arr.push(map[s[i]]);
      console.log("111", arr[i]);
    } else if (!map[s[i]] && arr.pop() === s[i]) {
      console.log("att", arr, s[i]);
    } else {
      arr.push(s[i]);
    }
  }
  return arr.length >= 1 ? false : true;
};

1. 删除字符串中的所有相邻重复项

var removeDuplicates = function (s) {
  if (s.length < 0) return [];
  const arr = [];
  for (var i = 0; i < s.length; i++) {
    let pre = arr.pop();
    if (pre !== s[i]) {
      arr.push(pre);
      arr.push(s[i]);
    }
  }
  return arr.join("");
};

1. 最小栈

var MinStrack = function () {
  this.items = [];
  this.min = null;
};
MinStrack.prototype.push = function (item) {
  if (this.items.length === 0) this.min = item;
  this.min = Math.min(this.min, item);
  this.items.push(item);
};
const strack = new MinStrack();
MinStrack.prototype.pop = function () {
  this.items.pop();
  this.min = Math.min(...this.items);
};
MinStrack.prototype.top = function () {
  if (!this.items.length) return null;
  return this.items[this.items.length - 1];
};
strack.push(3);
strack.push(2);
strack.push(5);
strack.pop();
// 时间复杂度：进栈O(1)，出栈O(n)，获取栈顶元素O(1)，获取最小元素O(1)
// 空间复杂度：O(n)

1. 整数反转

var reverse = function (x) {};

1. 爬楼梯

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  const dp = [];
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};
// 调用栈的深度是楼梯数 n，空间复杂度是O(n)O(n)，时间复杂度最坏是O(2^n)O(2n)，所有节点都遍历到。

可以用动态规划的问题都能用递归 从子问题入手，解决原问题，分两种做法：自顶向下和自底向上 前者对应递归，借助函数调用自己实现，是程序解决问题的方式，它不会记忆解 后者对应 DP，利用迭代将结果存在数组里，从数组 0 位开始顺序往后计算 递归的缺点在于包含重复的子问题，DP 的效率更高

1. 打家劫舍

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length;
    if(len == 0){
      return 0;
    }
    const dp = new Array(len + 1);
    dp[0] = 0;
    dp[1] = nums[0];
  for(let i = 2; i <= len; i++) {
      dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
  }
  return dp[len];
}
    console.log(rob([2, 7, 9, 3, 1]));

1. 1. 词典中最长的单词

/**
 * @param {string[]} words
 * @return {string}
 */
var longestWord = function (words) {
  //按长度排序，如果长度相同，按字典序降序排列,
  let map = new Map();
  words.sort(function (a, b) {
    if (!map.has(a)) map.set(a, 1);
    if (!map.has(b)) map.set(b, 1);
    if (a.length == b.length) {
      for (let i = 0; i < a.length; ++i) {
        if (a[i] != b[i]) return b[i].charCodeAt() - a[i].charCodeAt();
      }
    } else return a.length - b.length;
  });
  //字典序的降序排列保证同长度下满足条件的第一个一定是字典序最小的
  for (let i = words.length - 1; i >= 0; --i) {
    let flag = true;
    //如果到了一个长度的字符必然是true
    for (let j = 0; j < words[i].length - 1; ++j) {
      let temp = words[i].substr(0, j + 1);
      if (!map.has(temp)) flag = false;
    }
    if (flag) return words[i];
  }
  return "";
};

1. 整数去反

var reverse = function (x) {
  let numString = x.toString();
  const MAXVALUE = Math.pow(2, 31) - 1;
  let res = "";
  if (numString[0] === "-") {
    res = "-" + reverse(Number(numString.slice(1)));
  } else {
    res = numString.split("").reverse().join("");
    if (Number(res) > MAXVALUE) return 0;
  }
  return res;
};