【当前排名67359】挑战leetcode进入前1w名-油猴中文网

李恒道 发表于 2025-1-3 14:11:50

https://leetcode.cn/problems/scramble-string/submissions/590861667/
```js
var isScramble = function (s1, s2) {
const cahce = new Map();
const dfs = (l1, r1, l2, r2) => {
const tag = `${l1} ${r1} ${l2} ${r2}`;
if (cahce.has(tag)) {
   return cahce.get(tag);
}
if (l1 == r1) {
   return s1 == s2;
}
let ans = false;
for (let index = 0; index < r1 - l1; index++) {
   //不变动位置
   ans =
   dfs(l1, l1 + index, l2, l2 + index) &&
   dfs(l1 + index + 1, r1, l2 + index + 1, r2);
   const len = r1 - l1 - index - 1;
   ans =
   ans ||
   (dfs(l1 + index + 1, r1, l2, l2 + len) &&
      dfs(l1, l1 + index, l2 + len + 1, r2));
   if (ans) {
   break;
   }
}
cahce.set(tag, ans);
return ans;
};
return dfs(0, s1.length - 1, 0, s2.length - 1);
};
```

李恒道 发表于 2025-1-3 15:08:18

https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/submissions/590876242/

dfs链表
```js
var sortedListToBST = function (head) {
const dfs = (root, end) => {
if(root==end){
   return null
}
let slow = root;
let fast = root;
while (fast !== end) {
   fast = fast.next;
   if (fast == end) {
   break;
   }
   fast = fast.next;
   slow = slow.next;
}
const ret = {
   val: slow.val,
};
ret.left = dfs(root, slow);
ret.right = dfs(slow.next, end);
return ret
};
return dfs(head, null);
};
```

李恒道 发表于 2025-1-3 15:20:22

https://leetcode.cn/problems/minimum-depth-of-binary-tree/submissions/590879629/
简单题
收工
```js
var minDepth = function (root) {
if(root==null){
   return 0
}
let ans = Number.MAX_SAFE_INTEGER;
const dfs = (node, layout) => {
layout++;
if (node.left == null && node.right == null) {
   ans = Math.min(ans, layout);
   return;
}
node.left&&dfs(node.left,layout)
node.right&&dfs(node.right,layout)
};
dfs(root,0);
return ans;
};
```

李恒道 发表于 2025-1-3 15:22:17

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/submissions/590880129/
二题过了一也直接秒了
```js
/**
* // Definition for a _Node.
* function _Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/

/**
* @param {_Node} root
* @Return {_Node}
*/

var connect = function (root) {
if(root==null){
   return null
}
let stack = []
stack.push(root);
right = null;
let nextStack = []
while (stack.length !== 0) {
   let item = stack.pop()
   item.next = right;
   right = item;
   item.right && nextStack.unshift(item.right);
   item.left && nextStack.unshift(item.left);
   if (stack.length == 0) {
         stack = nextStack;
         nextStack = [];
         right = null;
   }
}
return root
};
```

李恒道 发表于 2025-1-3 15:36:52

https://leetcode.cn/problems/pascals-triangle-ii/submissions/590884227/
简单题
秒了
```js

var getRow = function (numRows) {
const arr =
const result = [[...arr]]
for (let index = 1; index <= numRows; index++) {
   arr.push(1)
   for (let pos = arr.length - 2; pos > 0; pos--) {
         arr=arr+arr
   }
   result.push([...arr])
}
return result
};```

李恒道 发表于 2025-1-4 18:43:26

https://leetcode.cn/problems/word-ladder/submissions/591089660/
双向dfs，这个没太理解，看了一下源码
真神奇啊
```js
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @Return {number}
*/
var ladderLength = function (beginWord, endWord, wordList) {
const jump = new Set();
for (const word of wordList) {
jump.add(word);
}
const jumpStack1 = [];
jumpStack1.push(beginWord);
const jumpStack2 = [];
jumpStack2.push(endWord);
const steps1 = new Map();
steps1.set(beginWord, 0);
const steps2 = new Map();
steps2.set(endWord, 0);
if(!jump.has(endWord)){
return 0
}
const modify = (str, pos, char) => {
str = str.split("");
str = char;
return str.join("");
};
const handler = (stack, stepCache, targetStep) => {
let size = stack.length;
for (let index = 0; index < size; index++) {
   let word = stack.shift();
   let times = stepCache.get(word);
   for (let pos = 0; pos < word.length; pos++) {
   for (let index = 0; index < 26; index++) {
      const char = word;
      word=modify(word, pos, String.fromCharCode(97 + index));
      if (stepCache.has(word)) {
         word=modify(word, pos, char);
         continue;
      }
      if (!jump.has(word)) {
         word=modify(word, pos, char);
         continue;
      }
      if (targetStep.has(word)) {
         return times + targetStep.get(word) + 1+1;
      } else {
         stepCache.set(word, times + 1);
         stack.push(word);
      }
      word=modify(word, pos, char);
   }
   }
}
return -1;
};
while (jumpStack1.length !== 0 && jumpStack2.length !== 0) {
let ans = -1;
if (jumpStack1.length <= jumpStack2.length) {
   //步进正向
   ans = handler(jumpStack1, steps1, steps2);
} else {
   ans = handler(jumpStack2, steps2, steps1);
}
if (ans != -1) {
   return ans;
}
}
return 0;
};
```

