leetcode刷题记录
2024.10.18
1.两数之和 复杂度O(n2)【哈希、数组】
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] + nums[i] === target) {
return [i, j];
}
}
}
};
哈希法，O(n)复杂度
复习了一下map的基本用法
mp.has(t):查询t是否存在在map中
mp.get(key):通过键值拿到value值
mp.set(key, value):设置键值对
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const mp = new Map();
for (let i = 0; i < nums.length; i++) {
if (mp.has(target - nums[i])) {
return [mp.get(target - nums[i]), i];
}
mp.set(nums[i], i);
}
};
49. 字母异位词分组【哈希】
先排序，在判断
array.split(''):分割
array.sort(''):排序
array.join(''):组合
map的基本用法
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
let res = [];
let mp = new Map();
for (let i = 0; i < strs.length; i++) {
const newStr = strs[i].split('').sort().join('');
if (mp.has(newStr)) {
res[mp.get(newStr)].push(strs[i]);
} else {
mp.set(newStr, res.length);
res.push([strs[i]]);
}
}
return res;
};
128. 最长连续序列
时间复杂度O(nlog(n))
排序后判断连续：容易踩坑的点在最开始和最后面的判断与赋值
注意数字重复的情况
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
if (nums.length === 0) return 0;
const newNums = nums.sort((a, b) => a - b);
console.log(newNums);
let cnt = 1, maxCnt = 1;
for (let i = 1; i < newNums.length; i++) {
const num = newNums[i], preNum = newNums[i - 1];
if (num === preNum + 1) {
cnt++;
} else if (num !== preNum) {
maxCnt = cnt > maxCnt ? cnt : maxCnt;
cnt = 1;
}
}
maxCnt = cnt > maxCnt ? cnt : maxCnt;
return maxCnt;
};
11. 盛最多水的容器
双指针+两边夹
水桶效益、这个需要一点数学理解
总的高度较短的个指针先往中间一动
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let i = 0, j = height.length - 1;
let maxContent = 0;
while (i < j) {
const w = j - i;
const h = Math.min(height[i], height[j]);
maxContent = Math.max(maxContent, w * h);
if (height[i] > height[j]) {
j--;
} else {
i++;
}
}
return maxContent;
};
42. 接雨水
脑细胞要死光了，只考虑到了左高右低的情况，还要改，写点简单的轻松一下
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
const len = height.length;
if (len < 3) return 0;
let slow = 0, fast = 0;
let left;
let res = 0;
// 在每一个迭代中，slow为左高点, 只要右高点的高度>=左高点，即判断一个凹处理完毕
// 迭代找凹
while(slow < len && fast < len) {
// 保证slow的下一个一定比他低
while(slow + 1 < len && height[slow + 1] >= height[slow]) slow++;
console.log('-------------------------------');
left = height[slow];
console.log('找到slow点了吗', slow, ', left:', left)
fast = slow + 1;
blackContent = 0;// (,) 不计算左、右高点柱子
while(fast < len && height[fast] < left) {
// s 为左高点
blackContent += height[fast];
fast++;
}
//fast 为右高点
// 如果找不到右高点，就已经到了尾巴，就找次高点
if (fast === len) {
console.log('到访天刚', fast, ', left:', height[fast]);
console.log('到访天刚', slow, ', right:', height[slow]);
break;
}
console.log('找到fast点了吗', fast, ', right:', height[fast]);
console.log('blackContent: ', blackContent);
// 右高点 == l，或者 > l
res += ((left * (fast - slow - 1)) - blackContent);
console.log('res: ', res);
// 每一找凹的迭代中，left和slow参数是不变的,定位了凹字的左高点
// 每一轮迭代后，维护更新左高点
slow = fast;
console.log('-------------------------------');
}
const st = slow;
if (fast === len) {
fast -= 1;
slow = fast;
while (fast)
// 保证fast的下一个一定比他低
while(slow + 1 < len && height[slow + 1] >= height[slow]) slow++;
console.log('---------------a----------------');
left = height[slow];
console.log('找到slow点了吗', slow, ', left:', left)
fast = slow + 1;
blackContent = 0;// (,) 不计算左、右高点柱子
while(fast < len && height[fast] < left) {
// s 为左高点
blackContent += height[fast];
fast++;
}
//fast 为右高点
// 如果找不到右高点，就已经到了尾巴，就找次高点
if (fast === len) {
console.log('到访天刚', fast, ', left:', height[fast]);
console.log('到访天刚', slow, ', right:', height[slow]);
break;
}
console.log('找到fast点了吗', fast, ', right:', height[fast]);
console.log('blackContent: ', blackContent);
// 右高点 == l，或者 > l
res += ((left * (fast - slow - 1)) - blackContent);
console.log('res: ', res);
// 每一找凹的迭代中，left和slow参数是不变的,定位了凹字的左高点
// 每一轮迭代后，维护更新左高点
slow = fast;
console.log('-------------------------------');
}
return res;
};
原文地址：https://blog.csdn.net/shifff/article/details/143035696
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！