每日算法

2021-10-22

剑指 Offer 59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

思路:

双指针维持一个长度为3的滑动窗口
每一次计算滑动窗口中的最大值,push到res数组中
getMax(arr,left,right)工具函数,获取滑动窗口中的最大值

代码:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    // 储存结果
    let res = []
    let i = 0
    let j = k - 1
    // 如果数组为空 直接retun []
    if(nums.length === 0) {
        return []
    }
    // j++ i++ 是滑动窗口soso往前走
    while(j < nums.length) {
        let max = getMax(nums, i, j)
        res.push(max)
        i++
        j++
    }
    //最后返回结果
    return res

    //工具函数 获取一段数组的最大值
    function getMax(arr, left, right) {
        max = arr[left]
        for(left = left+1; left <= right; left++) {
            if(arr[left] > max ) {
                max = arr[left]
            }
        }
        return max
    }
};
// 看评论 可以用双端队列来解,,,,, 但是我不会嗷.....

剑指 Offer II 024. 反转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：

1 2	输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

1 2	输入：head = [1,2] 输出：[2,1]

示例 3：

1 2	输入：head = [] 输出：[]

代码:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
   // 初始化前驱结点为 null
    let pre = null;
    // 初始化目标结点为头结点
    let cur = head;
    // 只要目标结点不为 null，遍历就得继续
    while (cur !== null) {
        // 记录一下 next 结点
        let next = cur.next;
        // 反转指针
        cur.next = pre;
        // pre 往前走一步
        pre = cur;
        // cur往前走一步
        cur = next;
    }
    // 反转结束后，pre 就会变成新链表的头结点
    return pre
};