【当前排名67359】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/scramble-string/submissions/590861667/

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[l1] == s2[l2];
    }
    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);
};

李恒道

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

dfs链表

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);
};

李恒道

https://leetcode.cn/problems/minimum-depth-of-binary-tree/submissions/590879629/
简单题
收工

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;
};

李恒道

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/submissions/590880129/
二题过了一也直接秒了

/**
 * // 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
};

李恒道

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

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

李恒道

https://leetcode.cn/problems/word-ladder/submissions/591089660/
双向dfs，这个没太理解，看了一下源码
真神奇啊

/**
 * @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[pos] = 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[pos];
          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;
};

李恒道

https://leetcode.cn/problems/word-ladder/submissions/591089660/
双向dfs，这个没太理解，看了一下源码
真神奇啊

/**
 * @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[pos] = 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[pos];
          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;
};

李恒道

https://leetcode.cn/problems/word-ladder-ii/submissions/591114621/
这题真难啊
真的凹了好久

const modify = (str, pos, char) => {
  str = str.split("");
  str[pos] = 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[index];
    wordCache.add(word);
  }
  if (!wordCache.has(endWord)) {
    return [];
  }
  const curWord = new Map();
  const curWordTimes = new Map();
  const stack = [beginWord];
  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[pos];
        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;
};

李恒道

https://leetcode.cn/problems/word-break-ii/submissions/591121062/
dfs秒了，回溯问题

/**
 * @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[index];
    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
};

李恒道

https://leetcode.cn/problems/middle-of-the-linked-list/
简单链表题

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
};