大数据算法系列6:面试题与ACM题选讲2

一. POJ1700(快速过河)

http://poj.org/problem?id=1700

大意:
有n个人要过一条河，每个人过河都需要一个时间ai，有一艘船，每次过河只能最多装两个人。两个人划船过河所需的时间都取决于过河时间长的那个人。比如，A，B两人过河所需时间分别为a，b，那么，他们成一条船过河所需的时间为：max{a，b}。现在让你安排一个过河方案，让所有人用最短的时间全部过河。

分析:
n个人过河，只有一条船，一条船最多装两个人，来回时间以最多那个人为标准，问过河最短时间

首先这个问题需要分类讨论假设有m个人，按时间大小排好序

1. m==1时，只有一个人过河 ,t+=a[1]

2. m==2时，两个人过河，直接t取大的,t+=a[2]

3. m==3时，三个人过河，先让最快的载最慢的过河，然后最快的回来，再在次快的过河,t+=a[3]+a[1]+a[2]

4. m>=4时，这里要用到贪心

无论m多大，我们只看4个人，最快 次最快 最慢 次最慢

一般我们能想到的就是第一种做法，让最快的载最慢的，然后最快的回来，再载次最慢的，然后最快的回来，这里我们不需要管次最快的，这里我们就减少了两个人了，因此m-=2,在去判断，m在哪个范围再进行求解就好了。

第二种，先给个样例 1 2 1000 1000 ，这个显然用第一种做法，是行不通的，1000+1+1000=2001，我们显然可以知道，先让最快和次快过河，然后最快回来，然后最慢和次慢过河，然后次快回来，2+1+1000=1003，贪心取时间最短，所以这就是最短时间的做法，这里我们还是没有把最快和次最快过河，因此还是减少两人，m-=2。

分析结果:
第一种：最快+最慢去，最快回；最快+次慢去，最快回。
第二种：最快+次块去，最快回；最慢+次慢去，次快回。
(此时使用a,b,c,d来代替)

把上面化解一下
变为2b与a+c

代码:

package com.suanfa.数据结构;

import java.util.Arrays;
import java.util.Scanner;


