Java 中范围内双递增序列的计数

2024年9月10日 | 阅读 9 分钟

给出两个整数 P 和 Q。任务是找到一个系列的总计数，其中当前元素是系列中上一个元素的两倍或更多，并且该系列的任何元素都不能超过 P。它可以等于 P。

示例 1

输入

int P = 9, int Q = 3

输出 14

解释：共有 14 个大小为 3 的系列，当前元素是该系列上一个元素的两倍或更多，并且该系列的每个元素都小于或等于 9。所有这些系列是：{1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 2, 7}, {1, 2, 8}, {1, 2, 9}, {1, 3, 6}, {1, 3, 7}, {1, 3, 8}, {1, 3, 9}, {1, 4, 8}, {1, 4, 9}, {2, 4, 8}, {2, 4, 9}

示例 2

输入

int P = 12, int Q = 4

输出 10

解释：共有 10 个大小为 4 的系列，当前元素是该系列上一个元素的两倍或更多，并且该系列的每个元素都小于或等于 12。所有这些系列是：{1, 2, 4, 8}, {1, 2, 4, 9}, {1, 2, 4, 10}, {1, 2, 4, 11}, {1, 2, 4, 12}, {1, 2, 5, 10}, {1, 2, 5, 11}, {1, 2, 5, 12}, {1, 2, 6, 12}, {1, 3, 6, 12}

示例 3

输入

int P = 15, int Q = 7

输出 0

解释：不存在大小为 7 的系列，其中当前元素是前一个元素的两倍或更多，并且每个元素都小于或等于 15。因此，输出为 0。

朴素方法

在朴素方法中，我们将使用自顶向下的递归来找到解决方案。

文件名：DoubleIncSeq.java

public class DoubleIncSeq 
{
    public int getTotalSeqCount(int p, int q)
    {
    // handling the base case 
    // which is if either the value of p
    // or q (sequence size) is zero, then it is 
    // not possible to generate the sequence
    // hence, the answer is 0
    if(p == 0 || q == 0)
    {
        return 0;
    }
    
    // handling another base case where the value of
    // q (sequence size) is equal to 1, then in that case
    // every number 1 to p is a sequence in itself. Therefore,
    // the answer is p.
    if(q == 1)
    {
        return p;
    }

    // recursively finding the solution where the current element is twice 
    // or more than twice the previous element
    return (getTotalSeqCount(p - 1, q) + getTotalSeqCount(p / 2, q - 1));
            
    }
    
    // main method
    public static void main(String argvs[]) 
    {
    // creating an object of the class DoubleIncSeq
    DoubleIncSeq obj = new DoubleIncSeq();
    
    // input 1
    int p = 9;
    int q = 3;
    
    // invoking the method getTotalSeqCount()
    // and storing the answer
    int ans = obj.getTotalSeqCount(p, q);
    
    if(ans > 0)
    {
    System.out.println("There are total " + ans + " series whose elements are <= " + p + " and are of size: " + q);
    }
    else
    {
    System.out.println("There is no series whose elements are <= " + p + " and is of size: " + q);    
    }
    
    System.out.println();
    
    // input 2
    p = 12;
    q = 4;
    
    // invoking the method getTotalSeqCount()
    // and storing the answer
    ans = obj.getTotalSeqCount(p, q);
    
    if(ans > 0)
    {
    System.out.println("There are total " + ans + " series whose elements are <= " + p + " and are of size: " + q);
    }
    else
    {
    System.out.println("There is no series whose elements are <= " + p + " and is of size: " + q);    
    }
    
    System.out.println();
    
    // input 3
    p = 15;
    q = 7;
   
    // invoking the method getTotalSeqCount()
    // and storing the answer
    ans = obj.getTotalSeqCount(p, q);
    
    if(ans > 0)
    {
    System.out.println("There are total " + ans + " series whose elements are <= " + p + " and are of size: " + q);
    }
    else
    {
    System.out.println("There is no series whose elements are <= " + p + " and is of size: " + q);    
    }
    
    }
}

输出

There are total 14 series whose elements are <= 9 and are of size: 3

There are total 10 series whose elements are <= 12 and are of size: 4

