我们有2-3 + 5 + 7-20 = -9，所以输出为5 ，我的问题是的复杂性，现在是 O（n ^ 3）一只鸟低声说，可以在 O（n）
public class mmn { public static void main [] args） { int a [] = {2，-3,5,7，-20,7}; int r = what（a）; System.out.println（r）; } private static int f（int [] a，int low，int high） { int res = 0; （int i = low; i< = high; i ++） res + = a [i]; return res; } public static int what（int [] a） { int temp = 0; （int i = 0; i { for（int j = i; j< a.length; j ++） { int c = f（a，i，j）; if（c％3 == 0） { if（j-i + 1> temp） temp = j-i + 1; } } } return temp; } }尝试重写O（n）：
import java.util。*; class Main { public static void main（String [] args）throws Exception { //应该只使用一个Scanner对象扫描仪扫描器=新的扫描仪（System.in ）; int a [] = {3,1,3,1,3,1}; int n = a.length; int S [] = new int [n]; int i [] = new int [n]; int最好; int sum; （int j = 0; j< n; j ++） { S [j] = a [j]％3; i [j] = j; //初始化 //System.out.println(S[j]）; //System.out.println(i[j]）; } best = 1; （int k = 1; k在Python中的一个 O（n）算法的例证，使一个遍历数组。这个想法是 dp [i] [r] 表示最长的序列， s ，以索引 i 其中（sum s）％3 = r 。 Cleary我们寻找最高的 dp [i] [0] 。如果前面的步骤根据适当的模结果记录任何长度，我们只能增加特定单元的序列。由于我们每次通过数组迭代访问三个单元格（一个常量），所以该算法具有时间和空间复杂度。 （空格可以很容易地适应 O（1），因为我们只需要在每次迭代时使用前三个单元格。）
a = [2，-3,5,7，-20,7] best = 0 对于我在范围（1（1）+ 1）中的i，bestIndex = -1 dp = [[0,0,0]]] len（a）+ 1）：r = a [i-1]％3 为范围（3）中的j： canSumToJ = dp [i-1] [ （3 + j-r）％3]> 0 dp [i] [j] = max（1如果r == j else 0 ，1 + dp [i-1] [（3 + j - r）％3 ]如果canSumToJ else 0） bestIndex = i - 1如果dp [i] [0]>最佳其他bestIndex best = max（best，dp [i] [0]） print（best，（bestIndex - best + 1，bestIndex））＃（5，（0， 4）） ＃dp ＃=> [[0，0，0] ＃，[0，0，1] ＃，[1，0，2] ＃，[0,3,2] ＃，[3，1，4] ＃，[5，4，2] ＃，[3，6，5]] pre>I wrote a code that finds the longest continuum in the array that the sum of the values in the continuum equal to zero modulo 3, e.g for the array a[]={2,-3,5,7,-20,7}
We have 2-3+5+7-20=-9 so the output is 5, My problem is the complexity, now it's O(n^3) a bird whispered me that it can be done in O(n)
public class mmn { public static void main(String[] args) { int a[]={2,-3,5,7,-20,7}; int r=what(a); System.out.println(r); } private static int f(int[]a,int low, int high) { int res=0; for (int i=low;i<=high;i++) res+=a[i]; return res; } public static int what(int[]a) { int temp=0; for(int i=0;i<a.length;i++) { for (int j=i;j<a.length;j++) { int c=f(a,i,j); if (c%3==0) { if(j-i+1>temp) temp=j-i+1; } } } return temp; } }Attempt to rewrite in O(n):
import java.util.*; class Main { public static void main (String[] args) throws Exception { // you should use only one Scanner object Scanner scanner = new Scanner(System.in); int a[]={3,1,3,1,3,1}; int n=a.length; int S[]=new int[n]; int i[]=new int[n]; int best; int sum; for (int j=0; j<n; j++) { S[j]=a[j]%3; i[j]=j;// initialize //System.out.println(S[j]); //System.out.println(i[j]); } best=1; for (int k=1; k<n; k++) { if((S[k-1]+S[k])%3==0) {//checking if we want a longer continuum S[k]=S[k-1]+a[k]; i[k]=i[k-1]; } if(S[k]<S[best])//check if i should update the better best=k-1; } System.out.println(best); } }解决方案
Here's an illustration of an O(n) algorithm in Python, making one pass over the array. The idea is that dp[i][r] represents the longest sequence, s, ending at index i where (sum s) % 3 = r. Cleary we look for the highest dp[i][0]. We can only augment the sequence for a particular cell if the previous step recorded any length at all for the appropriate modulo result. Since we access only three cells (a constant) on each iteration through the array, the algorithm has O(n) time and space complexity. (Space can be easily adapted to O(1) since we only need the previous three cells at each iteration.)
a = [2,-3,5,7,-20,7] best = 0 bestIndex = -1 dp = [[0,0,0] for i in range(len(a) + 1)] for i in range(1,len(a) + 1): r = a[i-1] % 3 for j in range(3): canSumToJ = dp[i-1][(3 + j - r) % 3] > 0 dp[i][j] = max(1 if r == j else 0 ,1 + dp[i-1][(3 + j - r) % 3] if canSumToJ else 0) bestIndex = i - 1 if dp[i][0] > best else bestIndex best = max(best,dp[i][0]) print(best,(bestIndex - best + 1, bestIndex)) # (5, (0, 4)) # dp # => [[0, 0, 0] # ,[0, 0, 1] # ,[1, 0, 2] # ,[0, 3, 2] # ,[3, 1, 4] # ,[5, 4, 2] # ,[3, 6, 5]]
更多推荐
找到数组中最长的连续体,连续体中的值之和等于零模3
发布评论