# 面试题目集(一)

```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]);
}

}

}```

```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开始

}

}```

```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%10;
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));

}

}```

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

}

}```

0 条评论

• ### 动态规划算法举例解析（最大收益和最小损失选择）

版权声明：本文为博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。

• ### 基于分治和DP的算法设计

发现下面的策略都是比较糟糕的，这里提及一下分治和动态规划的区别，动态规划避免了分治方法的重复计算，下面的基本上是用了最朴素的动态规划方案，接下来会用自底向上的方...

• ### 在其他数都出现k次的数组中找到只出现一次的数

版权声明：本文为博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。

• ### 拓扑排序 HDU - 5695

众所周知，度度熊喜欢各类体育活动。  今天，它终于当上了梦寐以求的体育课老师。第一次课上，它发现一个有趣的事情。在上课之前，所有同学要排成一列， 假设最开始每...

• ### leetcode 204题求素数个数

Count the number of prime numbers less than a non-negative number, n

• ### POJ 3020 Antenna Placement(二分图最小边覆盖)

题意是有一个n*m的地图，图中'*'表示城市，现在要给每个城市覆盖无线，需要安装基站，每个基站最多只能覆盖相邻的两个城市，也就是1*2或者2*1的...

• ### Oil Deposts(dfs)

题意就是有一大片地方，让你去找里面有多少片油田(八个方向)，我们只需要遍历地图，当找到'@'的时候进行dfs，把搜索到的'@'都变成'*'就好了，然后用一个变量...

• ### 水果Fruit（母函数） - HDU 2152

转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。 ...

• ### 挖掘机技术哪家强（c++实现）

描述：为了用事实说明挖掘机技术到底哪家强，组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。