字符统计

问题描述

　　给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。

输入格式

　　第一行一个数字L。
　　第二行是字符串S。
　　L大于0，且不超过S的长度。

输出格式

　　一行，题目要求的字符串。

　　输入样例1：
　　4
　　bbaabbaaaaa

　　输出样例1：
　　bbaa

　　输入样例2：
　　2
　　bbaabbaaaaa

　　输出样例2：
　　aa

数据规模和约定

　　n<=60
　　S中所有字符都是小写英文字母。

提示

　　枚举所有可能的子串，统计出现次数，找出符合条件的那个

思路：用substring截取字符串，map存字符串，valve存子串出现的次数。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //截取字符串最短长度
        int L = scanner.nextInt();
        //字符串
        String S = scanner.next();
        //统计的最多次数
        int count = 0;
        //输出结果最大子串
        String max ="";
        //创建map
        Map<String,Integer> map = new HashMap<>();
        //进入循环，截取字符串，存入map中，进行比较，输出最大子串
        for (int i = L;i <S.length();i++){//可以截取的子串长度
            for (int j=0;j<S.length()-i;j++){//从0开始
                 String str = S.substring(j,j+i);//截取j到j+i
                //首次出现
                if (map.size()==0){
                    count=1;
                    max = str;
                    map.put(str,1);
                }
                //不是首次
                else{
                    if (map.containsKey(str)){
                        //存在字符串
                        int g = map.get(str);
                        g++;
                        map.put(str,g);//更新
                        if (g>count){
                            count = g;
                            max =str;
                        }
                        else if (g == count){
                            //更新max
                            if (str.length()>max.length()){
                                max = str;
                            }
                        }
                    }
                    else {
                        map.put(str,1);
                    }
                }
            }
        }
        System.out.println(max);
    }
}

未名湖边的烦恼

问题描述

　　每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
　　每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）

输入格式

　　两个整数，表示m和n

输出格式

　　一个整数，表示队伍的排法的方案数。

样例输入

3 2

样例输出

5

数据规模和约定

　　m,n∈［0,18］

思路：汉诺塔问题，先判断是mn的大小，再进行递归

import java.util.Scanner;

public class Main {
    public static int fun(int m,int n)
    {
        if(m<n)
        {
            return 0;
        }
        else if (n==0)
        {
            return 1;
        }
        else return fun(m-1,n)+fun(m,n-1);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        System.out.println(fun(m,n));
    }
}

数字三角形

问题描述

　　（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
　　径，使该路径所经过的数字的总和最大。
　　●每一步可沿左斜线向下或右斜线向下走；
　　●1＜三角形行数≤100；
　　●三角形中的数字为整数0，1，…99；

　　.
　　（图３.１－１）

输入格式

　　文件中首先读到的是三角形的行数。

　　接下来描述整个三角形

输出格式

　　最大总和（整数）

样例输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出

30

思路：从倒数第二层开始加，加到第一层，将最大值结果累加到相应的位置，最后a【0】【0】就是最大值

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();//三角形行数
        int [][]a = new int[num][num];
        for (int i=0;i<num;i++){
            for (int j=0;j<=i;j++){
                a[i][j]=scanner.nextInt();
            }
        }
        //往上加,每一层选择最大值加
        for (int i = a.length-2; i >= 0; i--) {//从倒数第二层开始
            for (int j = 0; j < i+1; j++) {//第b层有b+1个数
                a[i][j]  += Math.max(a[i+1][j] , a[i+1][j+1]);
            }
        }
        System.out.println(a[0][0]);
    }
}