https://leetcode.cn/problems/maximum-sum-circular-subarray/submissions/595064777/?envType=study-plan-v2&envId=top-interview-150
没凹出来
第一个想出来的简直是天才
我满脑子模拟
```js
var maxSubarraySumCircular = function (nums) {
let pre = 0,
maxAns = nums;
nums.forEach((x) => {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
});
pre = 0;
minAns = nums;
let total = 0;
nums.forEach((x) => {
pre = Math.min(pre + x, x);
minAns = Math.min(minAns, pre);
total += x;
});
if (total == minAns) {
return maxAns;
}
return Math.max(maxAns, total - minAns);
};
```
https://leetcode.cn/problems/evaluate-division/submissions/595066170/?envType=study-plan-v2&envId=top-interview-150
复杂除法
这题真的思路很爽
```js
/**
* @param {string[][]} equations
* @param {number[]} values
* @param {string[][]} queries
* @Return {number[]}
*/
var calcEquation = function (equations, values, queries) {
const map = new Map();
for (let index = 0; index < equations.length; index++) {
const = equations;
const value = values;
if (!map.has(n1)) {
map.set(n1, new Map());
}
if (!map.has(n2)) {
map.set(n2, new Map());
}
const n1Map = map.get(n1);
const n2Map = map.get(n2);
n1Map.set(n2, value);
n2Map.set(n1, 1 / value);
}
const dfs = (start, end, visit) => {
const temp = map.get(start);
if (temp == undefined) {
return -1;
}
if (map.get(end) == undefined) {
return -1;
}
if (start == end) {
return 1;
}
visit.set(start,true)
for (let data of temp) {
if (visit.has(data)) {
continue;
}
const value = data;
const nextValue = dfs(data, end, visit);
if (nextValue == -1) {
continue;
}
return value * nextValue;
}
return -1;
};
let ans = [];
for (const of queries) {
ans.push(dfs(query0, query1, new Map()));
}
return ans;
};
```
https://leetcode.cn/problems/redundant-connection/submissions/595237637/
并查集
秒了！
```js
class UnionFind {
constructor(n) {
this.parent = new Array(n).fill(0).map((_, index) => index);
this.rank = new Array(n).fill(1);
}
find(x) {
if (this.parent !== x) {
this.parent = this.find(this.parent); // 路径压缩
}
return this.parent;
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank > this.rank) {
this.parent = rootX;
} else if (this.rank < this.rank) {
this.parent = rootY;
} else {
this.parent = rootX;
this.rank += 1;
}
}
}
isConnected(x, y) {
return this.find(x) === this.find(y);
}
}
/**
* @param {number[][]} edges
* @Return {number[]}
*/
var findRedundantConnection = function (edges) {
const union = new UnionFind(edges.length);
for (let index = 0; index < edges.length; index++) {
const edge = edges;
if(union.isConnected(edge,edge)){
//已经是一个了
return edge
}else{
union.union(edge,edge)
}
}
return -1
};
```
https://leetcode.cn/problems/minimum-money-required-before-transactions/description/
这题不喜欢
贪心 贪不出来是真难受
```js
var minimumMoney = function (transactions) {
let totalLostt = 0,
mx = 0;
for (const transaction of transactions) {
totalLostt += Math.max(transaction - transaction, 0);
mx = Math.max(mx, Math.min(transaction, transaction));
}
return totalLostt + mx;
};
```
https://leetcode.cn/problems/number-of-operations-to-make-network-connected/submissions/595242423/
爽了
```js
class UnionFind {
constructor(n) {
this.parent = new Array(n).fill(0).map((_, index) => index);
this.rank = new Array(n).fill(1);
}
find(x) {
if (this.parent !== x) {
this.parent = this.find(this.parent); // 路径压缩
}
return this.parent;
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank > this.rank) {
this.parent = rootX;
} else if (this.rank < this.rank) {
this.parent = rootY;
} else {
this.parent = rootX;
this.rank += 1;
}
}
}
isConnected(x, y) {
return this.find(x) === this.find(y);
}
}
/**
* @param {number[][]} edges
* @Return {number[]}
*/
/**
* @param {number} n
* @param {number[][]} connections
* @return {number}
*/
var makeConnected = function (n, connections) {
if (connections.length < n - 1) {
return -1;
}
let ans = 0;
let ok = 0;
const union = new UnionFind(n);
for (const connection of connections) {
if (union.isConnected(connection, connection)) {
ans++;
} else {
ok++;
union.union(connection, connection);
}
}
return Math.min(ans, n - 1 - ok);
};
```
https://leetcode.cn/problems/combination-sum-ii/description/?envType=daily-question&envId=2025-01-26
打卡题
```js
var combinationSum2 = function (candidates, target) {
const map = new Map();
for (let index = 0; index < candidates.length; index++) {
const candidate = candidates;
map.set(candidate, (map.get(candidate) ?? 0) + 1);
}
candidates = [...map.keys()];
candidates.sort((a, b) => a - b);
const ans = [];
const dfs = (pos, val, arr) => {
if (val > target) {
return;
}
if (val == target) {
ans.push([...arr]);
return;
}
if (pos >= candidates.length) {
return;
}
dfs(pos + 1, val, arr);
let maxCount = map.get(candidates);
const newArr = [...arr];
for (let index = 1; index <= maxCount; index++) {
newArr.push(candidates);
dfs(pos + 1, val + candidates * index, newArr);
}
};
dfs(0, 0, []);
return ans;
};
```
https://leetcode.cn/problems/snakes-and-ladders/submissions/595568804/?envType=study-plan-v2&envId=top-interview-150
这题边界真是给我干蒙了
```js
var snakesAndLadders = function (board) {
const n = board.length;
const stack = ;
const getPos = (index) => {
const x = n - 1 - Math.floor((index - 1) / n);
let isReverse = x % 2 == 0 ? true : false;
if (n % 2 != 0) {
isReverse = !isReverse;
}
const originY = (index - 1) % n;
const y = isReverse ? n - 1 - originY : originY;
return ;
};
const cache = new Map();
cache.set(1, 0);
while (stack.length !== 0) {
const index = stack.shift();
for (let next = index + 1; next <= Math.min(index + 6, n * n); next++) {
const = getPos(next);
let nextIndex = next;
if (board !== -1) {
nextIndex = board;
}
if (cache.has(nextIndex)) {
continue;
}
cache.set(nextIndex, cache.get(index) + 1);
stack.push(nextIndex);
}
}
const min = cache.get(n * n);
return min == undefined ? -1 : min;
};
```
https://leetcode.cn/problems/jump-game-ii/
这两天都是这种题
```js
var jump = function (nums) {
if(nums.length==1){
return 0
}
let right = nums;
let pos = 0;
let times = 1;
let nextRight = nums;
while (pos <= right && right < nums.length - 1) {
for (let index = pos; index < right; index++) {
const num = nums;
nextRight = Math.max(nextRight, index + num);
}
if (pos == right) {
if (right == nextRight) {
return -1;
}
right = nextRight;
times++;
}
pos++;
}
returntimes;
};
```
https://leetcode.cn/problems/minimum-genetic-mutation/submissions/595576532/?envType=study-plan-v2&envId=top-interview-150
bfs过了
```js
const charList = "ACGT".split("");
var minMutation = function (startGene, endGene, bank) {
const cache = new Set();
for (const str of bank) {
cache.add(str);
}
const visit = new Set();
const steps = new Map();
const stack = ;
steps.set(startGene, 0);
while (stack.length !== 0 && !steps.has(endGene)) {
let ostr = stack.shift();
if (visit.has(ostr)) {
continue;
}
let str = ostr.split("");
let step = steps.get(ostr);
for (let index = 0; index < str.length; index++) {
const originChar = str;
if(index==4){
debugger
}
for (let pos = 0; pos < charList.length; pos++) {
const char = charList;
if (char == originChar) {
continue;
}
str = char;
const generateStr = str.join("");
if(cache.has(generateStr)){
debugger
}
if (cache.has(generateStr) && !visit.has(generateStr)) {
stack.push(generateStr);
steps.set(generateStr, step + 1);
}
str = originChar;
}
}
visit.add(ostr);
}
return steps.has(endGene) ? steps.get(endGene) : -1;
};
```
https://leetcode.cn/problems/minimum-genetic-mutation/submissions/595578637/?envType=study-plan-v2&envId=top-interview-150
优化了一下
暴打100%
```js
const charList = "ACGT".split("");
var minMutation = function (startGene, endGene, bank) {
const cache = new Set();
for (const str of bank) {
cache.add(str);
}
const steps = new Map();
const stack = ;
steps.set(startGene, 0);
while (stack.length !== 0 && !steps.has(endGene)) {
let ostr = stack.shift();
let str = ostr.split("");
let step = steps.get(ostr);
for (let index = 0; index < str.length; index++) {
const originChar = str;
for (let pos = 0; pos < charList.length; pos++) {
const char = charList;
if (char == originChar) {
continue;
}
str = char;
const generateStr = str.join("");
if (cache.has(generateStr) && !steps.has(generateStr)) {
stack.push(generateStr);
steps.set(generateStr, step + 1);
}
str = originChar;
}
}
}
return steps.has(endGene) ? steps.get(endGene) : -1;
};
```