https://leetcode.cn/problems/multiply-strings/submissions/590550128/
模拟题秒了，有点脏
但是凭感觉写的乘法还是蛮自豪的
```js
const addNum = (str1, str2) => {
let maxLen = Math.max(str1.length, str2.length);
while (str1.length !== maxLen) {
str1 = "0" + str1;
}
while (str2.length !== maxLen) {
str2 = "0" + str2;
}
let extra = 0;
let ans = "";
for (let index = maxLen - 1; index >= 0; index--) {
const num1 = str1 ? str1.charCodeAt() - 48 : 0;
const num2 = str2 ? str2.charCodeAt() - 48 : 0;
let total = num1 + num2 + extra;
extra = Math.floor(total / 10);
total = total - extra * 10;
ans = total + ans;
}
if(extra!==0){
ans="1"+ans
}
return ans;
};
const add = (num, times) => {
let timeNum = num;
let result = "0";
for (let index = 0; index < 32; index++) {
if (times & (1 << index)) {
result = addNum(result, timeNum);
}
timeNum = addNum(timeNum, timeNum);
}
return result;
};
/**
* @param {string} num1
* @param {string} num2
* @Return {string}
*/
var multiply = function (num1, num2) {
if(num1=="0"||num2=="0"){
return "0"
}
let last = "";
for (let index = 0; index < num2.length; index++) {
if (last !== "") {
last += "0";
}
const times = num2.charCodeAt() - 48;
last = addNum(last, add(num1, times));
}
return last
};
```
https://leetcode.cn/problems/valid-number/submissions/590566702/
感觉这题挺烂的
懒得思考了
直接对着测例硬编码过去了
```js
var isNumber = function (s) {
const isNum=(pos)=>{
const code = s?.charCodeAt();
if (code >= 48 && code <= 57 ) {
return true;
}
return false
}
let pAndnPos=-1
let pAndnNum = 0;
let dot = 0;
let dotPos=-1;
let eNum=0;
let ePos=-1;
for (let index = 0; index < s.length; index++) {
const char = s;
if (char == "+" || char == "-") {
if(s=="+"||s=="-"){
return false
}
if(s=="+"||s=="-"){
return false
}
pAndnPos=index
pAndnNum++;
}
if (char == "e"||char == "E") {
eNum++
ePos=index;
}
if (char == ".") {
dot++;
dotPos=index
}
const code = char.charCodeAt();
if (code >= 97 && code <= 122 && code !== 101) {
return false;
}
if (code >= 64 && code <= 90 && code !== 69) {
return false;
}
}
if(dot>1||eNum>1){
return false
}
if(ePos!==-1){
if(!isNum(ePos+1)&&s!='+'&&s!='-'){
return false
}
if(!isNum(ePos-1)&&s!='.'){
return false
}
}
if(pAndnPos!==-1){
if(!isNum(pAndnPos+1)&&s!=='.'){
return false
}
if(!isNum(pAndnPos+1)&&s=='.'&&pAndnPos!=0){
return false
}
if(isNum(pAndnPos+1)&&isNum(pAndnPos-1)){
return false
}
}
if(dotPos!==-1){
if(!isNum(dotPos+1)){
if(!isNum(dotPos-1)){
return false
}
}
}
if(ePos!==-1&&dotPos!==-1&&ePos<dotPos){
return false
}
// if(ePos!==-1&&pAndnPos!==-1&&ePos<pAndnPos){
// return false
// }
return true
};
```
https://leetcode.cn/problems/permutation-sequence/submissions/590574873/
一次过hard题！
数字的数量刨分
```js
function factorial(n) {
if (n === 0 || n === 1) {
return 1;
}
return n * factorial(n - 1);
}
var getPermutation = function (n, k) {
const arr = new Array(n + 1).fill(false);
const dfs = (n, k) => {
if(n<1){
return ""
}
let childNum = factorial(n - 1);
for (let index = 1; index < arr.length; index++) {
const num = index;
const status = arr;
if (status) {
continue;
}
if (k <= childNum) {
arr = true;
return `${index}` + dfs(n - 1, k);
} else {
//大于
k -= childNum;
}
}
};
return dfs(n,k)
};
```
https://leetcode.cn/problems/remove-duplicates-from-sorted-list/submissions/590586599/
简单题
炸了
```js
var deleteDuplicates = function (head) {
if(head==null){
return null
}
let node = {};
ret = node;
while (head != null) {
if (node.val !== head.val) {
node.next = {
next: null,
val: head.val,
};
head=head.next;
node=node.next;
}else{
head=head.next;
}
}
return ret.next
};
```
https://leetcode.cn/problems/restore-ip-addresses/submissions/590588548/
dfs一次过
```js
var restoreIpAddresses = function (s) {
let ans = [];
const dfs = (pos, block, str) => {
if (pos == s.length) {
if (block == 4) {
ans.push(str);
} else {
return;
}
}
if (block >= 4) {
return;
}
let num = "";
for (let index = 0; index < 3; index++) {
num +=s;
if (parseInt(num) > 255) {
break;
} else {
dfs(pos + index + 1, block + 1, str == "" ? `${num}` : str + "." + num);
}
if(num=="0"){
break;
}
}
};
dfs(0, 0, "");
return ans
};
```
https://leetcode.cn/problems/subsets-ii/submissions/590589695/
tag大法好
```js
var subsetsWithDup = function (nums) {
nums.sort((a,b)=>a-b)
const arr = [];
const ans = [];
const cache = new Map();
const dfs = (i) => {
if (i >= nums.length) {
const tag = arr.join(" ");
if (cache.has(tag)) {
return;
}
cache.set(tag, true);
ans.push([...arr]);
return;
}
dfs(i + 1, arr);
arr.push(nums);
dfs(i + 1, arr);
arr.pop();
};
dfs(0)
return ans;
};
```
https://leetcode.cn/problems/my-calendar-i/submissions/590594518/
依靠gpt的avl模板打过了
```js
class AVLTree {
constructor(compare) {
this.root = null;
this.compare = compare || ((a, b) => a - b);
}
getHeight(node) {
return node ? node.height : 0;
}
getBalanceFactor(node) {
return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
}
rightRotate(y) {
let x = y.left;
let T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;
x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;
return x;
}
leftRotate(x) {
let y = x.right;
let T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;
y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;
return y;
}
insert(node, key) {
if (!node) return new Node(key);
if (this.compare(key, node.key) < 0) {
node.left = this.insert(node.left, key);
} else if (this.compare(key, node.key) > 0) {
node.right = this.insert(node.right, key);
} else {
return node;
}
node.height =
1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
let balance = this.getBalanceFactor(node);
if (balance > 1 && this.compare(key, node.left.key) < 0) {
return this.rightRotate(node);
}
if (balance < -1 && this.compare(key, node.right.key) > 0) {
return this.leftRotate(node);
}
if (balance > 1 && this.compare(key, node.left.key) > 0) {
node.left = this.leftRotate(node.left);
return this.rightRotate(node);
}
if (balance < -1 && this.compare(key, node.right.key) < 0) {
node.right = this.rightRotate(node.right);
return this.leftRotate(node);
}
return node;
}
insertKey(key) {
this.root = this.insert(this.root, key);
}
findGreater(node, key, result) {
if (!node) return;
if (this.compare(node.key, key) > 0) {
result.push(node.key);
this.findGreater(node.left, key, result);
}
this.findGreater(node.right, key, result);
}
findSmaller(node, key, result) {
if (!node) return;
if (this.compare(node.key, key) < 0) {
result.push(node.key);
this.findSmaller(node.right, key, result);
}
this.findSmaller(node.left, key, result);
}
getGreaterThan(key) {
let result = [];
this.findGreater(this.root, key, result);
return result;
}
getSmallerThan(key) {
let result = [];
this.findSmaller(this.root, key, result);
return result;
}
}
// 使用示例
var MyCalendar = function () {
this.tree = new AVLTree((a, b) => a.left - b.left);
};
/**
* @param {number} startTime
* @param {number} endTime
* @Return {boolean}
*/
MyCalendar.prototype.book = function (startTime, endTime) {
const lefts = this.tree.getSmallerThan({
left: startTime,
});
const rights = this.tree.getSmallerThan({
left: endTime ,
});
for (let index = 0; index < lefts.length; index++) {
const left = lefts;
if (left !== undefined) {
if (left.right >= startTime) {
return false;
}
}
}
for (let index = 0; index < rights.length; index++) {
const right = rights;
if (right !== undefined) {
if (right.left <= endTime && right.left >= startTime) {
return false;
}
if (right.right <= endTime && right.right >= startTime) {
return false;
}
if (right.left <= startTime && right.right >= endTime) {
return false;
}
}
}
this.tree.insertKey({
left: startTime,
right: endTime - 1,
});
return true;
};
```
https://leetcode.cn/problems/sudoku-solver/submissions/590541196/
dfs炸了
```js
var solveSudoku = function (board) {
const next = (x, y) => {
if (y >= board.length) {
return ;
} else {
return ;
}
};
const line = new Array(9).fill(0).map(() => new Map());
const row = new Array(9).fill(0).map(() => new Map());
const block = new Array(9).fill(0).map(() => new Map());
const setChar = (index, indey, char, status = true) => {
line.set(char, status);
row.set(char, status);
block.set(char, status);
};
const getUseNumber = (x, y) => {
const list = [];
for (let index = 1; index <= 9; index++) {
const num = index + "";
if (line.get(num) == true) {
continue;
}
if (row.get(num) == true) {
continue;
}
if (block.get(num) == true) {
continue;
}
list.push(num);
}
return list;
};
let ans = false;
const dfs = (x, y) => {
if (x == board.length) {
ans = true;
return;
}
const char = board;
if (char == ".") {
const list = getUseNumber(x, y);
const = next(x, y);
for (let index = 0; index < list.length; index++) {
const num = list;
board = num;
setChar(x, y, num);
dfs(nextX, nextY);
if (ans == true) {
break;
}
setChar(x, y, num, false);
board = ".";
}
} else {
const = next(x, y);
dfs(nextX, nextY);
}
};
for (let index = 0; index < board.length; index++) {
for (let indey = 0; indey < board.length; indey++) {
const char = board;
if (char == ".") {
continue;
}
setChar(index, indey, char);
}
}
dfs(0, 0);
};
```
https://leetcode.cn/problems/number-of-recent-calls/submissions/590601467/
线段树
```js
class Node {
left;
right;
val = 0;
lazy = 0;
}
class SegmentTreeDynamic {
root;
constructor() {
this.root = new Node();
}
update(node, start, end, l, r, val) {
if (l <= start && end <= r) {
node.val += (end - start + 1) * val;
node.lazy += val;
return;
}
let mid = (start + end) >> 1;
this.pushDown(node, mid - start + 1, end - mid);
if (l <= mid) this.update(node.left, start, mid, l, r, val);
if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
this.pushUp(node);
}
pushUp(node) {
node.val = node.left.val + node.right.val;
}
query(node, start, end, l, r) {
if (l <= start && end <= r) return node.val;
let mid = (start + end) >> 1,
ans = 0;
this.pushDown(node, mid - start + 1, end - mid);
if (l <= mid) ans += this.query(node.left, start, mid, l, r);
if (r > mid) ans += this.query(node.right, mid + 1, end, l, r);
return ans;
}
pushDown(node, leftNum, rightNum) {
if (node.left == null) node.left = new Node();
if (node.right == null) node.right = new Node();
if (node.lazy == 0) return;
node.left.val += node.lazy * leftNum;
node.right.val += node.lazy * rightNum;
node.left.lazy += node.lazy;
node.right.lazy += node.lazy;
node.lazy = 0;
}
}
var RecentCounter = function () {
this.tree = new SegmentTreeDynamic();
};
/**
* @param {number} t
* @Return {number}
*/
RecentCounter.prototype.ping = function (t) {
this.tree.update(this.tree.root, 1, 10 ** 9, t, t, 1);
return this.tree.query(this.tree.root, 1, 10 ** 9, t - 3000, t);
};
```
https://leetcode.cn/submissions/detail/590601467/
线段树
```js
class Node {
left;
right;
val = 0;
lazy = 0;
}
class SegmentTreeDynamic {
root;
constructor() {
this.root = new Node();
}
update(node, start, end, l, r, val) {
if (l <= start && end <= r) {
node.val += (end - start + 1) * val;
node.lazy += val;
return;
}
let mid = (start + end) >> 1;
this.pushDown(node, mid - start + 1, end - mid);
if (l <= mid) this.update(node.left, start, mid, l, r, val);
if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
this.pushUp(node);
}
pushUp(node) {
node.val = node.left.val + node.right.val;
}
query(node, start, end, l, r) {
if (l <= start && end <= r) return node.val;
let mid = (start + end) >> 1,
ans = 0;
this.pushDown(node, mid - start + 1, end - mid);
if (l <= mid) ans += this.query(node.left, start, mid, l, r);
if (r > mid) ans += this.query(node.right, mid + 1, end, l, r);
return ans;
}
pushDown(node, leftNum, rightNum) {
if (node.left == null) node.left = new Node();
if (node.right == null) node.right = new Node();
if (node.lazy == 0) return;
node.left.val += node.lazy * leftNum;
node.right.val += node.lazy * rightNum;
node.left.lazy += node.lazy;
node.right.lazy += node.lazy;
node.lazy = 0;
}
}
var RecentCounter = function () {
this.tree = new SegmentTreeDynamic();
};
/**
* @param {number} t
* @Return {number}
*/
RecentCounter.prototype.ping = function (t) {
this.tree.update(this.tree.root, 1, 10 ** 9, t, t, 1);
return this.tree.query(this.tree.root, 1, 10 ** 9, t - 3000, t);
};
```