科大讯飞7.31笔试（Java岗）

第一题

1,5,10,50,100五种纸币，每种对应一个数量，求找零所需最小纸币数，如无方案输出-1。
用的是贪心的思想，但通过率很低，就不贴代码了。。。

第二题

给一个数列和按某种排序方式每一步生成的数列，要求实现该排序算法并输出每一步内容。
很明显是快排，通过率100%。
有个问题是刚开始我是用Arrays.toString来进行输出的，但和标准结果比多了[]，后来自己写了个print函数。

import java.util.Scanner;

public class QuickSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        quicksort(nums, 0, n - 1);
    }

    public static void quicksort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = partition(nums, left, right);
        print(nums);
        quicksort(nums, left, mid - 1);
        quicksort(nums, mid + 1, right);
    }

    public static void print(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
            if (i != nums.length - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }

    public static int partition(int[] nums, int left, int right) {
        if (left >= right) {
            return left;
        }
        int i = left;
        int j = right;
        int key = nums[left];
        while (i < j) {
            while (i < j && nums[j] >= key) {
                j--;
            }
            while(i < j && nums[i] <= key) {
                i++;
            }
            if(i < j){
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
        nums[left] = nums[i];
        nums[i] = key;
        return i;
    }

    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

第三题

(0,0)(4,2)代表矩形两个对角顶点。输入8个数字代表两个矩形，求二者是否相交，相交返回1，反之返回0；
这题可以取巧来做，根据输入可以发现，8个数字分别是矩形1左下角，矩形1右上角，矩形2左下角，矩形2右上角。
因此可以判断矩形2左下角横坐标是否在矩形1横坐标之间，矩形2左下角纵坐标是否在矩形1纵坐标之间，借此判断是否相交。
通过率100%。

import java.util.Scanner;

public class Square {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] square1 = new int[2][2], square2 = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                square1[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                square2[i][j] = sc.nextInt();
            }
        }

        if (xIn(square1, square2) && yIn(square1, square2)) {
            System.out.print(1);
        } else {
            System.out.print(0);
        }
    }

    public static boolean xIn(int[][] square1, int[][] square2) {
        return square2[0][0] >= square1[0][0] && square2[0][0] <= square1[1][0];
    }

    public static boolean yIn(int[][] square1, int[][] square2) {
        return square2[0][1] >= square1[0][1] && square2[0][0] <= square1[1][1];
    }
}

第四题

从输入的字符串中提取整数，如+1a2返回12，要求尽可能多包含异常处理。
可以通过遍历字符串方式来实现。当时只考虑到负号，可能还有小数点啥的吧。。
通过率80%多。

import java.util.Scanner;

public class GetNum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();

        long number = 0;
        int flag = 1;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (isDigit(c)) {
                number *= 10;
                number += c - '0';
            }

            if (c == '-') {
                flag *= -1;
            }
        }
        System.out.print(number * flag);
    }

    public static boolean isDigit(char c) {
        return c >= '0' && c <= '9';
    }
}