作者:ShawnNg
链接:https://www.nowcoder.com/discuss/33737
来源:牛客网
编程题
- 1~n这n个数现在去掉两个,如何找到去掉的两个数。 假设去掉的两个数是a和b,那么通过求和,平方和可以知道a+b和a^2+b^2,然后解方程就行了。
- char a[4] = {1, 2, 3, 4}; char *b = a; b[0] = 100; 请问输出a的结果是什么?
- 一个 N*M 的矩阵,从左上走到右下最小需要(N+M)步走完,问一共有多少种走法。
- 一个严格递增的数组,将前缀取一部分放在后面,在修改后的数组上找到最小的数。(剑指Offer原题)
- 一个大写字符串如ABABB(len<1000),代表游客进游乐场的顺序及从哪个入口进入,要求每个入口(不多于26个入口)从第一个游客直到该入口的最后一个游客,检票员都不能离开,问最少检票人数K。
- 一个字符数组中,每个字符都出现了3次,只有一个出现了2次,如果快速找出这个出现2次的?
- 一个字符矩阵,只可能是R,G,B三种字符。判断是否满足某个条件。这个条件是每种符号连成一个长方体,三个长方体长宽一致,且横着平行
- 一个广告,它有一个id,一个上线时间,一个下线时间,现在我有很多这样的广告,如果现在给你一个时间,告诉我有多少个广告在这个时间在线的
- 一个数据流中,如何采样得到100个数,保证采样得到的100个数是随机的?
- 一个数组中某个数出现次数大于一半,最快找出该数。
- 一个数组只有一个数字是单独出现,其他出现了三次。
- 一个数组存着1-1000连续的整数,假如我取出其中一个数,怎么能快速找到(用类二分查找)
- 一个数组存着负数与正数,将正数放在前面,负数放在后面
- 一个运算序列只有+、*、数字,计算运算序列的结果。(Code)
- 一堆ip地址区间,不会重叠,来一个新的ip地址,看它在不在,在哪个区间。
- 一维数组,swap 其中的几对数字(每个数字只属于一次 swap 操作),实现查找(与二分有关);
- 一维有序数组,经过循环位移后,最小的数出现在数列中间,如果原数组严格递增或递减,如何找这个最小数;
- 一维有序数组,经过循环位移后,最小的数出现在数列中间,如果原数组严格递增,如何找这个最小数。
- 一维有序数组,经过循环位移后,最小的数出现在数列中间,如果原数组非严格递增或递减,如何找这个最小数;
- 一维有序数组,经过循环位移后,最小的数出现在数列中间,数组可能是递增、递减、递减后递增、递增后递减四种情况,递增递减都是非严格的,如果有转折点,返回转折点的值,否则返回-1;
- 一道题:给定一个整数数组,里面有两个数相同,其他数都是不同的,如何尽快找到这两个数(答,用hash表,O(N),有更好的方法么?)
- 一题是多位数用链表存储( e.g. 123 用 1->2->3 存储),实现相加功能函数
- 不创建临时产量换两个数
- 两个同样大小有序数组求中位数,写代码
- 两个大整数相乘。(Code)
- 两棵树相加——对应位置两棵树都有值则相加,对应位置只有一棵树有值则取该值;
- 中序遍历二叉树,利用O(1)空间统计遍历的每个节点的层次。(Bug Free Code)
- 中缀表达式转逆波兰表达式,逆波兰表达式求值;
- 为分析用户行为,系统常需存储用户的一些 query ,但因 query 非常多,故系统不能全存,设系统每天只存 m 个 query ,现设计一个算法,对用户请求的 query 进行随机选择 m 个,请给一个方案,使得每个 query 被抽中的概率相等,并分析之,注意:不到最后一刻,并不知用户的总请求量。
- 二分查找
- 二分查找,查找target,在区间[start,end]之间,如果有重复元素,返回最后一个下标,其他情况返回-1
- 二叉树前序递归遍历算法(手写代码)
- 二叉树的前中后遍历
- 二叉树的文件存储,也就是序列化。
- 二叉树遍历,描述下层序遍历。
- 二维数组,每行递增,每列递增,任意交换其中的两数,发现并恢复。
- 二维数组,每行递增,每列递增,实现查找。
- 二维数组,每行递增,每列递增,求第k大的数。
- 什么样的数据结构可以满足多次插入删除,取最小数,给出时间复杂度。
- 介绍二叉树前序遍历非递归遍历算法(手写代码)
- 介绍大顶堆和小顶堆
- 从一组数中找出和为sum的三个数(leetcode原题,先sort再找,并且剪枝),写代码,四个数呢?说思路。
- 假设有个M*N的方格,从最左下方开始往最右上方走,每次只能往右或者往上,问有多少种走法,假设中间有若干个格子不能走,又有多少种走法。
- 允许两个元素交换一次的最大连续子序列和。
- 全排列
- 全排列。
- 冒泡排序(手写代码)
- 写 find 函数,在目标串中匹配模式串(要考虑中文字符的情况)
- 写一个二叉树的非递归的后续遍历
- 写一个简单的正则匹配表达式(将文本中的123.4匹配出来)
- 写个动态规划,最长公共子序列
- 判断一个字符串是否为另外一个字符串旋转之后的字符串
- 前k大的数
- 单链表的翻转
- 去掉连续的重复数字,输出新数组,例如:1,2,2,2,1,3,5——> 3,5。
- 去除字符串S1中的字符使得最终的字符串S2不包含’ab’和’c’。(Code)
- 合法括号匹配
- 在一个字符串中,找出最长的无重复字符的字串
- 在二叉树结点结构中加一个指针域,使其指向层次遍历的下一个结点,特别地,每一层的最后一个结点为空。(Code)
- 堆排序(手写代码)
- 堆是怎么调整的。
- 复杂链表的复制。
- 如果给出一个二叉搜索树的后续能不能建立(可以,因为只要将遍历结果排序就可以得到中序结果)。
- 字符串反转(手写代码)
- 字符串移位,给出字符串abc##dfg##gh,实现将所有#移至字符串串头。输出####abcdfggh。
- 字符串转整数
- 字符串,给一个url,求中间的site
- 字符串,给一个url,求中间的site。
- 定义满足$n=x^a+y^b$($x,y,a,b$是非负整数)的n是神奇数。如$4 = 2^0 + 3^1,17 = 2^3 + 3^2$。输入l和r,请求出闭区间$[l,r]$里,最长的一段不含有神奇数的连续区间长度。$x,y,l,r<=10^{18},x>=2,y>=2$,如$3\ 5\ 10\ 22$,在$[10,22]$区间内,$x=3,y=5$的条件下,区间内[14]是神奇数,所以最长的区间是$[15,22]$长度为$8$,如$2,3,1,10$,在$[1,10]$区间内,$x=2,y=3$的条件下,$2,3,4,5,7,9$都是神奇数,所以最长的区间只有长度$1$。
- 实现栈,使得 添加、删除、max 操作的复杂度为 O(1)。
- 对于一个字符串,请设计一个算法,只在字符串的单词间做逆序调整,也就是说,字符串由一些由空格分隔的部分组成,你需要将这些部分逆序。给定一个原字符串A和它的长度,请返回逆序后的字符串。
- 对于一个字符串,请设计一个算法,将字符串的长度为len的前缀平移到字符串的最后。
- 寻找字符串中第一个只出现一次的字符;
- 将字符串连续重复出现的字符删到只剩一个,这个可以用双指针,时间复杂度n,空间复杂度1。
- 常用排序算法的时间和空间复杂度
- 平衡二叉树是什么
- 归并排序(手写代码)
- 快速排序(手写代码)
- 快速排序+二分查找
- 手写快排(easy)
- 打印数组的组合数。
- 打印螺旋数组;
- 把一个bst转化成一个双向链表。
- 把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,不能申请额外的空间。例如AbcDeFGhi ->bceiADFG
- 排序二叉树转双向链表。(Code)
- 描述Dijkstra最短路径算法
- 插入排序(手写代码)
- 数列中找第 k 大的数字(与快排或堆排序有关)
- 数据解压缩,3(a4(ab)) -> aababababaababababaabababab;
- 数组有只有一个数出现一次,其他数都出现三次,找出那个数。
- 旋转数组
- 最少时间复杂度求数组中第k大的数。(Code)
- 最短路径代码。
- 最长公共子串(动态规划有关);
- 最长公共子序列
- 有一堆无向好友列表 1-2, 3-4, 2-3 之类的,问能不能把这些用户划分两组,组内都不互为好友。
- 有序数组寻找和为某数的一对数字;
- 正数数组,找三个数使积最小,问有多少种选择。
- 母鸡、公鸡和小鸡问题:公鸡五块一只,母鸡三块一只,小鸡一块三只,用100元买100只鸡的所有方法。
- 求double类型的二进制1的个数。
- 求二叉树最近公共祖先(leetcode原题)
- 求连续子数组最大乘积,还让考虑边界问题(最后问了:连乘有可能导致溢出,存不下了)
- 用一个队列,将每个二叉树的root先放入队列。
- 用数组实现队列,各操作的复杂度分析。
- 用速度不同的指针可以判断链表中是否有环,问两速度满足怎样的关系可以保证发现环。
- 直接插入排序写代码
- 看段代码,问输出是啥。(就是段求二进制中1的个数)
- 矩阵求最长连续递增的路径长度
- 矩阵求最长连续递增的路径长度。
- 第一题是链表倒数第 k 节点;第二题是二叉树打印路径,第三题是矩阵中将 0 元素所在行列全置 0 的最优空间解法
- 第二轮是写出一个算法输出二叉树的 s 序列,何为 s 序列,比如现在有个二叉树 1-2,3-4,5 6,7 这是一颗完全二叉树, S 序列输出就是按照 1237654 这个顺序输出,用两个栈就能实现比较简单。
- 算法题,也只记得一个了:存在一个数组,大小98,里面的元素均为在[1,100],且无重复, 不申请额外空间的情况下,在时间复杂度为O(N)情况下,找出缺失的两个元素值。
- 给一个n*n的矩阵,矩阵中满足每行每列都是递增的,要查找矩阵是否存在某个数.(leetcode原题)
- 给一个数组,只有一个元素出现了一次,其他都出现了两次,找出出现一次的数。
- 给一个数组,数组种存在一种数,它的左边都比它小,右边都比它大,找出所有这些数的位置。
- 给一个股票,n天的价格,只能两次买入卖出,而且只能只能先卖再买,问最多赚多少钱?
- 给一个股票,n天的价格,只能进行一次买入和卖出,问最多赚多少钱?
- 给一个股票,n天的价格,可以买入卖出k次,而且只能只能先卖再买,问最多赚多少钱?
- 给一个股票,n天的价格,可以无限次买入卖出,问最多赚多少钱?
- 给了一个链表,第1个结点标号为1,把链表中标号在M到N区间的部分反转。
- 给你一个无重复的数组输出全排列。
- 给你一颗二叉树按层输出每一层输出后都换行
- 给出一个二维矩阵,从(0,0)出发走到右下角,只能向右或向下走,找到一条路径,是这条路径上的总和最大。
- 给出一段代码问代码作用(二进制数据1的个数)
- 给出一颗二叉树,两个叶节点,找到这两个叶节点互连通的一条最短路径。
- 给定一个数组,只有一个元素出现了一次,其他都出现了3次,找出出现一次的数。
- 给定一个数组,有两个元素出现了一次,其他都出现了两次,找出两个出现一次的数。
- 给定一个正整数向量,判断这个向量是否存在一个片段,使得反转这个片段后能够使该向量升序排列。如:[1, 2, 4, 3],就可以通过反转[4, 3]使得向量变为[1, 2, 3, 4]。
- 给定二叉树的先序跟后序遍历,能不能将二叉树重建(不能,因为先序:父节点-左节点-右节点,后序:左节点-右节点-父节点,两者的拓扑序列是一样的,所以无法建立)
- 给定循环递增数组 $a=[7,8,9,1,2,3]$和一个值$k=2$,返回该值得再数组中的下标。
- 给定数组A[]={1,4,7,…}和一个数T。求和为T的A中的数最少要几个。A中的数可复用。 我写了个递归,面试官不建议使用,因为效率不高。但没有反对。
- 给定数组,寻找 next big(堆排序有关);
- 给我一个数组[1,2,5,10,20,50,100],可以从里面取若干个数,要求得出和为100的不同取法有多少?(说出思路)
- 统计数列中的逆序对(归并排序有关);
- 编程题:实现求正整数平方根整数部分的函数(使用梯度下降)
- 翻转二叉树(Code)
- 若干个二叉树,如何按照层序遍历
- 设 rand ( s , t )返回 [s,t] 之间的随机小数,利用该函数在一个半径为 R 的圆内找随机 n 个点,并给出时间复杂度分析。
- 输入一个大长方形,长宽ab,和一堆小长方形。选择两个小长方形,它能放进大长方形,而这个小长方形面积和最大
-
输入一个宿舍楼亮灯描述图,计算把所有灯关掉的最短时间,管理员起点在左下角,只能在最左或最右的楼梯往上一层,不可往下一层。每次往上一层花费1分钟,每次往左或往右一间宿舍花费1分钟,关灯不花时间。输入的高<=15,宽<=100。
如图:0010 0100 从左下角开始,最短花费时间是先往右(关灯),再往左,再上一层,再往右两次(关灯)完成:5
再如:
001000 000010 000010 最短时间是先往右四次(关灯),往右一次,上一层,往左一次(关灯),往右一次,上一层,往左三次(关灯),完成,12
- 输入两个正数数组,在两个数组分别选一个数,要求第一个数组选的数的下标小于第二个数组选的数的下标。使得两个数的乘积最大。
- 输出字符串中的所有重复子串,例如:abcab,输出: a, b, ab
- 连续子数组最大和
- 迷宫的深度搜索、广度搜索;
- 选取任意数据结构实现添加、删除、随机返回三个功能,分析复杂度。
- 选择排序(手写代码)
- 链表上的快速排序。
- 长度为N的序列Sequence=abc……Z,问有多少不同的二叉树形态中序遍历是这个。(Code)
- 问了一两个算法题,记不清了,只记得其中一个是:找数组中2个出现两次的数字,还有3个两次的数字
- 问了一个1的平方加到100的平方结果
- 非常经典的0-1背包问题
今天的文章常见编程题分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/56466.html