大数据算法系列5:面试题与ACM题选讲1

原创只是甲 2022-10-21

287

一. POJ2299(归并排序)
二. POJ1363(判断合法栈序列)
三. POJ 3349（哈希算法）
四. Uva10391(字符串检索)
五. POJ2255(二叉树遍历)
六. google面试题(栈的min函数)
七. POJ2833(优先队列)
八. POJ1828
九. 面试题（二叉树转为链表）
十. POJ2823(求移动区间最大值最小值)
参考:

一. POJ2299(归并排序)

大意：
给定一串数字，求冒泡排序需要交换的次数。

分析：
一个乱序序列的逆序数=只允许相邻两个元素交换的条件下，得到有序序列的交换次数。归并排序可以求数列的逆序数。

归并排序：
比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

代码:

package com.suanfa.数据结构;

import java.util.*;

public class POJ2299 {

    static int[] arr;

    // 交换数组中的两个元素
    static void swop(int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    //归并函数就写一个函数
    static long compute(int l,int r){
        // 记住递归结束的条件
        if (r-l<=1){
            if(arr[r]<arr[l]){
                swop( l,r );
                return 1;
            } else {
                return 0;
            }
        }
        int mid = (l+r)/2;

        // result = 两个数都位于前半部分时，逆序对数量d1 + 两个数都位于后半部分时，逆序对数量d2 +
        // 第一个数字位于前半部分，第二个数字位于后半部分时，逆序对数量count

        // 分治分治，先分后治
        long d1 = compute(l,mid);
        long d2 = compute(mid+1,r);
        //前半部分长度
        int len1 = mid-l+1;
        //后半部分长度
        int len2 = r-mid;
        int[] arr1 = new int[len1];
        int[] arr2 = new int[len2];

        // 把两个部分的数组拿出来，等会儿要用
        for(int i=0;i<len1;i++){
            arr1[i] = arr[l+i];
        }

        for(int j=0;j<len2;j++){
            arr2[j] = arr[mid+1+j];
        }

        // 计算第一个数字位于前半部分，第二个数字位于后半部分时,逆序对数量
        int i=0,j=0,k=l;
        // count 是结果，必须定义为long，否则WA
        long count=0;
        // 归并过程
        while (i<len1 && j<len2){
            if(arr1[i]<arr2[j]){
                arr[k++]=arr1[i++];
            } else {
                arr[k++]=arr2[j++];
                // 归并过程中，如果前面某个元素大于后面某个元素，说明前面的剩余元素都大于后面的这个元素
                // 所以把前面部分的剩余元素数量给加上
                count+=len1-i;

            }

        }

        if (i>len1 && j<len2){
            while (j<len2){
                arr[k++]=arr2[j++];
            }
        }
        if (j>=len2 && i<len1){
            while (i<len1){
                arr[k++]=arr1[i++];
            }
        }
        return count+d1+d2;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        while (n!=0){
            arr=new int[n];
            for (int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }
            long result = compute(0,n-1);
            System.out.println(result);

            n=sc.nextInt();
        }
    }
}

测试记录:

二. POJ1363(判断合法栈序列)

http://poj.org/problem?id=1363
大意:
给定一个数字序列判断该序列是否可以按照栈的规则得到

分析:
经发现，如果是三个数的情况下，不合法的顺序只有312，也就是一个数最大第二个数最小的情况下，出栈序列是不合法的

代码:

package com.suanfa.数据结构;

import java.util.*;


public class POJ1363 {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n != 0) {
            int tmp = scanner.nextInt();
            while (tmp != 0) {
                Queue<Integer> queue = new LinkedList<Integer>();
                queue.offer(tmp);
                for (int i = 1; i < n; i++) {
                    queue.offer(scanner.nextInt());
                }

                /*Iterator<Integer> iter = queue.iterator();

                while (iter.hasNext()){
                    System.out.println(iter.next());
                }*/

                if (check_is_valid_order(queue)) {
                    System.out.println("Yes");

                } else {
                    System.out.println("No");
                }

                tmp = scanner.nextInt();
            }


