1. 删除字符串s1 中在字符串s2 中出现的字符。
基本思路：把s1的字符存到一个set里面，然后遍历s2,看是否出现过，出现过就erase掉。但是直接输出set的元素这样会改变顺序，要想顺序不变，就顺序遍历一下s1 看是否出现，出现就输出。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
const int maxn=1005;
set<char>s;
int main()
{
string s1,s2;
cin>>s1>>s2;
int len=s1.length();
for (int i=0;i<len;i++)
s.insert(s1[i]);
len=s2.length();
for (int i=0;i<len;i++)
{
if (s.count(s2[i]))
s.erase(s.find(s2[i]));
}
len=s1.length();
for (int i=0;i<len;i++)
{
if (s.count(s1[i]))
cout<<s1[i];
}
cout<<endl;
return 0;
}
2.求一个论坛的在线人数，假设有一个论坛，其注册ID有两亿个，每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在线分布，取样粒度为秒。
一天总共有3600*24=86400秒。
定义一个长度为86400的整数数组intdelta[86400]，每个整数对应这一秒的人数变化值，可能为正也可能为负。开始时将数组元素都初始化为0。
然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1，将与退出时间对应的整数值减1。
这样处理一遍后数组中存储了每秒中的人数变化情况。
定义另外一个长度为86400的整数数组intonline_num[86400]，每个整数对应这一秒的论坛在线人数。
假设一天开始时论坛在线人数为0，则第1秒的人数online_num[0]=delta[0]。第n+1秒的人数online_num[n]=online_num[n-1]+delta[n]。
3.有序链表合并.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
} else if (l2 == NULL) {
return l1;
} else {
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
}
};
4.有n种硬币，面额分别为1~n，每种硬币都有无限个，假设要付款的金额为m。
m/n+!!(m%n)
5.一个数列：-1 2 -3 4 -5 6 ...询问q次，每次询问区间[l,r]的区间和,输出每个询问的答案。
第1个和第2个加起来为1，第3，4个加起来也为1......
所以前i项和为：
i/2+(i&1)*i;
区间和可以用前i项和算出来了
6.牛妹有剪刀，石头，布（以0，1，2表示）三种卡片无限张。现在牛妹拿出n张排成一排。然后你也拿出n张牌一一对应比对。若赢一局则获得一分。若你想得k分。现在输入n，k和牛妹的n张牌分别是什么，你想要恰好得k分，有多少种方法。
很容易想到答案跟牛妹每一张牌是什么没有关系。没一张牌只需要考虑赢、不赢。
赢k分，那就是从n张牌中拿出k张赢，
其他输，所以组合数c(n,k).对于赢了答k张，只有一种方法，但是对于剩下的n-k张，都有平局和输掉两种情况，所以是2的n-k次方。
两者相乘就是答案。
结果很大对mod=1e9+7取余，用到同余定理。
求2的幂直接暴力求（当然也可以快速幂）
求组合数的时候用到除法，
又要取余，所以用到逆元。所以用到逆元公式（当然还有其他求法）:pow(x,mod-2)%mod;
但是mod=1e9+7，所以暴力求幂会超时，
方法是用快速求幂法压缩时间（快速幂就不贴代码了）
typedef long long ll;
ll fast(ll a,ll n) // 快速幂 pow(a,n)
ll inv(ll x, ll mod)
{
return fast(x,mod-2);
7. const的含义及实现机制,比如: const int 1,是怎么做到i只可读的?
const用来说明所定义的变量是只读的。
这些在编译期间完成,編译器可能使用常数直接替换掉对此变量的引用。
8.有一个射击游戏有m种颜色的气球，颜色分别为1~m现在一个人开了n枪，告诉你一个数列，表示打爆的气球颜色分别是多少。（注意，0表示这一枪没有打中，mmp这里害得我debug了好久）求一个最小区间[l,r]，在区间内包含了所有1~m颜色。输出区间长度。
这个题是XUPT 2019寒假训练最后一场比赛的原题的强化版。刚好我做了并且在bilibli上给学弟学妹们讲了，很奈斯。
用一个变量维护当前区间里有多少种颜色，用book数组表示第i种颜色在当前区间内出现了多少次。
然后尺取。
9.到商店里买200的商品返还100优惠券(可以在本商店代替现金)。请问实际上折扣是多少？
由于优惠券可以代替现金,所以可以使用200元优惠券买东西,然后还可以获得100元的优惠券。
假设开始时花了x元,那么可以买到x+x/2+x/4+.的东西。所以实际上折扣是50%(当然,大部分
时候很难一直兑换下去,所以50%是折扣的上限)
如果使用优惠券买东西不能获得新的优惠券,那么总过花去了200元,可以买到200+100元的商品,所以实际折扣为200/300=67%。
10. TCP三次握手的过程, accept发生在三次握手哪个阶段？
accept发生在三次握手之后。
第一次握手:客户端发送syn包(syn=j)到服务器。
第二次握手:服务器收到syn包,必须确认客户的sY(ack=j+1),同时自己也发送一个ASK包(ask=k)。
第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=k+1)。
握手完成后,客户端和服务器就建立了tcp连接。这时可以调用 accept函数获得此连接。
11.用UDP协议道讯时怎样得知目标机是否获得了数据包?
可以在每个数据包中插入一个唯一的ID,比如 timestamp或者递增的int。
发送方在发送数据时将此ID和发送时间记录在本地。
接收方在收到数据后将ID再发给发送方作为回应。
12.求一个论坛的在线人数,假设有一个论坛,其注册ID有两亿个,每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间,要求写一个算法统计一天中论坛的用户在线分布,取样粒度为秒。
一天总共有3600*24=8600秒。
定义一个长度为86400的整数数组 int delta[86400],每个整数对应这一秒的人数变化值,可能为正也可能为负。开始时将数组元素都初始化为0。
然后依次读入每个用户的登录时间和退出时间,将与登录时间对应的整数值加1,将与退出时间对应的整数值减1。
这样处理一遄后数组中存储了每秒中的人数变化情况。
定义另外一个长度为86400的整数数组 int online num[86400,每个整数对应这一秒的论坛在线人数。
假设一天开始时论坛在线人数为0,则第1秒的人数 online num[0]= delta[0]。第n+1秒的人数
line num[n]= online num[n-1]+delta[n]。
这样我们就获得了一天中任意时间的在线人数。
13.从10G个数中找到中数在一个文件中有10G个整数,乱序排列,要求找出中位数。内存限制为2G.
不妨假设10G个整数是64bit的。
2G内存可以存放256M个64bit整数。
我们可以将64bit的整数空间平均分成256M个取值范围,用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后,我们便知道中数在那个范围内出现,以及这个范围内总共出现了多少个整数。
如果中数所在范围出现的整数比较少,我们就可以对这个范围内的整数进行排序,找到中数。如果这个范围还可以采用同样的方法将此范围再次分成多个更小的范围(256M-228,所以最多需要3次就可以将此范围缩小到1,也就找到了中数)
14.两个整数集合A和B,求其交集。
1.读取整数集合A中的整数,将读到的整数插入到mp中,并将对应的值设为1。
2.读取整数集合B中的整数,如果该整数在map中并且值为1,则将此数加入到交集当中,并将在map中的对应值改为2。
15.找出1到10w中没有出现的两个数字有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数?
申请10w个bit的空间,每个bit代表一个数字是否出现过。
开始时将这10个bit都初始化为0,表示所有数字都没有出现过。
然后依次读入已经打乱循序的数字,并将对应的bit设为1。
处理完所有数字后,根据为0的bi得出没有出现的数字。
首先计算1到10w的和,平方和。
然后计算给定数字的和,平方和。
两次的到的数字相减,可以得到这两个数字的和,平方和。
所以我们有
x + y = n
x^2 + y^2 = m
解方程可以得到x和y的值。
16.有1000瓶水,其中有一瓶有毒,小白鼠只要尝一点带奇的水24小时后就会死亡,至少要多少只小白鼠才能在24小时时鉴别出那瓶水有毒?
最容易想到的就是用1000只小白鼠,每只喝一瓶。但显然这不是最好答案。
既然每只小白鼠喝一瓶不是最好答案,那就应该每只小白鼠喝多瓶。那每只应该喝多少瓶呢?
首先让我们换种问法,如果有x只小白鼠,那么24小时内可以从多少瓶水中找出那瓶有毒的?
由于每只小白鼠都只有死或者活这两种结果,所以x只小白鼠最大可以表示2^x种结果。如果让每种结果都对应到某瓶水有毒,那么也就可以从2^x瓶水中找到有毒的那瓶水。那如何来实现这种对应关系呢?
第一只小白鼠喝第1到2^(x-1)瓶,第二只小白鼠喝第1到第2^(x-2)和第2^(x-1)+1到第2^(x-1)+2(x-2)瓶...以此类推。
回到此题,总过1000瓶水,所以需要最少10只小白鼠。
17.根据上排的数填写下排的数,并满足要求.
根据上排给出十个数,在其下排填出对应的十个数,要求下排每个数都是上排对应位置的数在下排出现的次数。上排的数:0,1,2,3,4,5,6,7,8,9。
18.给40亿个不重复的unsigned int的整数,没排过序的,然后再给几个数,如何快速判断这几个数是否在那10亿个数当中?
unsigned int的取值范围是0到2^32-1。我们可以申请连续的232/8-512M的内存,用每一个bit对应个 unsigned int数字。首先将51M内存都初始化为0,然后每处理一个数字就将其对应的bit设置为1。当需要查询时,直接找到对应bit,看其值是0还是1即可。
19. 1-20的两个数把和告诉A积告诉B,A说不知道是多少,B也说不知道,这时A说我知道了,B接着说我也知道了,问这两个数是多少?
2和3
20.爸爸妈妈妹妹小强,至少两个人同一生肖的概率是多少?
1-12*11*10*9/12*12212*12=1-5596=4196
21.计算ab<<2.
运算符优先级:括号,下标,->和(.成员)最高;
单目的比双目的高;
算术双目的比其他双目的高;
位运算高于关系运算;
关系运算高于按位运算(与,或,异或);
按位运算高于逻辑运算;
目的只有一个条件运算,低于逻辑运算;
赋值运算仅比,(顺序运算)高;
在此题中,位左移<<”优先级高于按位异或""所以b先左移两位(相当于乘以4)再与a异或。
例如:当a=6,b=4时;则a^b<<2=22
22.如何输出源文件的标题和目前执行行的行数?
printf("The file name:%dn", __FILE__);
printf("The current line No: %d\n", __LINE__);
ANSI C标准预定义宏;
__LINE__
__FILE__
__DATE__
__TIME__
__STDC__ 当要求程序严格遵循ANSC标准时该标识符被赋值为1
__cplusplus__ 当编写C+程序时该标识符被定义
23. a[3]4哪个不能表示a[1]1: *(&a[0][0]+5) *((a+1)+1) *(&a[1]+1) *(&a[0][0]+4)*(&a[1]+1).
24.希尔,冒泡,快速,插入哪个平均速度最快?
快速排序
快速排序、归并排序和基数排序在不同情况下都是最快最有用的
25. enum的声明方式
enum枚举类型名{
枚举常量1,
枚举常里2,
...
枚举常里n
};
For example:
enum weekday i sunday, monday, tuesday, wednesday,thursday, friday, saturday};
enum weekday week_day; //week_day就是一个枚举类型变量
京公网安备 11010502036488号