There is no series whose elements are <= 15 and is of size: 7

复杂度分析：一个递归调用会产生另外两个递归调用。因此，程序的 time complexity 是指数级的。

由于指数级的时间复杂度，上述程序不适用于较大的输入。因此，需要进行一些优化以降低时间复杂度。

方法：带记忆化的递归

在上述程序中有许多子问题被一遍又一遍地解决。因此，需要使用二维数组来存储已计算子问题的答案，以避免重复。下面的程序中说明了这一点。

文件名：DoubleIncSeq1.java

public class DoubleIncSeq1 
{
    // a method that assigns -1 to 
    // each element of the 2-D array 
    public void initialize(int dp[][])
    {
        int r = dp.length;
        int c = dp[0].length;
        
        for(int i = 0; i < r; i++)
        {
            for(int j = 0; j < c; j++)
            {
                dp[i][j] = -1;
            }
        }
    }
    
    
    public int getTotalSeqCount(int p, int q, int dp[][])
    {
    // handling the base case 
    // which is if either the value of p
    // or q (sequence size) is zero, then it is 
    // not possible to generate the sequence
    // hence, the answer is 0
    if(p == 0 || q == 0)
    {
        return 0;
    }
    
    // handling another base case where the value of
    // q (sequence size) is equal to 1, then in that case
    // every number 1 to p is a sequence in itself. Therefore,
    // the answer is p.
    if(q == 1)
    {
        return p;
    }
    
    // the value of dp[p][q] is already computed
    // hence no need to compute it again. We can simply
    // return the value of dp[p][q]
    if(dp[p][q] != -1)
    {
        return dp[p][q];
    }

    // recursively finding the solution where the current element is twice 
    // or more than twice the previous element
    dp[p][q] = (getTotalSeqCount(p - 1, q, dp) + getTotalSeqCount(p / 2, q - 1, dp));
    return (getTotalSeqCount(p - 1, q, dp) + getTotalSeqCount(p / 2, q - 1, dp));
            
    }
    
    // main method
    public static void main(String argvs[]) 
    {
    // creating an object of the class DoubleIncSeq1
    DoubleIncSeq1 obj = new DoubleIncSeq1();
    
    // input 1
    int p = 9;
    int q = 3;
    
    
    // creating a 2-D array temp for memoization
    int temp[][] = new int[p + 1][q + 1];
    
    // invoking the method initialize that
    // assign -1 to each element of the 2-D
    // array temp
    obj.initialize(temp);
    
    // invoking the method getTotalSeqCount()
    // and storing the answer
    int ans = obj.getTotalSeqCount(p, q, temp);
    
    if(ans > 0)
    {
    System.out.println("There are total " + ans + " series whose elements are <= " + p + " and are of size: " + q);
    }
    else
    {
    System.out.println("There is no series whose elements are <= " + p + " and is of size: " + q);    
    }
    
    System.out.println();
    
    // input 2
    p = 12;
    q = 4;
    
    // creating a 2-D array temp1 for memoization
    int temp1[][] = new int[p + 1][q + 1];
    
    // invoking the method initialize that
    // assign -1 to each element of the 2-D
    // array temp
    obj.initialize(temp1);
    
    // invoking the method getTotalSeqCount()
    // and storing the answer
    ans = obj.getTotalSeqCount(p, q, temp1);
    
    if(ans > 0)
    {
    System.out.println("There are total " + ans + " series whose elements are <= " + p + " and are of size: " + q);
    }
    else
    {
    System.out.println("There is no series whose elements are <= " + p + " and is of size: " + q);    
    }
    
    System.out.println();
    
    // input 3
    p = 15;
    q = 7;
    
    // creating a 2-D array temp2 for memoization
    int temp2[][] = new int[p + 1][q + 1];

    // invoking the method initialize that
    // assign -1 to each element of the 2-D
    // array temp
    obj.initialize(temp2);
    
    // invoking the method getTotalSeqCount()
    // and storing the answer
    ans = obj.getTotalSeqCount(p, q, temp2);
    
    if(ans > 0)
    {
    System.out.println("There are total " + ans + " series whose elements are <= " + p + " and are of size: " + q);
    }
    else
    {
    System.out.println("There is no series whose elements are <= " + p + " and is of size: " + q);    
    }    
    }
}

