2280. Minimum Lines to Represent a Line Chart

[Woodyiiiiiii]

You are given a 2D integer array stockPrices where stockPrices[i] = [dayi, pricei] indicates the price of the stock on day dayi is pricei. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown.

...

---

周赛第三题。

这道题凭直觉来讲是求解有多少个斜率。

如果直接从三点的斜率直接判断，即(y1 - y2) / (x1 - x2) == (y2 - y3) / (x2 - x3)，使用double来存储除数，会过不了一个样例。原因是double的精度问题：double无法精确表示10的负数次方。

比如

double res = 1.0 - 0.9; 

打印出来后是0.09999999999999998。因为浮点数是二进制运算，就像十进制无法精确表示1/3一样，二进制无法对0.1除尽。

代码如下：

class Solution {
    public int minimumLines(int[][] stockPrices) {
        
        if (stockPrices.length == 1) {
            return 0;
        } else if (stockPrices.length == 2) {
            return 1;
        }

        Arrays.sort(stockPrices, Comparator.comparingInt(o -> o[0]));

        double k = (stockPrices[1][1] - stockPrices[0][1]) * 1.0 / (stockPrices[1][0] - stockPrices[0][0]);
        int cnt = 1;

        for (int i = 2; i < stockPrices.length; i++) {
            double nextK = (stockPrices[i][1] - stockPrices[i - 1][1]) * 1.0 / (stockPrices[i][0] - stockPrices[i - 1][0]);
            if (k != nextK) {
                k = nextK;
                cnt++;
            }
        }

        return cnt;
        
    }
}

这时候要想到避免出现浮点数运算，考虑用叉乘代替除法：x1y2 == x2y1。又因为单个数字较大(最大为10^9)，相乘结果用long来存储，因为最大整型(Integer.MAX_VALUE)相乘也不会超过long的最大值。因为contest中不会显示错误test case，所以我还以为是我本身的算法问题而不是精度问题，也没想到叉乘，菜

class Solution {
    public int minimumLines(int[][] stockPrices) {
        
        if (stockPrices.length == 1) {
            return 0;
        } else if (stockPrices.length == 2) {
            return 1;
        }

        Arrays.sort(stockPrices, Comparator.comparingInt(o -> o[0]));
        
        int cnt = 1;
        for (int i = 2; i < stockPrices.length; i++) {
            long xDiff = stockPrices[i][0] - stockPrices[i - 1][0];
            long yDiff = stockPrices[i][1] - stockPrices[i - 1][1];
            long xxDiff = stockPrices[i][0] - stockPrices[i - 2][0];
            long yyDiff = stockPrices[i][1] - stockPrices[i - 2][1];
            if (xDiff * yyDiff != yDiff * xxDiff) {
                cnt++;
            }
        }

        return cnt;
        
    }
}

看了其他大佬的题解，还可以使用最大公约数来避免斜率除法的出现。算出最大公约数，然后判断倍数是否相等来判断斜率是否相等。

class Solution {
    public int minimumLines(int[][] stockPrices) {
        
        if (stockPrices.length == 1) {
            return 0;
        } else if (stockPrices.length == 2) {
            return 1;
        }

        Arrays.sort(stockPrices, Comparator.comparingInt(o -> o[0]));
        
        int cnt = 1;
        for (int i = 2; i < stockPrices.length; i++) {
            int x = stockPrices[i][0];
            int y = stockPrices[i][1];
            int preX = stockPrices[i - 1][0];
            int preY = stockPrices[i - 1][1];
            int ppreX = stockPrices[i - 2][0];
            int ppreY = stockPrices[i - 2][1];
            int gcd1 = gcd(y - preY, x - preX);
            int gcd2 = gcd(preY - ppreY, preX - ppreX);
            int dy1 = (y - preY) / gcd1;
            int dy2 = (preY - ppreY) / gcd2;
            int dx1 = (x - preX) / gcd1;
            int dx2 = (preX - ppreX) / gcd2;
            if (dy1 != dy2 || dx1 != dx2) {
                ++cnt;
            }
        }

        return cnt;
        
    }
    
    // 求最大公约数算法
    int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
    
}

---

reference:

• https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart/
• https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart/discuss/2061824/GCD-Slope
• https://blog.csdn.net/tomcat_2014/article/details/51453988