九度Online Judge求职面试题集及解题思路

2024-01-04 01:33

本文主要是介绍九度Online Judge求职面试题集及解题思路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目出处: http://ac.jobdu.com/hhtproblems.php
解题思路和部分相对复杂的题目代码在所有题目的最后。
题目1:二维数组中的查找
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。数组行数和列数最大均为1000。
题目2:重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。如果题目中所给的前序和中序遍历序列不能构成一棵二叉树,则输出”No”。  

题目3:旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转。

 
题目4:斐波那契数列
输出斐波那契数列的第n项, n<=70。
题目5:跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
题目6:变态跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。n<=50
题目7:矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? n<=70

 
题目8:顺时针打印矩阵
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

 
题目9:栈的压入压出
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。n<=100000。
题目10:二叉搜索树的后序遍历序列
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。n<=10000。

题目11:二叉树中和为某一值的路径
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。n<=10000。

 
题目12:字符串的排序
输入一个字符串,按字典序打印出该字符串中字符的所有排列。 长度不超过9。

 
题目13:数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。n<=100000,数的范围是[1-1000000000]。

 
题目14:最小的K个数
输入n个整数,找出其中最小的K个数,并按从小到大顺序打印。n<=200000,数的范围是[0,1000 000 000]。
题目15:最大子向量和
就是最大子段和,n<=100000,O(n)算法。
题目16:整数中1出现的次数
求两个整数间的数,10进制各个位上1出现的总次数,0<=a,b<=1,000,000,000
题目17:所有员工年龄排序
公司现在要对所有员工的年龄进行排序,请输出排序后的n个员工的年龄,n<=1000000,age<=99。
题目18:丑数
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

 
题目19:找到第一个只出现一次的字符
在一个字符串(1<=字符串长度<=10000,全部由大写字母组成)中找到第一个只出现一次的字符。

 
题目20:数组中的逆序对
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

 
题目21:数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。1<=n <= 10^6,查询次数<1000
题目22:二叉树的深度
输入一棵二叉树,求该树的深度。
题目23:数组中只出现一次的数字
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。2<=n <= 10^6。

 
题目24:和为S的两个数字
输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。n <= 10^6。

 
题目25:和为S的连续正数序列
有多少种连续的正数序列的和为S。S<=1,000,000。

 
题目26:翻转单词顺序
输入一句话,将该句子逆序,但单词的字母顺序不能变。
题目27:Move!Move!!Move!!!
给定字符串S,对它循环左移K位,求输出结果。
题目28:乐透之猜数游戏
给定n个骰子,每个骰子点数为m,求按概率排序前3的点数和。 概率值按 4 舍 5 入要求保留 2 位小数, n(0<=n<=10),m(6<=m<=8)。
题目29:扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

题目30:旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。n<=1000000, 数组中每个元素值不超过10000000。输出旋转数组中最小的元素。

题目思路
题目1:枚举行二分列,复杂度为O(nlogm)。但最简单的方法是直接读入的时候一个一个地比即可。

题目2:常规题,前序的第1个输出的为根结点,在中序中查找到该结点,在该结点前面的为左子树,后边的为右子树,递归重建左子树和右子树。在递归过程中,如果某一步前序的根结点在中序中没有出现,则不能重建。

题目4-7:递推,题目4、5、7递推式其实都是斐波那契数列,f(n)=f(n-1)+f(n-2),只是初值不同。题目6递推式为f(n)=f(n-1)+f(n-2)+...f(0)。由于n不大,可以用64位无符号数存放。如果n变得很大,可以将求解递推式转化为矩阵的n次方,用二分法进行求解,时间复杂度为O(logn)。

题目9:用一个栈作辅助,顺序描述压入序列和弹出序列,如果当前位置上压入序列和弹出序列值相等,直接都向后移一个元素;比较栈顶元素和弹出序列当前值,如果相等,出栈,弹出序列后移一个元素;其余情况,将压入序列当前值压栈,压入序列后移一个元素。如果到最后,弹出序列都处理不完,说明弹出序列不合法。时间复杂度为O(n)。
代码:http://www.oschina.net/code/snippet_203297_11241

题目10:二叉搜索树的性质之一为:根结点值大于左子树,小于右子树。设后序遍历顺序为 A B C,则有A<C<B。因此,从根结点(遍历的最后一个结点)出发,向前找到所有连续的大于根结点的值作为右子树,再往前的所有连续小于根结点的作为左子树,如果往前还有大于根结点的,则不是二叉搜索树的后序遍历结果。递归处理左子树和右子树。时间复杂度约为O(nlogn)。
代码:http://www.oschina.net/code/snippet_203297_11241

题目11:遍历二叉树,累加结果即可。结果可能超出int,需要用long long。

题目12:全排列生成,回溯或调用STL的next_permutation

题目13:将出现一半的数与其他数两两抵消,剩余的最后一个数即是答案。具体做法是每次选两个不同的数两两抵消,要么会抵消一个答案数字和一个非答案数字,要么抵消两个非答案数字,到最后剩余的一定是答案。时间复杂度为O(n)。
代码:http://www.oschina.net/code/snippet_203297_11241

题目14:堆排序,nlog(K);patial_sort;先找最K大的,O(n),再取出前K大的排序,O(KlogK)。题目极容易超时,原因在于输入输出耗费了很大一部分时间,用gets读一行,然后手动获取数据代替n次scanf可以通过。

题目15:动态规划,时间复杂度O(n)。

