• 寫一個算法，可以將一個二維數(shù)組順時針旋轉(zhuǎn)90度礼殊，說一下思路驹吮。

考察點：數(shù)組
參考回答：

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;
            }
        }
}

• 一個數(shù)組，除一個元素外其它都是兩兩相等晶伦，求那個元素?

考察點：數(shù)組
參考回答：

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

• 找出數(shù)組中和為S的一對組合碟狞，找出一組就行

考察點：數(shù)組
參考回答：

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;
}

• 求一個數(shù)組中連續(xù)子向量的最大和

考察點：數(shù)組
參考回答：

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;
}

• 尋找一數(shù)組中前K個最大的數(shù)

考察點：數(shù)組
參考回答：

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;
}