LeetCode(力扣)答案解析（九）

[Checkson]

61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例1：

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例2

示例2：

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

题解：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (!k) return head;
    var p = head,
        trail = head;
    var order = 0,
        len = 0;
    while (p) {
        trail = p;
        len++;
         p = p.next;
    }
    k = k % len;
    p = head;
    while (order < len - k) {
        order++;
        if (order == len - k) {
            trail.next = head;
            head = p.next;
            p.next = null;
            break;
        }
        p = p.next;
    }
    return head;
};

解析：

这道题的思路也很简单：

• 先找出链表中的最后一个节点的位置，并记录链表长度 len。
• 然后用 k 对链表长度 len 取余，减少无用的循环次数（当 k >= len，就存在白走了至少一轮链表移动）。
• 最后遍历到第 len - k 个元素（这里借助了 len - k - 1 元素），将其置为头节点，并且将链表原来的尾节点 trail 的 next 指针，指向链表头部 head 即可。

11. 盛最多水的容器

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明： 你不能倾斜容器，且 n 的值至少为 2。

示例：

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

题解：

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    var front = 0,
        rear = height.length - 1,
        max = 0;
    while (front < rear) {
        max = Math.max(Math.min(height[front], height[rear]) * (rear - front), max)
        if (height[front] <= height[rear]) {
            front++;
        } else {
            rear--;
        }
    }
    return max;
};

解析：

略。

238. 除自身以外数组的乘积

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例：

输入: [1,2,3,4]
输出: [24,12,8,6]

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

题解

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    var res = [1];
    for (var i = 1, len = nums.length; i < len; i++) {
        res[i] = res[i - 1] * nums[i - 1]; // [1, 1, 2, 6]
    }
    var right = 1;
    for (var i = nums.length - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }
    return res; // [24, 12, 8, 6]
};

解析：

这个解法非常巧妙，首先 res 数组是记录每个数左边的乘积，然后乘以每个数右边的乘积，就得到了答案。