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

李恒道

单词搜索题，递归，秒
https://leetcode.cn/problems/word-search/?envType=study-plan-v2&envId=top-100-liked

var exist = function (board, word) {
  word = word.split("");
  let status = false;
  const find = (x, y, index) => {
    if (index == word.length) {
      status = true;
      return;
    }
    const posPair = [
      [0, -1],
      [0, +1],
      [-1, 0],
      [1, 0],
    ];
    const char = board[x][y];
    board[x][y] = 0;
    for (const pos of posPair) {
      const posX = x + pos[0];
      const posY = y + pos[1];
      if (posX < 0 || posX >= board.length) {
        continue;
      }
      if (posY < 0 || posY >= board[0].length) {
        continue;
      }
      if (board[posX][posY] == word[index]) {
        find(posX, posY, index + 1);
      }
    }
    board[x][y] = char;
  };
  const char = word[0];
  for (let index = 0; index < board.length; index++) {
    for (let indey = 0; indey < board[0].length; indey++) {
      if ((char == board[index][indey])) {
        find(index, indey, 1);
      }
    }
  }
  return status;
};

李恒道

https://leetcode.cn/problems/palindrome-partitioning/?envType=study-plan-v2&envId=top-100-liked
看了一眼答案
没想到用了缓存dp，直接上个dp秒

var partition = function (s) {
    s = s.split("");
    const result = [];
    const stack = []
    const cache = new Map()
    const getIsPalind = (x, y) => {
        if (x == y) {
            return true
        }
        const cacheTag = `${x}-${y}`
        if (cache.has(cacheTag)) {
            return cache.get(cacheTag)
        } else {
            let status = undefined
            if (s[x] === s[y]) {
                if(x+1!=y){
                    status = getIsPalind(x + 1, y - 1)
                }else{
                    status=true
                }

            } else {
                status = false
            }
            cache.set(cacheTag, status)
            return status
        }

    }
    const dfs = (pos) => {
        if (pos === s.length) {
            result.push([...stack])
            return
        }
        for (let index = pos; index < s.length; index++) {
            if (getIsPalind(pos, index)) {
                stack.push(s.slice(pos, index + 1).join(""))
                dfs(index + 1)
                stack.pop()
            }
        }
    }
    dfs(0)//pos不包含当前位置
    return result
};

李恒道

https://leetcode.cn/problems/n-queens/submissions/562383181/?envType=study-plan-v2&envId=top-100-liked
n皇后问题，递归秒

var solveNQueens = function (n) {
    const board = []
    for (let index = 0; index < n; index++) {
        board.push(new Array(n).fill('.'))
    }
    const checkValid = (x, y) => {
        //上方
        for (let index = 0; index < x; index++) {
            const pos = board[index][y];
            if (pos === 'Q') {
                return false
            }
        }
        //右斜方
        for (let index = x - 1; index >= 0; index--) {
            const posY = y + (x - index)
            if (posY >= board.length) {
                break;
            }
            const pos = board[index][posY];
            if (pos === 'Q') {
                return false
            }
        }
        //左斜方
        for (let index = x - 1; index >= 0; index--) {
            const posY = y - (x - index)
            if (posY < 0) {
                break;
            }
            const pos = board[index][posY];
            if (pos === 'Q') {
                return false
            }
        }
        return true;
    }
    const result=[]
    const dfs = (index) => {
        if(index==board.length){
            result.push([...board].map((arr)=>arr.join('')))
            return
        }
        const layout = board[index]//第n行
        for (let y = 0; y < layout.length; y++) {//第y列
            if (checkValid(index, y)) {
                board[index][y]='Q'
                dfs(index+1)
                board[index][y]='.'
            }
        }
    }
    dfs(0)
    return result

};

李恒道

https://leetcode.cn/problems/search-insert-position/?envType=study-plan-v2&envId=top-100-liked
基础二分，一开始用错函数了...

var searchInsert = function (nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let center = Math.floor((left + right) / 2);
        if (nums[center] > target) {
            right = center - 1
        } else if (nums[center] < target) {
            left = center + 1
        } else {
            return center
        }

    }
    return left 
};

李恒道

