当前位置: 首页 > news >正文

中国工程监理人才网/武汉seo广告推广

中国工程监理人才网,武汉seo广告推广,sql2008做网站,网页美工设计论文简单 303. 区域和检索 - 数组不可变 给定一个整数数组 nums&#xff0c;处理以下类型的多个查询: 计算索引 left 和 right &#xff08;包含 left 和 right&#xff09;之间的 nums 元素的 和 &#xff0c;其中 left < right 实现 NumArray 类&#xff1a; NumArray(int[] …

简单

303. 区域和检索 - 数组不可变

给定一个整数数组 nums,处理以下类型的多个查询:

  1. 计算索引 leftright (包含 leftright)之间的 nums 元素的 ,其中 left <= right

实现 NumArray 类:

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 leftright 之间的元素的 总和 ,包含 leftright 两点(也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1:

输入:
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出:
[null, 1, -1, -3]解释:
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示:

  • 1 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • 0 <= i <= j < nums.length
  • 最多调用 10^4sumRange 方法
class NumArray {
public:int n; // nums.lengthvector<int> dp;NumArray(vector<int>& nums) : n(nums.size()), dp(n + 1) {for (int i = 1; i <= n; ++i)dp[i] = dp[i - 1] + nums[i - 1];}int sumRange(int left, int right) {return dp[right + 1] - dp[left];}
};

724. 寻找数组的中心下标

1991. 找到数组的中间位置

这两题相同。

给你一个整数数组 nums ,请计算数组的 中心下标

数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1

示例 1:

输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。

示例 2:

输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。

示例 3:

输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0 。
左侧数之和 sum = 0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示:

  • 1 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000
int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> dp(n + 1);for (int i = 1; i <= n; ++i)dp[i] = dp[i - 1] + nums[i - 1];for (int i = 0; i < n; ++i)if (dp[i] == dp[n] - dp[i + 1])return i;return -1;
}

可以优化空间复杂度,根据2 * sum + nums[i] == total

int pivotIndex(vector<int>& nums) {int total = accumulate(nums.begin(), nums.end(), 0);int sum = 0;for (int i = 0; i < nums.size(); ++i) {if (2 * sum + nums[i] == total)return i;sum += nums[i];}return -1;
}

中等

238. 除自身以外数组的乘积

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法,**且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示:

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

**进阶:**你可以在 O(1) 的额外空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组 不被视为 额外空间。)

与这题724. 寻找数组的中心下标类似。分别构建从前往后的乘积数组dp1,以及从后往前的乘积数组dp2,再初始化ans数组即可。

vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> dp1(n + 1);dp1[0] = 1;for (int i = 1; i <= n; ++i)dp1[i] = dp1[i - 1] * nums[i - 1];vector<int> dp2(n + 2);dp2[n + 1] = 1;for (int j = n; j > 0; --j)dp2[j] = dp2[j + 1] * nums[j - 1];vector<int> ans(n);for (int i = 0; i < n; ++i)ans[i] = dp1[i] * dp2[i + 2];return ans;
}

在此基础上还可以优化空间复杂度,先用ans作为从前往后的乘积数组dp1,sum作为从后往前的乘积和,再从后往前更新ans。

vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> ans(n);ans[0] = 1;for (int i = 1; i < n; ++i)ans[i] = ans[i - 1] * nums[i - 1];int sum = 1;for (int i = n - 1; i >= 0; --i) {ans[i] *= sum;sum *= nums[i];}return ans;
}

304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix,以下类型的多个请求:

  • 计算其子矩形范围内元素的总和,该子矩阵的 左上角(row1, col1)右下角(row2, col2)

实现 NumMatrix 类:

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1)右下角 (row2, col2) 所描述的子矩阵的元素 总和

示例 1:

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -10^5 <= matrix[i][j] <= 10^5
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • 最多调用 10^4sumRegion 方法

前缀和数组存储的是矩形左上角到以martix[i][j]为右下角的矩形和。

构建二维前缀和数组时,dp[i][j] = matrix[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1],既当前元素的值 + 上面的矩形 + 下面的矩形 - 左上矩形(相加后重复的部分);

矩形值的和等于dp[x1 - 1][y1 - 1] + dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2],既以x2, y2为右下角的矩形 + x1-1, y1-1为右下角的矩形(相减后减多的部分)- x1-1, y2为右下角的矩形 - x2, y1 - 1为右下角的矩形;

class NumMatrix {
public:int m; // matrix.lengthint n; // matrix[i].lengthvector<vector<int>> dp;NumMatrix(vector<vector<int>>& matrix) : m(matrix.size()), n(matrix[0].size()),dp(m + 1, vector<int>(n + 1)) {for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {dp[i][j] = matrix[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];}}}int sumRegion(int row1, int col1, int row2, int col2) {return dp[row1][col1] + dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1];}
};

525. 连续数组

给定一个二进制数组 nums , 找到含有相同数量的 01 的最长连续子数组,并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示:

  • 1 <= nums.length <= 10^5
  • nums[i] 不是 0 就是 1

