复盘携程0415笔试题
第二题游游现在有一个公司,这个公司里有n个任务,每一个任务都有一个能力值和收益值,现在有m个工人,每一个工人都有一个能力值,对于每一个任务来说,只有这个人的能力值不低于该任务需要的能力值,才可以完成这个任务。假设多个工人可以完成同一个任务,收益为这个任务的收益值乘以这个任务完成的次数,现在想知道每一个工人最多只能安排一个任务的前提下,最大的收益值是多少?
输入描述每一个文件输入第一行输入一个整数T($1 \leq T \leq 100$),代表有T组测试数据。
接下来T组,每一组第一行输入两个整数n,m($1 \leq n,m \leq 10^4$)
第二行输入n个整数,其中a[i]代表第i个任务所需要的的能力值
第三行输入n个整数,其中$p_i$($1 \leq p[i] \leq 10^5$)代表第i个任务的收益
第四行输入m个整数,其中$b_i$($1 \leq b[i] \leq 10^5$)代表第i个工人的能力数据保证同一个文件内n的总和不超过$10^5$,m的总和不超过$10^5$
数据保证同一个文件内n的总和不超过$10^5$,m的总和不超过$10^5$
输出描述对于每一 ...
JZ22 链表中倒数最后k个结点
描述输入一个长度为 n 的链表,设链表中的元素的值为 a_i ,返回该链表中倒数第k个节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。
数据范围:
0 \leq n \leq 10^5,0 \leq a_i \leq 10^9,0 \leq k \leq 10^9要求:空间复杂度 O(n),时间复杂度 O(n)
进阶:空间复杂度O(1),时间复杂度 O(n)
例如输入{1,2,3,4,5},2时,对应的链表结构如下图所示:
其中蓝色部分为该链表的最后2个结点,所以返回倒数第2个结点(也即结点值为4的结点)即可,系统会打印后面所有的节点来比较。
示例1输入:{1,2,3,4,5},2返回值:{4,5}说明:返回倒数第2个节点4,系统会打印后面所有的节点来比较。
示例2输入:{2},8返回值:{}
题解1首先求出链表的长度n,从题目的倒数第k个结点,推出是正数的第n - k个结点。若n - k < 0,则返回空值
/** * struct ListNode { * int v ...
jz23 链表中环的入口结点
描述给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。
数据范围: n≤10000,1<=结点值<=10000
要求:空间复杂度 O(1),时间复杂度 O(n)
例如,输入{1,2},{3,4,5}时,对应的环形链表如下图所示:
可以看到环的入口结点的结点值为3,所以返回结点值为3的结点。
输入描述:输入分为2段,第一段是入环前的链表部分,第二段是链表环的部分,后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述:返回链表的环的入口结点即可,我们后台程序会打印这个结点对应的结点值;若没有,则返回对应编程语言的空结点即可。
示例1输入:
{1,2},{3,4,5}
返回值:
3
说明:
返回环形链表入口结点,我们后台程序会打印该环形链表入口结点对应的结点值,即3
示例2输入:
{1},{}
返回值:
"null"
说明:
没有环,返回对应编程语言的空结点,后台程序会打印"null"
示例3输入 ...
JZ52 两个链表的第一个公共结点
输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)
数据范围: n≤1000要求:空间复杂度 O(1),时间复杂度 )O(n)
例如,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示:
可以看到它们的第一个公共结点的结点值为6,所以返回结点值为6的结点。
输入描述:输入分为是3段,第一段是第一个链表的非公共部分,第二段是第二个链表的非公共部分,第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表,并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面,用户得到的输入只有pHead1和pHead2。
返回值描述:返回传入的pHead1和pHead2的第一个公共结点,后台会打印以该节点为头节点的链表。
示例1输入:
{1,2,3},{4,5},{6,7}
返回值:
{6,7}
说明:
第一个参数{1,2,3 ...
jz25 合并两个排序的链表
描述输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围: 0≤10000≤n≤1000,−1000≤节点值≤1000−1000≤节点值≤1000要求:空间复杂度 O(1),时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示:
或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所以对应的输出为{-1,1,2,3,4,4},转换过程如下图所示:
示例1输入:
{1,3,5},{2,4,6}
返回值:
{1,2,3,4,5,6}
示例2输入:
{},{}
返回值:
{}
示例3输入:
{-1,2,4},{1,3,4}
返回值:
{-1,1,2,3,4,4}
题解1可以使用虚拟头结点,可以再新建一个链表,然后把两个 ...
JZ24 反转链表
描述给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
数据范围: 0≤10000≤n≤1000
要求:空间复杂度 O(1) ,时间复杂度 O(n) 。
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
示例1输入:
{1,2,3}
返回值:
{3,2,1}
示例2输入:
{}
返回值:
{}
说明:
空链表则输出空
题解1使用栈当做中转站,把每个节点倒过来,然后重新拼成一个新链表
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */class Solution { public: /** ...
JZ6 从尾到头打印链表
描述输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)。
如输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]
0 <= 链表长度 <= 10000
示例1输入:
{1,2,3}
返回值:
[3,2,1]
算法思路1主要考察翻转数组的操作,把链表的数据放到数组里,然后在数组里操作,一个比较简单的操作是调用C++的库函数
class Solution {public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> vt; ListNode* p = head; while(p != nullptr){ vt.push_back(p->val); p = p->next; } reverse(vt.begin(),vt.end()); ...
斐波那契数列 C_C++
用三种方法实现:
带备忘录的递归
dp迭代
迭代优化,空间复杂度为O(1)
#include <cstdio>#include <iostream>#include <vector>using namespace std;#define _for(i,a,b) for(int i=(a);i<=(b);i++)//备忘录int helper(vector<int>& memo, int n) { //base case if (n == 2 || n == 3) { return 1; } if (memo[n] != 0) { return memo[n]; } else { memo[n] = helper(memo, n - 1) + helper(memo, n - 2); return memo[n]; }}//带备忘录法int fib_1(int N) { if (N <= 1) { retur ...
图的邻接表表示转换成邻接矩阵
算法思想:先初始化邻接矩阵。依次遍历各个顶点的边表,根据边表中记录的“改弧所指向的顶点的位置”修改邻接矩阵arc[i][j]的值。例如遍历第 i 行的时候(当前的顶点所在行数为 i ),依次遍历该顶点的边表结点,若当前顶点的弧顶点的位置为j,则arc[i][j] = 1
创建如下的图:
全部代码如下:
#include <iostream>using namespace std;#pragma region 创建邻接表存储的无向图#define MaxVertexNum 100 //图中顶点数目最大值#define VertexType char#define _for(i,a,b) for(int i=(a);i<(b);i++)typedef struct ArcNode { //边表结点 int adjvex; //该弧所指向的顶点的位置 ArcNode* next; //指向下一条弧的指针}ArcNode;typedef struct VNode { / ...
LeetCode 131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: “aab”Output:[ [“aa”,”b”], [“a”,”a”,”b”]]
题目链接
可以回溯法切割出来字串,然后判断是否为回文串
由于要找出来全部的字串,所有回溯的范围应该是全部遍历一遍。使用for循环进行横向的遍历,for循环结束的条件就是本层集合的个数(也就是树中孩子的数量),cur代表当前要切割的位置
for(int i=cur;i<s.length();i++)
然后进行纵向的遍历,每当切割出来一个回文串,就把其放入tmp中,然后进行回溯。否则跳过。
if(Ispalindrome(s,cur,i)){ string item=s.substr(cur,i-cur+1); tmp.pu ...
