企业官网建设流程全解析

算法练习day10

1、除了自身以外的数组的乘积

问题：除自身以外数组的乘积。给定一个整数数组nums，返回一个数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。

题目要求：

• 不能使用除法
• 时间复杂度 O(n)
• 空间复杂度 O(1)（输出数组不计入空间复杂度）

解题思路

核心思路是使用前缀积和后缀积。我们可以通过两次遍历来完成：

1. 第一次遍历（从左到右）：计算每个位置左侧所有元素的乘积，存入answer数组。
2. 第二次遍历（从右到左）：用一个变量right记录当前位置右侧所有元素的乘积，然后与answer[i]相乘得到最终结果。

代码实现

const productExceptSelf = function (nums) { const len = nums.length const answer = new Array(len) // 左乘积：answer[i]存i左边所有乘积 answer[0] = 1 for (let i = 1; i < len; i++) { answer[i] = answer[i - 1] * nums[i - 1] } let right = 1 // right 保存右边乘积，从后往前遍历 for (let i = len - 1; i >= 0; i--) { answer[i] *= right right *= nums[i] } return answer }

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。我们只进行了两次遍历。

• 空间复杂度：O(1)，除了输出数组外，只使用了常数空间。

2、相交链表

问题：给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。

题目要求：

• 时间复杂度 O(m+n)，其中 m 和 n 分别是链表 A 和 B 的长度
• 空间复杂度 O(1)
• 不能修改链表结构

解题思路

核心思路是使用双指针法，让两个指针分别遍历两个链表，当走到链表末尾时，切换到另一个链表的头部继续遍历。如果两个链表相交，那么两个指针最终会在相交节点相遇；如果不相交，两个指针最终都会走到null。

具体算法：

1. 初始化两个指针pA和pB，分别指向链表 A 和链表 B 的头节点
2. 同时向前移动两个指针
3. 当pA到达链表 A 的末尾时，将其重定位到链表 B 的头节点
4. 当pB到达链表 B 的末尾时，将其重定位到链表 A 的头节点
5. 如果两个链表相交，pA和pB最终会在相交节点相遇
6. 如果不相交，两个指针最终都会到达null

为什么这样能工作？

• 设链表 A 的非公共部分长度为 a，链表 B 的非公共部分长度为 b，公共部分长度为 c
• 指针pA走过的路径：a + c + b
• 指针pB走过的路径：b + c + a
• 两者路径长度相等，所以如果相交，必然在相交节点相遇

代码实现

// Definition for singly-linked list class ListNode { constructor(val) { this.val = val this.next = null } } /** 寻找两个链表的相交节点 @param {ListNode} headA @param {ListNode} headB @return {ListNode} */ var getIntersectionNode = function(headA, headB) { if (!headA || !headB) return null let pA = headA let pB = headB // 双指针遍历 while (pA !== pB) { // 如果pA走到末尾，切换到链表B头部 pA = pA ? pA.next : headB // 如果pB走到末尾，切换到链表A头部 pB = pB ? pB.next : headA } // 返回相交节点或null return pA } // 测试用例：构造相交链表 const a1 = new ListNode(4) const a2 = new ListNode(1) const c1 = new ListNode(8) const c2 = new ListNode(4) const c3 = new ListNode(5) a1.next = a2 a2.next = c1 c1.next = c2 c2.next = c3 const b1 = new ListNode(5) const b2 = new ListNode(6) const b3 = new ListNode(1) b1.next = b2 b2.next = b3 b3.next = c1 // B链表接到c1，交点是c1(val=8) // 测试 const result = getIntersectionNode(a1, b1) console.log('相交节点值:', result ? result.val : 'null') // 输出: 8

复杂度分析

• 时间复杂度：O(m+n)，其中 m 和 n 分别是链表 A 和 B 的长度。每个指针最多遍历 m+n 个节点。
• 空间复杂度：O(1)，只使用了两个指针变量，没有使用额外的数据结构。

边界情况

• 两个链表都为空：返回null
• 一个链表为空：返回null
• 两个链表不相交：最终两个指针都指向null
• 两个链表完全重合：返回第一个节点
• 相交节点在链表头部：直接返回相交节点