把0看作-1,求和为0的区间。当之前的前缀和 - sum(当前缀和)== 0,既之前的前缀和 == sum(当前缀和)时,计算ans并取最大值。

int findMaxLength(vector<int>& nums) {int sum = 0, ans = 0;unordered_map<int, int> hash;hash[0] = -1; // 前缀和为0,默认下标-1for (int i = 0; i < nums.size(); ++i) {sum += (nums[i] == 0 ? -1 : 1);if (hash.count(sum))ans = max(ans, i - hash[sum]);elsehash[sum] = i;}return ans;
}

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数

子数组是数组中元素的连续非空序列。

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

提示:

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

每有一个前缀和为sum - k,就会有一个和为k的子数组。因为**之前的前缀和 + k == sum(当前缀和)**时,在当前区间与之前的前缀和区间中,存在一个区间和为k

int subarraySum(vector<int>& nums, int k) {int ans = 0, sum = 0;unordered_map<int, int> hash;hash[0] = 1;for (int i = 0; i < nums.size(); ++i) {sum += nums[i];if (hash.count(sum - k))ans += hash[sum - k];hash[sum]++;}return ans;
}

974. 和可被 K 整除的子数组

给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的非空 子数组 的数目。

子数组 是数组中 连续 的部分。

示例 1:

输入:nums = [4,5,0,-2,-3,1], k = 5
输出:7
解释:
有 7 个子数组满足其元素之和可被 k = 5 整除:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • 2 <= k <= 10^4

与这题类似560. 和为 K 的子数组。sum(当前缀和)- 之前的前缀和) % k == 0时,区间可被k整除,所以与之前的前缀和 % ksum % k相等时,区间也可被k整除。

int subarraysDivByK(vector<int>& nums, int k) {int ans = 0, sum = 0;unordered_map<int, int> hash;hash[0] = 1;for (int i = 0; i < nums.size(); ++i) {sum += nums[i];// 负数取模纠正int mod = (sum % k + k) % k;if (hash.count(mod))ans += hash[mod];hash[mod]++;}return ans;
}

1314. 矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和:

  • i - k <= r <= i + k,
  • j - k <= c <= j + k
  • (r, c) 在矩阵内。

示例 1:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出:[[12,21,16],[27,45,33],[24,39,28]]

示例 2:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出:[[45,45,45],[45,45,45],[45,45,45]]

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, k <= 100
  • 1 <= mat[i][j] <= 100

利用二维前缀和304. 二维区域和检索 - 矩阵不可变,求矩阵的左上和右下端点来求矩阵和即可。

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int i = 1; i <= m; ++i)for (int j = 1; j <= n; ++j)dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];vector<vector<int>> ans(m, vector<int>(n));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {int x1 = max(i - k, 0) + 1, x2 = min(i + k, m - 1) + 1;int y1 = max(j - k, 0) + 1, y2 = min(j + k, n - 1) + 1;ans[i][j] = dp[x2][y2] + dp[x1 - 1][y1 - 1] - dp[x1 - 1][y2] - dp[x2][y1 - 1];}}return ans;
}
http://www.whsansanxincailiao.cn/news/32029860.html

相关文章:

  • wordpress hack 主题/seo综合查询网站
  • wordpress配置多语言/关键词搜索排名优化
  • 优客逸家网站源码/黑龙江新闻
  • 描述网站建设的基本流程/seo服务方案
  • wordpress 文件上传功能/百度seo排名优化价格
  • 沥林行业网站建设/百度统计工具
  • 工信委网站建设方案/电商运营方案计划书
  • 网站建设 你真的懂吗/知名网络营销推广
  • 国内最大的网站建设公司排名/制作网站的平台
  • 广州大型网站制作公司/seo的工作流程
  • 珠海手机网站开发/年轻人不要做网络销售
  • wordpress加音乐/廊坊seo排名外包
  • 网站插入代码js插件/百度指数怎么查询
  • 做百家好还是个人网站/广告主广告商对接平台
  • 手机网站展示/网络站点推广的方法
  • 百度网站优化软件/公司的公关
  • 香港美女做旅游视频网站/佛山网站建设解决方案
  • 做时时彩网站代理费用/百家号seo
  • h5网站需要哪些技术/职业培训机构管理系统
  • 外包网站建设费用包括网站备份/友情链接教程
  • 京东的网络营销方式/高州网站seo
  • 沈阳做网站哪家质量好价格低/南京百度关键字优化价格
  • 衡水商城网站制作/西安 做网站
  • 网站正能量大全/河南平价的seo整站优化定制
  • 企业网站建设一般包含哪些内容/seo中文全称是什么
  • 南充网站建设天赐/代发关键词排名包收录
  • 全国感染的最新数据统计/seo排名快速刷
  • 软件介绍网站模板/千博企业网站管理系统
  • 东莞市建设网站首页/广州专门做seo的公司
  • 海淀周边网站建设/厦门seo培训学校