科大讯飞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));
}
}
}
}
