文章目录

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

剑指 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出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了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;
};