不满足现状 不抱怨生活 DO MYSELF！
最近在找实习，感觉自己没有特别的优势，终于腾讯到了hr面还因为非全被打了回来。
我有时候就想，是不是我的运气太差，考研报考的时候哪一个选择变化的话都能考上全日制。
我又觉得这是上天的安排。
最后还是回归理性，是我准备的还不够，觉得差不多够了的时候就有些松懈，我文科和理科发展的也差距有些大。
理性告诉我，我应该更努力的学。
懒惰也催促我快些玩耍，放松。
我偶尔回忆经历过的一些小小的“成功”与“失败”。
我发现成功不过几年，失败也并不绝对。
现在有些焦虑，焦虑看不到后面的路。
虽然我知道，后面总有路。
全都是阶段性胜利和失败。
胜利的欢呼能振奋人心。
失败的沮丧别打垮你的信心。
祝你幸福，人们。
题目来源于CSDN，只是改编为Java版本
推荐看看简单版本：n的阶乘末尾有多少零
代码如下：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
// 寻找的质数的范围，即 [2, maxn]
static int maxn = 10010;
// 存所有质数
static int[] prime;
static boolean[] isPrime;
// a存所求数的所有质因子
static int[] a;
// b存每个质因子的个数
static int[] b;
// num是maxn范围内素数的个数
static int num, cnt;
public static void init(){
a = new int[maxn+1];
b = new int[maxn+1];
prime = new int[maxn+1];
isPrime = new boolean[maxn+1];
num = 0;cnt = 0;
// 这里是寻找 maxn 以内的质数
Arrays.fill(isPrime, true);
for (int i = 2; i <= maxn; i++) {
if(isPrime[i]){
prime[num++] = i;
for (int j = i*i; j <= maxn; j+=i) {
isPrime[j] = false;
}
}
}
}
// 找到所有可疑的质数
private static void decom(int m){
cnt = 0;
for (int i = 0; i < num; i++) {
if(prime[i] > m) break;
int d = m;
while (d%prime[i] == 0){
a[cnt] = prime[i];
b[cnt]++;
d /= prime[i];
}
if(d < m)
cnt++;
}
}
// 计算 n! 里面有多少 x，比如8!里面有7个2
private static long cal(long n, long x){
if(n == 0 || n == 1){
return 0;
}
long answer = 0;
while(n != 0){
answer += n/x;
n /= x;
}
return answer;
}
private static long solve(long n, int m){
decom(m);
long answer = Long.MAX_VALUE;
for (int i = 0; i < cnt; i++) {
long t = cal(n, a[i]);
answer = Math.min(answer, t/b[i]);
}
return answer;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
String[] tmp = in.nextLine().split(" ");
long n = Long.parseLong(tmp[0]);
int m = Integer.parseInt(tmp[1]);
init();
System.out.println(solve(n,m));
}
}
}
import java.util.HashMap;import java.util.Scanner;
public class Main {
/** * 获取字符串的全部asc值 * @param str 输入 * @return 该字符串的asc值 */ static int getStrAsc(String str){ int answer = 0; int len = str.length(); for(int i = 0; i < len; i++){ answer += (int)str.charAt(i); } return answer; }
/** * 获取 strs 位于[start, end)之间的字符串asc值之和 * @param strs 字符串数组 * @param start 包含 * @param end 不包含 * @return 区间内asc之和 */ static int getStrsAsc(String[] strs, int start, int end){ int answer = 0; for(int i = start; i < end; i++){ answer += getStrAsc(strs[i]); } return answer; }
/** * 主要计算函数 * @param name1 * @param name2 * @return */ static int calcSimilarity(String name1, String name2) { String[] name1s = name1.split(" "); String[] name2s = name2.split(" "); int len1 = name1s.length; int len2 = name2s.length;
int answer = 0; // 算一下多出去的那部分字符串的asc值 if(len2 > len1){ answer += getStrsAsc(name2s, len1, len2); }else if(len1 > len2){ answer += getStrsAsc(name1s, len2, len1); } int len = Math.min(len1, len2);
for(int i = 0; i < len; i++){ // 获得最长公共子序列的map，包含字符和出现次数 HashMap<Character, Integer> map = getMap(name1s[i], name2s[i]); answer += getStrAsc(name1s[i]); answer += getStrAsc(name2s[i]); // 加和之和减去两倍公共的就是答案了 for(Character item : map.keySet()){ answer = answer - 2 * (int)item * map.get(item); } }
return answer; }
/** * 获得name1和name2的最长公共子序列的map，包含字符和次数 * @param name1 * @param name2 * @return map */ static HashMap<Character, Integer> getMap(String name1, String name2) { HashMap<Character, Integer> answer = new HashMap<>();
int len1 = name1.length(); int len2 = name2.length(); int[][] dp = new int[len1+1][len2+1]; // 记录这个最小值从哪里来，为了反向寻找 int[][] from = new int[len1+1][len2+1];
for(int i = 1; i <= len1; i++){ for (int j = 1; j <= len2; j++) { if(name1.charAt(i-1) == name2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1] + 1; // 来自 i-1,j-1 from[i][j] = 0; }else if(dp[i-1][j] > dp[i][j-1]){ dp[i][j] = dp[i-1][j]; // 来自 i-1,j from[i][j] = 1; }else{ dp[i][j] = dp[i][j-1]; // 来自 i,j-1 from[i][j] = 2; } } } int max = dp[len1][len2]; // 反向寻找 while(max > 0){ int nexti = len1; int nextj = len2; // 下面的判断是找该节点来自哪里 if(from[len1][len2] == 0){ nexti--; nextj--; }else if(from[len1][len2] == 1){ nexti--; }else { nextj--; }
// 相同说明没贡献，找到第一个对最长序列有贡献的点就是最后一个相同的点 if(dp[len1][len2] == dp[nexti][nextj]){ len1 = nexti; len2 = nextj; }else { answer.put(name1.charAt(len1-1), answer.getOrDefault(name1.charAt(len1-1), 0)+1); len1 = nexti; len2 = nextj; max--; } }
return answer; }
public static void main(String[] args){ Scanner in = new Scanner(System.in); while (in.hasNextLine()) { String name1 = in.nextLine(); String name2 = in.nextLine();
int sum = calcSimilarity(name1, name2); System.out.println(sum); } }}