public class POJ1700 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();  //T组数据
        for(int i=0;i<T;i++) {
            int n=sc.nextInt();
            int[] speed=new int[n];
            for(int j=0;j<n;j++) {
                speed[j]=sc.nextInt();
            }
            //排序
            Arrays.sort(speed);
            f(n,speed);  //对速度快慢进行排序
        }
    }
    private static void f(int n,int[] speed) {
        int left=n;
        int ans=0;
        while(left>0) {
            if(left==1) { //只有一个人
                ans+=speed[0];
                break;
            }else if(left==2) {  //只有2人
                ans+=speed[1];
                break;
            }
            else if(left==3) { //有3个人
                ans+=speed[2]+speed[0]+speed[1];
                break;
            }
            else {
                //1,2出发，1返回，最后两名出发，2返回
                int s1=speed[1]+speed[0]+speed[left-1]+speed[1];
                //1,3出发，1返回，1,4出发，1返回，1,2过河
                int s2=speed[left-1]+speed[left-2]+2*speed[0]; //a+2b+c
                ans+=Math.min(s1,s2);
                left-=2;  //左侧是渡河起点，left代表左侧的剩余人数
            }
        }
        System.out.println(ans);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

测试记录:

二. 面试题(链表中第k个节点)

题目:

分析:
使用双指针，让第一个指针领先第二个指针k-1，当第一个指针到达链表尾部时，第二个指针位置即n-(k-1)=n-k+1,也就是倒数第k个结点。
此题主要是让我们考虑程序鲁棒性，所以要把输入情况都要考虑在内。

代码:

public ListNode FindKthToTail(ListNode head,int k) {
        ListNode p1 = head;//快指针
        ListNode p2 = head;//慢指针
        if(head==null || k<=0){ //链表为空或k结点不再链表中
           return null;
        }
        for(int i=0;i<k-1;i++){
            if(p1.next!=null){
                p1 = p1.next;
            }
            else{
                return null;
            }
        }

        while(p1.next!=null){
                p1 =p1.next;
                p2 = p2.next;
        }
        return p2;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三. 面试题(遍历二叉树)

题目:

解决方案:
参考二叉树遍历即可:https://blog.csdn.net/weixin_40025107/article/details/124903300

四. 面试题(用两个栈实现队列)

题目:

分析:
栈stack1用来实现push操作，stack2空的前提下才能进行入栈，否则影响后续进出队列的顺序。
栈stack2用来实现pop操作，将push进去的stack1内的元素存入stack2中，再进行出栈，就是队列的出列顺序。

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        while(!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        } 
        stack1.push(node);
    }
    
    public int pop() {
        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

五. 面试题(判断二叉树是否为平衡二叉树)

题目:

分析:
这道题目其实和求二叉树的深度用到的方法是一样的，因为我们求二叉树的深度，其实就是求了左右子树的深度的最大值。

我们都知道如何判断一棵二叉树是不是平衡二叉树，就是它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

所以，这个时候我们只需要判断左右子树的深度之差有没有超过1，若超过了则不是平衡的，反之则为平衡二叉树。

public class Solution {
    boolean isBalanced = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        TreeDepth(root);
        return isBalanced;
    }
public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        int l = TreeDepth(root.left);
        if(l == -1)  return -1;  // 提前返回
        int r = TreeDepth(root.right);
        if(r == -1)  return -1;  // 提前返回
        if(Math.abs(l-r) > 1){
            isBalanced = false;  // 不是平衡树
            return -1;  // 加一个标记-1，已经不可能是平衡树了
        }
        return Math.max(l,r)+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

六.POJ1064(二分法)

大意:
有N条绳子，长度分别为 length[1,2,3,…,N]。

如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长有多长？

结果保留两位小数。

分析:
二分可能的长度。

精度问题

代码:

import java.util.Scanner;

public class Main {
    static int N, K;
    static double[] a;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        a = new double[N];
        for (int i = 0; i < N; i++)
            a[i] = sc.nextDouble();
        sc.close();
        double low = -1, high = 100001;
        while (high - low > 0.001) {
            double mid = (low + high) / 2;
            if (C(mid)) {
                low = mid;
            } else {
                high = mid;
            }
        }
        if (high < 0.01)
            System.out.println("0.00");
        else
            System.out.println(String.format("%.2f", (int) (high * 100) / 100.0));
    }

    static boolean C(double X) {
        int count = 0;
        for (int i = 0; i < N; i++)
            count = count + (int) (a[i] / X);
        return count >= K;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

七. POJ1840(简单hash)

大意:
给出ai（i=1～5），求
$a_1\ast x_1^3+a_2\ast x_2^3+a_3\ast x_3^3+a_4\ast x_4^3+a_5\ast x_5^3=0$
在－50到50之间的x的解的个数

分析:
将等式转化为
$-(a_1{x}_1^3+a_2{x}_2^3)=a_3{x}_3^3+a_4{x}_4^3+a_5{x}_5^3$
这样就直接减少了时间复杂度

将等式左边值设为Hash的下标，为了不为负，左右两边都加上一个$5050^33 = 18750000 $
所以要加一个比它大的数，这里用的是25000000

八. POJ3465（贪心+反悔）

大意:
剑圣在单挑大龙
剑圣每一次放技能龙就会打他一下，剑圣就三个技能：

1. 对龙攻击造成减少X点血
2. 躲掉龙的攻击
3. 回血Y点

龙N次攻击造成减少血量为 ai
初始状态下剑圣和龙的血量分别是 H1 H2

问剑圣是否可以solo过大龙，并输出相应的数据

分析:
每一次都攻击大龙，直到剑圣要死了，时光倒流，选择前面某一次进行回血或者躲避大龙的攻击

也就是说贪心攻击，时光倒流的时候用优先队列选择即可

九. POJ2002（哈希）

大意:
给定n个相异整数点，求能构成多少个正方形。

分析:
其实这题挺简单的，经过思考可以发现，我们可以通过枚举两个点（或者说一条边），然后求出可能构成正方形的另外两个点，然后判断是不是在给你的点集中就行了。求点问题是一个数学问题，判断要用到hash表。

十. POJ2786(贪心 + 优先队列)

题目:

分析:
用一个优先队列进行模拟（priority_queue）order的情况。
先按照截止日期due对Order进行从小到大的排序，用pass表示当前完成最多订单需要的最短的时间，
遍历Order，当pass + order[i].q <= order[i].d的时候，
表示可以正常完成该订单，进队，同时pass += order[i].q，
如果pass + order[i].q > order[i].d的时候，
则需要考虑order[i].q和队列中需要最长时间的订单之间的关系，
如果order[i].q较大，说明该订单不可能完成，否则入队，pass += order[i].q，
然后要减去队列中需要最长时间的订单（即队首），一直贪心，最后留在队列中的订单个数就是保留的订单个数。

结论:
其实题目的意思是保留最多的一个订单数，而非订单量，所以用贪心算法，一直到>=截止日期的时候，如果发现当前任务添加上去, 会超出最后期限, 选择当前任务和之前任务中最大的生产时间进行放弃.

参考:

1. http://www.dataguru.cn/article-5747-1.html