常见编程题

作者：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背包问题