首页 > 科大讯飞(8.29)-第一次ak~
头像
baker,
编辑于 2020-08-29 21:33
+ 关注

科大讯飞(8.29)-第一次ak~

今晚做了科大讯飞的笔试题,题型是4道编程题,时长为120分钟,第一次ak,无比激动~
1. 礼物价值的最大化
这是剑指offer的一道关于动态规划的题目,前不久才做过,所以很快就做出来了
/**
 * @Author Baker.chen
 * @create 2020/8/29 20:31
 *
 * 礼物价值最大化
 *  思路:创建一个二维数组dp[][],dp[i][j]代表的是从二维数组的左上角元素走到dp[i][j]这个单元格的最大价值
 *  状态转移方程为:dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + dp[i][j]
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] str = s.split(",");
        int m = Integer.parseInt(str[0]);
        int n = Integer.parseInt(str[1]);
        int[][] arr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        int res = max(arr);
        System.out.println(res);
    }

    public static int max(int[][] arr) {
        for (int i = 1; i < arr.length; i++) {
            arr[i][0] = arr[i][0] + arr[i - 1][0];
        }
        for (int j = 1; j < arr[0].length; j++) {
            arr[0][j] = arr[0][j] + arr[0][j - 1];
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                arr[i][j] = arr[i][j] + Math.max(arr[i - 1][j], arr[i][j - 1]);
            }
        }
        return arr[arr.length - 1][arr[0].length - 1];
    }
}
2. 排序
不得不说,这道题的题意有点点坑,第一个坑就是给出了部分序列的变化情况采样,一开始还以为是快速排序;第二个坑就是数组的输入竟然是以逗号隔开的,刚开始没注意这个细节,出现case通过为0,百思不得其解,最后认真读了一遍题意,才发现(细心读题很重要啊~)
/**
 * @Author Baker.chen
 * @create 2020/8/29 19:09
 *
 * 选择排序
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <= 0) {
            return;
        }
        sc.nextLine();
        int[] arr = new int[n];
        String s = sc.nextLine();
        String[] str = s.split(",");
        for (int i = 0; i < str.length; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
        selectSort(arr);
        for (int j = 0; j < arr.length; j++) {
            if (j == arr.length - 1) {
                System.out.print(arr[j]);
            }else {
                System.out.print(arr[j] + ",");
            }
        }
    }

    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp =arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }
}
3. 字符串的过滤
这道题是花费最长时间的,一开始是想用暴力的方法,用多个if循环进行判断过滤,case通过始终只有75%,(还是不知道原因出在哪里),最后有剩余时间回过头来继续做这道题,才想起可以使用正则表达式进行过滤,代码十分简洁
/**
 * @Author Baker.chen
 * @create 2020/8/29 19:36
 *
 * 字符串过滤
  *       思路:先用java的正则表达式将下划线超过2的替换成一个下划线;  *             再判断过滤后的字符串前后是否还有一个下划线,有则进一步过滤
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String str = s.replaceAll("[_]{2,}", "_");
        if (str.charAt(0) == '_') {
            str = str.substring(1, str.length());
        }
        if (str.charAt(str.length() - 1) == '_') {
            str = str.substring(0, str.length() - 1);
        }
        System.out.println(str);
    }
}
4. 分解质因数
这道题也是以前做过的,只不过之前用的是非递归实现,这次题目要求的是要用递归实现
/**
 * @Author Baker.chen
 * @create 2020/8/29 20:13
 *
 * 分解质因数
 *
 * 思路:
 *  1. 首先设置一个变量k,k的值等于最小素数2,注意变量k应该声明为类成员变量,不能声明在方法中,否则多次递归调用方***导致栈内存溢出
 *  2. 如果质数恰好等于n,代表分解已结束
 *  3. 若n>k,但n能被k整除,先打印k值,并用n除以k的商作为新的n,然后递归执行
 *  4. 若n不能被k整除,则用k+1作为k的值,然后递归执行
 */
public class Main {
    private static int k = 2;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        f(n);
    }

    public static void f(int n) {
        while (k <= n) {
            if (k == n) {
                System.out.print(n);
                break;
            } else if (n > k && n % k == 0) {
                System.out.print(k + "*");
                n = n / k;
                f(n);
                break;
            } else if(n > k && n % k != 0) {
                k = k + 1;
                f(n);
                break;
            }
        }
    }
}




全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