            n = scanner.nextInt();
            if (n == 0) {
                System.out.println();
            }



        }


    }

    private static boolean check_is_valid_order(Queue<Integer> queue) {
        Stack<Integer> stack = new Stack<Integer>();
        //System.out.println(queue);
        int len = queue.size();
        for (int i = 1; i <= len; i++) {
            stack.push(i);
            //System.out.println(queue);
            while (!stack.isEmpty() && stack.peek() == queue.peek()) {
                stack.pop();
                queue.poll();
            }
            //System.out.println(stack);
        }

        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }


}

测试记录:

三. POJ 3349（哈希算法）

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

大意:
一朵雪花有6个花瓣，每个花瓣有一个值，当两片雪花六个对应位置的花瓣都一样时，就是Twin Snowflakes。给出一个雪花的集合，要求查找里面是否有 Twin Snowflakes。

分析:
哈希的入门题目。如果直接数组存储比较会超时。建立一个哈希表，每读入一片雪花，就先排序，再存入哈希表，如果发现表中已经存储了一样的雪花，就判定为存在Twin Snowflakes，如果所有雪花都存入还没有存入相同的则判定为不存在。

代码:

package com.suanfa.数据结构;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class POJ3349{
    //Node节点类型数组
    static Node nodes[];
    static final int SIZE = 10000;
    static boolean flag;

    public static void main(String[] args) throws IOException {
        nodes = new Node[SIZE];
        initHead();
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String input = in.readLine();
        StringTokenizer st = new StringTokenizer(input);
        int N =  Integer.parseInt(st.nextToken());
        for(int i = 0; i < N; i++){
            int map[] = new int[6];
            input = in.readLine();
            st = new StringTokenizer(input);
            for(int j = 0; j < 6; j++){
                map[j] = Integer.parseInt(st.nextToken());
            }

            sort(map);

            int key = getKey(map);
            Node newNode = new Node();
            newNode.value = map;
            insert(key, newNode);

            //System.out.println("key:" +key);

            if(flag)
                break;
        }
        if(!flag){
            System.out.println("No two snowflakes are alike.");
        }else{
            System.out.println("Twin snowflakes found.");
        }
        in.close();
    }

    static void initHead(){
        for(int i = 0; i < SIZE; i++){
            nodes[i] = new Node();
            nodes[i].next = nodes[i];
            nodes[i].pre = nodes[i];
        }
    }

    static void insert(int key, Node newNode){
        Node cur = nodes[key].next;

        // cur是当前的数组,不与自身进行对比，而与key值相同的其它所有的数组进行对比
        while(cur != nodes[key]){
            if(isSame(cur.value, newNode.value)){
                flag = true;
                return;
            }
            //通过调用next方法,找到下一个
            cur = cur.next;
        }

        //这个地方是先比较，然后再插入，而非全部插入后，再进行对比
        newNode.pre = cur;
        newNode.next = cur.next;
        newNode.next.pre = newNode;
        cur.next = newNode;
    }

    static boolean isSame(int a[], int b[]){
        for(int i = 0; i < 6; i++){
            if(a[i] != b[i])
                return false;
        }
        return true;
    }

    static void sort(int a[]){
        for(int i =0; i < 6; i++){
            for(int j = i + 1; j < 6; j++){
                if(a[i] > a[j]){
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
    }

    static int getKey(int value[]){
        int sum = 0;
        for(int i = 0; i < 6; i++)
            sum += value[i];
        return sum % SIZE;
    }

    static class Node{
        Node next;
        Node pre;
        int value[];
    }
}

测试记录:

四. Uva10391(字符串检索)

大意:
给很多单词，其中有的单词以分成两部分的形式存在，如果某个单词以及它分成两部分的两个单词同时存在，输出原单词即可。

分析:
要么枚举两两拼接的情况，O(n^2),n这么大肯定会超时。要么枚举每个单词的拆分情况，当单词比较短时，O(n*m),可能可行。

代码:

package com.suanfa.数据结构;

import java.util.Scanner;
import java.util.TreeSet;



public class UVA10391{

    static TreeSet<String> set1 = new TreeSet<String>();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String line = null;
        System.out.println("input:");
        while(!"".equals((line=sc.nextLine().toLowerCase()))){
            set1.add(line);
        }
        sc.close();
        for(String word:set1){
            for(int i=0,len=word.length();i<len;i++){
                String pre = word.substring(0,i);
                String last = word.substring(i,len);
                if(set1.contains(pre)&&set1.contains(last)){
                    System.out.println(word);
                    break;
                }
            }
        }

    }
}

测试记录：

五. POJ2255(二叉树遍历)

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

大意:
不要通过不同的方法进行遍历二叉树

分析:
题目给出二叉树的前序和中序，输出后序序列。

因为先序序列中，第一个元素为二叉树的根，之后为它的左子树和右子树的先序序列；

中序序列中，先是左子树的中序序列，然后是根，再就是右子树的中序序列。

因此只要能建立起这个二叉树，就只要后序输出结果就可以了。

代码:

package com.suanfa.数据结构;

import java.util.Scanner;

public class POJ2255 {
    private static char[] pre;
    private static char[] mid;
    private static int p=-1;//pre数组的指针

    public static void main(String[] args) {
        Scanner sc = new Scanner( System.in );
        while(sc.hasNext()){
            pre=sc.next().toCharArray();
            mid=sc.next().toCharArray();
            tree(0,pre.length-1);
            System.out.println();
            p=-1;//指针置为-1
        }
    }

    private static void tree(int start,int end){
        if(start>end) {
            //没有左子树了  或 没有右子树了
            return;
        }
        p++;//首先指针+1
        for (int k = start; k <= end; k++){
            // 从树的开始位置到结束位置循环
            if(pre[p]==mid[k]){
                //先输出看左子树
                tree(start, k - 1);
                //再输出右子树
                tree(k+1, end);
                //最后输出根元素
                System.out.println(mid[k]);
                break;
            }
        }
    }
}

测试记录:

六. google面试题(栈的min函数)

题目:
设计包含 min 函数的栈。
定义栈的数据结构,要求添加一个 min函数,能够得到栈的最小元素。要求函数 min、push以及 pop的时间复杂度都是 O(1)。

解题思路:
栈是后进先出的数据结构，要求查询得到栈的最小元素，我们内部实现可以设计两个栈A、B，A栈保存用户进栈数据，B栈保存当前A栈中最小元素。但用户数据进栈，判断B栈的top元素，如果小于用户数据，则B栈top元素再次进入B栈，否则用户数据进入B栈。A栈与B栈一一对应，B栈index索引标志A栈index索引时的最小数据。

由此思路，我们封装一个MinEntry，用于保存当前用户数据，和当前栈的最小值。

代码:

public class MinStack {
	private List<MinEntry> stack = null;
	
	public MinStack(){
		stack = new ArrayList<MinEntry>();
	}
	
	public MinStack(int size){
		stack = new ArrayList<MinEntry>();
	}
	
	public void push(Integer value){
		Integer minest = value;
		if (stack.size() > 0){
			MinEntry top = stack.get(stack.size() - 1);
			if (top.minest < minest){
				minest = top.minest;
			}
		}
		stack.add(new MinEntry(value, minest));
	}
	
	public MinEntry pop(){
		int n = stack.size();
		if (n <= 0){
			throw new EmptyStackException();
		}
		return stack.remove(n - 1);
	}
	
	public MinEntry peek(){
		int n = stack.size();
		if (n <= 0){
			throw new EmptyStackException();
		}
		return stack.get(n - 1);
	}
	
	public boolean empty(){
		return stack.isEmpty();
	}
	
	
	class MinEntry{
		private Integer value;
		private Integer minest;
		public MinEntry(Integer value, Integer minest){
			this.value = value;
			this.minest = minest;
		}
		public Integer getValue(){
			return this.value;
		}
		public Integer getMinest(){
			return minest;
		}
	}
}

测试代码:

public class MinStackTest {
 
	@Test
	public void testPop() {
		int count = 100000;
		Random random = new Random();
		List<Integer> minList = new ArrayList<Integer>(count);
		MinStack stack = new MinStack(count);
		Integer minest = null;
		for (int i = 0; i < count; i++){
			Integer value = random.nextInt();
			if (minest == null || value < minest){
				minest = value;
			}
			minList.add(minest);
			stack.push(value);
		}
		Collections.sort(minList);
		for (int i = 0; i < count; i++){
			assertEquals(stack.pop().getMinest(), minList.get(i));
		}
	}

七. POJ2833(优先队列)

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

大意:
在演讲比赛中，当选手结束演讲时，评委将对他的表现进行评分。工作人员去掉最高等级和最低等级，并计算其余等级的平均值作为选手的最终等级。这是一个简单的问题，因为通常只有几个法官。

让我们考虑一下上述问题的广义形式。给定n个正整数，去掉最大的n1个和最小的n2个，然后计算其余的平均值。

分析:
用优先队列。Hint已经说了，空间不够存储所有的数字的。自己算也可以知道，n最大是 $5*10^6$ ，那么空间大小就是： $4*5*10^6/1024$ ，约等于2wk，而题目只给了1wk的空间，所以我们考虑用两个优先队列，一个存储最大的n1个值，另外一个存储最小的n2个值，再用总和减去这两个就可以计算平均值了。

优先队列:
https://blog.csdn.net/qq_45666842/article/details/121376127

八. POJ1828

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

大意:
这道题目是求猴王到底有多少个，猴王的定义是以他为坐标的。。。没有点的x轴和y轴均大于他，那么这个猴子就被成为猴王，显然猴王不只一个。开始我还一直以为猴王不是一个就是两个。

分析:
首先将输入的猴子按照位置排序，先按x从小到大排列，若x相同则再按y从小到大排列，然后对于排序好的数组，按照从后到前的顺序扫描，由于前面的猴子x不比后面的猴子x大，则若要当大王则必须要y比其后最大的y要大。根据该思想设计了算法。从后往前扫描，记录扫描过的猴子中最大的y，若碰到一个猴子y比之大则该猴子为猴王，记录猴王个数的num ++，并且扫描它之后最大的y即为其y。同时根据排序的原则，为了减少不必要的比较，同时记录下当前扫描过y最大的猴子的x，因为接着扫描过程中x与之相同的猴子肯定当不了大王，从而达到简化的目的。最终的num值即为猴王个数

九. 面试题（二叉树转为链表）

题目:

分析:
用队列等容器收集二叉树中序遍历结果的方法。时间复杂度为O(N)，额外空间复杂度为O(N)，具体过程如下：

生成一个队列，记为queue，按照二叉树中序遍历的顺序，将每个节点放入queue中。
从queue中依次弹出节点，并按照弹出的顺序重连所有的节点即可。

代码:

package com.suanfa.数据结构;

import java.util.LinkedList;
import java.util.Queue;


public class 二叉树 {

    public static class Node {
        public int data;
        public Node left;
        public Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    public static Node convert(Node head) {
        Queue<Node> queue = new LinkedList<>();
        inOrderToQueue(head, queue);
        if (queue.isEmpty()) {
            return head;
        }
        head = queue.poll();
        Node pre = head;
        pre.left = null;
        Node cur = null;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            pre.right = cur;
            cur.left = pre;
            pre = cur;
        }
        pre.right = null;
        return head;
    }

    private static void inOrderToQueue(Node head, Queue<Node> queue) {
        if (head == null) {
            return;
        }
        inOrderToQueue(head.left, queue);
        queue.offer(head);
        inOrderToQueue(head.right, queue);
    }

    public static void main(String[] args) {
        Node node1 = new Node(10);
        Node node2 = new Node(6);
        Node node3 = new Node(14);
        Node node4 = new Node(4);
        Node node5 = new Node(8);
        Node node6 = new Node(12);
        Node node7 = new Node(16);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        Node n = convert(node1);
        while (n != null) {
            System.out.printf("%d ", n.data);
            n = n.right;
        }
    }

}

测试记录:

十. POJ2823(求移动区间最大值最小值)

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

比较不错的单调队列的解法:
https://www.cnblogs.com/I-Love-You-520/p/13454305.html

大意:
给n个数，长度为k的窗口以此右移，求每个窗口中的最大值和最小值。

分析:
单调队列思考：
对于一个单调递增队列，每次从队尾插值，从队头取值。//这题不仅数值单调递增，时间（下标）也单调递增。
队尾维护当前状态最大值，所以插值的时候把队列中较大的值踢掉，这些值已经过时，随便删没问题。
队头维护当前状态最小值，所以查找的时候需要往右找到第一个符合条件的值。

代码:

package com.suanfa.数据结构;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class POJ2823 {
    static int[] a,q,id;
    static int n,k;
    static PrintWriter out = new PrintWriter(System.out);
    public static void main(String[] args) throws IOException {
        StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        sc.nextToken();
        n = (int)sc.nval;
        sc.nextToken();
        k = (int)sc.nval;
        q = new int[n+1];
        id = new int[n+1];
        a = new int[n+1];
        for(int i=1;i<=n;i++) {
            sc.nextToken();
            a[i] = (int)sc.nval;
        }
        getmin();
        getmax();
    }
    public static void getmin() {  //维持单调递增的序列
        int l = 1,r = 0;
        int i;
        for(i=1;i<k;i++) {   //先将前k-1个数入队
            while(l<=r&&q[r]>a[i]) r--;   //l<=r判断是否为空队列  队列中的所有元素都与新入队的元素比较q[r]>a[i]是维持递增   这样队头就是最小元素
            q[++r] = a[i];
            id[r] = i;
        }
        while(i<=n){
            while(l<=r&&q[r]>a[i]) r--;   //l<=r判断是否为空队列  队列中的所有元素都与新入队的元素比较q[r]>a[i]是维持递增   这样队头就是最小元素
            q[++r] = a[i];     //大于a[i]的元素都将出队    这里是用指针模拟出队
            id[r] = i;
            while(id[l]<i-k+1) l++;   //判断队头元素的下标是否属于该滑动窗口  不属于的话将其出队 同样是用指针模拟出队
            out.print(q[l]+" ");
            i++;
        }
        out.println();
        out.flush();
    }
    public static void getmax() {  //同上  维持单调递减的序列
        int l = 1,r = 0;
        int i;
        for(i=1;i<k;i++) {
            while(l<=r&&q[r]<a[i]) r--;
            q[++r] = a[i];
            id[r] = i;
        }
        while(i<=n){
            while(l<=r&&q[r]<a[i]) r--;
            q[++r] = a[i];
            id[r] = i;
            while(id[l]<i-k+1) l++;
            out.print(q[l]+" ");
            i++;
        }
        out.println();
        out.flush();
    }
}

测试记录:

参考:

http://www.dataguru.cn/article-5747-1.html
https://blog.csdn.net/fangchao2061/article/details/43338777

java

「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」

关注作者

文章被以下合辑收录

大数据及数据仓库（共239篇）

DBA转大数据之路

大数据算法系列5:面试题与ACM题选讲1

Table of Contents

一. POJ2299(归并排序)

二. POJ1363(判断合法栈序列)

三. POJ 3349（哈希算法）

四. Uva10391(字符串检索)

五. POJ2255(二叉树遍历)

六. google面试题(栈的min函数)

七. POJ2833(优先队列)

八. POJ1828

九. 面试题（二叉树转为链表）

十. POJ2823(求移动区间最大值最小值)

参考:

文章被以下合辑收录

评论