题目16:按位统计,统计每位上1出现的次数。当前位刚好是1和刚好是0需要单独考虑。
代码:http://www.oschina.net/code/snippet_203297_11241

题目17:哈希,用100大小的数组直接统计,O(n)。

题目18:构造。用2,3,5构造出所有整型数范围内的丑数,排序即可。

题目19:扫描一遍字符串,统计每个字符出现的次数即可。

题目20:归并排序,在merge的时候统计逆序对,设需要merge的数组为A,B,A大小为n,B大小为m。如果A[i]>B[j],则逆序数将增加n-i。
代码:http://www.oschina.net/code/snippet_203297_11241

题目23:设两个数字为A和B,将所有数字异或,其他出现偶数次的数字均被消去,结果是A^B,找到结果中某位为1的位,表示该位上A和B是不同的,扫描一遍所有数字,用该位将所有数字分成两部分,单个部分异或即得到A和B的值。
参考代码:http://www.oschina.net/code/snippet_203297_10737

题目24:用两个游标,一个从头开始A[i],一个从尾开始A[j],如果A[i]+A[j]<S,则i后移一格,否则j前移一格,如果相等,则记录结果。算法复杂度为O(n)。
代码:http://www.oschina.net/code/snippet_203297_11241

题目25:由于序列是等差数列,有S=an+n(n-1)/2,其中a为序列第一个元素,n为个数。枚举n,一直到sqrt(2S),查看是否有整数解即可。复杂度为O(sqrt(S))。

题目28:递推,令f[i][j]表示前i个骰子,点数和为j的次数。有f[i][j] = f[i-1][j-1]+....+f[i-1][j-m]。也可直接用一维的轮换数组进行计算,即g[j] = f[j-1]+...+f[j-m], f=g。
代码:http://www.oschina.net/code/snippet_203297_11241


这篇关于九度Online Judge求职面试题集及解题思路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/567748

相关文章

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

三相直流无刷电机(BLDC)控制算法实现:BLDC有感启动算法思路分析

一枚从事路径规划算法、运动控制算法、BLDC/FOC电机控制算法、工控、物联网工程师,爱吃土豆。如有需要技术交流或者需要方案帮助、需求:以下为联系方式—V 方案1:通过霍尔传感器IO中断触发换相 1.1 整体执行思路 霍尔传感器U、V、W三相通过IO+EXIT中断的方式进行霍尔传感器数据的读取。将IO口配置为上升沿+下降沿中断触发的方式。当霍尔传感器信号发生发生信号的变化就会触发中断在中断

Jenkins 插件 地址证书报错问题解决思路

问题提示摘要: SunCertPathBuilderException: unable to find valid certification path to requested target...... 网上很多的解决方式是更新站点的地址,我这里修改了一个日本的地址(清华镜像也好),其实发现是解决不了上述的报错问题的,其实,最终拉去插件的时候,会提示证书的问题,几经周折找到了其中一遍博文

文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑燃料电池和电解槽虚拟惯量支撑的电力系统优化调度方法》

本专栏栏目提供文章与程序复现思路,具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源程序擅长文章解读,论文与完整源程序,等方面的知识,电网论文源程序关注python

如何打造个性化大学生线上聊天交友系统?Java SpringBoot Vue教程,2025最新设计思路

✍✍计算机编程指导师 ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java实战 | SpringBoot/SSM Python实战项目 | Django 微信小程序/安卓实战项目 大数据实战项目 ⚡⚡文末获取源码 文章目录

将添加功能的抽屉剥离,在父组件调用思路

一、新建组件 新建AddRoleEditerDrawer.vue <template><div><el-drawer v-model="dialog" title="添加角色" :before-close="handleClose" direction="rtl" @colse="cancelForm"class="demo-drawer" modal-class="add-drawer">

[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路,实操解析,解题软件使用,解题方法教程

题目来源 NSSCTF | 在线CTF平台因为热爱,所以长远!NSSCTF平台秉承着开放、自由、共享的精神,欢迎每一个CTFer使用。https://www.nssctf.cn/problem   [SWPUCTF 2021 新生赛]gift_F12 这个题目简单打开后是一个网页  我们一般按F12或者是右键查看源代码。接着我们点击ctrl+f后快速查找,根据题目给的格式我们搜索c

.Net Mvc-导出PDF-思路方案

效果图: 导语:     在我们做项目的过程中,经常会遇到一些服务性的需求,感到特别困扰,明明实用的价值不高,但是还是得实现;     因此小客在这里整理一下自己导出PDF的一些思路,供大家参考。     网上有很多导出PDF运用到的插件,大家也可以看看其他插件的使用,学习学习; 提要:     这里我使用的是-iTextSharp,供大家参考参考,借鉴方案,完善思路,补充自己,一起学习

.net MVC 导出Word--思路详解

序言:          一般在项目的开发过程中,总会接收到一个个需求,其中将数据转换成Work来下载,是一个很常见的需求;          那么,我们改如何处理这种需求,并输出实现呢?          在做的过程中,去思考 1、第一步:首先确认,Work的存在位置,并创建字符输出路:             //在的项目中创建一个存储work的文件夹             string

【POJ】Buy Tickets(思路 + 线段树)

一开始没有思路,之后问了一下学长,需要逆向处理输入。 最后一个加入队列的肯定是没有冲突的,所以我们可以从最后一个开始处理,从后往前,找第 i + 1个空着的地方。 线段树的话记录 区间中 空白位置的个数。 134418332013010521002828Accepted5368K1704MSC++1690B2014-09-14 21:19:45 #include<iost