周赛326总结
感谢力扣，第一次全部做完，耗时43分37秒，很满足了，虽然是题比较简单，新的一年继续努力呀！！
计能整除数字的位数
Given an integer num, return the number of digits in num that divide num.
An integer val divides nums if nums % val == 0.
- 思路：通过整除和取余的运算将num的每个数位取出，判断是否能整除num，统计能够整除的数位个数返回即可
- 实现
class Solution { public int countDigits(int num) { int ans = 0; int cur = num; while(cur / 10 != 0){ int x = cur % 10; if (num % x == 0){ ans++; } cur /= 10; } if (num % cur == 0){ ans++; } return ans; } }
。复杂度
- 时间复杂度：O ( n ) ，n 为num的数位个数
- 空间复杂度：O ( 1 )
- 别人的代码就是好看
// arignote class Solution { public int countDigits(int num) { int count = 0; for (int i = num; i > 0; i /= 10) { count += num % (i % 10) > 0 ? 0 : 1; } return count; } }
数组乘积中的不同质因数数目
Given an array of positive integers nums, return the number of distinct prime factors in the product of the elements of nums.
Note that:
- A number greater than 1 is called prime if it is divisible by only 1 and itself.
- An integer val1 is a factor of another integer val2 if val2 / val1 is an integer.
- 思路：求出数组nums中每个数的质因数，并存储在set集合中，最终返回set集合的大小
- 实现
class Solution { public int distinctPrimeFactors(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums){ for (int i = 2; i <= num; i++){ while (num >= i && num % i == 0 && isPrime(i)){ set.add(i); num /= i; } } } return set.size(); } public boolean isPrime (int x){ if (x <= 1){ return false; } for (int i = 2; i * i <= x; i++){ if (x % i == 0){ return false; } } return true; } }
。复杂度
- 时间复杂度：O(nU)，n为nums的长度，U=max(nums)
- 空间复杂度：O ( U /l o g U ) ,最多有U/ l o g U 个质因数
- 优化：不需要判断i是否是质因数，因为num已经用前面的i 分解了，所以从小到大用i 能够整除num时，i一定是num的质因数
class Solution { public int distinctPrimeFactors(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums){ for (int i = 2; i <= num; i++){ while (num >= i && num % i == 0){ set.add(i); num /= i; } } } return set.size(); } }
。复杂度
- 时间复杂度：
，n 为nums的长度,U=max(nums) - 空间复杂度：O ( U /l o g U ) ,最多有U /l o g U个质因数
将字符串分割成值不超过 K 的子字符串
You are given a string s consisting of digits from 1 to 9 and an integer k.
A partition of a string s is called good if:
- Each digit of s is part of exactly one substring.
- The value of each substring is less than or equal to k.
Return the minimum number of substrings in a good partition of s. If no good partition of s exists, return -1.
Note that:
- The value of a string is its result when interpreted as an integer. For example, the value of "123" is 123 and the value of "1" is 1.
- A substring is a contiguous sequence of characters within a string.
- 思路：贪心划分子字符串，保证每个子字符串的长度为所能够到达的最大长度，假设k的位数为n，子字符串的左边界为l ll，如果s.substring(l, l+n)对应的整数大小小于等于k，那么该子字符串即为最优子字符串；反之，s.substring(l, l+n - 1)为最优子字符串
。局部最优：每个子字符串的长度为最大长度
。全局最优：子字符串个数最少
- 实现
注意右边界的处理和k kk小于10的处理
。保证右边界小于等于字符串长度，如果右边界超出字符串长度，那么直接取最大值
。如果k小于10时，可能出现不能划分好字符串的情况，即字符串中的单个数值大于k时，此时返回-1
class Solution { public int minimumPartition(String s, int k) { int n = 1; int temp = k; while (temp / 10 > 0){ temp /= 10; n++; } int l = 0, m = s.length(), ans = 0; while (l < m){ int r = l + n <= m ? l + n : m; if (Integer.parseInt(s.substring(l,r)) <= k){ l += n; ans++; }else if(n == 1){ return -1; }else{ l += n - 1; ans++; } } return ans; } }
。复杂度
- 时间复杂度：O(m+logk)，n 为k的数位数量，m 为s的长度
- 空间复杂度：O ( 1 )
- 在遍历的过程中计算子字符串的整数值，不使用Integer.parseInt
// arignote class Solution { public int minimumPartition(String s, int k) { int count = 0; for (int i = 0; i < s.length(); count++) { if (s.charAt(i) - '0' > k) { return -1; } for (long curr = 0; i < s.length() && (curr = curr * 10 + s.charAt(i) - '0') <= k; i++) { } } return count; } }
。复杂度
- 时间复杂度：O(m)，n 为k的数位数量，m 为s的长度
- 空间复杂度：O ( 1 )
范围内最接近的两个质数
Given two positive integers left and right, find the two integers num1 and num2 such that:
- left <= nums1 < nums2 <= right .
- nums1 and nums2 are both prime numbers.
- nums2 - nums1 is the minimum amongst all other pairs satisfying the above conditions.
Return the positive integer array ans = [nums1, nums2]. If there are multiple pairs satisfying these conditions, return the one with the minimum nums1 value or [-1, -1] if such numbers do not exist.
A number greater than 1 is called prime if it is only divisible by 1 and itself.
- 思路：求出区间[left,right]范围的所有质数，并使用变量pre记录前一个质数的大小，dis记录最小质数距离，如果当前质数与前一个质数的距离小于当前最小距离，那么更新结果集。
- 实现
class Solution { public int[] closestPrimes(int left, int right) { int[] res = {-1, -1}; int pre = -1; int dis = Integer.MAX_VALUE; for (int i = left; i <= right; i++){ if (isPrime(i)){ if (pre != -1 && i - pre < dis){ dis = i - pre; res[0] = pre; res[1] = i; } pre = i; } } return res; } public boolean isPrime(int x){ if (x == 1){ return false; } for (int i = 2; i * i <= x; i++){ if (x % i == 0){ return false; } } return true; } }
。复杂度
- 时间复杂度：O(nlogn)
- 空间复杂度：O ( 1 )
- 优化：避免重复判断一个数是否是质数，可以提前打表，由于整数范围为[2,100000]，可以将该范围内的数进行预处理，然后找到[left,right]范围内的质数，找到相邻的距离最小的两个质数进行返回
// arignote class Solution { private static ArrayList<Integer> list = new ArrayList<>() { { Boolean[] prime = new Boolean[1000000]; for (int i = 2; i < 1000000; i++) { if (prime[i] == null) { add(i); for (int j = 2 * i; j < 1000000; j += i) { prime[j] = false; } } } } }; public int[] closestPrimes(int left, int right) { int[] result = { -1, -1 }; for (int i = 1; i < list.size(); i++) { if (list.get(i - 1) >= left && list.get(i) <= right && (result[0] < 0 || list.get(i) - list.get(i - 1) < result[1] - result[0])) { result = new int[] { list.get(i - 1), list.get(i) }; } } return result; } }
