http://hihocoder.com/contest/offers53/problems
题目1 : 继承顺位
建树,然后前序遍历
package l531;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
Set<String> dead=new HashSet<String>();
Map<String,List<String>> child = new HashMap<String,List<String>>();
String k=sc.next();
for(int i=0;i<n;i++) {
String t1=sc.next(),t2=sc.next();
if("birth".equals(t1)) {
String t3=sc.next();
if(!child.containsKey(t2)) child.put(t2, new ArrayList<String>());
child.get(t2).add(t3);
} else {
dead.add(t2);
}
}
List<String>res=new ArrayList<String>();
dfs(child,k,res);
for(String t:res) {
if(!k.equals(t) && !dead.contains(t))
System.out.println(t);
}
}
private static void dfs(Map<String, List<String>> child, String k, List<String> res) {
res.add(k);
if(!child.containsKey(k)) return;
for(String t:child.get(k)) {
dfs(child,t,res);
}
}
}
题目2 : hiho字符串3
递归
package l532;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++) {
long t=sc.nextLong();
System.out.println(get(100,t));
}
}
private static char get(int i, long t) {
if(i==1) return t%2==0?'i':'h';
char res=get(i-1,(t+1)/2);
if(res=='h') return t%2==0?'i':'h';
else if(res=='i') return t%2==0?'o':'i';
else return t%2==0?'h':'o';
}
}
题目3 : 最长一次上升子序列
把原问题分解成两个子问题,求0到i的最长下降子序列,和i到n的最长下降子序列,最长下降子序列用最小末尾辅助数组优化到NlogN
一直WA,不知bug在何处
package l533;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int[]a=new int[n];
for(int i=0;i<n;i++)a[i]=-sc.nextInt();
int[][] dp = new int[n][2];
for(int i=0;i<n;i++)dp[i][0]=1;
int[] lis = LIS(a), lds = LDS(a);
int max=lis[n-1];
for(int i=0;i<n-1;i++) {
max=Math.max(max, lis[i]+lds[i+1]);
}
System.out.println(max);
}
private static int[] LDS(int[] a) {
int[] b = new int[a.length];
for(int i=0;i<a.length;i++)b[i]=-a[a.length-1-i];
int[] t = LIS(b);
int[] res = new int[a.length];
for(int i=0;i<a.length;i++)res[i]=t[a.length-1-i];
return res;
}
private static int[] LIS(int[] a) {
int[] helper = new int[1+a.length]; //预留index为0
int[] res = new int[a.length];
res[0] = 1;
helper[0]=Integer.MIN_VALUE;
helper[1]=a[0];
int p=1;
for(int i=1;i<a.length;i++) {
if(a[i]>helper[p]) {
helper[++p] = a[i];
res[i] = p;
} else {
int t=Arrays.binarySearch(helper, 0, p, a[i]);
int pos=t>0?t:-(t+1);
helper[pos] = a[i];
res[i] = pos;
}
}
return res;
}
}
网友评论