一、给定一个整数序列,请获取最小(最大)的K个数字
这个题还算比较熟悉,在大数据计算时,经常会遇到类似于“Top N”的情况,这个题的解法有很多种,本例还是采用惯例做法:创建一个K大小的容器,容器内的数字都是排序的;在遍历输入序列时,如果遇到比容器内最大值还要大的数字时,则将容器中的最小值移除,即容器中保留K个“已经遇见”的最大数字。在java中,我们直接使用TreeSet作为容器,当然你也可以自己构建一个红黑数。
代码样例:
public static TreeSet<Integer> find(int[] source,int k) { TreeSet<Integer> top = new TreeSet<>(); for(int i= 0; i< source.length; i++) { int item = source[i]; if(top.isEmpty() || top.size() < k) { top.add(item); continue; } if(top.last() > item) { top.add(item); top.pollLast();//移除最后一个 } } return top; }
二、给定一个整数数组序列,请计算出“连续子数组”和值的最大值,数组中正负值都有,无序
描述:输入一个数组,这个数组中有正、负整数组成,求数组中“连续的几个元素”的和值的最大值;比如原始数组为{1,-2,3,10,-4,7,2,-5},其中{3,10,-4,7,2}这个子数组的和值最大,为18。
这个题其实并不复杂,认识到判断时机就可以突破了。
数组:1,-2,3,10,-4,7,2,-5 1) 初始最大值为,max = 1,即数组的第一个元素。 2) 1,-2和值为-1,因为-1比max小,继续。 3) -1,3和值为-2,此时我们就需要做中断了,因为-2比当前元素3的值还要小, 因此我们可以断定,前面的“子数组”的计算是无效的 (只要它参与计算,只会降低总和); 所以此时,我们将3作为新子数组的开始,max = 3,继续遍历。 4) 遍历时,如果和值比当前max大,则替换max。 直到数组的结尾!
代码样例:
private static int maxSum(int[] source) { if(source.length == 0) { throw new RuntimeException("Empty array!"); } int max = source[0]; int length = source.length; int current = max; for (int i = 1 ; i < length; i++) { current = source[i] + current; if (current <= source[i]) { max = source[i]; current = max; continue; } if(current > max) { max = current; } } return max; }
三、给定一个字符数组,请获得此数组中重复出现次数最多的字符元素(字符元素一定有重复)
这个题,其实很简单,如果你钻了牛角尖,估计就比较麻烦:比如你尝试使用逐个遍历比较的方式!我们已知的字符是有限的,我们可以使用Map来保存每个字符以及其出现的次数,这样就很容易得到答案,Map的key为字符值,value为其出现的次数。
代码样例:
public static char maxTimes(char[] sources) { if(sources.length == 0) { throw new RuntimeException("Empty array!"); } int maxTimes = 1; char result = sources[0]; Map<Character,Integer> container = new HashMap<>(); for(int i = 0;i < sources.length; i++) { char item = sources[i]; if(container.containsKey(item)) { Integer times = container.get(item); times++; if(times > maxTimes) { maxTimes = times; result = item; } container.put(item,times++); }else { container.put(item,1); } } return result; }
题目的变种可以为:
给定1亿个数字,它们被保存在文件中,请你找出出现次数最多的哪个数字!
思路为分治法,将数组取模并分散存储在多个小文件中,确保相同的数字被转存在相同的文件中,然后逐个计算每个文件中出现次数最多的数字,然后取次数最多的那个即可。
四、有两个单向链表,它们在某个节点开始,后续节点都重合,请你用程序找出首个重合点。
比如如下两个链表:
1-->2-->3-->4-->5-->6-->7
7-->10->5-->6-->7
我们看出,5是这两个链表的首个重合点。要实现这个算法,用粗暴的方式逐个遍历复杂度太高,当然实现起来简单。我们在上述几个题目都已经表示,对于单向链表,从后遍历或者查找,最好的办法就是借助辅助栈,这个题目我们也这么做。
用两个辅助栈分表保存链表的节点,然后同时逐个弹出,并比较栈顶的值,直到第一个不相同的节点出现为止。代码样例如下:
public static Node joinPoint(LinkedNodes first,LinkedNodes second) { if(first == null || second == null) { return null; } Node firstRoot = first.header.next; Node secondRoot = second.header.next; if(firstRoot == null || secondRoot == null) { return null; } //借助辅助栈,将单向链表反序 Stack<Node> data1 = new Stack<>(); Stack<Node> data2 = new Stack<>(); while (true) { Node item = firstRoot.next; if(item == null) { break; } data1.push(item); } while (true) { Node item = secondRoot.next; if(item == null) { break; } data2.push(item); } //依次弹出栈,并比较,最后一个相同点就是join点 Node result = null; while (true) { Node n1 = data1.pop(); Node n2 = data2.pop(); if(n1.value != n2.value) { break; }else { result = n1;//or n2; } } return result; }
五、求一个二叉树的最大深度
二叉树的树深,就是root节点到最底层叶子节点的最大距离。很简单,递归实现;代码样例如下:
public static int depth(BinaryTreeNode node) { if(node == null) { return 0; } BinaryTreeNode left = node.left; int l = 0; if(left != null) { l = depth(left); } BinaryTreeNode right = node.right; int r = 0; if(right != null) { r = depth(right); } return l > r ? l + 1 : r + 1; }
相关推荐
java算法编程题目及答案50道
C#数值计算算法编程 周长发,有利于数值算法编程开发
并行计算——结构·算法·编程习题答案 并行计算——结构·算法·编程习题答案 并行计算——结构·算法·编程习题答案 并行计算——结构·算法·编程习题答案 并行计算——结构·算法·编程习题答案
C#数值计算算法编程,C#数值计算算法编程,C#数值计算算法编程
12 用 C#实现数伯叶算算法的要点 7 第 2 章 复数运算 .................................. · ·12 2.1 复数类设计 12 2.2 复数乘法 25 23 复数附法 26 2.4 复数的膜 书,27 25 复数的根 28 2.6 复数的实茄指数 29...
C#数值计算算法编程.rar C#数值计算算法编程.rar
Java数值计算算法编程 + 目录 你可以对应目录选择所需要的代码。
游戏算法电子书 感觉不错 分享给大家 游戏核心算法编程内幕.pdf
资源包含了谷歌算法大赛的几个算法编程问题(包括磁盘问题,公交车,画图,矩阵中查找单词路径,球和篮子,扔石头问题)的要求和解答,适合喜欢算法的人研究,锻炼编程思维,挑战自我!
《游戏核心算法编程内幕》由三部分组成。其中第一部分主要介绍游戏编程的基本概念;第二部分详细介绍游戏编程中的各种技术和算法;第三部分是附录,介绍游戏编程中相关技术和知识以及其他相关读物。《游戏核心算法...
java算法与编程面试题java算法与编程面试题java算法与编程面试题java算法与编程面试题java算法与编程面试题
算法和编程方面不可多得的经典之作,国外大师所著
遗传算法编程分析.pdf遗传算法编程分析.pdf遗传算法编程分析.pdf遗传算法编程分析.pdf 遗传算法编程分析.pdf
决策树ID3算法编程(c语言课程设计)
一本基于java遗传算法编程技术的讲解书书籍,全书讲解很全面,适合对遗传算法感兴趣的读者。本书共分为6章,每章都会有实例。
Java算法编程题,一共50道,答案完整,可以检测Java的掌握情况
并行计算 陈国良编著 呵呵 大家来下载 是第三版《并行计算:结构•算法•编程(第3版)》是并行计算系列丛书之开篇,它以并行计算为主题,围绕并行计算机、并行算法和并行程序设计展开讨论,强调融并行计算机体系结构、...