当前位置:网站首页>Prefix and array series
Prefix and array series
2022-07-06 06:51:00 【Wang Liuliu's it daily】
It involves three questions :
303. Area and retrieval - The array is immutable
304. Two dimensional region and retrieval - The matrix is immutable
560. And for K Subarray
If you want to get 「 Interval and 」, The easiest way to think of is to traverse the desired interval , Add circularly . If there are many such needs , here , The time complexity is O(n^2)
Based on the scenario described above , We can use it 「 The prefix and 」 Optimize , The prefix and the value of each element in the array are interval [0…i] Elements and .
Be careful :
Prefixes and apply to invariant arrays ; For changing arrays , have access to 「 Line segment tree 」, The detailed introduction of segment tree can be seen Line tree details
Area and retrieval - The array is immutable
Area and retrieval - The array is immutable
Details of the topic can be seen : Area and retrieval - The array is immutable
Suggest :preSum[] Overall backward offset by one bit , Simple handling
If we find the interval [2,4] And , Just calculate preSum[4 + 1] - preSum[2] that will do
Code :
class NumArray {
// Record an array of prefixes and
private int[] preSum;
public NumArray(int[] nums) {
// preSum from 1 Start , Avoid cross-border problems
preSum = new int[nums.length + 1];
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
}
public int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
}
Two dimensional region and retrieval - The matrix is immutable
Details of the topic can be seen : Two dimensional region and retrieval - The matrix is immutable
If you sum the red intervals , Demand only preSum[4,4] - preSum[1,4] - preSum[4,1] + preSum[1,1] that will do
● preSum[4,4]: yellow + blue + green + red
● preSum[1,4]: yellow + blue
● preSum[4,1]: yellow + green
● preSum[1,1]: yellow
Code :
class NumMatrix {
private int[][] preSum;
public NumMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
preSum = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
}
}
And for K Subarray
Details of the topic can be seen And for K Subarray
reference 「 Sum of two numbers 」 The idea of , utilize HashMap.
Code :
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> preSum = new HashMap<>();
preSum.put(0, 1);
int sum = 0;
int res = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
int target = sum - k;
if (preSum.containsKey(target)) res += preSum.get(target);
preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
}
return res;
}
边栏推荐
- 19.段页结合的实际内存管理
- Number of query fields
- 万丈高楼平地起,每个API皆根基
- Erreur de type résolue avec succès: type de données « catégorie» non sous - jacente
- UDP攻击是什么意思?UDP攻击防范措施
- How to reconstruct the class explosion caused by m*n strategies?
- Fedora/rehl installation semanage
- Day 246/300 SSH connection prompt "remote host identification has changed!"
- 电子书-CHM-上线CS
- ROS学习_基础
猜你喜欢
Lesson 7 tensorflow realizes convolutional neural network
雲上有AI,讓地球科學研究更省力
接口自动化测试实践指导(上):接口自动化需要做哪些准备工作
[unity] how to export FBX in untiy
Attributeerror: can 't get attribute' sppf 'on < module' models. Common 'from' / home / yolov5 / Models / comm
Chinese English comparison: you can do this Best of luck
Reflex WMS medium level series 3: display shipped replaceable groups
Is it difficult for girls to learn software testing? The threshold for entry is low, and learning is relatively simple
SAP SD发货流程中托盘的管理
SQL Server Manager studio (SSMS) installation tutorial
随机推荐
How to do a good job in financial literature translation?
Windows Server 2016 standard installing Oracle
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Day 248/300 关于毕业生如何找工作的思考
SSO process analysis
GET 和 POST 请求类型的区别
Map of mL: Based on the adult census income two classification prediction data set (whether the predicted annual income exceeds 50K), use the map value to realize the interpretable case of xgboost mod
成功解决TypeError: data type ‘category‘ not understood
AttributeError: Can‘t get attribute ‘SPPF‘ on <module ‘models. common‘ from ‘/home/yolov5/models/comm
简单描述 MySQL 中,索引,主键,唯一索引,联合索引 的区别,对数据库的性能有什么影响(从读写两方面)
SQL Server manager studio(SSMS)安装教程
《从0到1:CTFer成长之路》书籍配套题目(周更)
Data security -- 13 -- data security lifecycle management
Pymongo gets a list of data
[brush questions] how can we correctly meet the interview?
Erreur de type résolue avec succès: type de données « catégorie» non sous - jacente
Changes in the number of words in English papers translated into Chinese
CS passed (cdn+ certificate) PowerShell online detailed version
Day 246/300 ssh连接提示“REMOTE HOST IDENTIFICATION HAS CHANGED! ”
万丈高楼平地起,每个API皆根基