1、距离的总和
题目描述:
定义两个大于2的偶数之间的距离,为这两个数之间质数的个数。从小到大输入n个大于2的偶数,输出所有数两两之间距离的总和(应该有n*(n-1)/2个距离,输出总和就好)。
输入
第一行是输入偶数的个数,最小为2,最大可能到几万。之后每行为一个偶数,最小是4,最大可能是几百万,不重复的升序排列。
输出
输出数据两两间距离的总和,这应该是一个不小于0的整数。
样例输入
3
4
6
12
样例输出
6
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] arg) { Scanner scan = new Scanner(System.in); while (scan.hasNext()) { int n = scan.nextInt(); int[] numbers = new int[n]; for (int i = 0; i < n; i++) { numbers[i] = scan.nextInt(); } System.out.println(solve(numbers,n)); } scan.close(); } private static long solve(int[] numbers, int n) { boolean[] isPrimes = new boolean[numbers[n-1] + 1]; Arrays.fill(isPrimes, true); getPrimes(isPrimes, numbers[n - 1]); long ans = 0; for (int i = 0, len = n - 1; i < len; i++) { int low = numbers[i]; int high = numbers[i + 1]; long count = 0; for (int j = low + 1; j < high; j += 2) { if (isPrimes[j]) { ++count; } } ans += count * (i + 1) * (n - 1 - i); } return ans; } private static void getPrimes(boolean[] isPrimes, int n) { isPrimes[0] = false; isPrimes[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrimes[i]) { for (int j = i * i; j <= n; j += i) { isPrimes[j] = false; } } } } }
2、 一个字符串的最大回文前缀长度
题目描述:
求一个字符串的最大回文前缀长度。回文是指正反方向读起来都一样的字符串,比如“abcdcba”就是一个回文。
输入
一个文本文件,至少包含一个字节。每个字节是一个字符。最大长度可能有几十万字节。
输出
最大回文前缀的长度。
样例输入
sogou
样例输出
1
import java.util.Scanner; public class Main { public static void main(String[] arg) { Scanner scan = new Scanner(System.in); while (scan.hasNext()) { String str = scan.nextLine(); char[] chs = str.toCharArray(); System.out.println(maxPrefixPlindrome(chs)); } scan.close(); } private static int maxPrefixPlindrome(char[] chs) { int length = chs.length; for (int i = length - 1; i > 0; i--) { if (isPlindrome(chs,0,i)){ return i + 1; } } return 1; } private static boolean isPlindrome(char[] chs,int low, int high) { while (low <= high) { if (chs[low] != chs[high]) { return false; } ++low; --high; } return true; } }