leetcode top 150
reference
- https://www.yuque.com/tangzixuan666/vd6445/sacikxxwlccs147q
- https://leetcode.cn/studyplan/top-interview-150/
打卡记录
[20240821~20240821] 堆，二分查找 [20240822~20240822] 分冶法 [20240824~20240824] 树，图； [20240825~20240825] lru, 哈希
滑动窗口
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长
子串
的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let res = 0
let left=0,right=left;
let charSet = new Set();
charSet.g
while(left<s.length) {
while(right<s.length) {
if (!charSet.has(s[right])) {
charSet.add(s[right])
right = right + 1;
// console.log("log", left, right, charSet)
res = Math.max(res, charSet.size)
} else {
break;
}
}
charSet.delete(s[left])
left = left + 1;
}
return res;
};
栈
最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
- solution:
// 16: 44 - 16: 52
var MinStack = function() {
this.sta = []
this.minSta= []
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.sta.push(val)
if(this.minSta.length) {
let possibleMinVal = this.minSta[this.minSta.length-1]
if(val <= possibleMinVal) {
this.minSta.push(val)
} else {
this.minSta.push(possibleMinVal)
}
} else {
this.minSta.push(val)
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.minSta.pop();
this.sta.pop()
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
if (this.sta.length) {
return this.sta[this.sta.length - 1]
}
return null
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
if (this.minSta.length) {
return this.minSta[this.minSta.length-1]
}
return null;
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(val)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/
- 官方solution:
var construct = function(grid) {
return dfs(grid, 0, 0, grid.length, grid.length);
};
const dfs = (grid, r0, c0, r1, c1) => {
let same = true;
for (let i = r0; i < r1; ++i) {
for (let j = c0; j < c1; ++j) {
if (grid[i][j] !== grid[r0][c0]) {
same = false;
break;
}
}
if (!same) {
break;
}
}
if (same) {
return new Node(grid[r0][c0] === 1, true);
}
const ret = new Node(
true,
false,
dfs(grid, r0, c0, Math.floor((r0 + r1) / 2), Math.floor((c0 + c1) / 2)),
dfs(grid, r0, Math.floor((c0 + c1) / 2), Math.floor((r0 + r1) / 2), c1),
dfs(grid, Math.floor((r0 + r1) / 2), c0, r1, Math.floor((c0 + c1) / 2)),
dfs(grid, Math.floor((r0 + r1) / 2), Math.floor((c0 + c1) / 2), r1, c1)
);
return ret;
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/construct-quad-tree/solutions/1449809/jian-li-si-cha-shu-by-leetcode-solution-gcru/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
堆
数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
// 14: 20 - 14:45
class MyMinHeap {
// 小根堆
constructor () {
this.arr = []
}
swap(index1, index2) {
if(index1<0 || index1 >= this.arr.length) {
return;
}
if(index2<0 || index2 >= this.arr.length) {
return;
}
let temp = this.arr[index1]
this.arr[index1] = this.arr[index2]
this.arr[index2] = temp
}
getSize () {
return this.arr.length
}
// 0
// 1 2
// 3 4 5 6
add(val) {
this.arr.push(val);
let cur = this.arr.length -1;
while(cur) {
let parentIndex = Math.floor(cur -1)
if (this.arr[parentIndex]> this.arr[cur]) {
this.swap(parentIndex, cur)
cur = parentIndex
} else {
return;
}
}
}
deleteMin() {
this.swap(0, this.arr.length-1)
this.arr.pop()
let cur = 0;
while(cur < this.arr.length) {
let left = 2* cur + 1;
let right = 2* cur + 2;
let temp = cur;
if (left< this.arr.length && this.arr[temp] > this.arr[left]) {
temp = left;
}
if (right < this.arr.length && this.arr[temp] > this.arr[right]) {
temp = right
}
if (temp === cur) {
return;
}
this.swap(cur, temp)
cur =temp
}
}
getMin () {
return this.arr[0]
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
let myMinHeap = new MyMinHeap()
for(let i=0;i< k; i++) {
myMinHeap.add(nums[i])
}
// console.log(myMinHeap.arr)
for(let i=k;i< nums.length; i++) {
if(nums[i] > myMinHeap.getMin()) {
myMinHeap.add(nums[i])
// console.log(myMinHeap.arr)
myMinHeap.deleteMin()
// console.log(myMinHeap.arr)
}
// console.log(i,myMinHeap.arr)
}
// console.log(myMinHeap.arr)
return myMinHeap.getMin()
};
链表
LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put
- 非常经典： 链表，哈希，缓存逻辑设计
// 15: 15 - 15:38
// 15: 15 - 15:38
class DoubleLinkNode {
constructor (val, pre, next) {
this.val = val;
this.pre = pre || null;
this.next = next || null;
}
}
class DoubleLink {
constructor () {
this.head = new DoubleLinkNode();
this.tail = new DoubleLinkNode();
this.head.next = this.tail;
this.tail.pre = this.head;
}
addValueToHead (val) {
let newNode = new DoubleLinkNode(val);
let next = this.head.next;
this.head.next = newNode;
newNode.pre = this.head;
newNode.next = next;
next.pre = newNode;
return newNode;
}
deleteLastNode() {
if (this.tail.pre !== this.head) {
let node = this.tail.pre
let newLast = node.pre;
newLast.next = this.tail;
this.tail.pre = newLast;
return node;
}
return null;
}
deleteNode (node) {
if (node) {
let pre = node.pre;
let next = node.next;
pre.next =next;
next.pre = pre;
}
}
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity = capacity
this.doubleLink = new DoubleLink();
this.map = new Map();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (this.map.has(key)) {
let node = this.map.get(key)
let nodeVal = node.val.value;
// console.log('log', key, node)
this.doubleLink.deleteNode(node);
let newNode = this.doubleLink.addValueToHead({key, value: nodeVal});
this.map.set(key, newNode);
return nodeVal;
}
return -1
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if (this.map.has(key)) {
let node = this.map.get(key);
this.doubleLink.deleteNode(node);
this.map.delete(key);
}
if(this.map.size === this.capacity) {
let tailNode = this.doubleLink.deleteLastNode();
this.map.delete(tailNode.val.key)
}
let newNode = this.doubleLink.addValueToHead({key, value});
this.map.set(key, newNode);
// console.log('log', this.map.size, key, value, this.map)
};
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
class Node {
constructor(key = 0, value = 0) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.dummy = new Node(); // 哨兵节点
this.dummy.prev = this.dummy;
this.dummy.next = this.dummy;
this.keyToNode = new Map();
}
getNode(key) {
if (!this.keyToNode.has(key)) { // 没有这本书
return null;
}
const node = this.keyToNode.get(key); // 有这本书
this.remove(node); // 把这本书抽出来
this.pushFront(node); // 放在最上面
return node;
}
get(key) {
const node = this.getNode(key);
return node ? node.value : -1;
}
put(key, value) {
let node = this.getNode(key);
if (node) { // 有这本书
node.value = value; // 更新 value
return;
}
node = new Node(key, value) // 新书
this.keyToNode.set(key, node);
this.pushFront(node); // 放在最上面
if (this.keyToNode.size > this.capacity) { // 书太多了
const backNode = this.dummy.prev;
this.keyToNode.delete(backNode.key);
this.remove(backNode); // 去掉最后一本书
}
}
// 删除一个节点（抽出一本书）
remove(x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
// 在链表头添加一个节点（把一本书放在最上面）
pushFront(x) {
x.prev = this.dummy;
x.next = this.dummy.next;
x.prev.next = x;
x.next.prev = x;
}
}
作者：灵茶山艾府
链接：https://leetcode.cn/problems/lru-cache/solutions/2456294/tu-jie-yi-zhang-tu-miao-dong-lrupythonja-czgt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
哈希表
字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
// 14:58 - 15:04
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
const getSortedStr = (str)=> {
return str.split('').sort((a,b)=> a.charCodeAt() - b.charCodeAt()).join('')
}
// console.log('log', getSortedStr(strs[0]))
let map = new Map()
for(const str of strs) {
const key = getSortedStr(str)
if(map.has(key)) {
map.get(key).push(str)
} else {
map.set(key,[str])
}
}
let res= []
for(const [key, value] of map.entries()) {
res.push(value)
}
return res
};
树
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
// 16:43 - 16:52
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
const dfs = (node)=> {
if (!node || !p || !q) {
return null;
}
if (node == p || node == q) {
return node
}
const leftRes = dfs(node.left)
const rightRes = dfs(node.right)
if(leftRes && rightRes) {
return node
}
return leftRes || rightRes;
}
return dfs(root);
};
图
岛屿数量链接
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'
// 16: 27 ～ 16:40
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
if (grid.length < 0) {
return 0
}
let row = grid.length, col = grid[0]?.length;
const visited = new Array(row).fill(0).map(_=>new Array(col).fill(false));
let res = 0
const checkXY = (x, y) => {
if(x<0 || x>= row || y<0 || y>= col) {
return false
}
return true
}
const search = (x,y)=> {
if(!checkXY(x,y)) {
return;
}
visited[x][y] = true;
const diff = [
[-1, 0],
[1, 0],
[0, 1],
[0, -1]
]
for(const [diffX, diffY] of diff) {
if (checkXY(x+diffX, y+ diffY) && grid[x+diffX][y+diffY] === '1' && !visited[x+diffX][y+diffY]) {
search(x+diffX, y + diffY)
}
}
}
for(let i=0;i<row;i++) {
for(let j=0;j<col;j++) {
// console.log('log', res, i, j, visited[i][j])
if(grid[i][j] === "1" && !visited[i][j]) {
res++;
search(i, j)
}
}
}
return res;
};
分治
建立四叉树
给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
你需要返回能表示矩阵 grid 的 四叉树 的根结点。
四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：
val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
我们可以按以下步骤为二维区域构建四叉树：
如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。
如果你想了解更多关于四叉树的内容，可以参考 wiki 。
四叉树格式：
你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。
它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。
如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。
示例 1：
输入：grid = [[0,1],[1,0]]
输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释：此示例的解释如下：
请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。
示例 2：
输入：grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
解释：网格中的所有值都不相同。我们将网格划分为四个子网格。
topLeft，bottomLeft 和 bottomRight 均具有相同的值。
topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。
解释如下图所示：
提示：
n == grid.length == grid[i].length
n == 2x 其中 0 <= x <= 6
- solution1:
/**
* // Definition for a QuadTree node.
* function _Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight) {
* this.val = val;
* this.isLeaf = isLeaf;
* this.topLeft = topLeft;
* this.topRight = topRight;
* this.bottomLeft = bottomLeft;
* this.bottomRight = bottomRight;
* };
*/
function _Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight) {
this.val = val;
this.isLeaf = isLeaf;
this.topLeft = topLeft;
this.topRight = topRight;
this.bottomLeft = bottomLeft;
this.bottomRight = bottomRight;
};
/**
* @param {number[][]} grid
* @return {_Node}
*/
var construct = function(grid) {
const getSplit4Res = (arr)=> {
if(arr.length<=1) {
return arr;
}
let left=0, mid= arr[0].length/2, right =arr[0].length
let top=0, topMid = arr.length/2, bottom = arr.length
const getIndexArr = (x1,x2,y1,y2)=> {
let temp = []
for(let i=y1;i<y2;i++) {
let temp1 = []
for(let j=x1;j<x2;j++) {
temp1.push(arr[i][j])
}
temp.push(temp1)
}
return temp
}
return [
getIndexArr(0,mid, top, topMid),
getIndexArr(mid,right, top, topMid),
getIndexArr(0,mid, topMid, bottom),
getIndexArr(mid,right, topMid, bottom)
]
}
const getTree= (arr)=> {
if(arr.length == 0) {
return null
}
if(arr.length == 1) {
return new _Node(arr[0][0], 1)
}
// console.log("log", arr)
let root = new _Node(1, 0)
let childArr = getSplit4Res(arr)
root.topLeft = getTree(childArr[0])
root.topRight= getTree(childArr[1])
root.bottomLeft= getTree(childArr[2])
root.bottomRight= getTree(childArr[3])
// console.log("log1", getTree(grid))
return root
}
let tree = getTree(grid)
console.log("log", tree)
// 层次遍历 => arr
let res = []
// 层次遍历
return res
};
回溯
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
- soluton:
// 16:33 - 16:41
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
let numberMapArr = [
[],
[],
['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'i'],
['j', 'k', 'l'],
['m', 'n', 'o'],
['p', 'q', 'r', 's'],
['t', 'u', 'v'],
['w', 'x', 'y', 'z']
]
let res = []
const dfs=(index, currentStr)=> {
if (index === digits.length) {
if(currentStr) {
// console.log(currentStr)
res.push(currentStr)
}
return;
}
let charArr = numberMapArr[Number(digits[index])]
for(const i of charArr) {
dfs(index+1, currentStr + i)
}
}
dfs(0,'')
return res;
};
二分查找
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
// 14:10 - 14: 17
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
if(nums.length == 0 || target< nums[0] || target > nums[nums.length -1]) {
return [-1, -1]
}
const findLeftEqual = () => {
let mid;
let left=0, right= nums.length-1;
while(left< right) {
mid = Math.floor((left + right)/2)
if (target > nums[mid]) {
left = mid + 1;
} else if(target < nums[mid]) {
right = mid -1
} else {
// ==
right = mid
}
}
return nums[left] == target ? left : -1
}
const findRightEqual = () => {
let mid;
let left=0, right= nums.length-1;
while(left < right) {
mid = Math.ceil((left + right)/2)
if (target > nums[mid]) {
left = mid + 1;
} else if(target < nums[mid]) {
right = mid -1
} else {
// ==
left = mid
}
}
return nums[right] == target ? right : -1
}
return [findLeftEqual(), findRightEqual()]
};
多维动态规划
最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200
// 13: 26 ~ 13: 42
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function(grid) {
if (grid.length === 0) {
return -1
}
let row = grid.length, col = grid[0].length
let tempState = new Array(col).fill(0)
for(let i=0; i< row; i++) {
// console.log("log", i)
if (i == 0) {
for(let j=0;j< col; j++) {
if (j== 0) {
tempState[j] = grid[i][j]
} else {
tempState[j] = grid[i][j] + tempState[j-1]
}
}
} else {
let newTempState = new Array(col).fill(0);
for(let j=0;j< col;j++) {
// console.log("log", j, col)
if(j==0) {
newTempState[j] = tempState[j] + grid[i][j]
} else {
newTempState[j] = Math.min(tempState[j], newTempState[j-1]) + grid[i][j]
}
}
tempState = newTempState;
}
}
return tempState[col -1]
};