[编程题]山寨金闪闪
链接：https://www.nowcoder.com/questionTerminal/9363dcb83ca44c61a2c1a8f65aa722b8来源：牛客网
金闪闪死后，红A拿到了王之财宝，里面有n个武器，长度各不相同。红A发现，拿其中三件武器首尾相接，组成一个三角形，进行召唤仪式，就可以召唤出一个山寨金闪闪。（例如，三件武器长度为10、15、20，可以召唤成功。若长度为10、11、30，首尾相接无法组成三角形，召唤失败。）红A于是开了一个金闪闪专卖店。他把王之财宝排成一排，每个客人会随机抽取到一个区间[l,r],客人可以选取区间里的三件武器进行召唤（客人都很聪慧，如果能找出来合适的武器，一定不会放过）。召唤结束后，客人要把武器原样放回去。m个客人光顾以后，红A害怕过多的金闪闪愉悦太多男人，于是找到了你，希望你帮他统计出有多少山寨金闪闪被召唤出来。链接：https://www.nowcoder.com/questionTerminal/9363dcb83ca44c61a2c1a8f65aa722b8
来源：牛客网第一行武器数量:n <= 110^7
第二行空格分隔的n个int，表示每件武器的长度。
第三行顾客数量：m <= 110^6
后面m行，每行两个int l，r，表示每个客人被分配到的区间。（l<r）
- 解析：找三角形：只需要使最小的两条边的和大于第三边就可以判断是有效三角形，但是一个trick是当区间【l,r】的范围大于45时，一定能找到三角形，为什么呢？假设刚好不能满足是有效三角形，那么有边1、1、2、3、5、8、13、、、，连续的三个数都正好最小两边和为第三边，不满足三角不等式，因此不能拼成三角形，但是选择这三个数的区间内，却一定是有效三角形，比如【3、5、8】，那么在区间 4 ~ 8 或 3 ~ 7 的数都满足三角不等式，可以是三角形。而上面的数字正好是斐波那契数列，【f1， f2, f3、。。f45】正好可以把 INT_MAX大小部分覆盖，相当于整个1至INT_MAX的整数段，被斐波那契数列 f1 、f2、….、 f45 分割成了45个区间，如下。那么现在我在这个区间上放46个数，使得它们里面找的三个数不能组成三角形，那么我就把它们放在划分区间的边界处，也就是f0（为1）、f1、f2、。。。f45的地方，现在我再放一个数，它必然使得这里存着三个数组成三角形，由斐波那契数知道，【f1,f3】【f2，f4】【f3, f5】是三个划分区间，而每两个挨着的区间都有一半以上是重叠的。那么，我这个数X必然要与左边或者右边重叠，比如放在区间【f2,…,X, …,f4】的正中间，它不能结合这个区间的两个边界成为有效的三角形，但是因为重叠，会使得【X,…,f3….,f4】成为一个有效的三角形组合。也可以视为【f2,…,f3….,f4】是无效三角形组合，但是必须放入一个到其中的时候，我们知道【f2,…….,f4-1】与【f2+1,…….,f4】内如果有三个数，那么必然是满足三角不等式。
1 | int fibonacci(int n) |
题解：
1 |
|
给定一个合法的表达式字符串，其中只包含非负整数、加法、减法以及乘法符号（不会有括号），例如7+345+2+4-3-1，请写程序计算该表达式的结果并输出；
同leetcode 227. Basic Calculator II
解析：1.先去掉空白符；2.处理数字与非数字；遇到非数字，即操作符号的时候总是把之前计算好的数存到栈中，若操作符号是乘除符号，那么取出栈顶左边数，与当前得到的右边数做对应运算，然后放入栈顶。可以看到，遇到操作符时，我们已经计算得到了符号的右边数，该符号是正负，那么先把右边数存起来便是，只有遇到乘除号需要计算之后入栈，反正栈中的元素全是计算完的部分结果，拿来出栈全部就和。
骚python：
1 | def main(): |
小A最多会新认识的多少人
小A参加了一个n人的活动，每个人都有一个唯一编号i(i>=0 & i<n)，其中m对相互认识，在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后，小A最多会认识多少人？
链接：https://www.nowcoder.com/questionTerminal/1fe6c3136d2a45fa8ef555b459b6dd26?f=discussion
来源：牛客网第一行聚会的人数：n（n>=3 & n<10000）； 第二行小a的编号: ai（ai>= 0 & ai < n)；
第三互相认识的数目: m（m>=1 & m
< n(n-1)/2）；
第4到m+3行为互相认识的对，以’,’分割的编号。
- 图的深度优先搜索，先建立邻接表，然后深度搜索，问题要求的是A认识的新人，因此要删除A已经认识的人，还有查找集合里A本身。
1 |
|
python：
利用并查集来做，它的概念：https://juejin.im/entry/5922593d44d904006cd20175；
它是用来把多个集合合并的数据结构，开始时，各个元素都属于各自的集合，根节点为它们自己；
当需要合并（union）任意两个节点时，先查找函数（find）它们的根节点，若是同一个根，说明它们已经在同一集合内；若不是，设置其中一个的根节点为另一个的根节点；设置的技巧可以先配一个rank，rank表示这个根节点的子节点数目，数目越多，该根节点更有理由作为另一个的根节点，这样整个森林才比较平衡，而平衡有利于快速的搜索。
因此，就有合并函数和查找函数：其中查找函数的为：
1 | def find(self, x): |
理解它只需要这个图就行：
现在要找到元素9所在树的根节点，在找根节点的过程中使用路径压缩，也就是说9到根的路径上的节点9，6，3，1的父节点都设置成为根节点0，所以呢，在FIND-SET(9)之后，树的形态就变成了下面的样子：
题目代码：
1 | class UnionSet: |
扭蛋机
链接：https://www.nowcoder.com/questionTerminal/9d26441a396242a9a0f7d2106fc130c7?f=discussion
来源：牛客网
22娘和33娘接到了小电视君的扭蛋任务：
一共有两台扭蛋机，编号分别为扭蛋机2号和扭蛋机3号，22娘使用扭蛋机2号，33娘使用扭蛋机3号。
扭蛋机都不需要投币，但有一项特殊能力：
扭蛋机2号：如果塞x（x范围为>=0正整数）个扭蛋进去，然后就可以扭到2x+1个
扭蛋机3号：如果塞x（x范围为>=0正整数）个扭蛋进去，然后就可以扭到2x+2个
22娘和33娘手中没有扭蛋，需要你帮她们设计一个方案，两人“轮流扭”（谁先开始不限，扭到的蛋可以交给对方使用），用“最少”的次数，使她们能够最后恰好扭到N个交给小电视君。输入一个正整数，表示小电视君需要的N个扭蛋。
输出一个字符串，每个字符表示扭蛋机，字符只能包含”2”和”3”。
解析：
链接：https://www.nowcoder.com/questionTerminal/9d26441a396242a9a0f7d2106fc130c7?f=discussion来源：牛客网
初始位置是x=0，然后每步有两种选择
1、第一种选择是走到编号为 2*x+1 的方格，代号为 ‘2’
2、第一种选择是走到编号为 2*x+2 的方格，代号为 ‘3’
求一种可以正好走到 编号为 n 的方式
1
2
3
4
5
6
7
8
9
10
11# 逆推法：根据最后一步的奇偶，判断前一步的选择
n = int(input())
res = ''
while n > 0:
if (n-2) % 2:
n = (n-1) // 2
res = '2' + res
else:
n = (n-2) // 2
res = '3' + res
print(res)
1 | # 简化版 |
脸滚键盘
>
>
链接：https://www.nowcoder.com/questionTerminal/2a3dc06f337d4a2ba41d25c688f95e2f
来源：牛客网av394281 中，充满威严的蕾米莉亚大小姐因为触犯某条禁忌，被隙间妖怪八云紫（紫m……èi）按住头在键盘上滚动。
同样在弹幕里乱刷梗被紫姐姐做成罪袋的你被指派找到大小姐脸滚键盘打出的一行字中的第k个仅出现一次的字。
(为简化问题，大小姐没有滚出 ascii 字符集以外的字)
解析：用map计算就行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std;
string res(string s, int N)
{
if(s.empty() || N == 0) return "Myon~";
unordered_map<char, int> table;
for (auto c : s)
table[c]++;
int count = 0;
string _res = "[*]";
for (int i = 0; i < s.size(); i++)
{
if (table[s[i]] == 1)
{
count++; _res[1] = s[i];
if (count == N) break;
}
}
return count == N ? _res : "Myon~";
}
int main()
{
int N;
string s;
while (getline(cin, s))
{
N = 0;
while(s[N] != ' ') N++;
string substr = s.substr(0, N);
s = s.substr(N + 1, s.length());
N = stoi(substr);
cout << res(s, N) << endl;
}
}
比较两个版本字符串version1和version2
输入的version字符串非空，只包含数字和字符.。.字符不代表通常意义上的小数点，只是用来区分数字序列。例如字符串2.5并不代表二点五，只是代表版本是第一级版本号是2，第二级版本号是5.
- 考虑两个version的版本号长度不一样，为此，在最短的version号上添置0，使得长度一致。
1 | def main(): |
精灵鼠从入口到出口的最少减少速度
猛兽侠中精灵鼠在利剑飞船的追逐下逃到一个n*n的建筑群中，精灵鼠从（0,0）的位置进入建筑群，建筑群的出口位置为（n-1,n-1），建筑群的每个位置都有阻碍，每个位置上都会相当于给了精灵鼠一个固定值减速，因为精灵鼠正在逃命所以不能回头只能向前或者向下逃跑，现在问精灵鼠最少在减速多少的情况下逃出迷宫？
解析：
1
2
3
4
5
6
7
8
9
10
11
12def main():
n = int(input())
table = [list(map(int, input().split(","))) for _ in range(n)]
for i in range(n):
for j in range(n):
# 初始化第一行和第一列，即一直往下或者右走
if i == 0 and j >= 1: table[i][j] += table[i][j - 1]
if j == 0 and i >= 1: table[i][j] += table[i - 1][j]
if i >= 1 and j >= 1: table[i][j] += min(table[i -1][j], table[i][j - 1])
print(table[n - 1][n - 1])
if __name__ == "__main__":
main()
顺时针打印数字矩阵
2
3
4
5
1 2 3
4 5 6
7 8 9
-1 -1
- 解：充分利用python语言的extend还有pop性质，想法是每次从矩阵里消去第一行，倒数列，倒数行，第一列的循环，并且会发生失败，还搭上try/except语句。
1 | while 1: |
判断输入的字符串是否属于内网IP
什么属于内网IP：
1 | if input().split('.')[0] in ['127','192','10','172']: print(1) |
给定一个整数数组,判断其中是否有3个数和为N
- 解析：固定其中一个数，然后使用初始化其他两个数的索引，对它们的索引更新使用二分查找。
1 | def main(): |
孙悟空的徒弟
> 链接：https://www.nowcoder.com/questionTerminal/7b841a840db64f5ebec77f6ee7e307e2?f=discussion
> 来源：牛客网
>
> 打败魔人布欧以后，孙悟空收了n个徒弟，每个徒弟战斗力各不相同。他教导所有的徒弟和体术，合体后战斗力为原战斗力相乘。任何两个徒弟都可以合体，所以一共有n*(n-1)/2种合体徒弟。有一天，他想考验一下孙悟天战斗力如何，希望在所有n*(n-1)/2种合体徒弟中选择战斗力第k高的，与孙悟天对战。可是孙悟空徒弟太多了，他已然懵逼，于是找到了你，请你帮他找到对的人。
>
> 1
输入：第一行两个int。徒弟数量：n <= 1*10^6；战斗力排名:k <= n*(n-1)/2第二行空格分隔n个int，表示每个徒弟的战斗力。
>
> 1
输出：战斗力排名k的合体徒弟战斗力。
>
> 示例：
>
> 1
2
3
4
5 2
1 3 4 5 9
output：
36
解析：
1 |
|
翻转链表
对于一个链表 L: L0→L1→…→Ln-1→Ln,
将其翻转成 L0→Ln→L1→Ln-1→L2→Ln-2→…输入是一串数字，请将其转换成单链表格式之后，再进行操作
2
3
>output:
>1,5,2,4,3
1 | a = input().split(',') |
参考一个答案：https://www.nowcoder.com/questionTerminal/f350f14cd22c41aabfa7e54a1b8e8825?f=discussion，不喜欢写链表。
1 |
|