一、用栈来实现队列的功能
描述:栈,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算法编程题目及答案 本资源提供了50道JAVA算法编程题目及答案,涵盖了算法设计、数据结构、程序设计等多个方面的知识点。以下是对标题、描述、标签和部分内容的详细解释: 标题:JAVA算法编程题目及答案 本...
C#数值计算算法编程 周长发,有利于数值算法编程开发
常见的算法类型包括排序(如冒泡排序、快速排序、归并排序)、搜索(如二分查找、广度优先搜索、深度优先搜索)、图论算法(如最短路径问题、最小生成树)以及动态规划等。理解算法的工作原理并能高效地实现它们,是...
通过阅读本书,你将熟悉遗传算法与编程语言相关的问题和概念,掌握构建自己的算法所需的全部知识,并且将获得用遗传算法解决问题的能力。请拿起本书,进入遗传算法这个迷人的领域,看看真正能工作的Java代码,并运用...
在本资源中,"算法编程大赛题目(.zip)"包含了一系列来自谷歌算法大赛的编程挑战,这些挑战旨在提升编程思维并锻炼解决复杂问题的能力。以下是这些算法问题的详细解析和相关知识点: 1. **磁盘问题**:这通常涉及...
12 用 C#实现数伯叶算算法的要点 7 第 2 章 复数运算 .................................. · ·12 2.1 复数类设计 12 2.2 复数乘法 25 23 复数附法 26 2.4 复数的膜 书,27 25 复数的根 28 2.6 复数的实茄指数 29...
本资料主要关注并行计算的三个方面:结构、算法和编程,旨在通过习题解答帮助学习者深入理解和应用这些概念。 1. **并行计算结构**: 并行计算结构通常分为共享内存和分布式内存两大类。共享内存系统中,所有...
游戏算法电子书 感觉不错 分享给大家 游戏核心算法编程内幕.pdf
《游戏核心算法编程内幕》由三部分组成。其中第一部分主要介绍游戏编程的基本概念;第二部分详细介绍游戏编程中的各种技术和算法;第三部分是附录,介绍游戏编程中相关技术和知识以及其他相关读物。《游戏核心算法...
《JAVA遗传算法编程》这本书是面向对遗传算法有兴趣并希望通过Java语言进行实现的读者的一本专业指南。遗传算法(Genetic Algorithm,简称GA)是一种基于生物进化论中的自然选择和遗传原理的优化方法,它在解决复杂...
PDF格式的C#数值计算算法编程,记录了各种初级、高级算法。
《编程珠矶算法》是一套深入探讨算法的电子书籍,旨在帮助读者理解并掌握各种重要的算法,提升编程技能。在计算机科学中,算法是解决问题或执行任务的精确步骤,是编程的基础。通过学习这些算法,开发者可以更有效地...
第二部分是算法进阶,详细介绍了几个经典的算法问题及其对应的Scratch实现。这些问题包括约瑟夫环问题、最长回文子串、0/1背包问题、拓扑排序等。通过这些实例,读者可以深入理解算法的本质和实现方法,提高解决问题...
一本基于java遗传算法编程技术的讲解书书籍,全书讲解很全面,适合对遗传算法感兴趣的读者。本书共分为6章,每章都会有实例。
在《并行计算——结构·算法·编程》这本书中,作者深入探讨了这一主题,提供了丰富的习题来帮助读者理解和掌握相关概念。现在,我们来详细探讨这些习题答案中可能涵盖的知识点。 首先,结构方面,可能包括以下内容...
2. **搜索算法**:如二分查找、广度优先搜索(BFS)、深度优先搜索(DFS),以及哈希表查找等。这些算法在数据检索和遍历复杂结构时发挥关键作用。 3. **图论算法**:如Dijkstra最短路径算法、Floyd-Warshall全连接...
本书分为两个部分,第一部分是Python编程入门,第二部分是算法进阶。 在Python编程入门部分,本书详细讲解了Python编程的基础知识,包括变量、数据类型、运算符、条件语句和循环语句等。通过简单的例子和练习题,...
并行计算 陈国良编著 呵呵 大家来下载 是第三版《并行计算:结构•算法•编程(第3版)》是并行计算系列丛书之开篇,它以并行计算为主题,围绕并行计算机、并行算法和并行程序设计展开讨论,强调融并行计算机体系结构、...