https://leetcode.cn/problems/length-of-last-word/submissions/570106650/?envType=study-plan-v2&envId=programming-skills
随手来一道练习题
今日收工
```js
func lengthOfLastWord(s string) int {
var word string
for index := len(s) - 1; index >= 0; index-- {
if s == " " && word != "" {
break
}
if s != " " {
word += s
}
}
return len(word)
}
```
https://leetcode.cn/problems/max-submatrix-lcci/submissions/571458474/
这题挺难凹的
```js
var getMaxMatrix = function (matrix) {
let maxValue = Number.MIN_SAFE_INTEGER;
let top = undefined;
let bottom = undefined;
let right = undefined;
let size = undefined;
const findMax = (arr, localTop, localBottom) => {
let currentValue = arr;
if (maxValue < currentValue) {
maxValue = currentValue;
right = 0;
size = 0;
top = localTop;
bottom = localBottom;
}
const dp = new Array(arr.length).fill(0);
dp = arr <= 0 ? 0 : arr
let left = 0;
let localRight = 0;
for (let index = 1; index < arr.length; index++) {
const num = arr;
if (dp + arr <= arr) {
left=index;
dp = num
} else {
if (num <= 0) {
dp = dp + num
} else {
dp = dp + num
}
}
if(currentValue<dp){
localRight=index
currentValue=dp
}
if (maxValue < currentValue) {
maxValue = currentValue;
right = localRight;
size = left;
top = localTop;
bottom = localBottom;
}
}
}
for (let index = 0; index < matrix.length; index++) {
const arr = new Array(matrix.length).fill(0)
for (let indey = index; indey < matrix.length; indey++) {
//添加每一行的值
for (let indez = 0; indez < arr.length; indez++) {
arr += matrix;
}
findMax(arr, index, indey)
//查找最大的正方形
}
}
return
};
```
https://leetcode.cn/problems/the-skyline-problem/submissions/571618493/?envType=problem-list-v2&envId=XVBr8pQX
轮廓线问题
被我写的一团乱麻A过了
```js
class MaxHeadp {
heap;
border;
compare;
constructor(nums, compare) {
this.heap = nums;
this.border = nums.length - 1;
this.compare = compare ?? ((a, b) => a - b);
this.initHeap();
}
initHeap() {
const endIndex = this.getTopNode(this.border);
for (let index = endIndex; index >= 0; index--) {
this.downNode(index);
}
}
//有多少个元素
haveNum() {
return this.border + 1;
}
//弹出最顶的
pop(index = 0) {
if (this.border === -1) {
return undefined;
}
const temp = this.heap;
this.heap = this.heap;
this.border--;
this.downNode(index);
return temp;
}
//插入元素
insert(node) {
this.border++;
this.heap = node;
this.upNode(this.border);
}
getNode(callback,index=0) {
if (index <= this.border) {
const result = callback(this.heap);
if (result == 0) {
return { index, item: this.heap };
}
const index1 = this.getNode(callback,this.getLeftNode(index));
if (index1.item !== undefined) {
return index1;
}
const index2 = this.getNode(callback,this.getRightNode(index));
if (index2.item !== undefined) {
return index2;
}
}
return { index: -1, item: undefined };
}
swap(x, y) {
let temp = this.heap;
this.heap = this.heap;
this.heap = temp;
}
downNode(index) {
let left = this.getLeftNode(index);
let right = this.getRightNode(index);
while (left <= this.border || right <= this.border) {
let maxIndex = undefined;
if (left <= this.border || right <= this.border) {
maxIndex =
this.compare(this.heap, this.heap) < 0 ? right : left;
} else {
maxIndex = left <= this.border ? right : left;
}
// if (this.heap < this.heap) {
if (this.compare(this.heap, this.heap) < 0) {
this.swap(index, maxIndex);
index = maxIndex;
left = this.getLeftNode(index);
right = this.getRightNode(index);
} else {
break;
}
}
}
upNode(index) {
while (index != 0) {
const parentIndex = this.getTopNode(index);
if (this.compare(this.heap, this.heap) < 0) {
this.swap(parentIndex, index);
index = parentIndex;
} else {
break;
}
}
}
getTopNode(index) {
return Math.floor((index - 1) / 2);
}
getLeftNode(index) {
return (index + 1) * 2 - 1;
}
getRightNode(index) {
return (index + 1) * 2;
}
}
var getSkyline = function (buildings) {
const posArr = [];
for (let index = 0; index < buildings.length; index++) {
const build = buildings;
posArr.push({
pos: build,
height: build,
});
posArr.push({
pos: build,
height: -build,
});
}
posArr.sort((a, b) => {
if (a.pos !== b.pos) {
return a.pos - b.pos;
} else {
return b.height - a.height;
}
});
const maxHeightHeap = new MaxHeadp([], (a, b) => {
return a.height - b.height;
});
const ret = [];
for (let index = 0; index < posArr.length; index++) {
if (index === 3) {
debugger;
}
const posItem = posArr;
const { item: node, index: posIndex } = maxHeightHeap.getNode(
(a) => a.height - Math.abs(posItem.height)
);
if (node !== undefined) {
if (posItem.height > 0) {
node.times++;
} else {
if (node.times == 1) {
maxHeightHeap.pop(posIndex);
} else {
node.times--;
}
}
} else {
maxHeightHeap.insert({
pos: posItem.pos,
times: 1,
height: posItem.height,
});
}
const result = maxHeightHeap.heap;
if (maxHeightHeap.border == -1) {
if (ret !== 0) {
ret.push();
}
} else {
if (index == posArr.length - 1 || posArr.pos !== posItem.pos) {
if (ret.length==0||ret !== result.height) {
ret.push();
}
}
}
}
return ret;
};
```
https://leetcode.cn/problems/longest-common-prefix/submissions/571650018/?envType=study-plan-v2&envId=top-interview-150
来个简单题睡觉了
```js
var longestCommonPrefix = function (strs) {
let minLen = strs.length;
for (let index = 1; index < strs.length; index++) {
minLen = Math.min(minLen, strs.length)
}
let preFix = ""
for (let index = 0; index < minLen; index++) {
const globalChar = strs
for (let indey = 1; indey < strs.length; indey++) {
const char = strs;
if(globalChar!==char){
return preFix;
}
}
preFix+=globalChar
}
return preFix
};
```
https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/submissions/571858393/
基础dfs
```js
var bstFromPreorder = function (preorder) {
const build = (l, r) => {
if(l>r){
return null
}
const node = {
val: preorder,
}
let border = l + 1;
while (border <= r) {
if (preorder < preorder) {
border++;
} else {
break;
}
}
node.left = build(l + 1, border - 1)
node.right = build(border, r)
return node
}
return build(0, preorder.length - 1)
};
```
https://leetcode.cn/problems/minimum-size-subarray-sum/submissions/571876069/?envType=study-plan-v2&envId=top-interview-150
基础滑窗题
```js
var minSubArrayLen = function (target, nums) {
let l = 0; r = 0;
let result = nums;
let minLen = Number.MAX_SAFE_INTEGER
while (l <= r && l < nums.length) {
if (result < target) {
if (r < nums.length-1) {
r++;
result += nums;
} else {
result -= nums;
l++;
}
} else {
minLen = Math.min(minLen, r - l+1);
result -= nums;
l++;
}
}
return minLen==Number.MAX_SAFE_INTEGER?0:minLen
};
```
https://leetcode.cn/submissions/detail/571930586/
感觉上应该用DC3，但是找不到js版本的
就看了一下题解用双指针过的
```js
var lastSubstring = function (s) {
let i = 0,
j = 1,
k = 0;
while (j + k < s.length) {
if (s == s) {
k++;
} else if (s < s) {
i = i + k + 1;
k = 0;
if (i == j) {
j = i + 1;
}
} else {
j = j + k + 1;
k = 0;
if (i == j) {
j = i + 1;
}
}
}
return s.slice(i);
};
```
https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
前缀树问题
但是我是真想不通为什么要出这个狗螺蛳粉边界卡
```js
class Tree {
head;
constructor() {
this.head = {};
}
add(num) {
let head = this.head;
for (let index = 31; index >= 0; index--) {
const bit = (num >> index) & 1;
head = head ?? {};
head = head;
}
}
getMaxXor(num) {
let head = this.head;
let result = num;
for (let index = 31; index >= 0; index--) {
let bit = ((num >> index) & 1) == 0 ? 1 : 0;
if (head == undefined) {
bit = bit==0?1:0;
}
result = result ^ (bit << index);
head = head;
}
return result;
}
}
var findMaximumXOR = function (nums) {
const tree = new Tree();
tree.add(nums);
let result = 0;
for (let index = 1; index < nums.length; index++) {
const num = nums;
result = Math.max(result, tree.getMaxXor(num));
tree.add(num)
if(result==1073741823){
break;
}
}
return result;
};
```
好吧，是我复杂度问题
https://leetcode.cn/problems/maximum-xor-with-an-element-from-array/submissions/572171968/
这个确实难，完全是对着题解的海量题硬凹了一个优化打过去的
```js
var maximizeXor = function (nums, queries) {
function generateTree(maxBit) {
let treeHead = { min: Number.MAX_SAFE_INTEGER }
let querie = 0
const add = (num) => {
let head = treeHead;
head.min = Math.min(head.min, num)
for (let index = maxBit; index >= 0; index--) {
const bit = (num >> index) & 1;
head = head ?? {
min: Number.MAX_SAFE_INTEGER
};
head = head;
head.min = Math.min(head.min, num)
}
}
getMaxXor = (num) => {
let head = treeHead;
if (head.min > querie) {
return -1
}
let result = num;
for (let index = maxBit; index >= 0; index--) {
let bit = ((num >> index) & 1) == 0 ? 1 : 0;
if (head == undefined || head.min > querie) {
bit = bit == 0 ? 1 : 0;
}
result = result ^ (bit << index);
head = head;
}
return result;
}
return {
setQuery: (num) => {
querie = num
},
add,
getMaxXor
}
}
const tree = generateTree(31 - Math.clz32(Math.max(...nums)));
let maxXor = Number.MIN_SAFE_INTEGER;
if (queries.length == 1) {
for (let index = 0; index < nums.length; index++) {
const num = nums;
if (num <= queries) {
maxXor = Math.max(maxXor, num ^ queries)
}
}
return
}
for (let index = 0; index < nums.length; index++) {
const num = nums;
tree.add(num)
}
let result = [];
for (let index = 0; index < queries.length; index++) {
const = queries;
tree.setQuery(query)
result.push(tree.getMaxXor(num));
}
return result;
};
```