题目一

描述

输入一个长度为4的倍数的字符串，字符串中仅包含WASD四个字母。

将这个字符串中的连续子串用同等长度的仅包含WASD的字符串替换，如果替换后整个字符串中WASD四个字母出现的频数相同，那么我们称替换后的字符串是“完美走位”。

求子串的最小长度。

示例

输入：
WASDAASD输出：
1说明：
将第二个A替换为W，即可得到完美走位  

输入：
AAAA输出：
3说明：
将其中三个连续的A替换为WSD，即可得到完美走位  

思路与代码

这题我并没有AC，用例通过率95.45%，确定是效率问题，经过改进后时间复杂度从O(n^{3)降低为O(n}2)。

首先确定一下如何判断一个子串被替换后可以让整个字符串变成“完美走位”。

假设要替换的子串长度为m，子串前长度n1，子串后长度n2，：

在最开始，用HashMap统计整个字符串中WASD的出现频数，得到map

然后用HashMap统计m子串中WASD的出现频数，得到insideMap

用map各个键的值减去insideMap中对应键的值，可得n1+n2中WASD频数映射，写回insideMap

找到insideMap中最大的值，乘四然后减去所有值的和，就是替换m后成为完美走位需要的m的长度needSteps

如果m的长度大于等于needSteps，m经过替换后整个字符串可以成为完美走位。

最简单的方式就是暴力枚举，检查各个m是否符合要求，取最短的m的长度，即可得到答案：

