LeetCode刷题笔记 - JavaScript（三）

剑指 Offer 59 - I. 滑动窗口的最大值
剑指 Offer 43. 1～n 整数中 1 出现的次数

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

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

题目大意：求每个滑动窗口的最大值。

解题思路：考虑维护一个单调队列在滑动窗口移动的同时维护这个单调队列就可以了。

代码：

	var maxSlidingWindow = function(nums, k) {
    const res = []; // 答案序列
    const dque = []; // 单调队列
    const n = nums.length;
    let l = 0, r = 0; // 滑动窗口的边界
    while(r < n) {
        // 维护滑动窗口的边界
        while(dque.length !== 0 && dque[dque.length - 1] < nums[r]) {
            dque.pop();
        }
        dque.push(nums[r++]);
        if(r>=k) {
            res.push(dque[0]);
            if(dque[0] === nums[l]) dque.shift();
            l++;
        }
    }
    return res;
};

1.剑指 Offer 43. 1～n 整数中 1 出现的次数

输入一个整数 n 求1～n这n个整数的十进制表示中1出现的次数。
例如输入121～12这些整数中包含1 的数字有1、10、11和121一共出现了5次。

题目大意：求1~n中每个数字出现的1的数量的和。

解题思路：总结规律。规律一：n位数上总的1的个数为n*（10^(n-1))如1位数1的总和为1,2位数的1的总和为20,3位数的总和为300; 规律二：求1~n之间的所有数上的1的数量总和就是求n上的每一个数位区间上的1的数量的总和。设f(n)是可以求出1-n之间所有1的数量的函数假如n=234那么1-n之间所有1的数量就等于：f(200)+f(30)+f(4);
结合以上两个规则就可以求出1～n 整数中 1 出现的次数。

代码：

	var countDigitOne = function(n) {
    let res = 0;
    let count = 1;
    for(let i = 0; n >= count ; i++) {
        res += Math.floor(n / (count * 10)) * count + Math.min(Math.max(n % (count * 10) - count + 1, 0),count);
        count *= 10;
    }
    return res;
};