输出

There are total 14 series whose elements are <= 9 and are of size: 3

There are total 10 series whose elements are <= 12 and are of size: 4

There is no series whose elements are <= 15 and is of size: 7

复杂度分析：由于记忆化，程序的 time complexity 为 O(p x q)。此外，该程序使用辅助数组来存储子问题的答案，使得程序的 space complexity 为 O(p x q)，其中 p 是所需系列中元素的最大可能值，q 是找到的系列总数。

众所周知，迭代方法总是优于递归方法，因此我们将尝试使用循环来编写上述程序。

文件名：DoubleIncSeq2.java

public class DoubleIncSeq2 
{

public int getTotalSeqCount(int p, int q)
{

// creating a 2-D array temp for memoization
int dp[][] = new int[p + 1][q + 1];

for (int m = 0; m < p + 1; m++)
{
for (int n = 0; n < q + 1; n++)
{
// handling the base case 
// which is if either the value of m
// or n (the sequence size) is zero, then it is 
// not possible to generate the sequence
// hence, the answer is 0
if (m == 0 || n == 0)
{
dp[m][n] = 0;
}

// a sequence can never exist if its length
// is greater than the maximum value
// cannot exist
else if (m < n)
{
dp[m][n] = 0;
}

// handling another base case where the value of
// n (sequence size) is equal to 1, then in that case
// every number 1 to m is a sequence in itself. Therefore,
// the answer is m.

else if (m == 1)
{
dp[m][n] = m;
}

// else do the calculation
else
{
dp[m][n] = dp[m - 1][n] + dp[m / 2][n - 1];
}
}
}
return dp[p][q];    



}

// main method
public static void main(String argvs[]) 
{
// creating an object of the class DoubleIncSeq2
DoubleIncSeq2 obj = new DoubleIncSeq2();

// input 1
int p = 9;
int q = 3;

// invoking the method getTotalSeqCount()
// and storing the answer
int ans = obj.getTotalSeqCount(p, q);

if(ans > 0)
{
System.out.println("There are total " + ans + " series whose elements are <= " + p + " and are of size: " + q);
}
else
{
System.out.println("There is no series whose elements are <= " + p + " and is of size: " + q);    
}

System.out.println();

// input 2
p = 12;
q = 4;

// invoking the method getTotalSeqCount()
// and storing the answer
ans = obj.getTotalSeqCount(p, q);

if(ans > 0)
{
System.out.println("There are total " + ans + " series whose elements are <= " + p + " and are of size: " + q);
}
else
{
System.out.println("There is no series whose elements are <= " + p + " and is of size: " + q);    
}

System.out.println();

// input 3
p = 15;
q = 7;

// invoking the method getTotalSeqCount()
// and storing the answer
ans = obj.getTotalSeqCount(p, q);

if(ans > 0)
{
System.out.println("There are total " + ans + " series whose elements are <= " + p + " and are of size: " + q);
}
else
{
System.out.println("There is no series whose elements are <= " + p + " and is of size: " + q);    
}



}
}

输出

There are total 14 series whose elements are <= 9 and are of size: 3

There are total 10 series whose elements are <= 12 and are of size: 4

There is no series whose elements are <= 15 and is of size: 7

复杂度分析：该程序的时间复杂度和空间复杂度与前一个程序相同。

下一个主题Java 中的最长连续子序列

← 上一个下一个 →

Java 中范围内双递增序列的计数

朴素方法

方法：带记忆化的递归

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中范围内双递增序列的计数

朴素方法

方法：带记忆化的递归

相关帖子

Java 中编码三个字符串

Java 中的情侣牵手问题

Java 中编译时多态和运行时多态之间的区别

Method Hiding in Java

Java 8 中 map() 和 flatMap() 方法的区别

How to Generate Random Number in Java

Doubly Linked List Program in Java

How to prepare for Java Interview

Busy Waiting in Multithreading in Java

Java 中使用二分查找查找最长只包含元音的子字符串

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器