https://leetcode.cn/problems/search-a-2d-matrix/submissions/562391623/?envType=study-plan-v2&envId=top-100-liked
上波的代码改改继续秒，缝缝补补是我的一生~

var searchInsert = function (nums, target) {
    if(nums==undefined){
        return -1
    }
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let center = Math.floor((left + right) / 2);
        if (nums[center] > target) {
            right = center - 1
        } else if (nums[center] < target) {
            left = center + 1
        } else {
            return center
        }

    }
    return left 
};
var searchMatrix = function (matrix, target) {
    let x = 0
    for (let index = 0; index < matrix.length; index++) {
        if (target > matrix[index][matrix[index].length - 1]) {
            x++;
        }else{
            break;
        }
    }
    const left=searchInsert(matrix[x],target)
    return matrix[x]?.[left]==target?true:false
};

李恒道

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/562393358/?envType=study-plan-v2&envId=top-100-liked
缝缝补补又怼进去了...

var searchInsert = function (nums, target, l, r) {
    if (nums == undefined) {
        return -1
    }
    let left = l ?? 0, right = r ?? nums.length - 1;
    while (left <= right) {
        let center = Math.floor((left + right) / 2);
        if (nums[center] >= target) {
            right = center - 1
        } else if (nums[center] < target) {
            left = center + 1
        }

    }
    return left
};
/**
 * @param {number[]} nums
 * @param {number} target
 * @Return {number[]}
 */
var searchRange = function (nums, target) {
    const left = searchInsert(nums, target)
    const right = searchInsert(nums, target + 1, left)-1
    if(right<left){
        return [-1,-1]
    }
    return [left,right]
};

李恒道

https://leetcode.cn/problems/search-in-rotated-sorted-array/submissions/562473289/?envType=study-plan-v2&envId=top-100-liked

边界没扣明白，看了题解，发现其实自己思路完全是错的

var search = function (nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const center = Math.floor((left + right) / 2);
        if (nums[center] === target) {
            return center
        } else if (nums[0] <= nums[center]) {
            if (nums[0] <= target && target < nums[center]) {
                right = center - 1
            } else {
                left = center + 1
            }
        } else {
            if (nums[center] < target && target < nums[0]) {
                left = center + 1
            } else {
                right = center - 1
            }

        }
    }
    return -1
};

李恒道

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/submissions/562479728/?envType=study-plan-v2&envId=top-100-liked
理解上一题思路这题就ok了
边界秒

var findMin = function (nums) {
    let left = 0, right = nums.length - 1;
    let minValue = nums[0]
    while (left <= right) {
        const center = Math.floor((left + right) / 2);
        minValue = Math.min(minValue, nums[center])
        if (nums[0] <= nums[center]) {
            left = center + 1
        } else {
            right = center - 1

        }
    }
    return minValue
};

李恒道

https://leetcode.cn/problems/daily-temperatures/submissions/562485231/?envType=study-plan-v2&envId=top-100-liked
堆栈解，但是执行效率不高
回头再看一下好用的

var dailyTemperatures = function (temperatures) {
    const stack = [];
    const result = [];
    for (let index = 0; index < temperatures.length; index++) {
        const temp = temperatures[index];
        if (stack.length !== 0) {
            while (stack.length!=0&&stack[stack.length - 1].temp < temp) {
                const lastTemp = stack.pop()
                result[lastTemp.index] = index - lastTemp.index
            }

        }
        stack.push({
            index,
            temp
        })
    }
    while(stack.length!=0){
        const lastTemp = stack.pop()
        result[lastTemp.index] = 0
    }

    return result

};

李恒道

https://leetcode.cn/problems/ransom-note/submissions/562487621/?envType=study-plan-v2&envId=top-interview-150
做个简单题舒缓一下心情睡觉了
哥哥们晚安

var canConstruct = function (ransomNote, magazine) {
    const map = new Map()
    ransomNote = ransomNote.split("")
    magazine = magazine.split("")
    let success = 0
    for (const char of ransomNote) {
        if (map.has(char)) {
            map.set(char, map.get(char) + 1)
        } else {
            success++;
            map.set(char, 1)
        }
    }
    for (const char of magazine) {
        if (map.has(char)) {
            const num =map.get(char)
            map.set(char, num - 1)
            if(num==1){
                success--
            }
        }
    }
    return success==0

};