美文网首页
hihocoder53

hihocoder53

作者: GoDeep | 来源:发表于2018-04-04 20:18 被阅读0次

    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;
        }
    }
    
    

    相关文章

      网友评论

          本文标题:hihocoder53

          本文链接:https://www.haomeiwen.com/subject/fdelhftx.html