李恒道 发表于 2025-1-4 21:18:59

李恒道 发表于 2025-1-4 21:19:16

https://leetcode.cn/problems/word-ladder-ii/submissions/591114621/
这题真难啊
真的凹了好久
```js
const modify = (str, pos, char) => {
str = str.split("");
str = char;
return str.join("");
};
var findLadders = function (beginWord, endWord, wordList) {
const wordCache = new Set();
for (let index = 0; index < wordList.length; index++) {
const word = wordList;
wordCache.add(word);
}
if (!wordCache.has(endWord)) {
return [];
}
const curWord = new Map();
const curWordTimes = new Map();
const stack = ;
let minLen = Number.MAX_SAFE_INTEGER;
const hasVisit=new Set()
const insert = (last, word, times) => {
if (!curWord.has(word)) {
   curWord.set(word, new Set());
   curWordTimes.set(word, times);
}
const preTimes = curWordTimes.get(word);
if (times > preTimes) {
   return false;
}
if (preTimes > times) {
   curWord.set(word, new Set());
   curWordTimes.set(word, times);
}
curWord.get(word).add(last);
return true;
};
let times = 0;
while (times <= minLen && stack.length !== 0) {
let size = stack.length;

times++;
for (let index = 0; index < size; index++) {
   let word = stack.shift();
   const last = word;
   for (let pos = 0; pos < word.length; pos++) {
   const char = word;
   for (let index = 0; index < 26; index++) {
      word = modify(word, pos, String.fromCharCode(97 + index));
      if (!wordCache.has(word)) {
         continue;
      }
      let status = insert(last, word, times);
      if (word == endWord) {
         minLen = Math.min(minLen, times);
         continue;
      }
      if (status&&!hasVisit.has(word)) {
         hasVisit.add(word)
         stack.push(word);
      }
   }
   word = modify(word, pos, char);
   }
}
}
const ans = [];
const dfs = (arr, str, times) => {
arr.push(str);
if (str == beginWord) {
   const copy = [...arr];
   copy.reverse();
   ans.push(copy);
} else {
   curWord.get(str)?.forEach((val) => {
   dfs(arr, val, times - 1);
   });
}
arr.pop();
};
dfs([], endWord, minLen);
return ans;
};
```

李恒道 发表于 2025-1-4 21:51:59

https://leetcode.cn/problems/word-break-ii/submissions/591121062/
dfs秒了，回溯问题
```js
/**
* @param {string} s
* @param {string[]} wordDict
* @Return {string[]}
*/
var wordBreak = function (s, wordDict) {
let maxLen = 0;
const wordSet = new Set();
for (let index = 0; index < wordDict.length; index++) {
const word = wordDict;
wordSet.add(word);
maxLen = Math.max(word.length, maxLen);
}
const ans=[]
const dfs = (pos, arr) => {
if(pos==s.length){
   ans.push(arr.join(" "))
   return

}
for (let index = 0; index < maxLen; index++) {
   const str = s.slice(pos, pos + index + 1);
   if (wordSet.has(str)) {
   arr.push(str);
   dfs(pos + index + 1, arr);
   arr.pop();
   }
}
};
dfs(0, []);
return ans
};
```

李恒道 发表于 2025-1-4 22:10:52

https://leetcode.cn/problems/middle-of-the-linked-list/
简单链表题
```js
var middleNode = function(head) {
let slow=head;
let fast=head;
while(fast!=null&&fast.next!==null){
fast=fast?.next?.next;

slow=slow.next
}
return slow
};
```

页: 29 30 31 32 33 34 35 36 37 38 [39] 40 41 42 43

油猴中文网's Archiver