ggnb 多少名了
王一之 发表于 2024-5-2 16:34
ggnb 多少名了
还没名次，貌似要打到几百题才有10w名以内
没想出来思路
双指针单调性问题
但是单调性太难证了...
最后看了一下题解
巧妙
```js
/**
* @param {number[]} height
* @Return {number}
*/
var maxArea = function (height) {
let l = 0
let r = height.length - 1;
const calcCapacity = () => {
return (r - l) * Math.min(height, height)
}
let result = calcCapacity()
while (r >= l) {
let isSet = false
if (height < height) {
// r移动
for (let index = r - 1; index > l; index--) {
if (height > height) {
r = index
isSet = true
break;
}
}
} else {
// 大于等于，l移动
for (let index = l + 1; index < r; index++) {
if (height > height) {
l = index
isSet = true
break;
}
}
}
if(!isSet){
break;
}
result = Math.max(result, calcCapacity())
}
return result
};
//2 131 3 2
console.log(maxArea())
```
https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked
这道题也没凹出来
看的答案都卡了好久
核心思路是排序之后
利用a<b<c的双指针做处理
但是还不允许重复
这里只需要控制a和b跳就可以了
c因为在b相等时候构成，而b不等于之前的值
则a+b+c一定会超过0，所以只控制a，b不等即可
```js
var threeSum = function (nums) {
nums = nums.sort((a,b)=>a-b)
const result = []
for (let index = 0; index < nums.length; index++) {
const a = nums;
if (nums == a) {
continue;
}
let indey = index + 1;
let indez = nums.length - 1
while (indey < nums.length && indez != index && indey < indez) {
const b = nums
if (nums == b&&indey - 1!=index) {
indey++;
continue;
}
const c = nums
const num = a + b + c
if (num === 0) {
result.push()
indey++;
indez--;
} else if (num < 0) {
indey++;
} else {
indez--;
}
}
}
return result
};
```
https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/?envType=study-plan-v2&envId=top-100-liked
双指针问题
但是我个人不喜欢这道
官方题解是两个人互相攻擂，挑较小的继续算
left一定小于等于leftIndex
这个时候右方一定存在一个大于或等于的才可以计算
所以可以确保结果
实际上感觉比较抽象
我更喜欢对比右边界而不是right的算法
```js
var trap = function (height) {
let leftIndex = 0
let rightIndex = height.length - 1
let left = leftIndex
let right = rightIndex
let total = 0
while (left <= right) {
if (height >= height) {
leftIndex = left
}
if (height >= height) {
rightIndex = right
}
if (height<height ) {
total += Math.min(height, height) - height
left++
} else if(height<height ) {
total += Math.min(height, height) - height
right--
}else{
left++
}
}
return total
};
```
https://leetcode.cn/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-100-liked
简单滑窗题
```js
var lengthOfLongestSubstring = function (s) {
if(s.length==0){
return 0
}
let left = 0, right = 0;
let max = 1;
const charSet = new Set()
for (let index = 0; index < s.length; index++) {
const char = s;
while (charSet.has(char)) {
charSet.delete(s)
left++
}
charSet.add(char)
right++;
max = Math.max(max, right - left )
}
return max
};
```
https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/1123971/zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-xzin/?envType=study-plan-v2&envId=top-100-liked
简单滑窗，这题也不用思考
```js
var findAnagrams = function (s, target) {
if (s.length == 0) {
return 0
}
let targetStr = new Array(26).fill(0);
for (let index = 0; index < target.length; index++) {
targetStr.charCodeAt() - 97]++;
}
targetStr = targetStr.toString()
let left = 0, right = 0;
let result = [];
let compareArr = new Array(26).fill(0);
for (let index = 0; index < s.length; index++) {
const char = s;
if (right - left == target.length) {
if (compareArr.toString() === targetStr) {
result.push(left)
}
compareArr.charCodeAt() - 97]--
left++;
}
compareArr++
right++;
}
if (compareArr.toString() === targetStr) {
result.push(left)
}
return result
};
```
https://leetcode.cn/problems/intersection-of-two-linked-lists/submissions/557408809/?envType=study-plan-v2&envId=top-100-liked
假设A多余的是a，b多余的是b，共同的是c
则a+c-(b+c)=a-b的差
取最长的链扣掉差，两链相等，则同时步进即可
```js
var getIntersectionNode = function (headA, headB) {
let numA = 0
let numB = 0
let firstA = headA
let firstB = headB
while (firstA !== null || firstB !== null) {
if (firstA !== null) {
firstA = firstA.next
numA++
}
if (firstB !== null) {
firstB = firstB.next
numB++
}
}
let nextHead = numA > numB ? headA : headB
let lastHead = nextHead === headA ? headB : headA
const nextStep = Math.abs(numA - numB)
for (let index = 0; index < nextStep; index++) {
nextHead = nextHead.next
}
while (nextHead!=null&&lastHead!=null) {
if(nextHead==lastHead){
return nextHead
}else{
nextHead = nextHead.next
lastHead = lastHead.next
}
}
return null
};
```
https://leetcode.cn/problems/reverse-linked-list/submissions/557412237/?envType=study-plan-v2&envId=top-100-liked
链表反转，简单题
var reverseList = function (head) {
let ret = null
while (head != null) {
let next = head.next
head.next = ret
ret = head
head = next
}
return ret
};
https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/557412974/?envType=study-plan-v2&envId=top-100-liked
中序，简单题
```js
var inorderTraversal = function(root,ret=[]) {
if(root==null){
return ret
}
inorderTraversal(root.left,ret)
ret.push(root.val)
inorderTraversal(root.right,ret)
return ret
};
```