时间戳

首页 > 解决方案 > 当需要在第 30 行找到值时，帕斯卡三角整数溢出

java - 当需要在第 30 行找到值时，帕斯卡三角整数溢出

问题描述

这是整数溢出问题，但我无法绕开它只使用整数作为解决方案[不使用 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;
        
    }

标签： javainteger-overflow

解决方案

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;
    
}

但是问题可以不使用就解决long。该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]

推荐阅读