https://leetcode.cn/problems/happy-number/submissions/576209580/?envType=study-plan-v2&envId=top-interview-150
缓存秒了
```js
var isHappy = function (n) {
const cache = new Map();
while (true) {
if (cache.has(n)) {
return false;
}
cache.set(n, true);
let newN = 0;
while (n != 0) {
newN += (n % 10) * (n % 10);
n = parseInt(n / 10);
}
n = newN;
if(newN==1){
break;
}
}
return true
};
```
https://leetcode.cn/problems/valid-sudoku/submissions/576211089/?envType=study-plan-v2&envId=top-interview-150
脑筋急转弯题
```js
var isValidSudoku = function (board) {
for (let index = 0; index < board.length; index++) {
const hasNum = new Array(10).fill(false);
for (let indey = 0; indey < board.length; indey++) {
const char = board;
if (char !== ".") {
if (hasNum) {
return false;
}
hasNum = true;
}
}
}
//竖排
for (let index = 0; index < board.length; index++) {
const hasNum = new Array(10).fill(false);
for (let indey = 0; indey < board.length; indey++) {
const char = board;
if(char=='5'){
debugger
}
if (char !== ".") {
if (hasNum) {
return false;
}
hasNum = true;
}
}
}
for (let x = 0; x < board.length / 3; x++) {
for (let y = 0; y < board.length / 3; y++) {
const hasNum = new Array(10).fill(false);
for (let index = 0; index < 3; index++) {
for (let indey = 0; indey < 3; indey++) {
const char = board;
if (char !== ".") {
if (hasNum) {
return false;
}
hasNum = true;
}
}
}
}
}
return true;
};
```
https://leetcode.cn/problems/reverse-pairs/submissions/587579007/
考察归并排序问题
一次过！
```js
function merge(arr, l, m, r) {
var result = [];
let check2 = m + 1;
let ans = 0;
for (let index = l; index <= m; index++) {
while (arr > arr * 2 && check2 <= r) {
check2++
}
ans += check2 - m - 1
}
let pos1 = l;
let pos2 = m + 1;
while (pos1 <= m && pos2 <= r) {
if (arr < arr) {
result.push(arr);
}
else {
result.push(arr);
}
}
while (pos1 <= m) {
result.push(arr);
}
while (pos2 <= r) {
result.push(arr);
}
for (let index = 0; index < result.length; index++) {
arr = result
}
return ans;
}
function mergeSort(arr, l, r) {
if (l == r) return 0;
const mid = l + Math.floor((r - l) / 2);
return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}
/**
* @param {number[]} nums
* @Return {number}
*/
var reversePairs = function (nums) {
return mergeSort(nums, 0, nums.length - 1)
};```
https://leetcode.cn/problems/copy-list-with-random-pointer/submissions/587584803/
简单题，多次遍历即可
```js
var copyRandomList = function (head) {
if(head==null){
return head
}
let node = head;
while (node !== null) {
let next = node.next;
node.next = {
val: node.val,
next: next,
random: null,
}
node = next;
}
node = head;
while (node !== null) {
node.next.random = node.random?.next ?? null;
node = node.next.next;
}
node = head;
let newNode = node.next;
let ret = newNode
while (node !== null) {
node.next = node.next.next;
node = node.next
newNode.next = node?.next ?? null;
newNode = newNode.next
}
return ret
};
```
https://leetcode.cn/problems/check-completeness-of-a-binary-tree/submissions/587588536/
感觉到bfs了
但是边界没扣好
看了一眼答案
```js
var isCompleteTree = function (root) {
const stack = ;
let pre = root;
while (stack.length !== 0) {
const item = stack.shift();
if (item !== null) {
if (pre == null) {
return false
}
stack.push(item.left);
stack.push(item.right);
}
pre = item;
}
return true
};
```
https://leetcode.cn/problems/network-delay-time/submissions/587598445/
dj算法，没记下来，要好好背一下QAQ
```js
var networkDelayTime = function (times, n, k) {
const g = new Array(n).fill(0).map(() => new Array(n).fill(Infinity))
for (let index = 0; index < times.length; index++) {
const = times;
g = z
}
const dis = new Array(n).fill(Infinity)
const vis = new Array(n).fill(false)
dis = 0;
while (true) {
let x = -1
for (let index = 0; index < dis.length; index++) {
if (vis !== true && (x == -1 || dis < dis)) {
x = index;
}
}
if (x == -1) {
const result= Math.max(...dis)
return result===Infinity?-1:result
}
for (let index = 0; index < dis.length; index++) {
dis = Math.min(dis, dis + g)
}
vis=true
}
};
```
https://leetcode.cn/problems/minimum-number-of-valid-strings-to-form-target-i/submissions/587607803/
前缀树+dp
```js
var minValidStrings = function (words, target) {
const tree = {}
for (let index = 0; index < words.length; index++) {
const word = words.split("");
let node = tree
for (let index = 0; index < word.length; index++) {
const char = word;
if (node == undefined) {
node = {}
}
node = node
}
node.end = true
}
const dp = new Array(target.length + 1).fill(Number.MAX_SAFE_INTEGER);
dp = 0;
for (let index = target.length - 1; index >= 0; index--) {
let node = tree;
let pos = index;
while (pos < target.length) {
node = node]
if (node == undefined) {
break;
}
const num = dp;
if (num !== Number.MAX_SAFE_INTEGER) {
dp = Math.min(dp, num + 1)
}
pos++
}
}
return dp===Number.MAX_SAFE_INTEGER?-1:dp
};
```
https://leetcode.cn/problems/stickers-to-spell-word/submissions/587794484/
一个&&和&扣了一个小时...
```js
var minStickers = function (stickers, target) {
const allT = (1 << target.length) - 1;
const cache = new Map();
const dfs = (status) => {
if (status == allT) {
return 0;
}
if (cache.has(status)) {
return cache.get(status)
}
let ans = Number.MAX_SAFE_INTEGER
for (let index = 0; index < stickers.length; index++) {
const sticker = stickers;
let newStatus = status
for (let indey = 0; indey < sticker.length; indey++) {
const char = sticker;
for (let indez = 0; indez < target.length; indez++) {
const tchar = target;
if (tchar == char && ((newStatus & (1 << indez)) === 0)) {
newStatus = newStatus | (1 << indez)
break;
}
}
}
if (newStatus !== status) {
ans = Math.min(ans, dfs(newStatus) + 1)
}
}
cache.set(status, ans)
return ans
}
const ans = dfs(0)
return ans == Number.MAX_SAFE_INTEGER ? -1 : ans
};
```
https://leetcode.cn/problems/maximum-subarray-min-product/
大数问题扣了半天...
```js
var maxSumMinProduct = function (nums) {
const left = new Array(nums.length).fill(-1);
const right = new Array(nums.length).fill(-1);
const sum = new Array(nums.length).fill(-1);
const getSum = (l, r) => {
if (l == -1) {
if (r == -1) {
return sum
}
return sum
}
if (r == -1) {
return sum - sum
}
return sum - sum
}
sum = nums
for (let index = 1; index < nums.length; index++) {
sum = sum + nums
}
let stack = [];
for (let index = 0; index < nums.length; index++) {
const num = nums;
while (stack.length !== 0 && nums] >= num) {
stack.pop()
}
if (stack.length !== 0) {
left = stack
}
stack.push(index)
}
stack = [];
for (let index = nums.length - 1; index >= 0; index--) {
const num = nums;
while (stack.length !== 0 && nums] >= num) {
stack.pop()
}
if (stack.length !== 0) {
right = stack
}
stack.push(index)
}
let ans = 0n
const bigIntMax = (...args) => args.reduce((m, e) => e > m ? e : m);
for (let index = 0; index < nums.length; index++) {
const num = nums;
const l = left;
const r = right;
const sum = getSum(l, r);
ans = BigInt(bigIntMax(ans, BigInt(sum) * BigInt(num) ));
}
return Number(ans%BigInt(10**9+7))
};
```
https://leetcode.cn/problems/maximal-rectangle/submissions/587821910/
柱形的变形题
```js
var largestRectangleArea = function (heights) {
const n = heights.length;
const left = Array(n).fill(-1);
const st = [];
for (let i = 0; i < n; i++) {
const x = heights;
while (st.length && x <= heights]) {
st.pop();
}
if (st.length) {
left = st;
}
st.push(i);
}
const right = Array(n).fill(n);
st.length = 0;
for (let i = n - 1; i >= 0; i--) {
const x = heights;
while (st.length && x <= heights]) {
st.pop();
}
if (st.length) {
right = st;
}
st.push(i);
}
let ans = 0;
for (let i = 0; i < n; i++) {
ans = Math.max(ans, heights * (right - left - 1));
}
return ans;
};
/**
* @param {character[][]} matrix
* @Return {number}
*/
var maximalRectangle = function (matrix) {
let ans = 0;
for (let start = 0; start < matrix.length; start++) {
let stack = new Array(matrix.length).fill(0);
for (let index = start; index < matrix.length; index++) {
//每行的数字都加上
for (let indey = 0; indey < matrix.length; indey++) {
const num = matrix;
stack += parseInt(num);
if (parseInt(num) == 0) {
stack = 0
}
}
ans = Math.max(ans, largestRectangleArea(stack))
}
}
return ans
};
```