国庆旅行, 二维数组区块计数, 字符串展开, 2019头条笔试题

1 国庆旅行

import java.util.*;
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 res = 0;
        int maxSorces = a[0];
        for(int j=1; j < n; j++) {
            int t = maxSorces+(a[j]-j);
            
            res = Math.max(res, t);
            maxSorces = Math.max(maxSorces, a[j]+j);
        }
        System.out.println(res);
    }
}

2 二维数组区块计数

import java.util.*;
public class Main {
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    static int m, n;
    static boolean[][] st;
    static void dfs(int[][] a, int i, int j, int c) {
        st[i][j] = true;
        a[i][j] = c;
        for(int k = 0; k < 8; k++) {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0  && y < n && a[x][y] == 1 && st[x][y] == false) {
                dfs(a, x, y, c);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt(); n = sc.nextInt();
        int[][] a = new int[m][n];

        for(int i=0; i < m; i++) {
            for(int j=0; j < n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int c = 2;
        st = new boolean[m][n];
        for(int i=0; i < m; i++) {
            for(int j=0; j < n; j++) {
                if(a[i][j] != 1 || st[i][j] == true) continue;
                dfs(a, i, j, c++);
            }
        }
        System.out.println(c-2);
    }
}

3 字符串展开

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char[] c = s.toCharArray();
        
        System.out.println(dfs(c, 0, c.length-1));
    }
    static String dfs(char[] c, int s, int e) {
        if(s > e) return "";
        StringBuilder res = new StringBuilder();
        for(int i=s; i <= e; i++ ) {
            if(c[i] >= '0' && c[i] <= '9') {
                int t = c[i++]-'0'; //重复次数
                while(i <= e && c[i] >= '0' && c[i] <= '9')
                    t = t*10 + c[i++]-'0';
                int end = find(c,i+1, e); // 合适的 # 的位置
                String str = dfs(c, i+1, end-1); //重复的字符串
                for(int k=0; k < t; k++) {
                    res.append(str);
                }
                if(i != -1)  i = end; //更新i
            } else {
                res.append(c[i]);
            }
        }
        return res.toString();
    }
    static int find(char[] c, int l, int r) {
        int cnt = 1;
        for(int i=l; i <= r; i++) {
            if(c[i] == '%') cnt++;
            if(c[i] == '#') cnt--;
            if(cnt == 0) return i;
        }
        return -1;
    }
}