2017年校招全国统一模拟笔试(第二场)参考代码java版
感谢大神&网友的思路和部分代码的分享，下面是我总结的Java版代码，仅供参考学习共勉。
最长公共子串
分析
注意跟最长公共子序列的区别,还有空格也作为字符在匹配就好了,经典题。
参考code
import java.util.*;
public class Main {
static String str1;
static String str2;
static int[][] dp;
static int Max;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
str1 = cin.nextLine();
str2 = cin.nextLine();
int len1 = str1.length();
int len2 = str2.length();
if ( len1 < 1 || len2 < 1){
System.out.print(0);
}
dp = new int[str1.length()+1][str2.length()+1];
char[] ch1 = str1.toCharArray();
char[] ch2 = str2.toCharArray();
for ( int i = 0 ; i < len1 ; i++){
if ( ch1[i] == ch2[0]){
dp[i][0] = 1;
}
}
for ( int i = 0 ; i < len2 ; i++){
if ( ch2[i] == ch1[0]){
dp[0][i] = 1;
}
}
Max = dp[0][0];
for ( int i = 1 ; i < len1 ; i++){
for ( int j = 1 ; j < len2 ; j++){
if ( ch1[i] == ch2[j]){
dp[i][j] = dp[i-1][j-1]+1;
}
if ( dp[i][j] > Max){
Max = dp[i][j];
}
}
}
System.out.print(Max);
}
}
}
找整除
分析
裸暴力不能通过所有数据。所以调整a到一个可以被c整除的位置,然后以c为步长计算就好了。。
参考code
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
long a=cin.nextLong();
long b=cin.nextLong();
long c=cin.nextLong();
while(a%c!=0)a++;
if(a>b){
System.out.println("0");
}else{
System.out.println((b-a)/c+1);
}
}
}
}
组装三角形
分析
暴力枚举三边,然后check一下就好了。
参考code
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
int n=cin.nextInt();
int count=0;
int[] arry=new int[n];
for(int i = 0; i < n; i++){
arry[i] =cin.nextInt();
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
for(int k = j + 1; k < n; k++) {
if(check(arry[i], arry[j], arry[k])) count++;
}
}
}
System.out.println(count);
}
}
public static boolean check(int a,int b,int c){
return a < b + c && b < a + c &&
c < a + b;
}
}
最小矩阵
分析
维护X,Y坐标最大最小坐标,然后计算一发就好了。
参考code
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
int n=cin.nextInt();
int minx = 10000;
int maxx = -100000;
int miny = 100000;
int maxy = -100000;
for(int i=0;i<n;i++) {
int x=cin.nextInt();
int y=cin.nextInt();
minx = Math.min(minx,x);
maxx = Math.max(maxx,x);
miny = Math.min(miny,y);
maxy = Math.max(maxy,y);
}
System.out.println((maxx - minx)*(maxy - miny));
}
}
}
平衡数
分析
枚举断点暴力check一下就好。
参考code
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
int num=cin.nextInt();
System.out.println(solve(num));
}
}
public static String solve(int number) {
String s = String.valueOf(number);
int n = s.length();
long n1;
long n2;
for(int i = 1; i < n; i++) {
n1 = n2 = 1;
for(int j = 0; j < i; j++)
n1 *= s.charAt(j) - '0';
for(int j = i; j < n; j++)
n2 *= s.charAt(j) - '0';
if(n1 == n2)
return "YES";
}
return "NO";
}
}
字符串分类
分析
我们可以容易的观察到,两个字符串是同一类当且仅当构成他们的字符集合相同且个数也相同。于是对于每个字符串进行排序,最后再对整个字符串数组排序一下,扫一遍计算个数就好。
参考code
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
int n = cin.nextInt();
HashSet<String> list = new HashSet();
char[] ch = null;
for (int i = 0; i < n; i++) {
ch = cin.next().toCharArray();
Arrays.sort(ch);
list.add(new String(ch));
ch=null;
}
System.out.println(list.size());
}
}
}
创造新世界
分析
这道题很容易想到使用贪心。。然而。。
一种比较容易想到的贪心是尽量去满足更短的字符串。但是我们考虑2个0和5个1,要组成的字符串是{00, 011, 0111}.这样贪心的答案是1,其实我们可以组成2个。
另外一种贪心是尽量使用更多的1或者0.考虑我们当前有5个0和4个1,组成的字符串是{100000, 110, 110},这样又是不行的。。
这道题的正解是动态规划,首先预处理出需要组成的每个字符串需要0和1的个数,然后dp[i][j]表示使用i个0和j个1能组成的个数,然后对于枚举每个字符串做个转移就行。。详情看代码。
时间复杂度
O(MAX_STRINGS MAX_ZEROES MAX_ONES)
参考code
import java.util.*;
public class Main {
public static int solve(int i, int numZeroes, int
numOnes, List<String> list) {
if (i == list.size()-1) {
for (int x = 0; x < list.get(i).length(); ++x) {
if (list.get(i).charAt(x) == '1')
--numOnes;
if (list.get(i).charAt(x) == '0')
--numZeroes;
}
if ((numOnes | numZeroes) >= 0)
return 1;
else
return 0;
}
int a = solve(i + 1, numZeroes, numOnes, list);
for (int x = 0; x < list.get(i).length(); ++x) {
if (list.get(i).charAt(x) == '1')
--numOnes;
if (list.get(i).charAt(x) == '0')
--numZeroes;
}
if ((numOnes | numZeroes) < 0)
return a;
int b = 1 + solve(i + 1, numZeroes, numOnes, list);
return Math.max(a, b);
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
int x = cin.nextInt();
int n = cin.nextInt();
int m = cin.nextInt();
List<String> list = new ArrayList();
for (int i = 0; i < x; i++) {
list.add(cin.next());
}
System.out.println(solve(0, n, m, list));
}
}
}
优美的回文串
分析
对于一个字符串,我们依次替换掉字符是不影响最后结果的统计的。。
比如AJNFHALJJFJ,我们可以依次替换为a, b, c, d, e 和 f变为abcdeafbbdb,于是我们现在就挨着去生成长度为n的这样的字符串,然后暴力统计出满足条件的个数。最后计算上每个的贡献就行了。。
考虑abcdeafbbdb,第一个a可以换为26个字符的任意一个,b可以换为25个中的一个......
所以对于一个有k种字符的字符串贡献就是26 × 25 × ... × (26-k+1)。计算出答案即可
参考code
import java.util.*;
public class Main {
static long cnt[] = new long[12];
static long res = 0;
static char[] s = new char[12];
static int N;
static int M;
static int K;
public static void solve(int k, int p) {
if (k == 0) {
int tmp = 0;
for (int i = 0; i < N - M + 1; i++) {
boolean ok = true;
for (int j = 0; j < M / 2; j++) {
if (s[i + j] != s[i + M - 1 - j]) {
ok = false;
break;
}
}
if (ok)
tmp++;
}
if (tmp >= K) {
res += cnt[p];
}
return;
}
for (int i = 0; i < p + 1; i++) {
s[k - 1] = (char) ('a' + i);
solve(k - 1, Math.max(p, i + 1));
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
cnt[0] = 0;
cnt[1] = 26;
N = cin.nextInt();
M = cin.nextInt();
K = cin.nextInt();
for (int i = 2; i <= N; i++) {
cnt[i] = cnt[i - 1] * (26 - i + 1);
}
solve(N, 0);
System.out.println(res);
}
}
}
