数组

写一个算法，可以将一个二维数组顺时针旋转90度，说一下思路。

考察点：数组

public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n/2; i++) {
            for (int j = i; j < n-1-i; j++)
{
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
}

一个数组，除一个元素外其它都是两两相等，求那个元素?

考察点：数组

解法：位运算，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。

 public static int find1From2(int[] a){
        int len = a.length, result = 0;
        for(int i = 0; i < len; i++){
            result = result ^ a[i];
        }
        return result;
}

找出数组中和为S的一对组合，找出一组就行

考察点：数组

解法：两数之和经典题，找到一组即可返回，使用HashMap即可。

public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[] a = new int[2];
        map.put(nums[0], 0);
        for (int i = 1; i < nums.length;i++) {
            if (map.containsKey(target - nums[i])) {
                a[0] = map.get(target - nums[i]);
                a[1] = i;
                return a;
            } else {
                map.put(nums[i], i);
            }
        }
        return a;
}

求一个数组中连续子向量的最大和

考察点：数组

public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        if (nums == null || nums.length == 0) {
            return sum;
        }
        for (int i = 0; i < nums.length;i++) {
            sum += nums[i];
            maxSum = Math.max(maxSum, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxSum;
}

寻找一数组中前K个最大的数

考察点：数组

解法：考场排序，可以用堆排序，也可以用快排，面试的时候看面试官怎么要求。这里给出快排的解法，自己也可以尝试其他的方法。

public int findKthLargest(int[] nums, int k) {
    if (k < 1 || nums == null) {
        return 0;
    }
    return getKth(nums.length - k +1, nums, 0,nums.length - 1);
}
 // 快排模板
public int getKth(int k, int[] nums, int start, int end) {
    int pivot = nums[end];
    int left = start;
    int right = end;
    while (true) {
        while(nums[left] < pivot && left < right) {
            left++;
        }
        while(nums[right] >= pivot && right > left) {
            right--;
        }

        if(left == right) {
            break;
        }

        swap(nums,left, right);
    }
    swap(nums, left, end);
    if (k == left + 1) {
        return pivot;
    } else if (k < left + 1) {
        return getKth(k, nums, start, left - 1);
    } else {
        return getKth(k, nums, left + 1, end);
    }
}
// 交换元素值
public void swap(int[] nums, int n1, int n2) {
    int tmp = nums[n1];
    nums[n1] = nums[n2];
    nums[n2] = tmp;
}