美文网首页
计算题目

计算题目

作者: 卡路fly | 来源:发表于2020-05-20 03:11 被阅读0次

    9. 斐波那契数列

    描述

    输出斐波那契数列的第n项(从0开始,第0项为0)。

    公式:
    f(n) = n, n <= 1
    f(n) = f(n-1) + f(n-2), n > 1

    思路:采用自底向上方法来保存了先前计算的值,为后面的调用服务。

    public int Fibonacci(int n) {
        if(n<=1)
                return n;
    
            int f1 = 0;
            int f2 = 1;
            for(int i=2;i<=n;i++) {
                f2 = f1+f2;
                f1 = f2-f1;
            }
            return f2;
        }
    

    青蛙跳台阶

    描述

    一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

    思路

    基于斐波那契

       public int numWays(int n) {
            int f1 = 1;
            int f2 = 1;
            int result = 0;
            
            for(int i=0;i< n;i++){
                result = (f1 + f2)%1000000007;
                f1 = f2;
                f2 = result;
            }
            return f1;
        }
    

    变态青蛙跳

    描述

    一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    思路

    在n阶台阶,一次有1、2、...n阶的跳的方式时,总得跳法为:

                  | 1       ,(n=0 ) 
    
    f(n) =     | 1       ,(n=1 )
    
                 | 2*f(n-1),(n>=2)
    
    public int JumpFloorII(int target) {
            if (target <= 0) {
                return -1;
            } else if (target == 1) {
                return 1;
            } else {
                return 2 * JumpFloorII(target - 1);
            }
        }
    

    10. 位运算

    描述

    输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

    思路

    如果一个整数不为0,那么这个整数至少有一位是1。如果我们把这个整数减1,那么原来处在整数最右边的1就会变为0,原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。

    举个例子:二进制数1100,从右边数起第三位是处于最右边的一个1。减去1后,第三位变成0,它后面的两位0变成了1,而前面的1保持不变,因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算,从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说,把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1,就可以进行多少次这样的操作。

    public int NumberOf1(int n) {
            int count = 0;
            while (n != 0) {
                count++;
                n = (n - 1) & n;
            }
            return count;
        }
    

    11. 整数的N次方

    描述

    给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

    思路
    1. 指数为负时,可以先对指数求绝对值,算出次方的结果后再取倒数

    2. 当底数为0,指数为负时,会出现对0求倒数情况,要特殊处理

    3. 0的0次方在数学上没有意义,因此无论输出0还是1都是可以接受的

    4. 在计算次方的时候,除了简单的遍历,我们可以使用递归的思想,如下公式,来减少计算量:

    public double Power(double base, int exponent) {
            int n = exponent;
            if(exponent==0){
                // 当指数为0底数为0时,没有意义,返回0或者返回1都可以
                return 1;
            }else if(exponent < 0){
                if(base == 0){
                    throw new RuntimeException("分母不能为0"); 
                }
                n = -exponent;
            }
            double res = PowerUnsignedExponent(base, n);
            return exponent < 0? 1/res: res;
      }
    
    public double PowerUnsignedExponent(double base, int n){
            if(n == 0)
                return 1;
            if(n == 1)
                return base;
            //递归
            double res = PowerUnsignedExponent(base, n&gt;&gt;1);
            res *= res;
            if((n & 0x1) == 1)
                res *= base;
            return res;
    }
    

    32. 整数中1出现的次数

    描述

    思路

    public int NumberOf1Between1AndN_Solution(int n) {
            if (n <= 0)
                return 0;
            int count = 0;
            for (long i = 1; i <= n; i *= 10) {
                long diviver = i * 10;
                count += (n / diviver) * i + Math.min(Math.max(n % diviver - i + 1, 0), i);
            }
            return count;
        }
    

    34. 丑数

    描述

    把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

    思路

    1. 只求丑数,不要去管非丑数。
    2. 每个丑数必然是由小于它的某个丑数乘以2,3或5得到的,我们把求得的丑数都保存下来,用之前的丑数分别乘以2,3,5,找出这三这种最小的并且大于当前最大丑数的值,即为下一个我们要求的丑数。
    3. 这种方法用空间换时间,时间复杂度为O(n)。
    public int GetUglyNumber_Solution(int index) {
            if (index <= 0)
                return 0;
    
            if (index == 1)
                return 1;
    
            int[] reslut = new int[index];
            int t2 = 0, t3 = 0, t5 = 0;
            reslut[0] = 1;
            for (int i = 1; i < index; i++) {
                reslut[i] = Min(reslut[t2] * 2, reslut[t3] * 3, reslut[t5] * 5);
                if (reslut[i] == reslut[t2] * 2)
                    t2++;
                if (reslut[i] == reslut[t3] * 3) 
                    t3++;
                if (reslut[i] == reslut[t5] * 5) 
                    t5++;
            }
            return reslut[index - 1];
        }
    

    46. 1+ 2 +...+n

    描述

    思路

    1.需利用逻辑与的短路特性实现递归终止。
    2.当n==0时,(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断,为false,然后直接返回0;
    3.当n>0时,执行sum+=Sum_Solution(n-1),实现递归计算Sum_Solution(n)。

     public int Sum_Solution(int n){
            int sum=n;
            boolean ans=(n>0)&&((sum+=Sum_Solution(n-1))>0);
            return sum;
        }
    

    不用加减乘除做加法

    思路

    首先看十进制是如何做的: 5+7=12,三步走
    第一步:相加各位的值,不算进位,得到2。
    第二步:计算进位值,得到10. 如果这一步的进位值为0,那么第一步得到的值就是最终结果。
    第三步:重复上述两步,只是相加的值变成上述两步的得到的结果2和10,得到12。 同样我们

    可以用三步走的方式计算二进制值相加: 5-101,7-111
    第一步:相加各位的值,不算进位,得到010,二进制每位相加就相当于各位做异或操作,101^111。
    第二步:计算进位值,得到1010,相当于各位做与操作得到101,再向左移一位得到1010,(101&111)<<1。
    第三步重复上述两步, 各位相加 010^1010=1000,进位值为100=(010&1010)<<1。
    继续重复上述两步:1000^100 = 1100,进位值为0,跳出循环,1100为最终结果。

    public int Add(int num1,int num2) {
            int sum,carry;
            while(num2!=0){
                sum = num1^num2;
                carry = (num1&num2)<<1;
                num1 = sum;
                num2 = carry;
            }
            return num1;
        }
    

    相关文章

      网友评论

          本文标题:计算题目

          本文链接:https://www.haomeiwen.com/subject/xnzvohtx.html