asp.net 网站管理系统,贵城乡建设官方网站,服务器上构建企业网站,购房网#x1f4d1;前言
本文主要是前缀和的文章#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ #x1f3ac;作者简介#xff1a;大家好#xff0c;我是青衿#x1f947; ☁️博客首页#xff1a;CSDN主页放风讲故事 #x1f304;每日一句#xff1a;努力一点…前言
本文主要是前缀和的文章如果有什么需要改进的地方还请大佬指出⛺️ 作者简介大家好我是青衿 ☁️博客首页CSDN主页放风讲故事 每日一句努力一点优秀一点 目录 文章目录 前言**目录**1. 统计范围内的元音字符串数2.二维区域和检索 - 矩阵不可变 文章末尾 1. 统计范围内的元音字符串数
leetcode2559 给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。
每个查询 queries[i] [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内包含 这两个值并且以元音开头和结尾的字符串的数目。
返回一个整数数组其中数组的第 i 个元素对应第 i 个查询的答案。
注意元音字母是 ‘a’、‘e’、‘i’、‘o’ 和 ‘u’ 。
示例 1 输入words [“aba”,“bcb”,“ece”,“aa”,“e”], queries [[0,2],[1,4],[1,1]] 输出[2,3,0] 解释以元音开头和结尾的字符串是 “aba”、“ece”、“aa” 和 “e” 。 查询 [0,2] 结果为 2字符串 “aba” 和 “ece”。 查询 [1,4] 结果为 3字符串 “ece”、“aa”、“e”。 查询 [1,1] 结果为 0 。 返回结果 [2,3,0] 。 示例 2 输入words [“a”,“e”,“i”], queries [[0,2],[0,1],[2,2]] 输出[3,2,1] 解释每个字符串都满足这一条件所以返回 [3,2,1] 。
提示 1 words.length 105 1 words[i].length 40 words[i] 仅由小写英文字母组成 sum(words[i].length) 3 * 105 1 queries.length 105 0 queries[j][0] queries[j][1] words.length 思路 1.初速化prefixSums[0]然后遍历求出prefixSum的值 2.求任意区间i到j的和,可以表示为prefixSum[j] -prefixSum[I -1]
代码如下
class Solution {public int[] vowelStrings(String[] words, int[][] queries) {int n words.length;int[] prefixSums new int[n];prefixSums[0] isVowelString(words[0]) ? 1 : 0;for (int i 1; i n; i) {int value isVowelString(words[i]) ? 1 : 0;prefixSums[i] prefixSums[i - 1] value;}int q queries.length;int[] ans new int[q];for (int i 0; i q; i) {int start queries[i][0], end queries[i][1];if(start 0) {ans[i] prefixSums[end];continue;}ans[i] prefixSums[end] - prefixSums[start - 1];}return ans;}public boolean isVowelString(String word) {return isVowelLetter(word.charAt(0)) isVowelLetter(word.charAt(word.length() - 1));}public boolean isVowelLetter(char c) {return c a || c e || c i || c o || c u;}
}2.二维区域和检索 - 矩阵不可变
leetcode304 给定一个二维矩阵 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 -105 matrix[i][j] 105 0 row1 row2 m 0 col1 col2 n 最多调用 104 次 sumRegion 方法 思路 1二维前缀和初始化preSum[0][0],以及第0行preSum[0][i]和第0列preSum[i][0] 2.从11开始遍历求出矩形的所有元素之和即 preSum[i][j] 左边前缀和上面前缀和-左上角前缀和 matrix[i][j]; 3.注意preSum[i][j]的定义以及左上角 (row1, col1) 、右下角 (row2, col2)
代码如下
public class NumMatrix {int[][] preSum;public NumMatrix(int[][] matrix) {int m matrix.length;if (m 0) {int n matrix[0].length;this.preSum new int[m][n];preSum[0][0] matrix[0][0];for (int i 1; i m; i) {preSum[i][0] preSum[i - 1][0] matrix[i][0];}for (int i 1; i n; i) {preSum[0][i] preSum[0][i - 1] matrix[0][i];}for (int i 1; i m; i) {for (int j 1; j n; j) {preSum[i][j] matrix[i][j] preSum[i - 1][j] preSum[i][j - 1] - preSum[i - 1][j - 1];}}}}public int sumRegion(int row1, int col1, int row2, int col2) {if (row1 0 col1 0) {return preSum[row2][col2];} else if (row1 0) {return preSum[row2][col2] - preSum[row2][col1-1];} else if (col1 0) {return preSum[row2][col2] - preSum[row1-1][col2];}return preSum[row2][col2] - preSum[row1-1][col2] - preSum[row2][col1-1] preSum[row1-1][col1-1];}
}文章末尾
