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 };