版权声明：本文为博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_27717921/article/details/74784226
时间好快
面试题目一：海量无序数据中，得到最小的K个数
考察知识点：大顶堆，堆排序建堆，调整过程
代码语言：javascript复制package learning;
public class minTopK {
/**
* 利用大根堆求解无序数组的最小的k个数
*/
public static void swap(int[] arr,int index1,int index2){
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
public static void heapInsert(int[] arr,int value,int index){
arr[index] = value;//index为0的话一定为根节点
while(index!=0){
int parent = (index -1)/2;
if(arr[parent]<arr[index]){
swap(arr,parent,index);
index = parent;
}else{
break;
}
}
}
public static void heapify(int[] arr,int index,int heapSize){
int left = index*2 1;
int right = index*2 2;
int largest = index;
while(left<heapSize){
if(arr[left]>arr[index]){
largest = left;
}
if(right<heapSize&&arr[right]>arr[largest]){
largest = right;
}
if(largest!=index){
swap(arr,largest,index);
}else{
break;
}
index = largest;
left = index*2 1;
right = index*2 2;
}
}
public static int[] getMinKNumsByHeap(int[] arr,int k){
if(k<1||k>arr.length){
return arr;
}
int[] kHeap = new int[k];
for(int i=0;i!=k;i ){
heapInsert(kHeap,arr[i],i);
}
for(int i=k;i!=arr.length;i ){
if(arr[i]<kHeap[0]){
kHeap[0] = arr[i];
heapify(kHeap,0,k);
}
}
return kHeap;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {8,4,11,6,7,11,3,9,1};
int[] arr_tmp = getMinKNumsByHeap(arr,5);
for(int i=0;i<arr_tmp.length;i ){
System.out.print(arr_tmp[i]);
}
}
}面试题目2：给定N个数据，将这N个数据分成两组，使得两组分别求和记作S1,S2，使得|S1-S2|最小，并返回这个绝对差值，比如这N个数为1,2,3,分成两组为A1,A2，A1包含1,2，A2包含3，则返回结果为0
考察知识点：动态规划，背包问题
代码语言：javascript复制package qidian;
public class Test2 {
public static int KnapSack(int num, int weight[], int value[], int x[], int C){
int V[][] = new int[C 1][C 1];
for(int i = 0 ; i <= num-1 ; i ){
V[i][0] = 0; //第一列都为0；
}
for(int j = 0 ; j <=C ; j ){
V[0][j]=0; //第一行都为0
}
for(int i = 1 ; i <= num-1 ; i ){
for(int j = 1 ; j <=C ; j ){
if(j<weight[i])
V[i][j]=V[i-1][j];
else{
V[i][j] = Math.max(V[i-1][j], V[i-1][j-weight[i]] value[i]);
}
}
}
return 2*C-2*V[num-1][C];
}
public static void main(String[] args) {
int[] weight = {-1,2,4,4}; //下标都从1开始
int[] value = {-1,2,4,4}; //下标都从1开始
int num = weight.length;
int CAP = 0;
for(int k=1;k<num;k ){
CAP =value[k];
}
CAP = CAP/2;
int[] x = new int[num]; //第0个元素不算，下标都从1开始
int answer = KnapSack(num,weight,value,x,CAP);
System.out.println("answer：" answer);
}
}面试题目3：判断一个数是否为回文数
考察知识点：数制
代码语言：javascript复制package learning;
public class palindrome {
/**
* 判断一个数是否为回文数
*/
public static int get_help(int num){
int help = 1;
while(num/10!=0){
num = num/10;
help = help*10;
}
System.out.print(help);
return help;
}
public static boolean ispalindrome(int num){
num = Math.abs(num);
int help = get_help(num);
while(help>1){
int left = num/help;
int right = num;
if(left!=right){
return false;
}
num = num%help/10;
help = help/100;
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a = -1211111;
int b = 123321;
int c = 2;
System.out.print(ispalindrome(a));
}
}面试题目4：将无序数组分成四块，不好切割点分别求和，使得和相同
缺点：正负整型符合不能正确求解，有大神可以解决么？
代码语言：javascript复制package qidian;
import java.util.HashMap;
import java.util.Map;
public class searchPoints_2 {
/**
* @param args
*/
public static void main(String[] args){
//int[] input = {2,0,2,0,2,0,2};
//int[] input = {1,3,1,4,2,2,1,1,2,4};
//int[] input = {2,-1,5,3,-2,-1,4,-3,2,1};
int[] input = {2,0,1,2,0,2,0,2};
int[] sums = new int[input.length];
Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
int tmp = 0;
for (int i = 0; i < input.length; i) {
tmp = input[i];
sums[i] = tmp;
if(!hashMap.containsKey(tmp)){
hashMap.put(tmp, i);
}
}
for (int pos1 = 1; pos1 < input.length; pos1) {
int sum = sums[pos1] - input[pos1];
if (hashMap.containsKey(sum sums[pos1])) {
int pos2 = hashMap.get(sum sums[pos1]) 1;
if (pos2 < input.length && hashMap.containsKey(sum sums[pos2])) {
int pos3 = hashMap.get(sum sums[pos2]) 1;
if (pos3 < input.length && sums[sums.length - 1] - sums[pos3] == sum) {
System.out.println("result:" pos1 "---" pos2 "----" pos3);
return;
}
}
}
}
return;
}
}
