`
QING____
  • 浏览: 2250492 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

算法编程(二)

 
阅读更多

一、用栈来实现队列的功能

    描述:栈,stack,特点是先进后出;队列,queue,先进先出;请使用栈来实现队列的功能,且此队列具有两个基本操作--添加、删除。

 

    这个题本身并不难,但是不能钻”牛角尖“;一个栈是无论如何也无法实现队列的,那么可以考虑用两个栈来试一试:

    1)两个栈A、B,其中一个只能“添加”,另一个只能“删除”。

    2)初始时,栈为空,如果执行“添加”操作,则选定其中一个栈A保存元素,。

    3)如果此后执行“删除”操作,则将栈A的元素逐个pop,且添加到栈B中,此后原来的栈底成了B的栈顶;那么此时从B中移除的元素,就是最早插入的元素;实现了“先进先出”的功能。

    4)此后再添加,则直接添加到A即可;如果移除,还是从B移除,直到B为空,再次执行3)。

 

    面试者还需要适度考虑多线程并发的情况,这一点属于加分项。代码样例:

public static void main(String[] args) {
    Queue<Integer> queue = new Queue<Integer>();
    queue.add(10);
    queue.add(11);
    System.out.println(queue.poll());
    queue.add(12);
    System.out.println(queue.poll());
}

static class Queue<T> {
    Stack<T> addContainer = new Stack<>();
    Stack<T> removeContainer = new Stack<>();

    synchronized void add(T t) {
        addContainer.push(t);
    }

    synchronized T poll() {
       if(removeContainer.isEmpty()) {
           if(addContainer.isEmpty()) {
               return null;
           }
           while (!addContainer.empty()) {
               removeContainer.push(addContainer.pop());
           }
       }
        return removeContainer.pop();
    }
}

 

二、从单向链表中删除指定的节点,且时间复杂度为O(1)

    输入:单向链表,和一个需要被删除的节点

    输出:无

    这个题有几个需要澄清的地方,首先是个单向链表,第二指定了需要删除的节点,注意是节点引用而不是节点值,然后强调复杂度为O(1)

    单向链表,如果要删除一个节点,最直接的思路就是必须找到此节点的“前一个”和“后一个”节点,然后将“前一个”节点的next引用指向“后一个”节点。这种思路下,需要从头遍历链表,逐个比较才能确定指定节点的位置,那么复杂度就是O(1),怎么办?

 

    其实这个题的解决思路不符合常规,既然无法遍历,而且只知道删除节点,那么久将“下一个”节点的值复制过来,转而删除“下一个”节点,很巧妙。(但是在面向对象编程中,其实这种方式不可行,API内部改变节点的值是违法设计原则的)

    public static void remove(LinkedNodes linked,Node target) {
        //如果target为
        Node nextNode = target.next;
        //如果删除尾节点
        if(nextNode == null) {
            target = null;
            return;
        }
        //如果是链表的首个元素
        //我们在设计链表时header是一个标记性的节点,它指向第一个元素
        if(target == linked.header.next) {
            linked.header.next = nextNode;
            return;
        }
        //删除中间节点
        target.value = nextNode.value;//覆盖值
        target.next = nextNode.next;
        nextNode.next = null;//
    }

 

三、从一个单线链表中找到倒数第K个节点

    这个题的解法很多,最基本的方式就是:遍历一次单向链表,计算出链表的总长度N,然后再遍历一次,对于第(N - K + 1)位置的元素,就是倒数第K个。这种实现,很简单,性能也不能说差,但是最大的问题就是需要遍历两次。假如面试官问你:如何在只遍历一次的情况下完成呢?

 

    单向链表的特点就是不能“反向”遍历,如果只遍历一次的话,那么我其实只要能在遍历的时候,以当前节点为基准,标记它的倒数第K个元素的位置就行了;那么当前节点是最后一个元素的时候,那么结果就显而易见了。

   在编程的时候,我们尽可能的兼顾边界情况。代码样例为:

public static Node find(LinkedNodes linked,int k) {
    if(linked == null) {
        return null;
    }
    //我们暂定header是标记性节点,链表的首个元素为header.next
    Node item = linked.header.next;
    //如果链表为空,怎返回
    if(item == null) {
        return null;
    }
    int i= 1;//当前节点的索引位置,从1开始
    Node target = null;
    while (true) {
        if(item == null) {
            break;
        }

        if(i - k >= 0) {
            if(target == null) {
                target = linked.header.next;
            }else {
                target = target.next;
            }
        }
        item = item.next;
        i++;
    }
    return target;

}
static class LinkedNodes {
    Node header = new Node();//标记性节点
    Node tail;
}
static class Node {
    Node next;
    int value;
}

 

四、将一个单向链表反转

    指定一个单向链表,不额外使用其他数据结构的前提下,保持原有元素的相对顺序,将此链表的方向反转。比如:

    输入链表:A -->B-->C-->D-->E

    输出链表:A<--B<--C<--D<--E

    这个题看起来容易,思路也很简单,但是编程的时候,总是小问题居多。

public static void reserve(LinkedNodes linked) {
    if(linked == null) {
        return;
    }
    Node current = linked.header.next;
    if(current == null) {
        return;//如果是空链表
    }

    Node next = current.next;
    current.next = null;//首个节点断开,特殊处理
    while (true) {
        if (next == null) {
            break;
        }
        Node item = next.next;
        next.next = current;
        current = next;
        next = item;
    }
    linked.header.next = current;
}

 

五、将两个有序的单向链表合并成一个新的有序的链表

    现有两个单向链表,链表中的元素按照值正序排列,要求将这两个链表合并成一个新的链表,且新链表中的元素也是正序排列的,两个链表中的元素值有可能重复,而且两个链表的元素个数有可能不同。

 

    其实这个题的实施方式,和“多路合并”非常类似。代码样例如下:

public static LinkedNodes merge(LinkedNodes left,LinkedNodes right) {
    //对于null,我们直接返回即可
    if(left == null || right == null) {
        return null;
    }
    LinkedNodes result = new LinkedNodes();
    Node n1 = left.header.next;
    Node n2 = right.header.next;
    while (true) {
        if(n1 == null && n2 == null) {
            break;
        }

        Node selected;
        //如果其中一个链表已经遍历完毕,则直接将另一个链表数据添加就行
        if(n1 !=null && n2 != null) {
            int v1 = n1.value;
            int v2 = n2.value;
            if(v1 <= v2) {
                selected = n1;
                n1 = n1.next;
            }else {
                selected = n2;
                n2 = n2.next;
            }
        }else if(n1 == null){
            selected = n2;
            n2 = n2.next;
        } else {
            selected = n1;
            n1 = n1.next;
        }

        if(result.header.next == null) {
            result.header.next = selected;
            result.tail = new Node();
        }

        result.tail.next = selected;
        result.tail = selected;
    }
    return result;

}

  

六、将指定的二叉树转换成它的镜像

    所谓镜像,就类似于“镜子的成像”,模拟图示如下:

二叉树:
        1
        |
    2      6
   /\       \
  1 3        8

镜像为:
         1
         |
    6       2
    /       /\
   8       3  1

即任何节点的左右子节点都交换位置

 

    代码样例:

static class BinaryTree {
    BinaryTreeNode root;
}
static class BinaryTreeNode {
    BinaryTreeNode left;
    BinaryTreeNode right;
    int value;
}

public static void mirror(BinaryTree tree) {
    if(tree == null) {
        return;
    }
    BinaryTreeNode root = tree.root;
    mirror(root);
}

private static void mirror(BinaryTreeNode node) {
    if(node == null) {
        return;
    }
    BinaryTreeNode left = node.left;
    BinaryTreeNode right = node.right;
    node.left = right;
    node.right = left;
    mirror(left);
    mirror(right);
}

 

七、写一个简单的多路合并输出的代码

    比如,有两个有序的数组A、B,元素为数字,排序为从小到大,A和B中可能有重复的数字,将A、B数组元素同时作为输入源,请有序输出前N个不同的元素。

    比如:A为{2,3,8,12,25},B为{2,3,5,11,22},输出前6个元素,结果为{2,3,5,8,11,12}

public static int[] merge(int[] a,int[] b,int n) {
    //边界条件
    //TODO
    int al = a.length;
    int bl = b.length;
    int j = 0;
    int c = 0;
    int[] result = new int[n];
    for(int i = 0 ;i < al; i++) {
        if(c >= n - 1) {
            break;
        }
        int x = a[i];
        for(;j< bl;j++) {
            int y = b[j];
            if(x > y) {
                result[c] = y;
                c++;
            }else if(x < y) {
                result[c] = x;
                c++;
                break;
            }
        }
    }
    return result;
}

 

分享到:
评论

相关推荐

    JAVA算法编程题目及答案.doc

    JAVA算法编程题目及答案 本资源提供了50道JAVA算法编程题目及答案,涵盖了算法设计、数据结构、程序设计等多个方面的知识点。以下是对标题、描述、标签和部分内容的详细解释: 标题:JAVA算法编程题目及答案 本...

    C#数值计算算法编程(周长发)

    C#数值计算算法编程 周长发,有利于数值算法编程开发

    算法&&编程

    常见的算法类型包括排序(如冒泡排序、快速排序、归并排序)、搜索(如二分查找、广度优先搜索、深度优先搜索)、图论算法(如最短路径问题、最小生成树)以及动态规划等。理解算法的工作原理并能高效地实现它们,是...

    java 遗传算法 编程

    通过阅读本书,你将熟悉遗传算法与编程语言相关的问题和概念,掌握构建自己的算法所需的全部知识,并且将获得用遗传算法解决问题的能力。请拿起本书,进入遗传算法这个迷人的领域,看看真正能工作的Java代码,并运用...

    算法编程大赛题目(.zip)

    在本资源中,"算法编程大赛题目(.zip)"包含了一系列来自谷歌算法大赛的编程挑战,这些挑战旨在提升编程思维并锻炼解决复杂问题的能力。以下是这些算法问题的详细解析和相关知识点: 1. **磁盘问题**:这通常涉及...

    C#数值计算算法编程.zip

    12 用 C#实现数伯叶算算法的要点 7 第 2 章 复数运算 .................................. · ·12 2.1 复数类设计 12 2.2 复数乘法 25 23 复数附法 26 2.4 复数的膜 书,27 25 复数的根 28 2.6 复数的实茄指数 29...

    并行计算——结构·算法·编程习题答案

    本资料主要关注并行计算的三个方面:结构、算法和编程,旨在通过习题解答帮助学习者深入理解和应用这些概念。 1. **并行计算结构**: 并行计算结构通常分为共享内存和分布式内存两大类。共享内存系统中,所有...

    游戏核心算法编程内幕.pdf

    游戏算法电子书 感觉不错 分享给大家 游戏核心算法编程内幕.pdf

    游戏核心算法编程内幕

    《游戏核心算法编程内幕》由三部分组成。其中第一部分主要介绍游戏编程的基本概念;第二部分详细介绍游戏编程中的各种技术和算法;第三部分是附录,介绍游戏编程中相关技术和知识以及其他相关读物。《游戏核心算法...

    JAVA遗传算法编程pdf版本书籍

    《JAVA遗传算法编程》这本书是面向对遗传算法有兴趣并希望通过Java语言进行实现的读者的一本专业指南。遗传算法(Genetic Algorithm,简称GA)是一种基于生物进化论中的自然选择和遗传原理的优化方法,它在解决复杂...

    C#数值计算算法编程

    PDF格式的C#数值计算算法编程,记录了各种初级、高级算法。

    编程珠矶算法

    《编程珠矶算法》是一套深入探讨算法的电子书籍,旨在帮助读者理解并掌握各种重要的算法,提升编程技能。在计算机科学中,算法是解决问题或执行任务的精确步骤,是编程的基础。通过学习这些算法,开发者可以更有效地...

    Scratch编程入门与算法进阶.pptx

    第二部分是算法进阶,详细介绍了几个经典的算法问题及其对应的Scratch实现。这些问题包括约瑟夫环问题、最长回文子串、0/1背包问题、拓扑排序等。通过这些实例,读者可以深入理解算法的本质和实现方法,提高解决问题...

    java遗传算法编程pdf

    一本基于java遗传算法编程技术的讲解书书籍,全书讲解很全面,适合对遗传算法感兴趣的读者。本书共分为6章,每章都会有实例。

    并行计算——结构·算法·编程 习题答案

    在《并行计算——结构·算法·编程》这本书中,作者深入探讨了这一主题,提供了丰富的习题来帮助读者理解和掌握相关概念。现在,我们来详细探讨这些习题答案中可能涵盖的知识点。 首先,结构方面,可能包括以下内容...

    编程语言算法100例

    2. **搜索算法**:如二分查找、广度优先搜索(BFS)、深度优先搜索(DFS),以及哈希表查找等。这些算法在数据检索和遍历复杂结构时发挥关键作用。 3. **图论算法**:如Dijkstra最短路径算法、Floyd-Warshall全连接...

    Python编程入门与算法进阶.pptx

    本书分为两个部分,第一部分是Python编程入门,第二部分是算法进阶。 在Python编程入门部分,本书详细讲解了Python编程的基础知识,包括变量、数据类型、运算符、条件语句和循环语句等。通过简单的例子和练习题,...

    [并行计算——结构·算法·编程].陈国良.文字版

    并行计算 陈国良编著 呵呵 大家来下载 是第三版《并行计算:结构•算法•编程(第3版)》是并行计算系列丛书之开篇,它以并行计算为主题,围绕并行计算机、并行算法和并行程序设计展开讨论,强调融并行计算机体系结构、...

Global site tag (gtag.js) - Google Analytics