瓜子二手车2019秋招编程题汇总

对于一个字符串，请设计一个算法，只在字符串的单词间做逆序调整，也就是说，字符串由一些由空格分隔的部分组成，你需要将这些部分逆序。
给定一个原字符串A，请返回逆序后的字符串。例，输入"I am a boy!", 输出"boy! a am I" 输入描述： 输入一行字符串str。(1<=strlen(str)<=10000)输入样例： It's a dog! 输出描述： 返回逆序后的字符串。输出样例 dog! a It's

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？ 输入描述： 输入整数n.(1<=n<=100000)输入样例： 13 输出描述： 输出组合数，答案对1e9+7取模。输出样例 16

对K个不同字符的全排列组成的数组,  面试官从中随机拿走了一个, 剩下的数组作为输入,  请帮忙找出这个被拿走的字符串?
比如[“ABC”, “ACB”, “BAC”, “CAB”, “CBA”] 返回 “BCA” 输入描述： 第一行输入整数n，表示给定n个字符串。(n == x!-1,2<=x<=10)
以下n行每行输入一个字符串。输入样例： 5 ABC ACB BAC CAB CBA 输出描述： 输出全排列缺少的字符串。输出样例 BCA

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
Tree 1  
     1   
    / \   
   3   2
  /      
 5   
    
Tree 2
   2
  / \
 1   3
  \   \
   4   7

合并后的树为
    3
   / \
  4   5
 / \    \
5  4    7 输入描述： 第一行输入整数n，m。(分别表示树1和树2的节点数,1<=n，m<=100)
接下来n行，第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第一棵树的第i个结点的左儿子编号，右儿子编号和权值。
接下来m行，第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第二棵树的第i个结点的左儿子编号，右儿子编号和权值。
（对于左右儿子，如果编号为0表示空。保证如果儿子不为空，则儿子编号大于父亲编号。）输入样例： 4 5 2 3 1 4 0 3 0 0 2 0 0 5 2 3 2 0 4 1 0 5 3 0 0 4 0 0 7 输出描述： 输出合并后树按层遍历的各结点权值，相邻权值之间以一个空格相间。输出样例 3 4 5 5 4 7

给定n个柱面的高度，表示降雨某地n块区域的海拔高度。
计算降雨之后该地最大储水面积。如果低于地平线，也就是小于0，则一定积水

输入描述： 第一行输入整数n.(1<=n<=10000)
第二行输入n个高度整数h。(-10000<=h<=10000)输入样例： 12 0 1 0 2 1 0 1 3 2 1 2 1 输出描述： 输出答案。输出样例 6

判断一个无序数组中是否存在长度为3的递增子序列。（不要求连续）（满足O(n)的时间复杂度和O(1)的空间复杂度。） 输入描述： 第一行一个正整数 1 <= n <= 100000

第二行n个整数a1,a2,...,an，(1<=ai<=1e9)输入样例： 5 12 8 36 9 20 输出描述： 如果存在，输出"true",否则输出"false"。（不含引号）。输出样例 true

用非递归方式编码对一个二叉树的前、中、后、层次遍历。 输入描述： 第一行一个正整数n(1<=n<=100)，表示二叉树有n个结点。

接下来n行，第i行两个整数li,ri (0<=li,ri<=n) ，分别表示第i个结点的左儿子和右儿子，为0代表空。

保证根为1，保证输入为合法二叉树。输入样例： 5 3 2 0 5 0 4 0 0 0 0 输出描述： 输出四行。

第一行为二叉树的前序遍历；

第二行为中序遍历；

第三行为后序遍历；

第四行为层次遍历。

每一行输出n个数，代表该方式遍历的结点的顺序，相邻两个数之间用一个空格相隔。输出样例 1 3 4 2 5 3 4 1 2 5 4 3 5 2 1 1 3 2 4 5

