https://leetcode.cn/problems/sum-root-to-leaf-numbers/submissions/574873979/?envType=study-plan-v2&envId=top-interview-150
dfs秒了
```js
var sumNumbers = function (root) {
let str = [];
let total = 0;
const dfs = (head) => {
if(head==null){
return
}
str.push(head.val);
if (head.left == null && head.right == null) {
total+=parseInt(str.join(""))
} else {
dfs(head.left);
dfs(head.right);
}
str.pop()
}
dfs(root)
return total
};
```
https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/submissions/575398891/
约瑟夫问题
```js
var iceBreakingGame = function (num, target) {
const dfs = (n, len) => {
if (n == 1) {
return 0
}
return (dfs(n - 1, len - 1) + target) % len
}
return dfs(num, num)
};
```
https://leetcode.cn/problems/patching-array/submissions/575406181/
边界题
```js
var minPatches = function (nums, n) {
let border = 0;
let addNum = 0;
for (let index = 0; index < nums.length; index++) {
const num = nums
while (border < num - 1) {
border += (border + 1)
addNum++;
if (border >= n) {
return addNum
}
}
border += num
if (border >= n) {
return addNum
}
}
while (border < n) {
border += (border + 1)
addNum++;
if (border >= n) {
return addNum
}
}
};
```
https://leetcode.cn/problems/design-add-and-search-words-data-structure/submissions/575498971/?envType=study-plan-v2&envId=top-interview-150
基础题
```js
var WordDictionary = function () {
this.tree = {}
};
/**
* @param {string} word
* @Return {void}
*/
WordDictionary.prototype.addWord = function (word) {
word = word.split("");
let head = this.tree
for (let index = 0; index < word.length; index++) {
const char = word;
head = head ?? (head = {})
}
head.end = true;
};
/**
* @param {string} word
* @return {boolean}
*/
WordDictionary.prototype.search = function (word) {
word = word.split("")
const dfs = (node, pos) => {
if (pos >= word.length) {
return node.end!==undefined? true:false
}
if (word !== '.') {
if (node] !== undefined) {
return dfs(node], pos + 1)
} else {
return false
}
} else {
const arr = Object.keys(node)
for (let index = 0; index < arr.length; index++) {
const char = arr;
if(char=='end'){
continue;
}
if (dfs(node, pos + 1)) {
return true
}
}
return false
}
}
return dfs(this.tree, 0)
};
```
https://leetcode.cn/problems/distinct-subsequences-ii/
卡我边界我靠
```js
var distinctSubseqII = function (s) {
const cache = new Map()
let all = 1;
const mod = 1e9 + 7
for (let index = 0; index < s.length; index++) {
const char = s;
const lastAll = all
all = (all + all)
all = all % mod
all = (all - (cache.get(char) ?? 0) + mod) % mod;
cache.set(char, lastAll)
}
return (all - 1 + mod) % mod
};
```
扣边界版本
```js
var distinctSubseqII1 = function (s) {
const cache = new Map()
let all = 0;
const mod = 1e9 + 7
for (let index = 0; index < s.length; index++) {
const char = s;
const lastAll = all
all = (all + all + 1)% mod
all = (all - (cache.get(char) ?? 0) + mod) % mod;
cache.set(char, lastAll + 1)
}
return all
};
```
https://leetcode.cn/problems/maximum-total-reward-using-operations-i/submissions/
这题卡的要死
```js
var maxTotalReward = function (rewardValues) {
rewardValues = rewardValues.sort((a, b) => a - b)
const dp = new Array(rewardValues.length).fill(0)
.map(() => new Array(rewardValues * 2).fill(0))
for (let index = 0; index < dp.length; index++) {
dp = true
}
dp] = true
let maxValue = rewardValues
for (let index = 1; index < dp.length; index++) {
for (let indey = 1; indey < dp.length; indey++) {
dp = dp
if ((indey - rewardValues) < rewardValues) {
dp = dp || dp]
}
if (dp) {
maxValue = Math.max(maxValue, indey)
}
}
}
return maxValue
};
```
https://leetcode.cn/problems/palindrome-pairs/submissions/575765214/
搞了半天回文对比偷懒导致的过不去...
```js
var palindromePairs = function (words) {
const cache = new Map()
for (let index = 0; index < words.length; index++) {
const word = words.split("").reverse().join("");
cache.set(word, index)
}
let result = [];
const isPalindrome = (str) => {
let l = 0, r = str.length - 1;
while (l < r) {
if (str == str) {
l++;
r--
} else {
return false
}
}
return true;
}
for (let index = 0; index < words.length; index++) {
const word = words;
if (isPalindrome(word) && cache.has("") && word !== "") {
result.push()
}
for (let len = 1; len <= word.length; len++) {
const left = word.slice(0, len);
const right = word.slice(len, word.length);
if (isPalindrome(left) && cache.has(right)) {
result.push()
}
if (isPalindrome(right) && cache.has(left) && cache.get(left) !== index) {
result.push()
}
}
}
return result
};
```
https://leetcode.cn/problems/shortest-bridge/submissions/576209259/
岛屿问题
```js
var shortestBridge = function (grid) {
const handleArea = (stack = [], x, y) => {
if (x >= grid.length || x < 0 || y < 0 || y >= grid.length) {
return;
}
if (grid == 1) {
stack.push({ x, y });
grid = 0;
handleArea(stack, x + 1, y);
handleArea(stack, x - 1, y);
handleArea(stack, x, y + 1);
handleArea(stack, x, y - 1);
}
return stack;
};
const gridStack = [];
for (let index = 0; index < grid.length; index++) {
for (let indey = 0; indey < grid.length; indey++) {
if (grid == 1) {
gridStack.push(handleArea([], index, indey));
}
}
}
const bfs = (stack) => {
const map = new Array(grid.length)
.fill(0)
.map(() => new Array(grid.length).fill(0));
let layout = 1;
while (stack.length !== 0) {
let newStack = [];
for (let index = 0; index < stack.length; index++) {
const item = stack;
const x = item.x;
const y = item.y;
if (x >= map.length || x < 0 || y < 0 || y >= map.length) {
continue;
}
if (map == 0) {
map = layout;
newStack.push({
x: x + 1,
y,
});
newStack.push({
x: x - 1,
y,
});
newStack.push({
x: x,
y: y + 1,
});
newStack.push({
x: x ,
y: y - 1,
});
}
}
layout++;
stack = newStack;
}
return map;
};
const map1 = bfs(gridStack);
const map2 = bfs(gridStack);
let min = Number.MAX_SAFE_INTEGER;
for (let index = 0; index < map1.length; index++) {
for (let indey = 0; indey < map1.length; indey++) {
min = Math.min(min, map1 + map2);
}
}
return min-3
};
```
https://leetcode.cn/problems/palindrome-number/submissions/576209476/?envType=study-plan-v2&envId=top-interview-150
今天有点晚了
打两道简单题
```js
var isPalindrome = function (x) {
if (x < 0) {
return false;
}
let reverse = 0;
let newX = x;
while (newX != 0) {
reverse=reverse*10
reverse += newX % 10;
newX = parseInt(newX / 10);
}
return x==reverse
};
```