一、质数排列(LeetCode-1175)
1.1 题目描述
1.2 解题思路
先统计出1-n中有多少个质数，得到质数个数(x)，剩下的数(y = n - x)；
使用排列组合公式得出结果
(A_x^x A_y^y)
1.3 解题代码
private static final long INF = 1000000007;
public int numPrimeArrangements(int n) {
int count = countPrime(n);
//剩余位数
int other = n - count;
long res = 1;
for (int i = 1; i <= count; i++) {
res *= i;
if(res > INF) res%=INF;
}
for (int i = 1; i <= other; i++) {
res *= i;
if(res > INF) res%=INF;
}
return (int) res;
}
/**
* 判断n个数中有多少个质数
*
* @param n
* @return
*/
private int countPrime(int n) {
int count = 0;
for (int i = 2; i <= n; i++) {
if (isPrime(i)) {
++count;
}
}
return count;
}
/**
* 判断是否是质数
*
* @param n
* @return
*/
private boolean isPrime(int n) {
if(n == 1){
return false;
}
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
二、健身计划评估(LeetCode-5174)
2.1 题目描述
2.2 解题思路
非常简单的一道题，理解清楚题意就好。只要是连续的k天，都可以。
2.3 解题代码
public class Solution {
public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
int res = 0;
int len = calories.length;
OK:
for (int i = 0; i < len; i++) {
int sum = 0;
if (i + k > len) {
continue OK;
}
for (int j = 0; j < k; j++) {
sum += calories[i + j];
}
if (sum > upper) {
res++;
}
if (sum < lower) {
res--;
}
}
return res;
}
}
三、构建回文串检测(LeetCode-5175)
3.1 题目描述
3.2 解题思路
注意审题，可以对子串进行重新排序。
思路1：所有可以统计子串中字符出现的次数。(超时)
思路2：使用动态规划的思想,定义dict[n][t]，dict[3][4]表示从第0个字符，到第3个字符的子串，第5个字符e的个数。（超时）
思路3：使用位运算的思想，只关心每个字符是奇数或偶数，定义dict[n],表示0-n的子字符串的异或运算结果。
例如：
abc的位异或运算结果为1+2+4 = 7。
abca = 1+2+4 -1 = 2+4 = 6
公式为
bitArray[i] = 1 << (strDict[i] - 'a');
if (i > 0) {
bitArray[i] ^= bitArray[i - 1];
}
最后统计子字符串异或结果中1的个数。
公式为
while (sum != 0) {
sum &= (sum - 1);
count++;
}
3.3 解题代码
思路1：下面的提交，会提示超时。
public class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
List<Boolean> res = new ArrayList<>(queries.length);
for (int i = 0; i < queries.length; i++) {
int left = queries[i][0];
int right = queries[i][1] + 1;
String subStr = s.substring(left, right);
res.add(isAlindrome(subStr, right - left, queries[i][2]));
}
return res;
}
private boolean isAlindrome(String str, int len, int k) {
if (k >= 13) {
return true;
}
if (len == 1 || len / 2 <= k) {
return true;
}
int[] z = new int[26];
for (int i = 0; i < len; i++) {
z[str.charAt(i) - 'a']++;
}
int diff = 0;
for (int i = 0; i < 26; i++) {
if (z[i] > 0 && z[i] % 2 != 0) {
diff++;
}
}
if (diff / 2 <= k) {
return true;
}
return false;
}
}
思路2：提交仍然会超时
public class Solution2 {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int len = s.length();
List<Boolean> res = new ArrayList<>(len);
int[][] dict = new int[len][26];
char[] strDict = s.toCharArray();
for (int i = 0; i < len; i++) {
if (i > 0) {
dict[i] = dict[i - 1].clone();
}
dict[i][strDict[i] - 'a']++;
}
for (int i = 0; i < queries.length; i++) {
int left = queries[i][0];
int right = queries[i][1];
int k = queries[i][2];
int diff = 0;
for (int j = 0; j < 26; j++) {
if (left == 0) {
if ((dict[right][j] & 1) != 0) {
diff++;
}
} else {
if (((dict[right][j] - dict[left - 1][j]) & 1) != 0) {
diff++;
}
}
}
res.add(diff / 2 <= k);
}
return res;
}
}
思路3：可以AC
public class Solution3 {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int len = s.length();
List<Boolean> res = new ArrayList<>(len);
int[] bitArray = new int[len];
char[] strDict = s.toCharArray();
for (int i = 0; i < len; i++) {
bitArray[i] = 1 << (strDict[i] - 'a');
if (i > 0) {
bitArray[i] ^= bitArray[i - 1];
}
}
for (int i = 0; i < queries.length; i++) {
int left = queries[i][0];
int right = queries[i][1];
int k = queries[i][2];
//子串各个位之和
int sum = 0;
if (left == 0) {
sum = bitArray[right];
} else {
sum = bitArray[right] ^ bitArray[left - 1];
}
//计算子串的位中有多少个1
int count = 0;
//k <= count/2 等价于 2*k + 1 <= count
k = 2 * k + 1;
boolean ok = true;
while (sum != 0) {
sum &= (sum - 1);
count++;
if (count > k) {
ok = false;
break;
}
}
res.add(ok);
}
return res;
}
}