LeetCode_数学

1、计数质数（力扣204）

//1.暴力解法(超出时间限制)public static int countPrimes(int n) {int count = 0;for (int i = 2; i < n; i++) {if(isPrimes(i)){count ++;}}return count;}public static boolean isPrimes(int num){//如果说num=x*y,则在遍历过程中，x和y只需要利用一个就好//例如：6=2*3，遍历过2就不用遍历3了//因为x和y中的较小值必定在[2，根号下num]范围内，枚举[2，根号下num]即可for (int i = 2; i * i <= num; i++) {if (num % i == 0){return false;}}return true;}

//2.埃氏筛public static int countPrimes2(int n) {int[] isPrime = new int[n];Arrays.fill(isPrime,1);int count = 0;for (int i = 2; i < n; i++) {if (isPrime[i] == 1){count ++;//注意i * i的取值if ((long)i * i < n){for (int j =  i * i; j < n; j+=i) {isPrime[j] = 0;}}}}return count;}

2、七进制数（力扣504）

//1.先%再/public String convertToBase7(int num) {if(num == 0) return "0";StringBuilder sb = new StringBuilder();int cur = num < 0 ? -num : num;while(cur > 0){sb.append(cur % 7);cur /= 7;}if(num < 0) sb.append("-");return sb.reverse().toString();}

3、数字转换为十六进制数（力扣405)

//1.利用进制转换规律/** 使用无符号右移 >>>* */public static String toHex(int num) {StringBuilder sb = new StringBuilder();char[] arr = "0123456789abcdef".toCharArray();if (num ==0) return "0";while (num != 0){//计算num二进制的后四位表示的十进制数的大小int temp = num & 15;sb.append(arr[temp]);//二进制->16进制，每四位二进制转换为一位16进制num = num >>> 4;}return sb.reverse().toString();}

4、Excel表列名称（力扣168)

public String convertToTitle(int columnNumber) {StringBuilder sb = new StringBuilder();while(columnNumber > 0){int len = columnNumber % 26;//特别注意这一步，因为转换不是从0开始的if(len == 0){len = 26;columnNumber -=1;}sb.append((char)('A' + len - 1));columnNumber /= 26;}return sb.reverse().toString();}

//2.直接减1public static String convertToTitle(int columnNumber) {StringBuilder sb = new StringBuilder();while (columnNumber > 0){columnNumber --;sb.append((char)('A' + columnNumber % 26));columnNumber /= 26;}return sb.reverse().toString();}

5、阶乘后的零（力扣172)

//1.找规律/** 找到规律，输入n，表示有n个数，每隔5个数出现一个5，* 每隔25个数出现2个5，每隔125个数出现3个5...* */public static int trailingZeroes(int n) {int count = 0;//先求间隔为5的5的数量，再加上间隔为25的数量，再加上...while (n >= 5){count += (n / 5);n /= 5;}return count;}

6、二进制求和（力扣67)

//1.位运算public static String addBinary(String a, String b) {int m = a.length() - 1, n = b.length() - 1;StringBuilder sb = new StringBuilder();int count = 0;//循环相加两个字符串相同长度的低位数部分while (m >= 0 && n >= 0) {int sum = count;sum += a.charAt(m--) - '0';sum += b.charAt(n--) - '0';//进位count = sum / 2;//当前位的值sb.append(sum % 2);}// 如果 a 还没遍历完成（a串比b串长），则继续遍历添加 a 的剩余部分while (m >= 0){int sum = count + a.charAt(m--) - '0';count = sum / 2;sb.append(sum % 2);}// 如果 b 还没遍历完成（b串比a串长），则继续遍历添加 b 的剩余部分while (n >= 0){int sum = count + b.charAt(n--) - '0';count = sum / 2;sb.append(sum % 2);}//如果count不等于0 还有个进位数没加进去，需要补充if (count == 1){sb.append(count);}//反转字符串获得正常结果return sb.reverse().toString();}

7、字符串相加（力扣415)

//1.思路很简单（只不过是十进制）public static String addStrings(String num1, String num2) {StringBuilder sb = new StringBuilder();int m = num1.length() - 1,n = num2.length() - 1;int count = 0;while (m >= 0 && n >= 0){int sum = count;sum += num1.charAt(m--) - '0';sum += num2.charAt(n--) - '0';count = sum / 10;sb.append(sum % 10);}while (m >= 0) {int sum = count + num1.charAt(m--) - '0';count = sum / 10;sb.append(sum % 10);}while (n >= 0) {int sum = count + num2.charAt(n--) - '0';count = sum / 10;sb.append(sum % 10);}if (count == 1){sb.append(1);}return sb.reverse().toString();}

