leetcode刷题记录(22)-中等
1.二维区域和检索
题目:
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2)。
上图子矩阵左上角 (row1, col1) = (2, 1) ,右下角(row2, col2) = (4, 3),该子矩形内元素的总和为 8。
思路:对于点(i,j)来说,缓存从(0,0)到(i,j)范围内的和,这样对于范围(row1,col1)-(row2,col2),范围内的元素和就等于cache(row2,col2)-cache(row1-2,col2)-cache(row2,col1-1)+cache(row1-1,col1-1)
时间复杂度:O(m*n),空间复杂度O(m*n)
/**
* @param {number[][]} matrix
*/
var NumMatrix = function(matrix) {
this.matrix = matrix;
this.cache = new Map();
};
/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @return {number}
*/
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
return (
this.getCache(row2, col2) -
this.getCache(row1 - 1, col2) -
this.getCache(row2, col1 - 1) +
this.getCache(row1 - 1, col1 - 1)
);
};
NumMatrix.prototype.getCache = function (row1, col1) {
if (row1 < 0 || col1 < 0) return 0;
if (this.cache.get(`${row1}-${col1}`)) {
return this.cache.get(`${row1}-${col1}`);
}
let count = 0;
for (let i = 0; i <= row1; i++) {
for (let j = 0; j <= col1; j++) {
count += this.matrix[i][j];
}
}
this.cache.set(`${row1}-${col1}`, count);
return count;
};
2.累加数
题目:
累加数是一个字符串,组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 '0'-'9'
的字符串,编写一个算法来判断给定输入是否是累加数。
说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03
或者 1, 02, 3
的情况
思路:回溯法。每次从开头开始截取,长度为1开始,判断前两个数和第三个数是否为累加,如果不是进入下一次截取
时间复杂度O(n2),空间复杂度O(n)
/**
* @param {string} num
* @return {boolean}
*/
var isAdditiveNumber = function(num) {
let result = false
for (let j = 1; j < num.length - 1; j++) {
if (num[0] === '0' && j > 1) {
break
}
for (let k = j + 1; k < num.length; k++) {
if (num[j] === '0' && k - j > 1) {
break
}
let num1 = Number(num.substring(0, j)), num2 = Number(num.substring(j, k))
next(num1, num2, k)
if (result) {
return result
}
}
}
function next(num1, num2, index) {
for (let i = index + 1; i <= num.length; i++) {
if (num[index] === '0' && i - index > 1) {
break
}
let num3 = Number(num.substring(index, i))
if (num1 + num2 === num3) {
if (i === num.length) {
result = true
return
}
if (num[i] === '0') {
continue
}
next(num2, num3, i)
}
}
}
return result
3.区域和检索-数组可修改
题目:
给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。
思路:缓存从0到i的结果,每次update(i),将大于等于i的缓存结果更新
时间复杂度:O(n),空间复杂度O(n)
/**
* @param {number[]} nums
*/
var NumArray = function (nums) {
const l = nums.length;
this.cache = new Array(l + 1);
this.cache[0] = 0;
for (let i = 1; i <= l; i++) {
this.cache[i] = this.cache[i - 1] + nums[i - 1];
}
this.nums = nums;
};
/**
* @param {number} i
* @param {number} val
* @return {void}
*/
NumArray.prototype.update = function (i, val) {
for (let j = i+1; j <= this.nums.length; j++) {
this.cache[j] = this.cache[j] - this.nums[i] + val;
}
this.nums[i] = val;
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function (i, j) {
return this.cache[j + 1] - this.cache[i];
};
4.最佳买卖股票时机含冷冻期
题目:
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
- 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
思路:直觉就是动态规划。对于第i天,有两种可能:持有股票,没有持有股票。所以可以用两个数组记录第i天持有和不持有股票时的收益。
持有股票时,收益=i-1天不持有股票 的收益 - 第i天的价格
不持有股票时,收益是 第i-1天持有股票的收益+第i天的价格,和第i-1天不持有股票收益,两者间的的最大值
时间复杂度:O(n),空间复杂度O(n)
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
const n = prices.length; // n天
if (n == 0) return 0
let hold = new Array(n); // 第i天持有股票的最大收益
let unhold = new Array(n); // 第i天不持有股票的最大收益
hold[0] = -prices[0]; // 第0天 买了股票的收益
unhold[0] = 0
for (let i = 1; i < n; i++) {
if (i == 1) { // base case
hold[i] = Math.max(hold[i - 1], -prices[1]);
} else {
hold[i] = Math.max(hold[i - 1], unhold[i - 2] - prices[i]);
}
unhold[i] = Math.max(unhold[i - 1], hold[i - 1] + prices[i]);
}
return unhold[n - 1];
};
5.最小高度树
题目:
对于一个具有树特征的无向图,我们可选择任何一个节点作为根。图因此可以成为树,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样的一个图,写出一个函数找到所有的最小高度树并返回他们的根节点。
格式
该图包含 n
个节点,标记为 0
到 n - 1
。给定数字 n
和一个无向边 edges
列表(每一个边都是一对标签)。
你可以假设没有重复的边会出现在 edges
中。由于所有的边都是无向边, [0, 1]
和 [1, 0]
是相同的,因此不会同时出现在 edges
里。
/**
* @param {number} n
* @param {number[][]} edges
* @return {number[]}
*/
var findMinHeightTrees = function(n, edges) {
if (n === 1 || edges.length === 0) return [0];
let root, len = edges.length, inDegs = new Array(n);
do {
// update length of edges
edges.length = len;
inDegs.fill(0);
for (let edge of edges) {
inDegs[edge[0]]++;
inDegs[edge[1]]++;
}
len = 0;
for (let edge of edges) {
// overwrite the value of edges if none of the edge's nodes is leaf
if (inDegs[edge[0]] > 1 && inDegs[edge[1]] > 1) edges[len++] = edge;
else if (inDegs[edge[0]] > 1) root = edge[0];
else if (inDegs[edge[1]] > 1) root = edge[1];
}
} while (len) // when len is 0, the edges hold the previous values
if (edges.length === 1) return edges[0]; // case 1
return [root]; // case 2
};
推荐阅读
-
leetcode刷题记录(22)-中等
-
Leetcode刷题记录——面试题 01.05. 一次编辑
-
Leetcode刷题记录——面试题 01.01. 判定字符是否唯一
-
Leetcode刷题记录——面试题 02.02. 返回倒数第 k 个节点
-
LeetCode刷题记录——面试题 02.02. 返回倒数第 k 个节点
-
Leetcode刷题记录——面试题 01.04. 回文排列
-
Leetcode刷题之旅--面试题 01.02. 判定是否互为字符重排
-
Leetcode刷题记录——面试题 01.02. 判定是否互为字符重排
-
leetcode刷题【简单】合并两个有序链表 c++
-
2021暑假Leetcode刷题——Two Pointers(2)