问题
Description
众所周知，右鸽喜欢在深夜多人运动（别想歪了哈哈哈）。他对陪同运动的伙伴们的资产有着严格的要求，如果伙伴们的资产形成的序列是好序列，他才能跑步，否则只能散步。
下面给好序列下个定义：一个整数序列，存在唯一元素。即对于序列a，存在一个a[i]使得任意其他元素都不等于a[i],即a[i] != a[j] for 1 <=j<=len(a)，j != i;
给出一个序列A，如果A的全部连续子序列都是好序列，才能说伙伴们的资产形成的序列是好序列，那么右鸽才能跑步，否则右鸽只能散步。
Input
输入描述：
第一行为整数n(1 <= n <= )，表示陪同右鸽一起运动的伙伴人数。
第二行为n个整数a[i]（0<=a[i] <= )，描述他们的资产。
Output
输出描述：
一行字符串，如果右鸽能跑步，则输出:"paobu"
否则输出："sanbu"
输入
5
1 2 3 2 1
输出：
paobu
思路
面对一个庞大的串(数组)，我们需要拆分为左子串、右子串，
- 若左字串为好且右字串为好，拆分规则为中间截断。
- 若
条件1满足再进行判断整个串为不为好。 - 若
条件1不满足，则直接返回。
代码解释
主要是使用递归，我很想使用while来实现，无奈技术太菜，也没有时间。
首先我们定义一个判断函数，接收参数s为开始，e为结束，功能是判断从s开始到e的字符是否是为好。
private static boolean judge(int s, int e) {
描写递归出口，当只有一个字符的时候，这个字符必然等于他自己。
if (s == e) {
return true;
}
if(e == s + 1){
return a[e] != a[s];
}
又递归调用，判断自己的子字符串
int end = ((e+1) / 2) < s? e :(e+1) / 2;
int endMin = Math.min(end + 1, e);
if (!judge(s, end) || !judge(endMin, e)) {
return false;
}
以上都没返回false的话，则进行自己本身的判断
//判断整个大子串
boolean result = true;
Set<Integer> set = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();
if(flag.get(end)!=null && flag.get(e)!=null){//若开头和结尾已经有记录了
set.addAll(flag.get(end));
set.removeAll(flag.get(e));
return set.size() >= 1;//则比较两个集合里面的元素是否相同
}
for (int i = s; i <= e; i++) {
int b = map.get(a[i]) == null ? 0 : map.get(a[i]);
++b;
map.put(a[i], b);
set.add(a[i]);
}
if (set.size() < e - s + 1) {//若有重复的
result = false;
Set<Integer> onlyOneSet = new HashSet<>();//记录没有重复的值
for (Integer i : set) {
if (map.get(i) < 2) {//若存在一个数是唯一的
result = true;
onlyOneSet.add(i);
}
}
if( result )
flag.put(e,onlyOneSet);
}else{
flag.put(e,set);
}
return result;
}
解题代码
package bird;
import java.util.*;
public class Solution {
static int[] a;
static Map<Integer, Set<Integer>> flag;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
a = new int[n + 1];
flag = new HashMap<>();
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt();
}
long startTime = System.currentTimeMillis();
String ans0 = "paobu";
String ans1 = "sanbu";
boolean j1 = judge(1, (n + 1) / 2);
if (!j1) {
System.out.println(ans1);
long endTime = System.currentTimeMillis();
System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
return;
}
boolean j2 = judge((n + 1) / 2 + 1, n);
if (!j2) {
System.out.println(ans1);
long endTime = System.currentTimeMillis();
System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
return;
}
boolean j3 = judge(1, n);
if (!j3) {
System.out.println(ans1);
long endTime = System.currentTimeMillis();
System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
return;
}
System.out.println(ans0);
long endTime = System.currentTimeMillis();
System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
}
private static boolean judge(int s, int e) {
if (s == e) {
return true;
}
if(e == s + 1){
return a[e] != a[s];
}
int end = ((e+1) / 2) < s? e :(e+1) / 2;
int endMin = Math.min(end + 1, e);
if (!judge(s, end) || !judge(endMin, e)) {
return false;
}
//判断整个大子串
boolean result = true;
Set<Integer> set = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();
if(flag.get(end)!=null && flag.get(e)!=null){//若开头和结尾已经有记录了
set.addAll(flag.get(end));
set.removeAll(flag.get(e));
return set.size() >= 1;//则比较两个集合里面的元素是否相同
}
for (int i = s; i <= e; i++) {
int b = map.get(a[i]) == null ? 0 : map.get(a[i]);
++b;
map.put(a[i], b);
set.add(a[i]);
}
if (set.size() < e - s + 1) {//若有重复的
result = false;
Set<Integer> onlyOneSet = new HashSet<>();//记录没有重复的值
for (Integer i : set) {
if (map.get(i) < 2) {//若存在一个数是唯一的
result = true;
onlyOneSet.add(i);
}
}
if( result )
flag.put(e,onlyOneSet);
}else{
flag.put(e,set);
}
return result;
}
//拆分为左子串、右子串
//若左字串为好且右字串为好，则判断整个串为不为好
//
}
网友评论