第7章 数组下标更多应用

1、统计字符数2

算法分析

• 1、由于小写字母和大写字母字符相差32，将所有的小写字母统一变成大写字母
• 2、计算所有字母的数量，算出最大值，再枚举所有字母，若输出第一个字母数量是最大值的字母

时间复杂度

Java 代码

import java.util.Scanner;

public class Main{
    static int N = 100;
    static int[] sum = new int[N];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        char[] temp = scan.next().toCharArray();
        int len = temp.length;
        for(int i = 0;i < len;i ++)
        {
            if(temp[i] - 'a' >= 0 && temp[i] - 'z' <= 0)
                temp[i] = (char)(temp[i] - 32);
        }
        int ans = 0;
        for(int i = 0;i < len;i ++)
        {   
            int x = (int)(temp[i]); 
            sum[x] ++;
        }
        int res = 0;
        for(int i = 0;i < 100;i ++) res = Math.max(res, sum[i]);
        for(int i = 0;i < 100;i ++)
        {
            if(sum[i] == res)
            {
                System.out.print(sum[i] + " " + (char)(i));
                break;
            }
        }
    }
}

import java.util.Scanner;

public class Main {
    static int[] ans = new int[100];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next().trim();
        int n = s.length();
        for(int i = 0;i < n;i ++)
        {
            char t;
            if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') t = s.charAt(i);
            else
            {
                t = (char)(s.charAt(i) - ('a' - 'A'));
            }
            ans[t] ++;
        }
        int maxv = 0;
        for(int i = 'A';i <= 'Z';i ++)
            maxv = Math.max(maxv, ans[i]);
        
        
        for(int i = 'A';i <= 'Z';i ++)
        {
            if(maxv == ans[i])
            {
                System.out.println(ans[i] + " " + (char)(i) );
                break;
            }
        }
    }
}

2、蒜头君的越野比赛

算法分析

这题主要就是考前缀和 和输入输出，需要熟练输入和输出
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));

时间复杂度

Java 代码

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{
    static int N = 100010;
    static long[] f = new long[N];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int k = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().split(" ");
        for(int i = 2;i <= n;i ++) 
        {
            int x = Integer.parseInt(s2[i - 2]);
            f[i] = f[i - 1] + x;
        }
        while(k -- > 0)
        {
            String[] s3 = br.readLine().split(" ");
            int a = Integer.parseInt(s3[0]);
            int b = Integer.parseInt(s3[1]);
            if(k != 0) log.write(f[b] - f[a] + " ");
            else log.write(f[b] - f[a] + "");
        }
        log.close();
    }
}

3、多项式相乘

算法分析

要求的东西过小，只有两项乘两项，直接写暴力，理清楚下标是幂的次数，值是系数

时间复杂度

Java 代码

import java.util.Scanner;

public class Main{
    static int N = 55;
    static int[] f = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a1 = scan.nextInt();
        int a2 = scan.nextInt();
        int b1 = scan.nextInt();
        int b2 = scan.nextInt();
        int c1 = scan.nextInt();
        int c2 = scan.nextInt();
        int d1 = scan.nextInt();
        int d2 = scan.nextInt();
        
        f[a2 + c2] += a1 * c1;
        f[a2 + d2] += a1 * d1;
        f[b2 + c2] += b1 * c1;
        f[b2 + d2] += b1 * d1;
        
        for(int i = 50;i >= 0;i --)
        {
            if(f[i] != 0)
            {
                System.out.println(f[i] + " " + i);
            }
        }
    }
}