https://leetcode.cn/problems/peak-index-in-a-mountain-array/submissions/588536794/?envType=study-plan-v2&envId=primers-list
标准二分法的故事
```go
func peakIndexInMountainArray(arr []int) int {
var l int
var r int = len(arr) - 1
for l != r {
center := l + int((r-l)/2)
next := center + 1
if arr > arr {
r = center
} else {
l = next
}
}
return l
}
```
https://leetcode.cn/problems/transpose-matrix/submissions/588536961/?envType=study-plan-v2&envId=primers-list
数组翻转
```go
func transpose(matrix [][]int) [][]int {
ans := make([][]int, len(matrix))
for i := range ans {
ans = make([]int, len(matrix))
}
for i := 0; i < len(matrix); i++ {
for y := 0; y < len(matrix); y++ {
ans = matrix
}
}
return ans
}
```
https://leetcode.cn/problems/powx-n/submissions/588537136/?envType=study-plan-v2&envId=top-interview-150
一眼位运算乘法
不过懒得优化了
```js
var myPow = function (x, n) {
if (n < 0) {
n = n * -1;
x = 1 / x;
}
let num = x;
let ans = 1;
for (let index = 0; index < 32; index++) {
if ((n & (1 << index)) !== 0) {
ans = ans * num;
}
num = num * num;
}
return ans;
};
```
https://leetcode.cn/problems/binary-search-tree-iterator/submissions/588537224/?envType=study-plan-v2&envId=top-interview-150
看到h一开始以为是重链刨分
想了一下重链不太符合空间要求
应该就是根据高度构造了
试了一下一次过
```js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
*/
var BSTIterator = function (root) {
this.stack = [];
while (root !== null) {
this.stack.push(root);
root = root.left;
}
};
/**
* @Return {number}
*/
BSTIterator.prototype.next = function () {
const item = this.stack.pop();
let root = item.right;
while (root !== null) {
this.stack.push(root);
root = root.left;
}
return item.val;
};
/**
* @return {boolean}
*/
BSTIterator.prototype.hasNext = function () {
if (this.stack.length == 0) {
return false;
}
return true;
};
/**
* Your BSTIterator object will be instantiated and called as such:
* var obj = new BSTIterator(root)
* var param_1 = obj.next()
* var param_2 = obj.hasNext()
*/
```
https://leetcode.cn/problems/sort-integers-by-the-power-value/submissions/588537770/
秒了
```js
const getRank = (num) => {
if (num == 1) {
return 0;
}
if (num % 2 == 0) {
return getRank(num / 2) + 1;
} else {
return getRank(3 * num + 1) + 1;
}
};
var getKth = function (lo, hi, k) {
const arr = new Array(hi - lo + 1).fill(0).map((v, index) => lo + index);
arr.sort((a, b) => {
a1=getRank(a);
b1=getRank(b);
if(a1==b1){
return a-b
}
return a1-b1
});
return arr
};
```
https://leetcode.cn/problems/clone-graph/submissions/588649523/?envType=study-plan-v2&envId=top-interview-150
dfs秒了
```js
var cloneGraph = function (node) {
const cache = new Map()
const cloneDfs = (node) => {
if(node==null){
return null
}
if (cache.has(node.val)) {
return cache.get(node.val)
}
const newNode = {
val: node.val,
neighbors: [],
}
cache.set(node.val,newNode)
for (let index = 0; index < node.neighbors.length; index++) {
const neighbor = node.neighbors;
newNode.neighbors.push(cloneDfs(neighbor))
}
return newNode
}
return cloneDfs(node)
};
```
https://leetcode.cn/problems/insert-interval/submissions/588668749/?envType=study-plan-v2&envId=top-interview-150
狂写判断
```js
var insert = function (intervals, newInterval) {
let newInter = [...newInterval];
let isInsert = false;
let ans = []
for (let index = 0; index < intervals.length; index++) {
const interval = intervals;
if ((interval > newInter && interval < newInter)
|| (interval > newInter && interval < newInter)
|| (interval <= newInter && interval >= newInter)
|| (interval == newInter)
|| (interval == newInter)) {
newInter = Math.min(interval, newInter)
newInter = Math.max(interval, newInter)
} else if (!isInsert && interval > newInter) {
ans.push(newInter)
ans.push(interval)
isInsert = true
} else {
ans.push(interval)
}
}
if (!isInsert) {
ans.push(newInter)
}
return ans
};
```
https://leetcode.cn/problems/sqrtx/submissions/588671482/?envType=study-plan-v2&envId=top-interview-150
二分法秒了
```js
var mySqrt = function (x) {
let l = 0;
let r = x;
let ans = x;
while (l != r) {
let c = l + Math.floor((r - l) / 2)
if (c * c <= x&&c!=0) {
ans = c;
l = c + 1;
} else {
r = c
}
}
return ans
};
```
https://leetcode.cn/problems/simplify-path/submissions/588714181/?envType=study-plan-v2&envId=top-interview-150
堆栈秒
```js
var simplifyPath = function (path) {
const stack = [];
let str = "";
if(path!=='/'){
path+="/"
}
for (let index = 1; index < path.length; index++) {
const char = path;
if (char == "/" && str !== "") {
if (str != ".") {
if (str == "..") {
stack.pop();
} else {
stack.push(str);
}
}
str = "";
} else {
if(char!=='/'){
str += char;
}
}
}
return '/'+stack.join('/')
};
```
https://leetcode.cn/problems/permutations-ii/submissions/588930894/
回溯题，秒了
```js
var permuteUnique = function (nums) {
const swap = (a, b) => {
const temp = nums;
nums = nums;
nums = temp;
};
const ans = [];
const cache = new Map();
const dfs = (i) => {
if (i == nums.length - 1) {
const tag = nums.join(" ");
if (cache.has(tag) ) {
return;
}
cache.set(tag, true);
ans.push([...nums]);
return;
}
for (let index = i; index < nums.length; index++) {
swap(i, index);
dfs(i + 1);
swap(i, index);
}
};
dfs(0);
return ans;
};
```