算法题

大数相加

解释

  • 首先我们用字符串的形式来保存大数，就保证了其在数学表示上不会发生变化
  • 初始化res, temp变量来保存中间计算的结果，在将两个字符串split为数组，以便我们进行每一位的运算
  • 循环的第一次就是进行 "个位" 的运算，将二者最末尾的两个数相加，由于每一位数字是0 - 9，所以需要进行进位，在进过取余数操作后，将结果保留在个位。
  • 判断 temp 是否大于 10，若是则将 temp 赋值为 true。
  • 在两个大数中的一个还有数字没有参与运算，或者前一次运算发生进位后，进行下一次循环。
  • 接着除了对新的两个数字相加还要加上 temp，若上次发生了进位，则此时 temp 为 true，Js因为存在隐式转换，所以 true 转换为 1，我们借用 Js 的类型转换，完成了逻辑上的逢10进1操作。
  • 接下来就是重复上述的操作，直到计算结束。
  • 除去非数字的字符
function sumBigNumber(a, b) {
    if (a.charAt(0) == 0 || b.charAt(0) == 0) {
      return "0";
    }
    var res = '', temp = 0;
    a = a.toString().split('');
    b = b.toString().split('');
    while (a.length || b.length || temp) {
        temp += ~~a.pop() + ~~b.pop();
        res = (temp % 10) + res;
        temp = temp > 9;
    }
    return res.replace(/^0+/, '');
}
console.log(sumBigNumber('3782647863278468012934670', '23784678091370408971329048718239749083')); // 23784678091374191619192327186252683753

字符串全排列

function perm(s) {
    var result = [];
    if (s.length <= 1) {
        return [s];
    } else {
        for (var i = 0; i < s.length; i++) {
            var char = s[i];
            var newStr = s.slice(0, i) + s.slice(i + 1, s.length);
            var str = perm(newStr);

            for (var j = 0; j < str.length; j++) {
                var tmp = char + str[j];
                result.push(tmp);
            }
        }
    }
    return result;
};

辗转相除法求最大公约数

约数

如果数 a 能被数 b 整除，a 就叫做 b 的倍数，b 就叫做 a 的约数。

最大公约数

最大公约数就是两个数中,大家都能相约且最大的数。

辗转相除法

辗转相除法又名欧几里得算法（Euclidean algorithm）,目的是求出两个正整数的最大公约数。它是已知最古老的算法,其可追溯至公元前300年前。

这条算法基于一个定理：两个正整数 a 和 b（a 大于 b）,它们的最大公约数等于 a 除以 b 的余数 c 和 较小数 b 之间的最大公约数。

算法计算过程是这样的:

  • 2个数相除，得出余数
  • 如果余数不为0，则拿较小的数与余数继续相除，判断新的余数是否为0
  • 如果余数为0，则最大公约数就是本次相除中较小的数。

比如数字 25 和 10 ，使用辗转相除法求最大公约数过程如下：

  • 25 除以 10 商 2 余 5
  • 根据辗转相除法可以得出，25 和 10 的最大公约数等于 5 和 10 之间的最大公约数
  • 10 除以 5 商 2 余 0， 所以 5 和 10 之间的最大公约数为 5，因此25 和 10 的最大公约数为 5

题目要求

完善函数 gcd 的功能。函数 gcd 会计算并返回传入的两个正整数参数之间最大的公约数

如下所示：

gcd(30，3); // 返回结果为 3
gcd(12, 24); // 返回结果为 12
gcd(111, 11); // 返回结果为 1
function gcd(num1,num2){
    var remainder = 0;
    do{
       remainder = num1 % num2;
       num1 = num2;
       num2 = remainder;
    }while(remainder!==0);
    return num1;
}

console.log(gcd(24,12));

实现辗转相除法通常有两种思路，分别如下

1、使用循环实现

function gcd(number1, number2){
  var remainder = 0;
  do {
    remainder = number1 % number2;
    number1 = number2; 
    number2 = remainder;
  } while(remainder !== 0);
  return number1;
}

2、使用函数递归

function gcd(number1, number2) { 
  if (number2 == 0) {
    return number1; 
  } else {
    return gcd(number2, number1 % number2); 
  }
}

JavaScript实现树的深度优先遍历和广度优先遍历

深度优先遍历（Depth-First Search, DFS）

该方法是以纵向的维度对dom树进行遍历，从一个dom节点开始，一直遍历其子节点，直到它的所有子节点都被遍历完毕之后在遍历它的兄弟节点。即如图所示（遍历顺序为红字锁标）：

clipboard.png

深度优先遍历可以通过递归或使用栈来实现。

首先，我们需要定义一个树的基本数据结构。这里我们使用一个简单的 JavaScript 对象来表示树的节点：

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  addChild(childNode) {
    this.children.push(childNode);
  }
}

递归实现

function dfsRecursive(node) {
  if (!node) return;

  console.log(node.value); // 访问当前节点

  node.children.forEach(child => {
    dfsRecursive(child); // 递归访问子节点
  });
}

使用栈实现

function dfsIterative(root) {
  if (!root) return;

  const stack = [root];

  while (stack.length > 0) {
    const node = stack.pop();
    console.log(node.value); // 访问当前节点

    // 将子节点压入栈中，注意顺序，保证先进后出
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

广度优先遍历（Breadth-First Search, BFS）

以横向的维度对dom树进行遍历，从该节点的第一个子节点开始，遍历其所有的兄弟节点，再遍历第一个节点的子节点，完成该遍历之后，暂时不深入，开始遍历其兄弟节点的子节点。即如图所示（遍历顺序为红字锁标）：

clipboard.png

可以通过队列来实现，每次从队列中取出一个节点，并将其子节点依次加入队列。

function bfs(root) {
  if (!root) return;

  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node.value); // 访问当前节点

    // 将子节点加入队列
    node.children.forEach(child => {
      queue.push(child);
    });
  }
}

实现一个函数isStrValid函数

判断字符串是否是有效字符串，字符串包括 '('，')'，'{'，'}'，'['，']' 、字母和数字

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。
[] => true
[]{} => ture
[[[] => false
[[()}] => false
function isStrValid(str) {
  let stack = [];
  for(let i = 0; i < str.length; i++) {
    if (str[i] === '(' || str[i] === '{' || str[i] === '[') {
      stack.push(str[i]);
    } else if (str[i] === ')') {
      if (stack[stack.length - 1] === '(') {
        stack.pop();
      } else {
        return false;
      }
    } else if (str[i] === ']') {
      if (stack[stack.length - 1] === '[') {
        stack.pop();
      } else {
        return false;
      }
    } else if (str[i] === '}') {
      if (stack[stack.length - 1] === '{') {
        stack.pop();
      } else {
        return false;
      }
    }
  }
  return stack.length === 0;
}

数组⭐

字符串⭐

排序

贪心算法

递归

滑动窗口

栈⭐

队列⭐

堆

哈希

链表⭐

二分查找

图论

二叉树⭐

DFS搜索

BFS搜索

动态规划⭐

多维动态规划

矩阵

双指针

回溯⭐

正则表达式

技巧

最近更新:
Contributors: csmSimona