https://leetcode.cn/problems/h-index/submissions/569715088/?envType=study-plan-v2&envId=top-interview-150
抠边界有点困难，其他还好
```js
var hIndex = function (citations) {
let maxH = 0;
citations = citations.sort((a, b) => b-a);
for (let index = 0; index < citations.length; index++) {
const num = citations;
if (num > maxH) {
maxH++;
}else{
break
}
}
return maxH
};
```
https://leetcode.cn/problems/insert-delete-getrandom-o1/submissions/569717371/?envType=study-plan-v2&envId=top-interview-150
设计题
很容易就秒了
```js
var RandomizedSet = function () {
this.cache = new Map();
};
/**
* @param {number} val
* @Return {boolean}
*/
RandomizedSet.prototype.insert = function (val) {
if (this.cache.has(val)) {
return false;
}
this.cache.set(val, true);
return true;
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function (val) {
if (!this.cache.has(val)) {
return false;
}
this.cache.delete(val);
return true;
};
/**
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
return [...this.cache];
};
```
https://leetcode.cn/problems/find-the-difference/submissions/569718040/?envType=study-plan-v2&envId=programming-skills
```go
func findTheDifference(s string, t string) byte {
var cache mapint32 = make(mapint32)
for _, v := range s {
cache++
}
var result byte
for _, v := range t {
if cache == 0 {
result = byte(v)
break
}
cache--
}
return result
}
```
https://leetcode.cn/problems/gas-station/submissions/569905538/?envType=study-plan-v2&envId=top-interview-150
我也知道要贪心
但是就是贪不起来...
```js
var canCompleteCircuit = function (gas, cost) {
for (let index = 0; index < gas.length; index++) {
let pos = 0;
let total = 0;
if (gas < cost) {
continue;
}
while (pos < gas.length) {
total += gas[(index + pos) % gas.length];
total -= cost[(index + pos) % gas.length];
if (total < 0) {
index = index+pos;
break;
}
pos++;
}
if (total >= 0) {
return index;
}
}
return -1;
};
```
https://leetcode.cn/problems/candy/submissions/569905683/?envType=study-plan-v2&envId=top-interview-150
一眼双遍历
```js
/**
* @param {number[]} ratings
* @Return {number}
*/
var candy = function (ratings) {
const arr = new Array(ratings.length).fill(1);
const arr2 = new Array(ratings.length).fill(1);
for (let index = 1; index < ratings.length; index++) {
const rate = ratings;
const lastRate = ratings;
if (rate > lastRate) {
arr = arr + 1;
}
}
for (let index = ratings.length - 1; index >= 0; index--) {
const rate = ratings;
const lastRate = ratings;
if (rate > lastRate) {
arr2 = arr2 + 1;
}
}
let total = 0;
for (let index = 0; index < ratings.length; index++) {
total += Math.max(arr, arr2);
}
return total
};
```
https://leetcode.cn/problems/roman-to-integer/submissions/569906117/?envType=study-plan-v2&envId=top-interview-150
简单题
一次秒了
```js
var romanToInt = function (s) {
const map = {
I: 1,
V: 5,
X: 10,
L: 50,
C: 100,
D: 500,
M: 1000,
undefined: 0,
};
let total = 0;
for (let index = 0; index < s.length; index++) {
const char = s;
if (char == "I" && (s == "V" || s == "X")) {
total -= map;
total += map];
index++;
} else if (char == "X" && (s == "L" || s == "C")) {
total -= map;
total += map];
index++;
} else if (char == "C" && (s == "D" || s == "M")) {
total -= map;
total += map];
index++;
} else {
total += map;
}
}
return total
};
```
https://leetcode.cn/problems/reverse-words-in-a-string/submissions/569906388/?envType=study-plan-v2&envId=top-interview-150
字符串处理题，还算简单
```js
var reverseWords = function (s) {
let result = "";
let word = "";
for (let index = 0; index < s.length; index++) {
const char = s;
if (char !== " ") {
word += char;
} else {
if (s !== undefined && s !== " ") {
if(result==""){
result = word
}else{
result = word + " " + result;
}
word=""
}
}
}
if(word!==""){
result = word + (result==""?"": " " + result)
}
return result
};
```
https://leetcode.cn/problems/largest-1-bordered-square/submissions/570102367/
需要进行状态的缓存，还是挺复杂的
```js
var largest1BorderedSquare = function (grid) {
const right = new Array(grid.length).fill(0).map(() => new Array(grid.length).fill(0))
const down = new Array(grid.length).fill(0).map(() => new Array(grid.length).fill(0))
for (let index = 0; index < grid.length; index++) {
for (let indey = grid.length-1; indey>=0; indey--) {
if (grid == 0) {
right = 0
} else {
right = (right ?? 0) + 1
}
}
}
for (let index = grid.length - 1; index >= 0; index--) {
for (let indey = 0; indey <grid.length; indey++) {
if (grid == 0) {
down = 0
} else {
down = (down?. ?? 0) + 1
}
}
}
let ans = 0;
for (let index = 0; index < grid.length; index++) {
for (let indey = 0; indey < grid.length; indey++) {
if (grid == 0) {
continue;
}
let pos = 0;
while (true) {
if ((index + pos) >= grid.length || (indey + pos) >= grid.length) {
break;
}
if (right >= (pos + 1) && down >= (pos + 1) && right >= (pos + 1) && down >= (pos + 1)) {
ans = Math.max(ans, pos + 1)
}
pos++;
}
}
}
return ans*ans
};
```
https://leetcode.cn/problems/closest-subsequence-sum/submissions/570104234/
没猜到是分治，没想到最后合并还可以利用双指针
我想用二分秒来着，虽然也是Nlog，但是编写的困难度高太多了
```js
var minAbsDifference = function (nums, goal) {
const sum = (start, end) => {
const result = []
const dfs = (index, total) => {
if (index >= end) {
result.push(total);
return;
}
dfs(index + 1, total)
dfs(index + 1, total + nums)
}
dfs(start,0)
return result
}
const arr1 = sum(0, Math.floor(nums.length / 2));
const arr2 = sum(Math.floor(nums.length / 2), nums.length);
arr1.sort((a, b) => a - b);
arr2.sort((a, b) => a - b);
let l = 0;
let r = arr2.length - 1;
let result = Number.MAX_SAFE_INTEGER;
while (l < arr1.length && r >= 0) {
const sum = arr1 + arr2;
result = Math.min(result, Math.abs(sum - goal));
if (sum > goal) {
//r小一点
r--;
} else {
//l大一点
l++;
}
}
return result;
};
```
https://leetcode.cn/problems/freedom-trail/submissions/570104763/
缓存dfs秒了！
```js
var findRotateSteps = function (ring, key) {
const map = new Map()
for (let index = 0; index < ring.length; index++) {
const char = ring;
if (map.has(char)) {
(map.get(char)).push(index)
} else {
map.set(char, )
}
}
const calcStep = (x, y) => {
const methodA = Math.abs(x - y)
return Math.min(methodA, ring.length - methodA)
}
const cache=new Map()
const dfs = (pos, index) => {
const flag=`${pos} ${index}`
if(cache.has(flag)){
return cache.get(flag)
}
if(index>=key.length){
return 0
}
const nextArr = map.get(key)
let result = Number.MAX_SAFE_INTEGER
for (let nextIndex = 0; nextIndex < nextArr.length; nextIndex++) {
const nextPos = nextArr;
const step = calcStep(pos, nextPos);
result = Math.min(result, step + 1 + dfs(nextPos, index + 1))
}
cache.set(flag,result)
return result
}
return dfs(0, 0)
};
```