20140704笔试面试总结(java)

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: 2

8: 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 38 

29 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 55 

18 13 1 1 3

以上是 20140704笔试面试总结(java) 的全部内容, 来源链接: utcz.com/z/390772.html

回到顶部