leetCode

文章目录

前言
原题题目
原题案例
解法分析
- 方法一:直接比较法
- 方法二:数学计算法

前言

今天我真的超级开心，嘿嘿，昨天发了一篇博文，在今天做leetCode题的时候，有人突然给我说，pier，你的博客上Java领域榜第三名了，我靠，牛啊。当时我其实不太信的，我就去看了一下，再仔细翻了一下，居然还上了全站综合热榜的第28名。再提一下，昨天没更新的原因是，我的题没有通过，失败了，也就没有打卡到，也没做出来。

打卡界面

原题题目

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行可能是不完整的。
给你一个数字 n ，计算并返回可形成完整阶梯行的总行数。

原题案例

解法分析方法一:直接比较法

我们通过求和的形式，比较两个数的大小，当我们的和大于我们的数n时，就可以将我们的数提出来了，如果没有大于它呢，就继续往下加，每一次加数的时候，就给我们的阶梯加1，最后返回阶梯数就好了。

方法一代码展示

  public int arrangeCoins(int n) {
        int index=0;
        //这里将数组长度写成long是因为数据会超出长度
        long sum=0;
        long n1 = n;
        for (int i = 1; i <= n ; i++) {
            sum+=i;
            if(sum>n){
                break;
            }
            index++;
        }
        return index;
    }
}

方法一leetcode运行截图

方法二:数学计算法

我们看一眼解题，他其实和我们求前n个数的和，就好像时我们1+2+3，就一直加到哪一个数会大于n就可以了。那么我们假设这个数为sum，有x个数,那么：
KaTeX parse error: Can't use function '$' in math mode at position 8: sum = X$̲times$(X+1)/2
按照题意来说，我们只需要求出来，当sum X × ( X + 1 ) / 2 n>X×(X+1)/2 n>X×(X+1)/2时X能取得最大值，我们将它用数学得方式来求就是，当 ( X × ( X + 1 ) / 2 ) − n > 0 (X×(X+1)/2)-n>0 (X×(X+1)/2)−n>0，那么这个我们怎么求呢，我们可以展开一下，即 X 2 + X − 2 n > 0 X^2 + X -2n>0 X2+X−2n>0,这一个因为n时常数，而二次方得系数为1>0,所以我们就可以用n求出来这个X了。我们令 X 2 − X − 2 n = 0 我们令X^2 -X -2n=0 我们令X2−X−2n=0
因为n>=1,所以 Δ = b 2 − 4 a c = 8 n + 1 > 0 Δ=b^2−4ac=8n+1>0 Δ=b2−4ac=8n+1>0
根据公式我们可以推得: x 1 = ( − 1 − ( 8 n + 1 ) ) / 2 , x 2 = ( − 1 + ( 8 n + 1 ) ) / 2 x1= (−1− sqrt(8n+1))/2,x 2 =(−1+sqrt (8n+1))/2 x1=(−1−( 8n+1))/2,x2=(−1+( 8n+1))/2

所以我们舍去x1<0,不可能存在这样得阶梯，提出来x2，写成代码就可了。

方法二代码展示

	public int arrangeCoins(int n) {
        return (int) ((Math.sqrt((long) 8 * n + 1) - 1) / 2);
    }

方法二leetCode运行截图

Ps:每日一句毒鸡汤：这孩子不是笨，是没有找对学习方法。嗯……或许叭，学习方法都找不到，不是笨是什么呀！

leetCode

Java相关栏目本月热门文章