科大讯飞7.31号笔试

研发类笔试

四道编程题

1、leetcode：零钱兑换 + 纸币的数量限制；60%

直接用的动态规划，写的零钱兑换

2、快排，输出每次变换后的序列 AC

刚开始，直接写的快排，0%，输出结果错误，后来对照了一下给定测试用例的输出和自己的输出结果，发现递归的出口改一下就可以了，大家看下代码，直接过一遍流程应该就看出来了

代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = in.nextInt();
        }
        quickSort(array, 0, n - 1);
    }

    public static void quickSort(int[] array, int left, int right) {
               // 改动就在这里，之前写的是left > right
        if (left >=right) {
            return;
        }
        int key = array[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && array[j] >= key) {
                j--;
            }
            while (i < j && array[i] <= key) {
                i++;
            }
            if (i < j) {
                swap(array, i, j);
            }
        }
        swap(array, left, j);
        for (int k = 0; k < array.length; k++) {
            if (k == 0) {
                System.out.print(array[k]);

            } else {
                System.out.print(" " + array[k]);
            }

        }
        System.out.println();
        quickSort(array, left, i - 1);
        quickSort(array, j + 1, right);
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

3、分别给出两个矩阵对角的坐标，判断两个矩阵是否相交； 83.3%

思路：

算出其中一个矩阵的横坐标和纵坐标的范围，判断另一个矩阵的四个点的坐标是否在那个范围里；

如果在，相交，不在就不相交；

不知道哪里出错了，只有83.3%

4、从一个字符串中提取出整数； AC

思路：

直接循环判断字符串中的字符，根据ASCII码（的亏我记得0的ASCII码是48），判断ASCII码范围在48-57的，输出；

首次出现 0 和 ’-‘ 号要做处理；

代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String string = in.nextLine();
        int length = string.length();
        int flag = 0;
        for (int i = 0; i < length; i++) {
            if (flag == 0 && string.charAt(i) == '-') {
                System.out.print(string.charAt(i));
            }
            if (string.charAt(i) >= 48 && string.charAt(i) <= 57) {
                if (flag == 0 && string.charAt(i) == 48) {
                    continue;
                }
                flag++;
                System.out.print(string.charAt(i));
            }
        }
    }
}

#科大讯飞##笔试题目#