专栏首页技术圈面试题目集(一)

面试题目集(一)

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

本文链接:https://blog.csdn.net/qq_27717921/article/details/74784226

时间好快

面试题目一:海量无序数据中,得到最小的K个数

考察知识点:大顶堆,堆排序建堆,调整过程

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

考察知识点:动态规划,背包问题

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:判断一个数是否为回文数

考察知识点:数制

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

	}

}

面试题目4:将无序数组分成四块,不好切割点分别求和,使得和相同

缺点:正负整型符合不能正确求解,有大神可以解决么?

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

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

    Kindear
  • 计蒜客2018 蓝桥杯省赛 B 组模拟赛(一)

    Zoctopus
  • 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的...

    Ch_Zaqdt
  • Oil Deposts(dfs)

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

    Ch_Zaqdt
  • 水果Fruit(母函数) - HDU 2152

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

    ACM算法日常
  • 挖掘机技术哪家强(c++实现)

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

    用户2038589

扫码关注云+社区

领取腾讯云代金券