Hello World

Appearance

On This Page

手写题[JavaScript][算法题] ​

1. 数组（Array） ​

1.1 三数之和 ​

三数之和（3Sum）是一个经典的算法问题，要求在给定数组中找到所有不重复的三元组，使得三个数的和为0。

下面是一个 JavaScript 的实现示例：

javascript
function threeSum(nums) {
  let result = [];
  nums.sort((a, b) => a - b); // 先对数组进行排序

  for (let i = 0; i < nums.length - 2; i++) {
    if (i === 0 || (i > 0 && nums[i] !== nums[i - 1])) {
      let left = i + 1;
      let right = nums.length - 1;
      let target = 0 - nums[i];

      while (left < right) {
        if (nums[left] + nums[right] === target) {
          result.push([nums[i], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;
          left++;
          right--;
        } else if (nums[left] + nums[right] < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }
  return result;
}

// 示例
const nums = [-1, 0, 1, 2, -1, -4];
console.log(threeSum(nums));

在这个实现中，我们首先对数组进行排序，然后使用双指针的方法来寻找三数之和为0的三元组。遍历数组，对于每一个数字，设定一个目标值，然后在剩余的部分使用双指针来找到满足条件的组合。

这样的实现能够在 O(n^2) 的时间复杂度内解决这个问题。

1.2 两数之和 ​

1.3 比较版本号 ​

当我们谈论比较版本号时，通常是指在软件开发中对软件版本进行比较。软件版本号是用来标识软件发布的不同版本的一种方式，通常采用数字和点号（.）组合而成的字符串表示。

一般来说，版本号的格式遵循主版本号.次版本号.修订版本号的形式，例如：1.2.3。

  • 主版本号：一般表示软件的重大更新或功能的重大改变，通常当软件有重大功能新增或变化时会增加主版本号。
  • 次版本号：表示软件的较小更新，可能包含了一些新的功能、改进或修复了一些bug。
  • 修订版本号：表示软件的修复版本，通常用于修复已知的bug或安全漏洞。

在比较版本号时，我们按照如下规则进行比较：

  1. 首先比较主版本号，主版本号较大的版本被认为是更新的版本。
  2. 如果主版本号相同，则比较次版本号，次版本号较大的版本被认为是更新的版本。
  3. 如果主版本号和次版本号都相同，则比较修订版本号，修订版本号较大的版本被认为是更新的版本。

通过这种方式，我们可以确定哪个版本号是较新的，或者两个版本号是否相同。

javascript
// 如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1，除此之外返回 0
function compareVersions(version1, version2) {
  const v1 = version1.split('.');
  const v2 = version2.split('.');
  // 比较两个数组的长度，得到最大的数组长度
  const maxLength = Math.max(v1.length, v2.length);
  // 遍历数组，分别比较同一个位置上的版本号
  for (let i = 0; i < maxLength; i++) {
    //  忽略前导0，使用 parseInt() 转为数字
    const num1 = parseInt(v1[i] || 0);
    const num2 = parseInt(v2[i] || 0);
    if (num1 > num2) {
      return 1;
    } else if (num1 < num2) {
      return -1;
    }
  }
  return 0;
};

// 示例
const version1 = "1.2.3";
const version2 = "1.2.4";
console.log(compareVersions(version1, version2)); // 输出: -1

1.4 冒泡排序 ​

1.5 快速排序 ​

2. 树（Tree） ​

2.1 反转二叉树 ​

3. 栈（Stack） ​

3.1 有效括号匹配 ​

有效括号匹配是指一个字符串中的括号是否能够完全匹配，即每个左括号都有相应的右括号与之匹配，并且括号之间的嵌套关系必须正确。

一种常见的解决方案是使用栈来实现。遍历字符串中的每个字符，当遇到左括号时，将其压入栈中；当遇到右括号时，检查栈顶元素是否为对应的左括号，如果是，则将栈顶元素弹出，继续遍历；如果不是，则说明括号不匹配，返回 false。最后，如果栈为空，则说明所有括号都匹配，返回 true；否则返回 false。

下面是一个 JavaScript 的实现示例：

javascript
function isValid(s) {
  const stack = [];
  const mapping = {
    ')': '(',
    ']': '[',
    '}': '{'
  };
  
  for (let char of s) {
    if (char in mapping) {
      const topElement = stack.pop() || '#';
      if (mapping[char] !== topElement) {
        return false;
      }
    } else {
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

// 示例
console.log(isValid("()"));       // true
console.log(isValid("()[]{}"));   // true
console.log(isValid("(]"));       // false
console.log(isValid("([)]"));     // false
console.log(isValid("{[]}"));     // true

4. 队列（Queue） ​

5. 链表（Linked List） ​

5.1 链式调用 ​

题目：提供了一个数组结构的 data，要求实现一个 query 方法，返回一个新的数组，query 方法内部有 过滤、排序、分组 等操作，并且支持链式调用，调用最终的 execute 方法返回结果。

5.2 判断链表有环 ​

在 JavaScript 中，要判断一个链表是否有环，可以使用一种称为“快慢指针”（也称为龟兔赛跑算法）的技术。这种方法通过两个指针以不同的速度遍历链表来检测环的存在。

具体步骤如下：

  1. 初始化两个指针：
    • slow 指针每次移动一步。
    • fast 指针每次移动两步。
  2. 遍历链表：
    • 同时移动 slow 和 fast 指针，直到它们相遇或 fast 指针到达链表的末尾。
  3. 判断结果：
    • 如果 slow 和 fast 指针相遇，则链表中存在环。
    • 如果 fast 指针到达链表的末尾（即 fast 或 fast.next 为 null），则链表中没有环。

以下是使用JavaScript实现这一算法的示例代码：

javascript
class ListNode {
  constructor(value = 0, next = null) {
    this.value = value;
    this.next = next;
  }
}

function hasCycle(head) {
  if (!head || !head.next) {
    // 空链表或只有一个节点的链表不可能有环
    return false;
  }

  let slow = head;
  let fast = head.next;

  while (slow !== fast) {
    // 如果快指针到达链表末尾，则没有环
    if (!fast || !fast.next) {
      return false;
    }
    // 慢指针移动一步
    slow = slow.next;
    // 快指针移动两步
    fast = fast.next.next;
  }

  // 慢指针和快指针相遇，说明有环
  return true;
}

// 示例用法
let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
let node4 = new ListNode(4);

node1.next = node2;
node2.next = node3;
node3.next = node4;
// 创建一个环
node4.next = node2;

console.log(hasCycle(node1)); // 输出: true

在上面的示例中，我们创建了一个带有环的链表，并调用了 hasCycle 函数来检测环的存在。函数返回 true，表示链表中确实有环。

请注意，这种方法的时间复杂度为 O(n)，其中 n 是链表中的节点数，因为两个指针最多遍历整个链表一次。空间复杂度为 O(1)，因为我们只使用了有限数量的额外变量（两个指针）。

5.3 循环链表 ​

javascript
interface ListNode {
  val: number;
  next: ListNode | null;
}

// 假设存在的函数，用于从尾节点获取头节点（在实际应用中需要实现这个函数）
function getHeadFromTail(tail: ListNode): ListNode {
  // 这个函数应该返回头节点的引用，但在这个例子中我们假设它总是正确的
  // 在实际应用中，你可能需要根据你的链表结构来实现这个函数
  return tail.next as ListNode; // 简单地返回 tail.next，因为我们知道它是循环的
}

function traverse(tail: ListNode | null): number[] {
  if (!tail || !tail.next) {
    return []; // 如果尾节点为空或尾节点没有指向任何节点，则返回空数组
  }

  const head = getHeadFromTail(tail); // 获取头节点
  const result: number[] = [];
  let current = head;

  // 使用一个集合来跟踪已经访问过的节点（避免无限循环，但在这个例子中我们不需要它，因为我们知道链表是循环的）
  // 但在实际应用中，如果链表不是循环的或结构未知，则应该使用这种机制来避免无限循环
  // const visited = new Set<ListNode>();

  do {
    result.push(current.val); // 将当前节点的值添加到结果数组中
    current = current.next; // 移动到下一个节点
    // if (visited.has(current)) { // 检查是否已经访问过当前节点（在这个例子中不需要）
    //   break; // 如果已经访问过，则退出循环（在这个例子中不需要）
    // }
    // visited.add(current); // 将当前节点标记为已访问（在这个例子中不需要）
  } while (current !== head); // 当我们再次回到头节点时停止（但在实际应用中，我们可以遍历直到尾节点的前一个节点）

  // 注意：由于我们知道链表是循环的，并且我们从头开始，所以上面的循环条件可以简化为遍历固定次数或直到我们接近尾节点
  // 但为了保持这个例子的通用性和清晰性，我们保留了检查是否回到头节点的逻辑

  // 在这个特定的例子中，由于我们知道链表是循环的，我们可以安全地移除上面的注释掉的代码（检查已访问节点的部分）

  // 由于我们是从头开始的，并且知道链表是循环的，我们实际上可以在遍历到尾节点的前一个节点时停止
  // 但为了简单起见，并且因为题目没有提供链表的长度信息，我们保留了回到头节点的检查

  // 重要的是要注意，在实际应用中，如果链表不是循环的，上面的代码可能会导致无限循环
  // 因此，在实际应用中，你应该始终确保你有一种机制来检测循环或确定链表的结束

  return result; // 返回包含所有节点值的结果数组
}

// 注意：上面的代码中的 getHeadFromTail 函数是一个假设的函数，你需要根据你的具体实现来替换它
// 在实际应用中，你可能需要根据你的链表结构来找到从头节点开始的正确方法