https://leetcode.cn/problems/remove-invalid-parentheses/submissions/573085240/
dfs，这题没想出来
```js
var removeInvalidParentheses = function (s) {
let lNum = 0;
let rNum = 0;
let other = 0;
for (let index = 0; index < s.length; index++) {
if (s == '(') {
lNum++
} else if (s == ')') {
rNum++
} else {
other++;
}
}
let max = Math.min(lNum, rNum);
let cache = new Set();
let len = 0;
const dfs = (index, str, score) => {
if (score < 0) {
return
}
if (index >= s.length) {
if (score == 0 && str.length >= len) {
if (str.length > len) {
cache = new Set();
len=str.length
}
cache.add(str)
}
//end
return;
}
const char = s
if (char == "(") {
dfs(index + 1, str + "(", score + 1)
dfs(index + 1, str, score)
} else if (char == ")") {
dfs(index + 1, str + ")", score - 1)
dfs(index + 1, str, score)
} else {
dfs(index + 1, str + char, score)
}
}
dfs(0, "", 0)
return[...cache]
};
```
https://leetcode.cn/problems/minimum-absolute-difference-in-bst/submissions/573093753/?envType=study-plan-v2&envId=top-interview-150
考察中序遍历
```js
var getMinimumDifference = function (root) {
let pre = undefined;
let result = Number.MAX_SAFE_INTEGER;
const dfs = (node) => {
if (node == null) {
return;
}
dfs(node.left);
if (pre !== undefined) {
result = Math.min(result, Math.abs(pre - node.val));
pre = node.val;
} else {
pre = node.val;
}
dfs(node.right);
};
dfs(root);
return result;
};
```
https://leetcode.cn/problems/find-peak-element/submissions/573095972/?envType=study-plan-v2&envId=top-interview-150
二分法
```js
var findPeakElement = function (nums) {
const findMax = (l, r) => {
if (l > r) {
return -1;
}
const center =Math.floor((l + r) / 2);
if (nums > (nums??Number.MIN_SAFE_INTEGER )&& nums > (nums??Number.MIN_SAFE_INTEGER)) {
return center;
} else {
//没找到
const result1 = findMax(l, center - 1);
if(result1!==-1){
return result1
}
const result2 = findMax(center + 1, r);
if(result2!==-1){
return result2
}
}
return -1
};
returnfindMax(0, nums.length - 1);
};
```
https://leetcode.cn/problems/minimum-average-of-smallest-and-largest-elements/submissions/573105227/
排序+双指针
简单题
```js
var minimumAverage = function (nums) {
nums.sort((a, b) => a - b);
const base=Math.floor(nums.length/2)
let result=Number.MAX_SAFE_INTEGER
for (let index = 0; index < base; index++) {
result=Math.min(result,(nums+nums)/2)
}
return result
};
```
https://leetcode.cn/problems/number-of-1-bits/submissions/573109008/?envType=study-plan-v2&envId=top-interview-150
简单题，查1
```js
var hammingWeight = function(n) {
let times=0;
for (let index = 0; index < 32; index++) {
times+=(n>>index)&1
}
return times
};
```
https://leetcode.cn/problems/k-inverse-pairs-array/submissions/573401817/
逆序对，mod卡我半天，优化卡我半天...
```js
var kInversePairs = function (n, k) {
const dp = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
for (let index = 0; index < dp.length; index++) {
dp = 1;
}
const mod = 1000000007;
for (let index = 2; index < dp.length; index++) {
for (let indey = 1; indey < dp.length; indey++) {
//5-3依赖于4-3 4-2 4-1 4-0
//5-4依赖于4-4 4-3 4-2 4-1 4-0
dp = (dp + dp) % mod;
if (indey >= index) {
// 5-6依赖于 4-6 4-5 4-4 4-3 4-2
// 5-7依赖于 4-7 4-6 4-5 4-4 4-3\
dp += mod;
dp -= dp;
dp = dp % mod;
}
}
}
return dp.pop().pop();
};
```
https://leetcode.cn/problems/boolean-evaluation-lcci/submissions/573403843/
dfs区间划分
```js
var countEval = function (s, result) {
const cache = new Map();
const dfs = (l, r) => {
const flag = `${l} ${r}`;
if (cache.has(flag)) {
return cache.get(flag);
}
if (l == r) {
return {
t: s === "1" ? 1 : 0,
f: s === "0" ? 1 : 0,
};
}
let t = 0;
let f = 0;
for (let index = l + 1; index < r; index += 2) {
let info1 = dfs(l, index - 1);
let info2 = dfs(index + 1, r);
switch (s) {
case "&":
t += info1.t * info2.t;
f += info1.t * info2.f;
f += info1.f * info2.t;
f += info1.f * info2.f;
break;
case "|":
t += info1.t * info2.t;
t += info1.t * info2.f;
t += info1.f * info2.t;
f += info1.f * info2.f;
break;
case "^":
f += info1.t * info2.t;
t += info1.t * info2.f;
t += info1.f * info2.t;
f += info1.f * info2.f;
break;
}
}
cache.set(flag, {
t,
f,
});
return {
t,
f,
};
};
let info = dfs(0, s.length - 1);
return result == 1 ? info.t : info.f;
};
```
https://leetcode.cn/problems/factorial-trailing-zeroes/submissions/573404825/?envType=study-plan-v2&envId=top-interview-150
找规律题
```js
var trailingZeroes = function (n) {
let fiveNum = 0;
for (let index = 5; index <= n; index *= 5) {
fiveNum += Math.floor(n / index);
}
return fiveNum;
};
```
https://leetcode.cn/problems/valid-palindrome/submissions/573405820/?envType=study-plan-v2&envId=top-interview-150
gpt完全给ascii的知识污染了
我日
```js
var isPalindrome = function (s) {
let l = 0,
r = s.length - 1;
while (l < r) {
let char1 = s.charCodeAt();
let char2 = s.charCodeAt();
if (char1 >= 65 && char1 <= 90) {
//转小写
char1 += 32;
}
if (char2 >= 65 && char2 <= 90) {
//转小写
char2 += 32;
}
if (!((char1 >= 97 && char1 <= 122) || (char1 >= 48 && char1 <= 57))) {
l++;
continue;
}
if (!((char2 >= 97 && char2 <= 122) || (char2 >= 48 && char2 <= 57))) {
r--;
continue;
}
if (char1 == char2) {
l++;
r--;
} else {
return false;
}
}
return true;
};
```
https://leetcode.cn/problems/palindrome-partitioning-ii/submissions/573717680/
双dp
```js
var minCut = function (s) {
const dp = new Array(s.length).fill(0).map(() => new Array(s.length).fill(0))
for (let index = 0; index <= dp.length - 2; index++) {
dp = 1;
dp = s == s ? 2 : 0;
}
dp = 1
for (let index = dp.length - 3; index >= 0; index--) {
for (let indey = index + 2; indey < dp.length; indey++) {
dp = s == s ? dp : 0;
}
}
const sp = new Array(s.length + 1).fill(0)
for (let pos = sp.length - 2; pos >= 0; pos--) {
let result = Number.MAX_SAFE_INTEGER;
for (let index = pos; index < s.length; index++) {
if (dp !== 0) {
result = Math.min(result, sp)
}
}
sp= result + 1
}
return sp - 1
};
```