/*** 求需要替换的最小连续走位长度* 完美走位：WASD四个字母出现次数相同* 输入步数为4的倍数*/
public class P1 {private static Scanner scanner=new Scanner(System.in);public static void main(String[] args) {String str=scanner.nextLine();//获取字符串本身的统计信息HashMap<Character,Integer> map=getAmountMap(str);//如果已经是完美走位，输出0，不检查if(map.get('A')==map.get('S')&&map.get('S')==map.get('W')&&map.get('W')==map.get('D')){System.out.println(0);return;}//记录已知的可行最小替换长度int minLen=str.length();//对每一个字母开头的序列进行检查for(int i=0;i<str.length();i++){//对每一个字母开头往后长度小于等于minLen的序列，检查可否替换后形成完美走位for(int j=0;j<minLen&&i+j<str.length();j++){//获取这段字符串中的统计HashMap<Character,Integer> insideMap=getAmountMap(str.substring(i,i+j+1));//得到源字符串减去字串后其他部分（外串）的统计信息insideMap.put('A',map.get('A')-insideMap.get('A'));insideMap.put('S',map.get('S')-insideMap.get('S'));insideMap.put('W',map.get('W')-insideMap.get('W'));insideMap.put('D',map.get('D')-insideMap.get('D'));//获取外串需要多少步来补（这里可以优化，对字符串中所有元素，建立两个map，其中对应map记录了每个元素左边和右边的统计信息）int needSteps=getNeedSteps(insideMap);//如果子串长度可以用于补足外串的差，那就可行if(needSteps==j+1){minLen=j+1;}}}System.out.println(minLen);}/*** 获取需要多少步来补* @param insideMap* @return*/private static int getNeedSteps(HashMap<Character, Integer> insideMap) {//获取四个步int a=insideMap.get('A');int s=insideMap.get('S');int d=insideMap.get('D');int w=insideMap.get('W');//获取最长的步int max=s;if(max<d){max=d;}if(max<w){max=w;}if(max<a){max=a;}return max*4-a-s-d-w;}/*** 获取一个字符串中四个字母的数量映射* @return*/private static HashMap<Character,Integer> getAmountMap(String str){//统计出wasd在字符串中各自的数量HashMap<Character,Integer> map=new HashMap<>();map.put('A',0);map.put('S',0);map.put('W',0);map.put('D',0);char c;for(int i=0;i<str.length();i++){c=str.charAt(i);map.put(c,map.get(c)+1);}return map;}
}

上述代码把统计子串WASD频数的操作放到了两个for循环中，而统计子串WASD本身时间复杂度为O(n)，因此整体时间复杂度上升到o(n^3)。

因为我们其实不需要知道子串中WASD频数，只要知道n1和n2的WASD频数，所以可以把统计频数的操作放到main函数中for循环的外部，记录下所有位置左边和右边WASD频数映射，到时候在两个for循环内直接取值即可：

/*** 求需要替换的最小连续走位长度* 完美走位：WASD四个字母出现次数相同* 输入步数为4的倍数* 优化时间复杂度为O(n^2)*/
public class P1_AD {private static Scanner scanner=new Scanner(System.in);public static void main(String[] args) {String str=scanner.nextLine();//获取字符串本身的统计信息HashMap<Character,Integer> map=getAmountMap(str);//如果已经是完美走位，输出0，不检查if(map.get('A')==map.get('S')&&map.get('S')==map.get('W')&&map.get('W')==map.get('D')){System.out.println(0);return;}//统计字符串中每个位置左边和右边WASD频数列表ArrayList<HashMap<Character,Integer>> leftMap=new ArrayList<>();ArrayList<HashMap<Character,Integer>> rightMap=new ArrayList<>();for (int i = 0; i < str.length(); i++) {leftMap.add(getAmountMap(str.substring(0,i)));rightMap.add(getAmountMap(str.substring(i+1)));}//记录已知的可行最小替换长度int minLen=str.length();//对每一个字母开头的序列进行检查for(int i=0;i<str.length();i++){//对每一个字母开头往后长度小于等于minLen的序列，检查可否替换后形成完美走位for(int j=0;j<minLen&&i+j<str.length();j++){//得到源字符串减去字串后其他部分（外串）的统计信息HashMap<Character,Integer> otherMap=new HashMap<>();otherMap.put('A',leftMap.get(i).get('A')+rightMap.get(i+j).get('A'));otherMap.put('S',leftMap.get(i).get('S')+rightMap.get(i+j).get('S'));otherMap.put('W',leftMap.get(i).get('W')+rightMap.get(i+j).get('W'));otherMap.put('D',leftMap.get(i).get('D')+rightMap.get(i+j).get('D'));//获取外串需要多少步来补（这里可以优化，对字符串中所有元素，建立两个map，其中对应map记录了每个元素左边和右边的统计信息）int needSteps=getNeedSteps(otherMap);//如果子串长度可以用于补足外串的差，那就可行if(needSteps==j+1){minLen=j+1;}}}System.out.println(minLen);}/*** 获取需要多少步来补* @param insideMap* @return*/private static int getNeedSteps(HashMap<Character, Integer> insideMap) {//获取四个步int a=insideMap.get('A');int s=insideMap.get('S');int d=insideMap.get('D');int w=insideMap.get('W');//获取最长的步int max=s;if(max<d){max=d;}if(max<w){max=w;}if(max<a){max=a;}return max*4-a-s-d-w;}/*** 获取一个字符串中四个字母的数量映射* @return*/private static HashMap<Character,Integer> getAmountMap(String str){//统计出wasd在字符串中各自的数量HashMap<Character,Integer> map=new HashMap<>();map.put('A',0);map.put('S',0);map.put('W',0);map.put('D',0);char c;for(int i=0;i<str.length();i++){c=str.charAt(i);map.put(c,map.get(c)+1);}return map;}
}

优化后时间复杂度为O(n^2)，空间复杂度为O(n)

题目二

描述

在一行中输入一个字符串数组，如果其中一个字符串的所有以索引0开头的子串在数组中都有，那么这个字符串就是潜在密码，在所有潜在密码中最长的是真正的密码，如果有多个长度相同的真正的密码，那么取字典序最大的为唯一的真正的密码，求唯一的真正的密码。

示例

输入：
h he hel hell hello o ok n ni nin ninj ninja输出：
ninja说明：
按要求，hello、ok、ninja都是潜在密码。检查长度，hello、ninja是真正的密码。检查字典序，ninja是唯一真正密码。

输入：
a b c d f输出：
f

思路与代码

已AC

因为在检查是否是潜在密码时需要进行很多次查找操作，所以可以先将所有字符串加入一个HashSet集合，查找字符串时的时间复杂度就降低到O(1)。

然后检查所有字符串是否是密码，对于是密码的，与之前遍历获得的密码比较长度和字典序，取最大的为唯一的真正的密码。

/*** 获取密码*/
public class P2 {private static Scanner scanner=new Scanner(System.in);public static void main(String[] args) {//获取输入的字符串String str=scanner.nextLine();//分割字符串String[] strs=str.split(" ");//将所有字符串放入哈希集合HashSet<String> wordSet=new HashSet<>();for (String s : strs) {wordSet.add(s);}//确认的密码String theWord="";//按顺序检查每一个词for (String s : strs) {//检查这个词是否是密码boolean isWord=true;for(int i=1;i<s.length();i++){String curSubStr=s.substring(0,i);if(!wordSet.contains(curSubStr)){isWord=false;break;}}//符合密码条件，则进一步检查if(isWord){//如果比之前密码更长，保留当前密码if(s.length()>theWord.length())theWord=s;//如果和之前密码长度一样，并且字典排序更大，也保留当前密码if(s.length()==theWord.length()&&s.compareTo(theWord)>0){theWord=s;}}}//输出结果System.out.println(theWord);}
}

时间复杂度O(n^2)

题目三

描述

简化版羊、狼、农夫过河。

羊、狼、农夫都在岸边，农夫有一艘容量固定的船，要求求出不损失羊情况下将全部羊和狼运到对岸需要的次数。

农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊。

只计算农夫去对岸的次数，回程时农夫不会运送羊和狼。

示例

输入：
5 3 3输出：
3说明：
第一次运2只狼
第二次运3只羊
第三次运2只羊和1只狼

输入：
5 4 1输出：
0说明：
如果找不到不损失羊的运送方案，输出0

思路与代码

使用递归和深度优先搜索，对每一种不损失羊的情况进行检查，即农夫离岸后羊比狼多，若找到比记录下来的次数更少的方案，记下来，最后输出结果。

/*** m只羊、n只狼、x容量* 农夫在或羊比狼多时，狼不会攻击，离岸时*/
public class P3 {/*** 运输时*  出发的一边，岸上的羊要比狼多*  船上只要不超出容量即可*  送到的**/private static Scanner scanner=new Scanner(System.in);//记录最少运输次数private static int minTimes=Integer.MAX_VALUE;public static void main(String[] args) {String str=scanner.nextLine();String[] strs=str.split(" ");int m0=Integer.parseInt(strs[0]);//羊int n0=Integer.parseInt(strs[1]);//狼int x=Integer.parseInt(strs[2]);//船int m1=0;int n1=0;getTransportTime(m0,n0,x,m1,n1,0);//如果步数等于初始化数字，那么代表没找到运输方法（理论上存在bug，需要优化）if(minTimes==Integer.MAX_VALUE){System.out.println(0);}else{System.out.println(minTimes);}}/*** 递归查找可行方案* @param m0* @param n0* @param x* @param m1* @param n1* @param times* @return*/private static int getTransportTime(int m0, int n0, int x, int m1, int n1,int times) {//若可以一次性运走，结束了，注意等于号。。。if(x>=m0+n0){if(times+1<minTimes){minTimes=times+1;}return times+1;}//尝试运一部分狼一部分羊//要上船的羊数量不可以超过岸上数量、也不可以超过船的容量for(int i=0;i<=m0&&i<=x;i++){//要上船的狼的数量不可以超过岸上数量、也不可以超过船装了羊后的剩余的容量for(int j=0;j<=n0&&i+j<=x;j++){//不可以不运if(i+j==0){continue;}//船离岸后，原来这岸，要么没有羊，要么羊比狼多，才可以运；对岸也要检查，不考虑回程带动物if((m0-i==0||m0-i>n0-j)&&(m1+i==0||m1+i>n1+j)){//运一次int result=getTransportTime(m0-i,n0-j,x,m1+i,n1+j,times+1);//如果获取了结果，和minTime比较，但是不结束，继续检查if(result<minTimes&&result!=0){minTimes=result;}}}}//没有方案了。。返回0return 0;}
}