当需要在第30行查找值时，Pascal三角整数溢出

Question

这是Integer溢出问题，但我无法理解它，因为我只使用Integer来解决问题[不使用long]。我想知道当溢出发生时，我们如何在不转移到更高数据类型的情况下测试或形成方程？

目的：尝试在i索引处找到帕斯卡三角形的值；

rowIndex的最大值可以是33。

代码：

class Solution {
public List<Integer> getRow(int rowIndex) {

List<Integer> pt = new ArrayList<>();

int prev=1;
int curr=1;
int n=rowIndex+1;
pt.add(prev);

for (int i=1; i <= rowIndex; i++) {    

curr = prev * (n-i)/i;

pt.add(curr);

prev=curr;
}
return pt;

}

Answer 1

您可以使用long而不是int来防止溢出。

public List<Integer> getRow(int rowIndex) {

List<Integer> pt = new ArrayList<>();

int prev=1;
int curr=1;
int n=rowIndex+1;
pt.add(prev);

for (int i=1; i <= rowIndex; i++) {    

curr = (int) ((long) prev * (n-i)/i);

pt.add(curr);

prev=curr;
}
return pt;

}

但该问题可以在不使用CCD_ 3的情况下得到解决。prev * (n-i)部分可能溢出，但是这个乘积应该可以被i整除。你可以先除法后乘法来避免溢出。如果预先计算(n-i)和i的GCD，可以重写如下。

int gcd = gcd(n - i, i);
curr = (prev / (i / gcd)) * ((n - i) / gcd);

GCD可以通过以下方法获得。

static int gcd(int m, int n) {
while (n > 0) {
int r = m % n;
m = n;
n = r;
}
return m;
}

之前：

[1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, -131213633, -123012780, -101304642, -73164463, -46209134, -25415023, -12102391, -4950978, -1722079, -502273, -120545, -23181, -3434, -367, -25, 0]

之后：

[1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, 155117520, 145422675, 119759850, 86493225, 54627300, 30045015, 14307150, 5852925, 2035800, 593775, 142506, 27405, 4060, 435, 30, 1]