20140704笔试面试总结(java)
1、与其他高级语言不同，Java在数组声明时并不为数组分配存储空间,因此，在声明的[]中不能指出数组的长度
2、为数组分配空间的两种方法：数组初始化和使用new运算符
3、未分配存储空间时，数组变量中只是一个值为null的空引用，要访问数组元素，必须需要经过初始化、分配存储空间创建数组后才能访问数组的元素
一维数组定义：
int[] arr; //注意int[5] arr；错误int arr[];
int[] arr = {1, 2, 3, 4, 5};
int[] arr = new int[5];
二维数组定义：
二维数组即是特殊的一维数组，每个元素是一个一维数组
int[] arr[]; //此种方式最好理解
int arr[][];
int[][] arr;
int arr[][] = {{1,2},{3,4},{5,6,7}};
int arr[][] = new int[3][3]
2. 二进制数种1的位数
注意：
1. 方式一通过右移计算，如果是负数右移时高位会补充0，此时可能会进入死循环
如4（100）返回1， 9（1001）返回2
public class BitCount { //方式一：移位加计数器 注意java中没有无符号整形
public static int bitCount(int n){
int count = 0;
while(n > 0){
if((n & 1) == 1){
count++;
}
n >>= 1;
}
return count;
}
public static int bitCount1(int n){ int count = 0;
unsigned int flag = 1;
while(flag){
if(n&flag){
count++;
}
flag = flag << 1;
}
return count;
}
//方式三：使用n = n & (n-1)public static int bitCount2(int n){
int count = 0;
while(n > 0){
n &= n-1; //消除最右边的1,和第一种方式等价，只是这个的执行次数由数字中的1决定
count++;
}
return count;
}
public static void main(String[] args) {
System.out.println("3: "+ bitCount(3));
System.out.println("8: "+ bitCount(8));
System.out.println("11: "+ bitCount(11));
System.out.println("6: "+ bitCount2(6));
System.out.println("7: "+ bitCount2(7));
System.out.println("13: "+ bitCount2(13));
}
}
输出：
3: 28: 1
11: 3
6: 2
7: 3
13: 3
http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html 中提供了很多其他很巧妙的方法
3.无序数组中最小的10个数
需要考虑数组是否可以修改
1）如果数组可以修改, 时间复杂度O(n)
可以参考快速排序的思路，基于数组的第k个数字来排序，使得比k小的所有数字排在数组的左边，比k大的数字排在数组的右边；另外这种方式找出的前k个数不一定是有序的
借用快速排序中partition函数
public static int partition(int[] data, int start, int end){ if(data == null || start < 0 || end >= data.length){
throw new InvalidParameterException();
}
Random rand = new Random();
int index = rand.nextInt(end-start+1)+start;
swap(data, index, end);
int borderPos = start-1; //记录小于部分和大于部分的分界点,指向最后一个小于的值
for(index = start; index < end; ++index){
if(data[index] < data[end]){
borderPos++;
if(borderPos != index){
swap(data, borderPos, index);
}
}
}
borderPos++;
swap(data, borderPos, end);
return borderPos;
}
public static void swap(int[] data, int pos1, int pos2){
int tmp = data[pos1];
data[pos1] = data[pos2];
data[pos2] = tmp;
}
查找最小的前k个数
public static int[] getSmallestNum(int[] numbers, int k){ if(numbers == null || k <= 0 || k > numbers.length){
throw new InvalidParameterException();
}
int start = 0,
end = numbers.length -1,
index = partition(numbers, start, end);
while(index != k-1){
if(index > k-1){
end = index - 1;
index = partition(numbers, start, end);
}else{
start = index + 1;
index = partition(numbers, start, end);
}
}
int[] result = new int[k];
for(int i = 0; i < k; i++){
result[i] = numbers[i];
}
return result;
}
测试：
public static void main(String[] args) { int[] arr = new int[20];
for(int i=0; i<20; i++){
arr[i] = (int) (Math.random()*100);
}
for(int i=0,len=arr.length; i<len; i++){
System.out.print(arr[i]+" ");
}
int[] result = getSmallestNum(arr,5);
System.out.println("");
for(int i=0,len=result.length; i<len; i++){
System.out.print(result[i]+" ");
}
输出：
91 69 75 29 69 55 80 44 63 19 36 53 62 45 97 52 8 93 34 3829 19 8 34 36
2) 使用大根堆
使用大根堆存储最小的k个数，将前k个数读入堆中，剩下的数据和堆中的最大值比较，小于最大值即替换最大值，如果比最大值大，丢弃该值，，大根堆的插入和删除时间复杂度为O(logk),因而整体的时间复杂度为O(nlogk)
此种方式不用更改数组，并且适合处理海量数据
public static int[] getSmallestNums1(int[] numbers, int k){ //参数检查
if(numbers == null || k <= 0){
throw new InvalidParameterException();
}
//存储大根堆，初始值为numbers的前k个数
int[] heap = new int[k];
for(int i = 0; i < k; i++){
heap[i] = numbers[i];
}
int rootIndex = k/2 -1;
while(rootIndex >= 0){
reheap(heap, rootIndex, k-1);
rootIndex--;
}
for(int i = k, len = numbers.length; i < len; i++){
//如果数值比最大值小，替换最大值
if(numbers[i] < heap[0]){
heap[0] = numbers[i];
reheap(heap, 0, k-1);
}
}
return heap;
}
//重建大根堆
public static void reheap(int[] heap, int rootIndex, int end){
int node = heap[rootIndex];
int leftIndex = rootIndex*2 +1;
boolean done = false;
while(!done && leftIndex <= end){
int index = leftIndex;
if(leftIndex+1 <= end){
int rightIndex = leftIndex + 1;
if(heap[rightIndex] > heap[leftIndex]){
index = rightIndex;
}
}
if(node < heap[index]){
heap[rootIndex] = heap[index];
rootIndex = index;
leftIndex = rootIndex*2 + 1;
}else{
done = true;
}
}
heap[rootIndex] = node;
}
测试：
public static void main(String[] args) { int[] arr = new int[20];
for(int i=0; i<20; i++){
arr[i] = (int) (Math.random()*100);
}
for(int i=0,len=arr.length; i<len; i++){
System.out.print(arr[i]+" ");
}
int[] result = getSmallestNums1(arr,5);
System.out.println("");
for(int i=0,len=result.length; i<len; i++){
System.out.print(result[i]+" ");
}
}
输出：
91 13 44 34 3 57 62 89 57 62 45 1 40 71 76 18 1 28 32 5518 13 1 1 3
以上是 20140704笔试面试总结(java) 的全部内容， 来源链接： utcz.com/z/390772.html
