每日两题 T3
每日两题 T3
算法
LeetCode T876. 链表的中间结点[1]
描述
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。(测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。提示：
•给定链表的结点数介于 1 和 100 之间。
分析
该问题有几种思路：
因为链表没有下标，因此该题需要遍历链表。
方法一：数组
遍历数组的同时，将元素放入数组，然后取出数组中间元素，但是会有内存额外开销，时间复杂度
•时间复杂度：O(N)，其中 N 是给定链表中的结点数目。•空间复杂度：O(N)，即数组 A 用去的空间。
方法二：单指针法
对数组进行两次遍历，第一次统计链表长度，计算出中间位置索引，进行第二次遍历返回中间链表节点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var middleNode = function(head) {
let linkSize = 0
let current = head
while(current) {
++linkSize;
current = current.next
}
let currentIndex = 0
const middleIndex = Math.floor(linkSize / 2)
current = head
while (currentIndex < middleIndex) {
++currentIndex;
current = current.next;
}
return current;
};•时间复杂度：O(N)，其中 N 是给定链表的结点数目。•空间复杂度：O(1)，只需要常数空间存放变量和指针。
快慢指针法
用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。
var middleNode = function(head) {
slow = fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};•时间复杂度：O(N)，其中 N 是给定链表的结点数目。•空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。
JavaScript
什么是防抖和节流？他们有什么区别？如何实现呢？
在高频事件（例如浏览器页面滚动）触发时，为了优化提升性能，我们经常使用到防抖与节流。
防抖：触发高频事件后n秒内函数只会执行一次，如果n秒内高频事件再次被触发，则重新计算时间
节流：高频事件触发，但在n秒内只会执行一次，所以节流会稀释函数的执行频率
防抖和节流的区别在于，防抖 是如果在给定n秒内再次出发，则会重新计算触发事件，如果你一直触发，则一直重新计算，直至你停下；节流 与防抖的区别是，不管你是否重复触发，我都会在你给定的时间到来时，执行事件函数。
防抖
function debounce(fn, wait) {
let timeout = null; // 存放定时器返回值
return function () {
clearTimeout(timeout); // 每当用户输入时将前一个定时器清除掉
timeout = setTimeout(() => { // 然后又创建一个新的 setTimeout, 这样就能保证输入字符后的 interval 间隔内如果还有字符输入的话，就不会执行 fn 函数
fn.apply(this, arguments);
}, wait);
};
}当然，考虑到其他一些优化后，我们最终优化的代码，支持立即执行、返回值
function debounce(func, wait, immediate) {
var timeout, result;
return function () {
var context = this;
var args = arguments;
if (timeout) clearTimeout(timeout);
if (immediate) {
// 如果已经执行过，不再执行
var callNow = !timeout;
timeout = setTimeout(function(){
timeout = null;
}, wait)
if (callNow) result = func.apply(context, args)
}
else {
timeout = setTimeout(function(){
func.apply(context, args)
}, wait);
}
return result;
}
}节流
时间戳形式实现
function throttle(func, wait) {
var context, args;
var previous = 0;
return function() {
var now = +new Date();
context = this;
args = arguments;
if (now - previous > wait) {
func.apply(context, args);
previous = now;
}
}
}定时器实现
function throttle(func, wait) {
var timeout;
var previous = 0;
return function() {
context = this;
args = arguments;
if (!timeout) {
timeout = setTimeout(function(){
timeout = null;
func.apply(context, args)
}, wait)
}
}
}最终的优化
function throttle(func, wait, options) {
var timeout, context, args, result;
var previous = 0;
if (!options) options = {};
var later = function() {
previous = options.leading === false ? 0 : new Date().getTime();
timeout = null;
func.apply(context, args);
if (!timeout) context = args = null;
};
var throttled = function() {
var now = new Date().getTime();
if (!previous && options.leading === false) previous = now;
var remaining = wait - (now - previous);
context = this;
args = arguments;
if (remaining <= 0 || remaining > wait) {
if (timeout) {
clearTimeout(timeout);
timeout = null;
}
previous = now;
func.apply(context, args);
if (!timeout) context = args = null;
} else if (!timeout && options.trailing !== false) {
timeout = setTimeout(later, remaining);
}
};
return throttled;
}添加取消功能
throttled.cancel = function() {
clearTimeout(timeout);
previous = 0;
timeout = null;
}References
[1] 876. 链表的中间结点: https://leetcode-cn.com/problems/middle-of-the-linked-list/
本文分享自 JavaScript全栈 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
