android-java面试题_android应届毕业生java面试题

1.冒泡排序

原理:

相邻的俩个元素比较,第一轮结束,最后一个是最大的

第二轮只需要比较leng-1-i即可,因为最后一个元素已经是最大的了

int[] arr = {3, 8, 7, 5, 1, 6};
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

2.选择排序

每一个元素和其他元素,逐一比较,第一轮结束后,最小的值在最左边

 int[] arr = {3, 8, 7, 5, 1, 6};
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
 
                }
            }
        }

3.二分查找

找一个数组的中间 元素,去比较要查找的元素值,跳效率

 int[] arr = {3, 8, 7, 5, 1, 6};
  getValue(arr, 3);
 
private int getValue(int[] arr, int value) {
        int min = 0;
        int max = arr.length - 1;
        int mid = (min + max) / 2;
        while (arr[mid] != value) {
            if (arr[mid] > value) {
                max = mid - 1;
            } else if(arr[mid] < value) {
                min = mid + 1;
            }
            mid = (min + max) / 2;
            if (min > max) {
                return -1;
            }
        }
        return mid;
    }

4.快速排序

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想，到时候再聊。

 int[] arr = {3, 8, 7, 5, 1, 6};
 getValue(arr, 0, arr.length - 1);
 
private void getValue(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int i = low;
        int j = high;
        int temp = arr[low];
        while (i < j) {
            while (arr[j] >= temp && i < j) {
                j--;
            }
            while (arr[i] <= temp && i < j) {
                i++;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        arr[low] = arr[i];
        arr[i] = temp;
        getValue(arr, low, j - 1);
        getValue(arr, j + 1, high);
    }

5.在字符串中找到第一个不重复的字符

灵活的运用linkedHasmap的特性,有序的

String str = "hellowee";
getFirstNoRepeatChar(str );
 
 private char getFirstNoRepeatChar(String str) {
        char[] chars = str.toCharArray();
        LinkedHashMap<Character, Integer> linkedHashMap = new LinkedHashMap<>();
        for (int i = 0; i < chars.length; i++) {
            linkedHashMap.put(chars[i], linkedHashMap.containsKey(chars[i]) ? linkedHashMap.get(chars[i]) + 1 : 1);
        }
        for (Map.Entry<Character, Integer> entry : linkedHashMap.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return ' ';
    }