数字与数学——常见面试算法题

目录

数字统计问题

符号统计

阶乘0的个数

溢出问题

整数反转

回文数

进制问题

七进制数

进制转换

数组实现加法

数组实现整数加法

字符串实现加法

二进制加法

幂运算

求2的幂

求3的幂

求4的幂

辗转相除法（之前博客有过详细推导） https://blog.csdn.net/qq_74092815/article/details/130471544?spm=1001.2014.3001.5502

素数和合数（之前博客有过详细推导） https://blog.csdn.net/qq_74092815/article/details/130464087?spm=1001.2014.3001.5502

埃氏筛（之前博客有过详细推导）https://blog.csdn.net/qq_74092815/article/details/130464087?spm=1001.2014.3001.5502

丑数

---

在算法中，一般只会选择各个学科的基础问题来考察，例如素数问题、幂、对数、阶乘、幂运算、初等数论、几何问题、组合数学等等。

数字统计问题

符号统计

给定一个数组，求所有元素的乘积的符号，如果最终答案是负的返回-1，如果最终答案是正的返回1，如果答案是0返回0。

• 只需要看有多少个负数，就能够判断最后乘积的符号了。

public int arraySign(int[] nums) {                           int prod = 1;                       for(int i = 0; i < nums.length; ++i) {     if(nums[i] == 0) {               return 0;//一切归零}else if(nums[i] < 0) {//交替就够了，很好的处理技巧prod = -prod;}}return prod;       
}

阶乘0的个数

算出 n 阶乘有多少个尾随零。

• 求n能拆分出多少个5【统计有多少个 0，实际上是统计 2 和 5 一起出现多少对，不过因为 2 出现的次数一定大于 5 出现的次数，因此我们只需要检查 5 出现的次数就好了】

public int trailingZeroes(int n) {int cnt = 0;for (long num = 5; n / num > 0; num *= 5) {cnt += n / num;}return cnt;
}

溢出问题

整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。假设环境不允许存储 64 位整数（有符号或无符号）。

• 核心点就俩，一是反转，二是溢出判断

• 反转--->取模

• 溢出，32位最大整数是MAX=2147483647，如果一个整数num>MAX，那么应该有以下规律：nums/10 >MAX/10=214748364

public int reverse(int x) {int res = 0;while(x!=0) {//获得末尾数字int tmp = x%10;//判断是否大于最大32位整数，也可以使用Integer.MAX_VALUE/10来代替214748364if (res>Integer.MAX_VALUE/10 || (res==Integer.MAX_VALUE/10 && tmp>7)) {return 0;}//判断是否小于最小的32位整数if (res<-214748364 || (res==-214748364 && tmp<-8)) {return 0;}res = res*10 + tmp;x /= 10;}return res;
}

回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

• 只反转 int 数字的一半【当反转数的位数超过或等于剩余 x 的位数时，循环终止。此时反转数已经处理了原数字的后半部分，而剩余 x 是前半部分。】

public boolean isPalindrome(int x) {// 特殊情况：// 如上所述，当 x < 0 时，x 不是回文数。// 同样地，如果数字的最后一位是 0，为了使该数字为回文，// 则其第一位数字也应该是 0// 只有 0 满足这一属性if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}int revertedNumber = 0;while (x > revertedNumber) {revertedNumber = revertedNumber * 10 + x % 10;x /= 10;}// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。return x == revertedNumber || x == revertedNumber / 10;
}

进制问题

七进制数

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。其中-10^7 <= num <= 10^7。

public String convertToBase7(int num) {StringBuilder sb = new StringBuilder();//先拿到正负号boolean sign = num < 0;//这样预处理一下，后面都按照正数处理num就行了if(sign)num *= -1;//循环取余和整除    do{sb.append(num%7 + "");num/=7;}while(num > 0);//添加符号if(sign)sb.append("-");//上面的结果是逐个在末尾加的，需要反过来   return sb.reverse().toString();
}

进制转换

十进制数M，以及需要转换的进制数N，将十进制数M转化为N进制数。M是32位整数，2<=N<=16。

• 定义大小为16的数组F，保存的是2到16的各个进制的值对应的标记，这样赋值时只计算下标，不必考虑不同进制的转换关系了。

• 使用StringBuffer完成数组转置等功能。

• 通过一个flag来判断正数还是负数，最后才处理。

// 要考虑到 余数 > 9 的情况，2<=N<=16.
public static final String[] F = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"};
//将十进制数M转化为N进制数
public String convert (int M, int N) {Boolean flag=false;if(M<0){flag=true;M*=-1;}StringBuffer sb=new StringBuffer();int temp;while(M!=0){temp=M%N;//技巧一：通过数组F[]解决了大量繁琐的不同进制之间映射的问题sb.append(F[temp]);M=M/N;}//技巧二：使用StringBuffer的reverse()方法sb.reverse();//技巧三：最后处理正负，不要从一开始就揉在一起。return (flag? "-":"")+sb.toString();
}

}

数组实现加法

数组实现整数加法

由整数组成的非空数组所表示的非负整数，在其基础上加一。这里最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。并且假设除了整数 0 之外，这个整数不会以零开头。

• 进位

  • 逼至首位【长度加1 如999 99 这种的结果是首位为1，其余位为0】

  • 普通进位

• 不进位

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

字符串实现加法

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

public String addStrings(String num1, String num2) {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 和 0。

示例1：

输入: a = "11", b = "1"

输出: "100"

示例2：

输入: a = "1010", b = "1011"

输出: "10101"

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的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

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

• 位运算：正整数 n 是2 的幂，当且仅当 n 的二进制表示中只有最高位是 1，其余位都是 0，此时满足 n & (n−1)=0。

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

求3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

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

• 在int 型的数据范围内存在最大的 3 的幂，不超过 2^31-1 的最大的 3 的幂是 3^19=1162261467。所以如果在1~ 2^31-1内的数，如果是3的幂，则一定是1162261467的除数

public boolean isPowerOfThree(int n) {return n > 0 && 1162261467 % n == 0;}

求4的幂

boolean isPowerOfFour(int n) {if (n <= 0)return false;while (n % 4 == 0)n /= 4;return n == 1;
}

辗转相除法（之前博客有过详细推导） 

public static int gcd(int a,int b){ while(b>0){ int temp = a%b; a=b; b=temp; } return a;
}public static int gcd(int a,int b){ return b==0?a:gcd(b,a%b);
}

素数和合数（之前博客有过详细推导）

boolean isPrime(int num) {int max = (int)Math.sqrt(num);for (int i = 2; i <= max; i++) {if (num % i == 0) {return false;}}return true;
}

埃氏筛（之前博客有过详细推导）

public int countPrimes(int n) {int[] isPrime = new int[n];Arrays.fill(isPrime, 1);int ans = 0;for (int i = 2; i < n; ++i) {if (isPrime[i] == 1) {ans += 1;if ((long) i * i < n) {for (int j = i * i; j < n; j += i) {isPrime[j] = 0;}}}}return ans;}

丑数

只包含质因子 2、3 和 5 的数称作丑数（Ugly Number），求按从小到大的顺序的第 n 个丑数。

    public boolean isUgly(int n) {if (n <= 0) {return false;}int[] factors = {2, 3, 5};for (int factor : factors) {while (n % factor == 0) {n /= factor;}}return n == 1;}

public class Solution {public int nthUglyNumber(int n) {int[] dp = new int[n];dp[0] = 1;int p2 = 0, p3 = 0, p5 = 0;for (int i = 1; i < n; i++) {int next2 = dp[p2] * 2;int next3 = dp[p3] * 3;int next5 = dp[p5] * 5;int minVal = Math.min(next2, Math.min(next3, next5));dp[i] = minVal;if (next2 == minVal) p2++;if (next3 == minVal) p3++;if (next5 == minVal) p5++;}return dp[n - 1];}
}