https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/submissions/572181751/?envType=study-plan-v2&envId=top-interview-150
双指针
```js
var twoSum = function(numbers, target) {
let l=0,r=numbers.length-1;
while(l!=r){
const total=numbers+numbers
if(total==target){
return
}else if(total<target){
l++
}else{
r--
}
}
};
```
https://leetcode.cn/problems/is-subsequence/submissions/572198403/?envType=study-plan-v2&envId=top-interview-150
简单题
秒了
```js
var isSubsequence = function(s, t) {
if(s.length==0){
return true
}
let l1=0;l2=0;
while (l2<t.length&&l1.length!=s.length) {
if(s==t){
l1++;
l2++;
if(l1==s.length){
return true
}
}else{
l2++
}
}
return false
};
```
https://leetcode.cn/problems/maximum-gap/submissions/572420356/
桶排，太复杂了...
凹了好久
```js
var maximumGap = function (nums) {
if (nums.length < 2) {
return 0
}
let min = nums;
let max = nums;
for (let index = 0; index < nums.length; index++) {
min = Math.min(min, nums)
max = Math.max(max, nums)
}
const bucket = new Array(nums.length).fill(undefined);
const sep = Math.ceil((max - min) / nums.length)
const getBucketIndex = (num) => {
return Math.floor((num - min) / (sep == 0 ? 1 : sep))
}
for (let index = 0; index < nums.length; index++) {
const bucketIndex = getBucketIndex(nums)
if (bucket == undefined) {
bucket = {}
bucket.max = nums
bucket.min = nums
} else {
bucket.max = Math.max(bucket.max, nums)
bucket.min = Math.min(bucket.min, nums)
}
}
let lastNum = bucket.max;
let result = bucket.max - bucket.min;
for (let index = 1; index < bucket.length; index++) {
if (bucket !== undefined) {
let currentNum = bucket.min;
result = Math.max(result, currentNum - lastNum);
lastNum = bucket.max;
}
}
return result
};
```
https://leetcode.cn/problems/binary-tree-cameras/submissions/572441200/
状态二叉树dp
```js
var minCameraCover = function (root) {
const dfs = (root) => {
if (root == null) {
return {
has_camera: Number.MAX_SAFE_INTEGER,
has_cover: 0,
no_cover: Number.MAX_SAFE_INTEGER,
};
}
// 放了相机，没放相机但是覆盖，没被覆盖
const left = dfs(root.left);
const right = dfs(root.right);
let has_camera =
Math.min(left.no_cover, left.has_camera, left.has_cover) +
Math.min(right.no_cover, right.has_camera, right.has_cover) +
1;
let no_cover = left.has_cover + right.has_cover;
let has_cover = Math.min(
left.has_camera + right.has_camera,
left.has_camera + right.has_cover,
left.has_cover + right.has_camera
);
return {
has_camera,
no_cover,
has_cover,
};
};
let result = dfs(root);
return Math.min(result.has_camera, result.has_cover);
};
```
https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/submissions/572446595/
这题没A出来
考虑鸡蛋掉落的最坏情况
```js
var twoEggDrop = function (n) {
const dp = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER);
dp = 0;
dp=1
for (let index =2; index < dp.length; index++) {
for (let indey = 1; indey <= index; indey++) {
dp = Math.min(
dp,
Math.max(indey - 1, dp) + 1
);
}
}
return dp.pop();
};
```
https://leetcode.cn/problems/combinations/submissions/572773506/?envType=study-plan-v2&envId=top-interview-150
dfs题，感觉最近打回溯和链表丝滑多了
```js
var combine = function (n, k) {
const result = []
const dfs = (ans, l) => {
if (ans.length == k) {
result.push([...ans])
return
} else if ((k - ans.length) > (n - l)) {
return
}
for (let index = l + 1; index <= n; index++) {
ans.push(index);
dfs(ans,index);
ans.pop();
}
}
dfs([], 0)
return result;
};
```
https://leetcode.cn/submissions/detail/572746217/
鸡蛋掉落题，这个是真难
```js
var superEggDrop = function (k, n) {
// k蛋数量
const dp = new Array(k + 1).fill(0).map(() => new Array(n + 1).fill(Number.MAX_SAFE_INTEGER))
for (let index = 0; index < dp.length; index++) {
dp = index
}
for (let index = 0; index < dp.length; index++) {
dp = 0;
}
for (let index = 2; index < dp.length; index++) {
for (let indey = 1; indey < dp.length; indey++) {
const layoutHeight = indey;
let l = 0, r = layoutHeight;
while (l <= r) {
const center = Math.floor((l + r) / 2);
let result1 = dp ?? Number.MIN_SAFE_INTEGER //随着楼层增高逐渐增大
let result2 = dp //随着楼层增高逐渐变小
dp = Math.min(dp, Math.max(result1, result2) + 1);
if (result1 <= result2) {
l = center + 1
} else {
r = center - 1
}
}
// for (let currentLayout = 1; currentLayout <= layoutHeight; currentLayout++) {
// dp = Math.min(dp, Math.max(dp, dp) + 1)
// }
}
}
return dp.pop().pop()
};
```
https://leetcode.cn/submissions/detail/572771593/
反转链表，一波过
```js
var reverseBetween = function (head, left, right) {
let reverNum = right - left + 1;
const reverse = (node) => {
let ret = node;
let endNode = node;
let current = node.next;
reverNum--
while (reverNum !== 0) {
const next = current.next;
current.next = ret;
ret = current;
current = next;
reverNum--;
}
endNode.next = current;
return ret
}
left = left - 1;
right = right - 1;
if (left == 0) {
return reverse(head)
} else {
let headNode = head
let lastNode = headNode
while (left != 0) {
lastNode = headNode
headNode = headNode.next;
left--;
}
lastNode.next = reverse(headNode)
}
return head
};
```
https://leetcode.cn/problems/maximum-height-of-a-triangle/submissions/572777112/
基础题
```js
var maxHeightOfTriangle = function (red, blue) {
let line1 = 0;
let lint2 = 0;
let isLine1 = true;
let times = 1;
let ret=0;
while (true) {
if (isLine1) {
line1 += times;
} else {
lint2 += times;
}
if((red>=line1&&blue>=lint2)||(blue>=line1&&red>=lint2)){
ret++
isLine1=!isLine1
times++;
}else{
break
}
}
return ret
};
```
https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/submissions/573065097/?envType=study-plan-v2&envId=top-interview-150
链表基础题
秒了
```js
var deleteDuplicates = function (head) {
let result = {
next: head
};
let pre = result;
while (head != null) {
if (head.next?.val == head.val) {
let val = head.val
while (val == head?.val) {
head = head.next;
}
pre.next = head;
}else{
pre = head;
head = head.next;
}
}
return result.next
};
```