A了2 3 第一题没看出来是动态规划结束后做出来了

第一题对于dp[j] 意为0~j这一段字串最大的得分，通过最大的dp[i]+score(i+1,j)获得，其中i=0~j-1，score(i+1,j)为i+1~j这段字串的得分

import java.util.ArrayList;
import java.util.Scanner;

public class Beike_01 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        in.nextLine();
        String s=in.nextLine();
        System.out.println(maxScore(s));
    }
    public static int maxScore(String s){
        int[] dp=new int[s.length()];
        dp[0]=-1;
        for(int i=1;i<s.length();i++){
            dp[i]=score(s.substring(0,i+1));
            for(int j=0;j<i;j++){
                dp[i]=Math.max(dp[i],dp[j]+score(s.substring(j+1,i+1)));
            }
        }
        return dp[s.length()-1];
    }
    public static int score(String s){
        int[] cnt=new int[26];
        for(int i=0;i<s.length();i++){
            int index=s.charAt(i)-'a';
            cnt[index]++;
        }
        int score=0;
        for(int i=0;i<26;i++){
            if(cnt[i]==0) continue;
            if(cnt[i]%2==0) score++;
            else score--;
        }
        return score;
    }
}

第二题我用暴力会超时所以维护了一个动态数组来记录各位和注意输入是有界的所以多写几个判断就好了

import java.util.Scanner;

public class Beike_02 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            System.out.println(numOfModNum(l, r));
        }
    }

    public static int numOfModNum(int l, int r) {
        int[] bitI = new int[6];
        int j = 0;
        int tmp = l;
        l--;
        while (l > 0) {
            for (int i = 0; i <= j; i++) bitI[i] += l % 10;
            l /= 10;
            j++;
        }
        l = tmp;
        int ret = 0;
        for (int i = l; i <= r; i++) {
            if (i == 1000000) continue;
            if (i % 100000 == 0) {
                bitI[5]++;
                for (int k = 0; k < 5; k++) bitI[k] = bitI[5];
            } else if (i % 10000 == 0) {
                bitI[4]++;
                for (int k = 0; k < 4; k++) bitI[k] = bitI[4];
            } else if (i % 1000 == 0) {
                bitI[3]++;
                for (int k = 0; k < 3; k++) bitI[k] = bitI[3];
            } else if (i % 100 == 0) {
                bitI[2]++;
                for (int k = 0; k < 2; k++) bitI[k] = bitI[2];
            } else if (i % 10 == 0) {
                bitI[1]++;
                for (int k = 0; k < 1; k++) bitI[k] = bitI[1];
            } else bitI[0]++;
            if (i % bitI[0] == 1) ret++;


        }
        return ret;

    }

}

第三题 BFS 和普通的BFS的区别在于只有两个方向而且需要区别以下，但是不用标记是否访问过了

import java.util.Arrays;
import java.util.Scanner;

public class Beike_03 {
    static int stringSum = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String s = in.nextLine();
        String[] ans = new String[n];
        for (int i = 0; i < n; i++) ans[i] = in.nextLine();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            board[i] = ans[i].toCharArray();
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dfs(n, i, j, 0, s, board, true);
                dfs(n, i, j, 0, s, board, false);
            }
        }
        System.out.println(stringSum);
    }

    public static void dfs(int n, int i, int j, int index, String s, char[][] board, boolean direct) {
        if (index == s.length()) {
            stringSum++;
            return;
        }
        if (i < 0 || i >= n || j < 0 || j >= n) return;
        char c = s.charAt(index);
        if (board[i][j] != c) return;
        if (direct) dfs(n, i, j + 1, index + 1, s, board, direct);
        else dfs(n, i + 1, j, index + 1, s, board, direct);
    }

}

#贝壳找房实习生招聘##贝壳找房##笔经#

3.21 贝壳服务端笔试

全站热榜