//2. 1的简化版public static String addStrings2(String num1, String num2) {int m = num1.length() - 1,n = num2.length() - 1;StringBuilder sb = new StringBuilder();int count = 0;//只要满足以下条件，都可以计算while (m >= 0 || n >= 0 || count != 0){//注意下面这一步int sum1 = m >= 0 ? num1.charAt(m--) - '0': 0;int sum2 = n >= 0 ? num2.charAt(n--) - '0': 0;int sum = sum1 + sum2 + count;count = sum / 10;sb.append(sum % 10);}return sb.reverse().toString();}

8、最少移动次数使数组元素相等 II（力扣462)

//1.把每个元素都变为中位数即可/** 假如数组长度为奇数2n+1 则中位数两边各有n个数* 设左边所有数和中位数的差值和为x 右边所有数和中位数的差值和为y* 则所有需要移动的次数为x+y 如果不选择中位数 例如选择中位数-1* 这样总的移动次数就变成了 >= ((x-n) + (y+n) + 1) 最好的情况下比中位数大1* 如果数组长度是偶数 有两个中位数 选择两个中位数的任何一个或* 者两个中位数的平均数 都是可以的* */public static int minMoves2(int[] nums) {int len = nums.length;Arrays.sort(nums);//选择中位数int midNum = nums[len / 2];int max = 0;for (int i = 0; i < len; i++) {max += Math.abs(nums[i] - midNum);}return max;}

9、多数元素（力扣169)

//1.排完序取中间即可public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}

//2.摩尔投票法/** 摩尔投票法：核心就是对拼消耗。玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。* */public int majorityElement2(int[] nums) {int count = 0,maxNum = 0;for(int i = 0;i < nums.length;i ++){if(count == 0){maxNum = nums[i];}if(nums[i] == maxNum){count ++;}else{count --;}}return maxNum;}

//3.哈希表（单独写一个）public static int majorityElement3(int[] nums) {//注意使用哈希表记录次数的写法Map<Integer,Integer> map = new HashMap<>();for (int i : nums){if (!map.containsKey(i)){map.put(i,1);}map.put(i,map.get(i) + 1);}int maxNum = 0,maxCount = 0;//哈希表的遍历方法for (Map.Entry<Integer,Integer> entry : map.entrySet()){if (entry.getValue() > maxCount){maxNum = entry.getKey();maxCount = entry.getValue();}}return maxNum;}

10、 3 的幂（力扣326)

//1.二分法public static boolean isPowerOfThree(int n) {//看n是否是3的幂次long left = 0,right = n,mid,guessNum;while (left <= right){mid = (left + right) >> 1;guessNum = (long) Math.pow(3, mid);if (guessNum == n){return true;}else if (guessNum < n){left = mid + 1;}else{right = mid - 1;}}return false;}

//2.找规律public static boolean isPowerOfThree2(int n) {int count = 2;while (n >= 3){n -= count;count *= 3;}return n == 1;}

//3.迭代法public static boolean isPowerOfThree3(int n) {if (n < 1){return false;}//说明n是3的倍数while (n % 3 == 0){n /= 3;}return n == 1;}

//4.找规律public static boolean isPowerOfThree4(int n) {//int类型中最大的3的幂次为1162261467return n > 0 && 1162261467 % n == 0;}

11、 除自身以外数组的乘积（力扣238)

//1.（分为左右两部分，分别计算）降低时间复杂度public static int[] productExceptSelf(int[] nums) {int len = nums.length;int[] res = new int[len];//res[i]表示i左边的数的乘积res[0] = 1;for (int i = 1; i < len; i++) {res[i] = nums[i - 1] * res[i - 1];}//乘完左边乘右边int right = 1;for (int i = len - 1; i >= 0 ; i--) {res[i] = res[i] * right;right *= nums[i];}return res;}

12、 三个数的最大乘积（力扣628)

/*1.如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；2.如果全是非正数，则最大的三个数相乘同样也为最大乘积。3.如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。*///1.先排序public static int maximumProduct(int[] nums) {Arrays.sort(nums);int len = nums.length;return Math.max(nums[len - 1] * nums[len - 2] * nums[len - 3], nums[0] * nums[1] * nums[len - 1]);}

//2.线性扫描/*在方法一中，我们实际上只要求出数组中最大的三个数以及最小的两个数，因此我们可以不用排序，用线性扫描直接得出这五个数。*/public static int maximumProduct2(int[] nums) {//min1：最小；min2：第二小int min1 = Integer.MAX_VALUE,min2 = Integer.MAX_VALUE;int max1 = Integer.MIN_VALUE,max2 = Integer.MIN_VALUE,max3 = Integer.MIN_VALUE;for (int i : nums){if (i < min1){min2 = min1;min1 = i;}else if (i < min2){min2 = i;}if (i > max1){max3 = max2;max2 = max1;max1 = i;}else if (i > max2){max3 = max2;max2 = i;}else if (i > max3){max3 = i;}}return Math.max(max1*max2*max3,min1*min2*max1);}