算法题 日常记录

题目：0-999999之间的所有整数数字中，任何一位都不包括数字3的数字总数有多少个？
答案：9+8*9+8*9*9+8*9*9*9+8*9*9*9*9+8*9*9*9*9*9

题目：25匹马5个跑道，怎样选出最快的5匹来？最少的次数。如果选3次呢？
答案：选5个最少8次，最多9次；
选3个，只需要比较7次。

题目：64匹马，8条跑道，分几次可以选出最快的4匹？
答案：11次。

首先：分为9组分别进行比赛后得到每一组的比赛名次，比赛场次：9；
然后：将9组的每组第一名比赛，得到第一名，肯定是所有马的第一名；比赛场次：1
最后：剩下马中有资格角逐前四名的马有A2、A3、A4、B1、B2、B3、C1、C2、D1，刚好有9匹马，在进行一场比赛就可以了，比赛场次：1

从数组中找出连续的最大值
如输入1,-3,5,5,-6,-2,-7 输出10
我自己写的maxSum()方法只通过百分之50
舍友的maxSum2()方法全通过了 不知道我漏掉哪里了 先记录一下

… 理解了 我输出的时候从0开始了 真是蠢哭自己 如果最大是负数就输出错了 让max从a0开始就好了 一个教训…

public class xiechengoj1 {
    
     static int maxSum(int[] a) {
         int x[]=new int[a.length];
         x[0]=a[0];
         for(int i=1;i<a.length;i++){
             if(a[i]>x[i-1]+a[i]){
                 x[i]=a[i];
             }else
                 x[i]=x[i-1]+a[i];
         }
         int max=0;
         for(int i=0;i<a.length;i++){
             if(x[i]>max)
                 max=x[i];
         }
         for(int i=0;i<a.length;i++)
             System.out.print(x[i]+" ");
         return max;
        }
     
     static int maxSum2(int[] a) {
         int temp=a[0];
         int sum=a[0];
         for(int i=1;i<a.length;i++){
             if(temp<0){
                temp=0;
            }
            temp+=a[i];
            if(sum<temp)
                sum=temp;
         }
         return sum;
     }
    /******************************结束写代码******************************/


        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            
            String s=sc.nextLine();
            String [] x=s.split(" ");
            int [] a=new int[x.length];
            for(int i=0;i<a.length;i++)
                a[i]=Integer.parseInt(x[i]);
            int res;
            
            res = maxSum(a);
            System.out.println(String.valueOf(res));  
            System.out.println(maxSum2(a)); 
//5 5 5 9 -23 -34 3 399 -444 3
        }
    
}

从一堆数里选出第一个只出现一次的数，时间复杂度0(n)
如1,1,2,2,3,3,4,5,4,8 输出 5

public class xiechengoj2 {

        public static void main(String[] args){
            Scanner in = new Scanner(System.in);
            String s=in.nextLine();
            String s1[]=s.split(",");
            HashSet<Integer> set=new HashSet<>();
            HashMap<Integer, Integer> map=new HashMap<>();
            int a[]=new int[s1.length];
            for(int i=0;i<s1.length;i++)
                a[i]=Integer.parseInt(s1[i]);
            for(int i=0;i<s1.length;i++){
                if(set.add(a[i])){
                    map.put(a[i],0);
                }else{
                    map.put(a[i],1);
                }
            }
            Iterator iter = map.entrySet().iterator();
            while(iter.hasNext()){
                Map.Entry entry=(Map.Entry)iter.next();
                int value=(int) entry.getValue();
                if(value==0){
                    System.out.println((int) entry.getKey());                   
                    break;
                }
            }
    
        }
}