数组操作：HackerRank 问题：JAVA
Array Manipulation : HackerRank Questions : JAVA
我正在做这个来自 hackerrank 的数组操作问题，它告诉我编译错误是由于超时而终止。
对于小型阵列，我的方法非常有效。 只有较大的数组值才会出现此错误。
这里是问题link。 Question Here
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.
For example, the length of your array of zeros . Your list of queries is as follows:
a b k
1 5 3
4 8 7
6 9 1
Add the values of between the indices and inclusive:
index -> 1 2 3 4 5 6 7 8 9 10
[0,0,0, 0, 0,0,0,0,0, 0]
[3,3,3, 3, 3,0,0,0,0, 0]
[3,3,3,10,10,7,7,7,0, 0]
[3,3,3,10,10,8,8,8,1, 0]
The largest value is after all operations are performed.
下面是我的方法。
static long arrayManipulation(int n, int[][] queries) {
long max = 0L;
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = 0L;
}
for (int i = 0; i < queries.length; i++) {
int[] q = queries[i];
int start = q[0] - 1;
int end = q[1] - 1;
int val = q[2];
long tempMax = updateVal(start, end, val, arr);
if (tempMax > max) {
max = tempMax;
}
}
return max;
}
static long updateVal(int start, int end, int val, long[] arr) {
long max = 0L;
for (int i = start; i <= end; i++) {
arr[i] = arr[i] + val;
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
下面给出的一些测试 类 不适用于我的代码。
Test1 Test2 Test3
请帮我解决这个问题。我根据 java 搜索了很多答案。
但我无法理解他们。
这是我最后的手段。请帮忙。
Kanahaiya 回答后更新
static long arrayManipulation(int n, int[][] queries) {
long max = 0L;
int a, b, k;
int[] arr = new int[n + 2];
for (int i = 0; i < queries.length; i++) {
a = queries[i][0];
b = queries[i][1];
k = queries[i][2];
for (int j = 0; j < arr.length; j++) {
if (j >= a) {
arr[j] = arr[j] + k;
}
if (j > b) {
arr[j] = arr[j] - k;
}
}
}
Arrays.sort(arr);
max = arr[arr.length - 1];
return max;
}
首先，万一你没意识到，Terminated due to timeout不是编译错误，而是你执行的太慢了。挑战不是对问题实施任何正确的解决方案。该解决方案还必须高效。由于您的解决方案效率低下，因此由于太慢而无法处理大量输入。
由于查询的数量似乎比数组的长度小 2 个数量级（在您发布的 3 个测试用例中为 100K 对 10M），仅使用查询会更有效率实际更新数组。
我不会给你一个实现，但我会建议一个比你当前的实现更有效的算法。
我建议您按如下方式处理查询：
将第一个查询添加到已处理查询列表中，该列表将包含具有不相交 sub-array 范围的查询。此列表将按第一个数组索引排序（您将通过在适当位置添加新元素来保持排序）。
对于每个尚未处理的查询，找到与其重叠的所有已处理查询（您可以使用二进制搜索来提高性能）。
拆分当前查询，使每个生成的查询都完全包含在现有的已处理查询中，或者不包含在每个现有的已处理查询中。
对于拆分中创建的每个查询：
- 如果它们的范围等于现有已处理查询的范围，则将该查询的值添加到已处理查询中。
- 如果它们的范围不包含在任何现有的已处理查询中，请将该查询添加为新的已处理查询。
- 如果它们的范围部分包含在现有的已处理查询中，则拆分已处理的查询。
我不确定我的解释是否足够清楚。我将用
展示一个例子
1 5 3
4 8 7
6 9 1
输入：
将 1 5 3 添加到已处理的查询列表中。
进程 4 8 7：有一个已处理的查询与其重叠 - 1 5 3。
将 4 8 7 分成两个 sub-queries : 4 5 7 和 6 8 7.
4 5 7 包含在 1 5 3 中，所以将 1 5 3 拆分为 1 3 3 和 4 5 3+7
6 8 7 未包含在任何已处理的查询中，因此请按原样添加。
现在处理的查询是：
1 3 3
4 5 10
6 8 7
处理6 9 1：有一个处理过的查询与其重叠：6 8 7。
将 6 9 1 拆分为两个子查询：6 8 1 和 9 9 1。
6 8 1 与 6 8 7 的范围相同，将变为 6 8 7+1
9 9 1 未包含在任何已处理的查询中，因此请按原样添加。
现在处理的查询是：
1 3 3
4 5 10
6 8 8
9 9 1
在处理查询时，您会跟踪最大处理查询值，因此在处理完所有查询后，您知道最大值为 10。
由于给定的时间限制，Brute-force 解决方案在这里不起作用。
这就是您会收到超时错误的原因。
所以你需要优化你的代码，这可以在前缀和数组的帮助下完成。
不是将数组中a到b范围内的所有元素都加k，而是累加差数组
每当我们在数组的任何索引处添加任何内容并应用前缀和算法时，相同的元素将被添加到每个元素，直到数组的末尾。
ex- n=5, m=1, a=2 b=5 k=5
i 0.....1.....2.....3.....4.....5.....6 //take array of size N+2 to avoid index out of bound
A[i] 0 0 0 0 0 0 0
将 k=5 添加到 a=2
A[a]=A[a]+k // 从应该添加 k 元素的位置开始索引
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 0 5 0 0 0 0
现在应用前缀和算法
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 0 5 5 5 5 5
所以你可以看到在应用前缀和之后，K=5 添加到所有元素直到最后，但我们不必将 k 添加到最后。所以为了抵消这种影响，我们还必须在 b+1 索引之后添加 -K 这样只有来自 [a,b] 范围才会有 K 元素添加效果。
A[b+1]=A[b]-k // 去除先前在 bth 索引后添加的 k 元素的影响。
这就是为什么在初始数组中添加 -k 和 +k 的原因。
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 0 5 0 0 0 -5
现在应用前缀和数组
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 0 5 5 5 5 0
您现在可以看到，K=5 已从 a=2 添加到 b=5，这是预期的。
这里我们只为每个查询更新两个索引，因此复杂度为 O(1)。
现在在输入中应用相同的算法
# 0.....1.....2.....3.....4.....5.....6 //taken array of size N+2 to avoid index out of bound
5 3 # 0 0 0 0 0 0 0
1 2 100 # 0 100 0 -100 0 0 0
2 5 100 # 0 100 100 -100 0 0 -100
3 4 100 # 0 100 100 0 0 -100 -100
要计算最大前缀和，将差数组累加到，同时取最大累加前缀。
执行所有操作后现在应用前缀和数组
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 100 200 200 200 100 0
现在你可以遍历这个数组找到最大值200。
遍历数组将花费 O(N) 时间并且为每个查询更新两个索引将花费 O(1)* 查询数(m)
整体复杂度=O(N)+O(M)
= O(N+M)
表示 = (10^7+10^5) 小于 10^8（每秒）
注：如果搜索video tutorial , you must check it out here有详细说明
import java.io.*;
import java.util.InputMismatchException;
import java.util.Random;
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
InputReader in = new InputReader(inputStream);
int n = in.readInt();
int m = in.readInt();
long[] list = new long[n+3];
while(m-- > 0) {
int a = in.readInt();
int b = in.readInt();
long k = in.readLong();
list[a] += k;
list[b+1] -= k;
}
long max = 0;
long c = 0;
for (int i = 1; i <= n; i++) {
c += list[i];
max = Math.max(max, c);
}
System.out.println(max);
}
}
class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int peek() {
if (numChars == -1)
return -1;
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
return -1;
}
if (numChars <= 0)
return -1;
}
return buf[curChar];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long readLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public boolean isExhausted() {
int value;
while (isSpaceChar(value = peek()) && value != -1)
read();
return value == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
java 中数组操作 hackerrank 的解决方案 ...
代码没有通过所有情况因为超时需要建议改进
static long arrayManipulation(int n, int[][] queries) {
ArrayList<Long> list = new ArrayList<Long>(n);
for(int i=0; i<n; i++){
list.add(i,0l);
}
for(int i=0; i<queries.length; i++){
int s = queries[i][0];
int e = queries[i][1];
long k = queries[i][2];
int size = 0;
for(int j = s - 1; j<e; j++){
list.set(j, list.get(j) + k);
}
}
long max =Collections.max(list);
return max;
}
针对此问题实施了 Java 中的解决方案并有效地工作。有需要的可以试试
public long arrayManipulation(int n, int[][] queries)
{
if(n==0 || queries==null || queries.length==0){
return -1;
}
long[] computation = new long[n];
for (int i = 0; i < queries.length; i++) {
int a = queries[i][0] - 1;
int b = queries[i][1] - 1;
int k = queries[i][2];
computation[a] += k;
if (b + 1 < n ) {
computation[b + 1] -= k;
}
}
long max = 0; long sum = 0;
for (int i = 0; i < n; i++) {
sum += computation[i];
max = Math.max(max, sum);
}
return max;
}
static long arrayManipulation(int n, int[][] queries)
{
// To Avoid "Index was outside the bounds of the array." exception
long[] numbers = new long[n + 1];
for(int i = 0; i < queries.length; i++)
{
int a = queries[i][0] - 1;
int b = queries[i][1];
int k = queries[i][2];
numbers[a] += k;
numbers[b] -= k;
}
// Calculate sum(s)
int max=0;
for(int i = 1; i < numbers.length; i++)
{
numbers[i] += numbers[i - 1];
if(numbers[i]>max)
{
max=numbers[i];
}
}
return max;
}
package arrayProblems;
import java.util.ArrayList;
import java.util.List;
import static java.util.Arrays.*;
public class ArrayManipuations {
public static void main(String[] args) {
int n=10;
int[] arr = new int[n];
List<List<Integer>> nl = new ArrayList<List<Integer>>();
nl=asList(asList(1,5,3),asList(4,8,7),asList(6,9,1));
for(int i=0;i<nl.size();i++) {
for(int j=nl.get(i).get(0);j<=nl.get(i).get(1);j++) {
arr[j-1]=arr[j-1]+nl.get(i).get(2);
}
}
int max = Integer.MIN_VALUE;
for(int k=0;k<n;k++) {
if(max<arr[k]) {
max = arr[k];
arr[k]=max;
}
}
System.out.print(max);
}
}
我正在做这个来自 hackerrank 的数组操作问题，它告诉我编译错误是由于超时而终止。
对于小型阵列，我的方法非常有效。 只有较大的数组值才会出现此错误。
这里是问题link。 Question Here
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.
For example, the length of your array of zeros . Your list of queries is as follows:
a b k 1 5 3 4 8 7 6 9 1Add the values of between the indices and inclusive:
index -> 1 2 3 4 5 6 7 8 9 10 [0,0,0, 0, 0,0,0,0,0, 0] [3,3,3, 3, 3,0,0,0,0, 0] [3,3,3,10,10,7,7,7,0, 0] [3,3,3,10,10,8,8,8,1, 0]The largest value is after all operations are performed.
下面是我的方法。
static long arrayManipulation(int n, int[][] queries) {
long max = 0L;
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = 0L;
}
for (int i = 0; i < queries.length; i++) {
int[] q = queries[i];
int start = q[0] - 1;
int end = q[1] - 1;
int val = q[2];
long tempMax = updateVal(start, end, val, arr);
if (tempMax > max) {
max = tempMax;
}
}
return max;
}
static long updateVal(int start, int end, int val, long[] arr) {
long max = 0L;
for (int i = start; i <= end; i++) {
arr[i] = arr[i] + val;
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
下面给出的一些测试 类 不适用于我的代码。
Test1 Test2 Test3
请帮我解决这个问题。我根据 java 搜索了很多答案。
但我无法理解他们。
这是我最后的手段。请帮忙。
Kanahaiya 回答后更新
static long arrayManipulation(int n, int[][] queries) {
long max = 0L;
int a, b, k;
int[] arr = new int[n + 2];
for (int i = 0; i < queries.length; i++) {
a = queries[i][0];
b = queries[i][1];
k = queries[i][2];
for (int j = 0; j < arr.length; j++) {
if (j >= a) {
arr[j] = arr[j] + k;
}
if (j > b) {
arr[j] = arr[j] - k;
}
}
}
Arrays.sort(arr);
max = arr[arr.length - 1];
return max;
}
首先，万一你没意识到，Terminated due to timeout不是编译错误，而是你执行的太慢了。挑战不是对问题实施任何正确的解决方案。该解决方案还必须高效。由于您的解决方案效率低下，因此由于太慢而无法处理大量输入。
由于查询的数量似乎比数组的长度小 2 个数量级（在您发布的 3 个测试用例中为 100K 对 10M），仅使用查询会更有效率实际更新数组。
我不会给你一个实现，但我会建议一个比你当前的实现更有效的算法。
我建议您按如下方式处理查询：
将第一个查询添加到已处理查询列表中，该列表将包含具有不相交 sub-array 范围的查询。此列表将按第一个数组索引排序（您将通过在适当位置添加新元素来保持排序）。
对于每个尚未处理的查询，找到与其重叠的所有已处理查询（您可以使用二进制搜索来提高性能）。
拆分当前查询，使每个生成的查询都完全包含在现有的已处理查询中，或者不包含在每个现有的已处理查询中。
对于拆分中创建的每个查询：
- 如果它们的范围等于现有已处理查询的范围，则将该查询的值添加到已处理查询中。
- 如果它们的范围不包含在任何现有的已处理查询中，请将该查询添加为新的已处理查询。
- 如果它们的范围部分包含在现有的已处理查询中，则拆分已处理的查询。
我不确定我的解释是否足够清楚。我将用
展示一个例子1 5 3
4 8 7
6 9 1
输入：
将 1 5 3 添加到已处理的查询列表中。
进程 4 8 7：有一个已处理的查询与其重叠 - 1 5 3。
将 4 8 7 分成两个 sub-queries : 4 5 7 和 6 8 7.
4 5 7 包含在 1 5 3 中，所以将 1 5 3 拆分为 1 3 3 和 4 5 3+7
6 8 7 未包含在任何已处理的查询中，因此请按原样添加。
现在处理的查询是：
1 3 3
4 5 10
6 8 7
处理6 9 1：有一个处理过的查询与其重叠：6 8 7。
将 6 9 1 拆分为两个子查询：6 8 1 和 9 9 1。
6 8 1 与 6 8 7 的范围相同，将变为 6 8 7+1
9 9 1 未包含在任何已处理的查询中，因此请按原样添加。
现在处理的查询是：
1 3 3
4 5 10
6 8 8
9 9 1
在处理查询时，您会跟踪最大处理查询值，因此在处理完所有查询后，您知道最大值为 10。
Brute-force 解决方案在这里不起作用。 这就是您会收到超时错误的原因。
所以你需要优化你的代码，这可以在前缀和数组的帮助下完成。
不是将数组中a到b范围内的所有元素都加k，而是累加差数组
每当我们在数组的任何索引处添加任何内容并应用前缀和算法时，相同的元素将被添加到每个元素，直到数组的末尾。
ex- n=5, m=1, a=2 b=5 k=5
i 0.....1.....2.....3.....4.....5.....6 //take array of size N+2 to avoid index out of bound
A[i] 0 0 0 0 0 0 0
将 k=5 添加到 a=2
A[a]=A[a]+k // 从应该添加 k 元素的位置开始索引
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 0 5 0 0 0 0
现在应用前缀和算法
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 0 5 5 5 5 5
所以你可以看到在应用前缀和之后，K=5 添加到所有元素直到最后，但我们不必将 k 添加到最后。所以为了抵消这种影响，我们还必须在 b+1 索引之后添加 -K 这样只有来自 [a,b] 范围才会有 K 元素添加效果。
A[b+1]=A[b]-k // 去除先前在 bth 索引后添加的 k 元素的影响。 这就是为什么在初始数组中添加 -k 和 +k 的原因。
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 0 5 0 0 0 -5
现在应用前缀和数组
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 0 5 5 5 5 0
您现在可以看到，K=5 已从 a=2 添加到 b=5，这是预期的。 这里我们只为每个查询更新两个索引，因此复杂度为 O(1)。
现在在输入中应用相同的算法
# 0.....1.....2.....3.....4.....5.....6 //taken array of size N+2 to avoid index out of bound
5 3 # 0 0 0 0 0 0 0
1 2 100 # 0 100 0 -100 0 0 0
2 5 100 # 0 100 100 -100 0 0 -100
3 4 100 # 0 100 100 0 0 -100 -100
要计算最大前缀和，将差数组累加到，同时取最大累加前缀。
执行所有操作后现在应用前缀和数组
i 0.....1.....2.....3.....4.....5.....6
A[i] 0 100 200 200 200 100 0
现在你可以遍历这个数组找到最大值200。 遍历数组将花费 O(N) 时间并且为每个查询更新两个索引将花费 O(1)* 查询数(m)
整体复杂度=O(N)+O(M) = O(N+M)
表示 = (10^7+10^5) 小于 10^8（每秒）
注：如果搜索video tutorial , you must check it out here有详细说明
import java.io.*;
import java.util.InputMismatchException;
import java.util.Random;
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
InputReader in = new InputReader(inputStream);
int n = in.readInt();
int m = in.readInt();
long[] list = new long[n+3];
while(m-- > 0) {
int a = in.readInt();
int b = in.readInt();
long k = in.readLong();
list[a] += k;
list[b+1] -= k;
}
long max = 0;
long c = 0;
for (int i = 1; i <= n; i++) {
c += list[i];
max = Math.max(max, c);
}
System.out.println(max);
}
}
class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int peek() {
if (numChars == -1)
return -1;
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
return -1;
}
if (numChars <= 0)
return -1;
}
return buf[curChar];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long readLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public boolean isExhausted() {
int value;
while (isSpaceChar(value = peek()) && value != -1)
read();
return value == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
java 中数组操作 hackerrank 的解决方案 ... 代码没有通过所有情况因为超时需要建议改进
static long arrayManipulation(int n, int[][] queries) {
ArrayList<Long> list = new ArrayList<Long>(n);
for(int i=0; i<n; i++){
list.add(i,0l);
}
for(int i=0; i<queries.length; i++){
int s = queries[i][0];
int e = queries[i][1];
long k = queries[i][2];
int size = 0;
for(int j = s - 1; j<e; j++){
list.set(j, list.get(j) + k);
}
}
long max =Collections.max(list);
return max;
}
针对此问题实施了 Java 中的解决方案并有效地工作。有需要的可以试试
public long arrayManipulation(int n, int[][] queries)
{
if(n==0 || queries==null || queries.length==0){
return -1;
}
long[] computation = new long[n];
for (int i = 0; i < queries.length; i++) {
int a = queries[i][0] - 1;
int b = queries[i][1] - 1;
int k = queries[i][2];
computation[a] += k;
if (b + 1 < n ) {
computation[b + 1] -= k;
}
}
long max = 0; long sum = 0;
for (int i = 0; i < n; i++) {
sum += computation[i];
max = Math.max(max, sum);
}
return max;
}
static long arrayManipulation(int n, int[][] queries)
{
// To Avoid "Index was outside the bounds of the array." exception
long[] numbers = new long[n + 1];
for(int i = 0; i < queries.length; i++)
{
int a = queries[i][0] - 1;
int b = queries[i][1];
int k = queries[i][2];
numbers[a] += k;
numbers[b] -= k;
}
// Calculate sum(s)
int max=0;
for(int i = 1; i < numbers.length; i++)
{
numbers[i] += numbers[i - 1];
if(numbers[i]>max)
{
max=numbers[i];
}
}
return max;
}
package arrayProblems;
import java.util.ArrayList;
import java.util.List;
import static java.util.Arrays.*;
public class ArrayManipuations {
public static void main(String[] args) {
int n=10;
int[] arr = new int[n];
List<List<Integer>> nl = new ArrayList<List<Integer>>();
nl=asList(asList(1,5,3),asList(4,8,7),asList(6,9,1));
for(int i=0;i<nl.size();i++) {
for(int j=nl.get(i).get(0);j<=nl.get(i).get(1);j++) {
arr[j-1]=arr[j-1]+nl.get(i).get(2);
}
}
int max = Integer.MIN_VALUE;
for(int k=0;k<n;k++) {
if(max<arr[k]) {
max = arr[k];
arr[k]=max;
}
}
System.out.print(max);
}
}