当前位置：首页 > article >正文

算法通关村第十三关|白银|数字与数学高频问题

article 2024/11/18 20:53:48

1.实现加法专题

1.1 数组实现整数加法

public int[] plusOne(int[] digits) {
	int len = digits.length;
    for (int i = len - 1; i >= 0; i--) {
        digits[i]++;
        digits[i] %= 10;
        if (digits[i] != 0) {
            return digits;
        }
    }
    digits = new int[len + 1];
    digits[0] = 1;
    return digits;
}

1.2 字符串加法

public String addStrings(String num1, String num2) {
    // add 是进位
	int i = num1.length() - 1, j = num2.length() - 1, add = 0;
    StringBuffer ans = new StringBuffer();
    while (i >= 0 || j >= 0 || add != 0) {
        int x = i >= 0 ? num1.charAt(i) - '0' : 0;
        int y = j >= 0 ? num2.charAt(j) - '0' : 0;
        int result = x + y + add;
        ans.append(result % 10);
        add = result / 10;
        i--;
        j--;
    }
    ans.reverse();
    return ans.toString();
}

1.3 二进制加法

public String addBinary(String a, String b) {
	StringBuilder ans = new StringBuilder();
    int ca = 0;
    for (int i = a.length() - 1, j = b.length() - 1; i > 0 || j > 0; i--, j--) {
        int sum = ca;
        sum += i >= 0 ? a.charAt(i) - '0' : 0;
        sum += j >= 0 ? b.charAt(j) - '0' : 0;
        ans.append(sum % 2);
        ca = sum / 2;
    }
    // 这种写法在循环中没有解决最后一个进位的问题
    ans.append(ca == 1 ? ca : "");
    return ans.reverse().toString();
}

2.幂运算

2.1 求2的幂

public boolean isPowerOfTwo(int n) {
	if (n <= 0) {
        return false;
	}
	while (n % 2 == 0) {
        n / 2;
    }
	return n == 1;
}

2.2 求2的幂但是采用位运算

public boolean isPowerOfTwo(int n) {
	return n > 0 && (n & (n - 1)) == 0;
}

2.3 求3的幂

除本方法外，还可以用整形范围内最大的3的幂来除以输入的n，仅需要一次除法，如果余数为0即为3的幂。

public boolean isPowerOfThree(int n) {
	if (n < 0) {
    	return false;
	}
	while (n % 3 == 0) {
        n /= 3;
    }
	return n == 1;
}

3.指数运算

原题：力扣50.

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
    public double quickMul(double x, long N) {
        double ans = 1.0;
        double x_contribute = x;
        while (N > 0) {
        	// N的二进制位为1时ans才需要乘该位的对应次方的数
            if (N % 2 == 1) {
                ans *= x_contribute;
            }
            x_contribute *= x_contribute;
            N /= 2;
        }
        return ans;
    }
}