输入描述： 第一行一个正整数n(1<=n<=100)，表示二叉树有n个结点。
接下来n行，第i行两个整数li,ri (0<=li,ri<=n) ，分别表示第i个结点的左儿子和右儿子，为0代表空。
保证根为1，保证输入为合法二叉树。输入样例： 5 3 2 0 5 0 4 0 0 0 0 输出描述： 输出一行。输出n个数，代表后序遍历的结点的顺序，相邻两个数之间用一个空格相隔。输出样例 4 3 5 2 1

给定两个字符串。
定义三种操作：
1.插入一个字符
2.修改一个字符
3.删除一个字符
求最少几步操作使得第一个字符串变成第二个字符串。
例如：第一个字符串lighten,第二个字符串fighting
fighten (l->f) 修改
fightin (e->i) 修改
fighting (->g) 插入
一共三步 输入描述： 第一行为一个字符串s(1<=|s|<=1000)。

第二行为一个字符串t(1<=|t|<=1000)。

(保证字符串里只含小写字母。)输入样例： lighten fighting 输出描述： 输出s到t的最短编辑距离。输出样例 3

输入描述： 第一行两个正整数n，v(1<=n<=100000，1<=v<=100000)，分别表示数组长度与查找值。

第二行n个正整数a1,a2,...,an(1<=a1<=a2<=...<=an<=n)表示有序数组。输入样例： 5 4 1 2 4 4 5 输出描述： 输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。输出样例 3

给一个单向链表，若其中包含环，请完善EntryNodeOfLoop方法找出该链表的环的入口结点，否则，输出null。要求空间复杂度为O(1)
public class ListNode {  //链表的数据结构
   int val
   ListNode next = null
}
public ListNode EntryNodeOfLoop(ListNode pHead) {

}

输入描述： 第一行输入整数n(1<=n<=100)表示链表的结点数。

第二行n个整数，第i个整数表示结点i指向的下一个结点，0表示null。

保证从链表1开始，保证最多只有一个入口结点。输入样例： 4 2 3 4 2 输出描述： 如果存在循环输出入口编号。
如果不存在输出NULL。输出样例 2

输入描述： 第一行两个正整数n,v(1<=n<=100000, 1<=v<=100000)，分别表示二叉树的结点数以及给定值。

接下来n行，每行三个整数li,ri,vi，表示二叉搜索树上第i个结点的左儿子编号（0为空），右儿子编号（0为空）以及权值。

保证二叉树合法(对于所有结点有：左子树权值<=根权值<=右子树权值)。输入样例： 5 2 0 0 4 3 1 2 5 4 1 0 0 2 0 0 1 输出描述： 输出n行，第i行输出两个整数li,ri，表示分开后第i个结点的左儿子编号和右儿子编号，如果为空请输出0，两个整数间以一个空格相间。输出样例 0 0 3 0 0 4 5 0 0 0

基于数组实现一个使用一个FIFO的队列，支持push和pop操作。并说明各项操作的复杂度。 输入描述： 第一行一个正整数n, (1<=n<=100000)，表示操作的个数

接下来n行，每行有一个操作，

如果操作为push，则后面接一个正整数v(1<=v<=100000)表示push进队列的数；

如果操作为pop，则应输出pop出的数为多少。输入样例： 10 push 60 pop push 9 pop push 27 pop push 22 push 37 pop push 100 输出描述： 对于每个pop操作，输出pop出的数为多少。输出样例 60 9 27 22

链表反转： 1->2->3->4->5 通过反转后成为5->4->3->2->1。说明算法的复杂度。 输入描述： 第一行一个正整数n(1<=n<=100000)

第二行n个正整数a1,a2,...,an(1 <= ai <=100000)，表示链表顺序的结点值。输入样例： 10 9 10 6 6 8 7 5 7 7 5 输出描述： 输出一行，n个数，表示反转后链表依次的结点值。输出样例 5 7 7 5 7 8 6 6 10 9

八皇后问题，是一个古老而著名的问题。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。利用回溯算法我们能很快的得到共有92种互不相同的解（独立解有12种）。当棋盘变成n行，n列，且皇后也有n个的时候（n<=20），问有多少种不同的解？ 输入描述： 一行，一个正整数n(1<=n<=20)输入样例： 8 输出描述： 输出一个整数，代表解的个数。输出样例 92