单词搜索题，递归，秒
https://leetcode.cn/problems/word-search/?envType=study-plan-v2&envId=top-100-liked
```js
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 = [
,
,
[-1, 0],
,
];
const char = board;
board = 0;
for (const pos of posPair) {
const posX = x + pos;
const posY = y + pos;
if (posX < 0 || posX >= board.length) {
continue;
}
if (posY < 0 || posY >= board.length) {
continue;
}
if (board == word) {
find(posX, posY, index + 1);
}
}
board = char;
};
const char = word;
for (let index = 0; index < board.length; index++) {
for (let indey = 0; indey < board.length; indey++) {
if ((char == board)) {
find(index, indey, 1);
}
}
}
return status;
};
```
https://leetcode.cn/problems/palindrome-partitioning/?envType=study-plan-v2&envId=top-100-liked
看了一眼答案
没想到用了缓存dp，直接上个dp秒
```js
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 === s) {
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皇后问题，递归秒
```js
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;
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;
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;
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//第n行
for (let y = 0; y < layout.length; y++) {//第y列
if (checkValid(index, y)) {
board='Q'
dfs(index+1)
board='.'
}
}
}
dfs(0)
return result
};
```
https://leetcode.cn/problems/search-insert-position/?envType=study-plan-v2&envId=top-100-liked
基础二分，一开始用错函数了...
```js
var searchInsert = function (nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let center = Math.floor((left + right) / 2);
if (nums > target) {
right = center - 1
} else if (nums < 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
上波的代码改改继续秒，缝缝补补是我的一生~
```js
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 > target) {
right = center - 1
} else if (nums < 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.length - 1]) {
x++;
}else{
break;
}
}
const left=searchInsert(matrix,target)
return matrix?.==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
缝缝补补又怼进去了...
```js
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 >= target) {
right = center - 1
} else if (nums < 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
};
```
https://leetcode.cn/problems/search-in-rotated-sorted-array/submissions/562473289/?envType=study-plan-v2&envId=top-100-liked
边界没扣明白，看了题解，发现其实自己思路完全是错的
```js
var search = function (nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const center = Math.floor((left + right) / 2);
if (nums === target) {
return center
} else if (nums <= nums) {
if (nums <= target && target < nums) {
right = center - 1
} else {
left = center + 1
}
} else {
if (nums < target && target < nums) {
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了
边界秒
```js
var findMin = function (nums) {
let left = 0, right = nums.length - 1;
let minValue = nums
while (left <= right) {
const center = Math.floor((left + right) / 2);
minValue = Math.min(minValue, nums)
if (nums <= nums) {
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
堆栈解，但是执行效率不高
回头再看一下好用的
```js
var dailyTemperatures = function (temperatures) {
const stack = [];
const result = [];
for (let index = 0; index < temperatures.length; index++) {
const temp = temperatures;
if (stack.length !== 0) {
while (stack.length!=0&&stack.temp < temp) {
const lastTemp = stack.pop()
result = index - lastTemp.index
}
}
stack.push({
index,
temp
})
}
while(stack.length!=0){
const lastTemp = stack.pop()
result = 0
}
return result
};
```
https://leetcode.cn/problems/ransom-note/submissions/562487621/?envType=study-plan-v2&envId=top-interview-150
做个简单题舒缓一下心情睡觉了
哥哥们晚安
```js
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
};
```