前端常见算法题

数组去重

let arr = [1, 2, 3, 4, 5, 3, 2];

// 方法1：使用 Set 去重
let set = new Set(arr);
let uniqueArr = Array.from(set);

// 方法2：使用 filter 过滤重复元素
let uniqueArr = arr.filter((item, index) => arr.indexOf(item) === index);

// 方法3：使用 for 循环去重
let uniqueArr = [];
for (let i = 0; i < arr.length; i++) {
    if (uniqueArr.indexOf(arr[i]) === -1) {
        uniqueArr.push(arr[i]);
    }
}

排序算法

let arr = [3, 1, 5, 4, 2];

// 方法1：使用 sort 排序
arr.sort((a, b) => a - b);

// 方法2：使用 for 循环排序
for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            let temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

二分查找

let str = 'hello world';

// 方法1：使用 split、reverse、join 实现
let reverseStr = str.split('').reverse().join('');

// 方法2：使用 for 循环实现
let reverseStr = '';
for (let i = str.length - 1; i >= 0; i--) {
    reverseStr += str[i];
}

快排

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];

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

斐波那契数列

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

简单的模板引擎实现

let template = `
<ul>
  <% for(let i=0; i < data.length; i++) { %>
    <li><%= data[i] %></li>
  <% } %>
</ul>
`;

let render = (template, data) => {
  let evalExpr = /<%=(.+?)%>/g;
  let expr = /<%([\s\S]+?)%>/g;

  template = template
    .replace(evalExpr, (match, code) => `' + ${code} + '`)
    .replace(expr, (match, code) => `'; ${code}; html += '`);

  let html = `let html = '${template}'; return html;`;

  return new Function('data', html)(data);
};

let data = [1, 2, 3, 4, 5];
let html = render(template, data);

console.log(html);

冒泡排序

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

let arr = [5, 4, 3, 2, 1];
console.log(bubbleSort(arr));

深拷贝的实现

1. JSON.parse(JSON.stringify(obj))：可以实现简单的对象的深拷贝，但是不支持函数、正则表达式、undefined、循环引用等特殊情况。
2. 递归：通过递归的方式对对象进行拷贝，可以实现更为灵活的深拷贝，支持特殊情况。

function deepClone(obj) {
  let result = Array.isArray(obj) ? [] : {};
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      if (typeof obj[key] === 'object') {
        result[key] = deepClone(obj[key]);
      } else {
        result[key] = obj[key];
      }
    }
  }
  return result;
}

数组中的最大/小值

let arr = [1, 2, 3, 4, 5];
let max = arr.reduce((a, b) => Math.max(a, b));
let min = arr.reduce((a, b) => Math.min(a, b));
console.log(max, min);

字符串的回文判断

function isPalindrome(str) {
  return str === str.split('').reverse().join('');
}

function isPalindrome(str) {
  let len = str.length;
  for (let i = 0; i < len / 2; i++) {
    if (str.charAt(i) !== str.charAt(len - 1 - i)) {
      return false;
    }
  }
  return true;
}

function isPalindrome(str) {
  return str === str.split(/[\W_]/g).reverse().join('');
}

搜索算法，例如 BFS 和 DFS

const bfs = (root, target) => {
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    if (node.value === target) return node;
    node.children.forEach(child => queue.push(child));
  }
  return null;
};

const dfs = (node, target) => {
  if (node.value === target) return node;
  for (const child of node.children) {
    const result = dfs(child, target);
    if (result) return result;
  }
  return null;
};

动态规划，例如计算背包问题

动态规划 (Dynamic Programming) 是一种用于解决最优化问题的算法。在背包问题中，我们需要选择物品，以便在不超过背包容量的情况下获得最大价值。

function knapsack(capacity, weights, values, n) {
  let i, w;
  let K = [];
  for (i = 0; i <= n; i++) {
    K[i] = [];
  }

  for (i = 0; i <= n; i++) {
    for (w = 0; w <= capacity; w++) {
      if (i === 0 || w === 0) {
        K[i][w] = 0;
      } else if (weights[i - 1] <= w) {
        K[i][w] = Math.max(
          values[i - 1] + K[i - 1][w - weights[i - 1]],
          K[i - 1][w]
        );
      } else {
        K[i][w] = K[i - 1][w];
      }
    }
  }
  return K[n][capacity];
}

let values = [3, 4, 5];
let weights = [2, 3, 4];
let capacity = 5;
let n = values.length;
console.log(knapsack(capacity, weights, values, n));

在这段代码中，我们创建了一个二维数组 K，用于记录所有的子问题的解。对于每一个物品，我们考虑是否将其放入背包中，以获得最大价值。最终，我们可以在 K[n][capacity] 中找到最终的答案。