每日两题 T33
算法
LeetCode T面试题51. 数组中的逆序对[1]
描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 :
输入: [7,5,6,4]
输出: 5限制：
0 <= 数组长度 <= 50000
分析
首先能想到使用暴力解法，双重循环，但时间复杂度为N方，显然有待改进。
可使用归并的方式实现
代码
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function (nums) {
// 归并排序
let sum = 0;
mergeSort(nums);
return sum;
function mergeSort(nums) {
if (nums.length < 2) return nums;
const mid = parseInt(nums.length / 2);
let left = nums.slice(0, mid);
let right = nums.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let res = [];
let leftLen = left.length;
let rightLen = right.length;
let len = leftLen + rightLen;
for (let index = 0, i = 0, j = 0; index < len; index++) {
if (i >= leftLen) res[index] = right[j++];
else if (j >= rightLen) res[index] = left[i++];
else if (left[i] <= right[j]) res[index] = left[i++];
else {
res[index] = right[j++];
sum += leftLen - i;//在归并排序中唯一加的一行代码
}
}
return res;
}
};前端
说说实现无缝轮播图的思路
无缝轮播的核心是制造一个连续的效果。最简单的方法就是复制一个轮播的元素，当复制元素将要滚到目标位置后，把原来的元素进行归位的操作，以达到无缝的轮播效果。
使用 React 结合 Hooks 实现核心代码片段如下：
useEffect(() => {
const requestAnimationFrame =
window.requestAnimationFrame || window.webkitRequestAnimationFrame || window.mozRequestAnimationFrame
const cancelAnimationFrame =
window.cancelAnimationFrame || window.webkitCancelAnimationFrame || window.mozCancelAnimationFrame
const scrollNode = noticeContentEl.current
const distance = scrollNode.clientWidth / 2
scrollNode.style.left = scrollNode.style.left || 0
window.__offset = window.__offset || 0
let requestId = null
const scrollLeft = () => {
const speed = 0.5
window.__offset = window.__offset + speed
scrollNode.style.left = -window.__offset + 'px'
// 关键行：当距离小于偏移量时，重置偏移量
if (distance <= window.__offset) window.__offset = 0
requestId = requestAnimationFrame(scrollLeft)
}
requestId = requestAnimationFrame(scrollLeft)
if (pause) cancelAnimationFrame(requestId)
return () => cancelAnimationFrame(requestId)
}, [notice, pause])References
[1] 面试题51. 数组中的逆序对: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录