Welcome To Learn Algorithms
post @ 2020-11-26

牛客编程巅峰赛S2第3场
题目链接

题目

牛牛在各个平台被各种传奇游戏的广告轰炸,所以他决定去玩一玩这类的游戏。这类游戏挂机就可以升级,所以牛牛每天都能变强。在第i天里,牛牛能杀死防御力小于等于i的怪物。但由于牛牛还要刷题,所以牛牛每天最多杀一只怪物。这个游戏共有n只怪物,每只怪物的防御力为DEF[i],牛牛想知道最少要到第几天才能把这n只怪物都杀死。

输入1

1
2,[7,3]

输出1

1
7

说明

牛牛可以在第3天杀死一只防御力为3的怪物,在第7天杀死一只防御力为7的怪物。所以牛牛最少能在第7天把这些怪物全杀死。

输入2

1
3,[4,5,5]

输出2

1
6

说明2

牛牛可以在第4天杀死一只防御力为4的怪物,在第5天杀死一只防御力为5的怪物,在第六天将另一只防御力为5的怪杀死。所以牛牛最少能在第6天把这些怪物全杀死。

备注

对于100%的数据:1≤n≤1e3, 1≤DEF[i]≤1e6

Read More
post @ 2020-11-20

牛客编程巅峰赛S2第2场
题目链接

题目

系统中有一棵n个点的完全k叉树,现给出它的BFS层序遍历序列ai(即从根节点开始,每一层从左向右遍历),请你还原这棵树,并返回加密后的答案。
答案加密方法:所有边两个端点异或的和,即
upload successful,其中
upload successful为一条树上的边。

下面给出完全二叉树的定义:若设二叉树的深度为k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第k层所有的结点都连续集中在最左边
请你根据这个定义进行适度推广,得到完全k叉树的含义。

输入

1
2,[1,2,3,4,5]

输出

1
18

说明

树边为(1, 2), (1, 3), (2, 4), (2, 5),加密过程为(1^2)+(1^3)+(2^4)+(2^5),答案为18。

样例1构成的完全二叉树为:

输入2

1
3,[1,2,3,4,5]

输出2

1
17

说明2

树边为(1, 2), (1, 3), (1, 4), (2, 5),加密过程为(1^2)+(1^3)+(1^4)+(2^5),答案为17。

样例2构成的完全三叉树为:

备注

upload successful

题解

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
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param k int整型 表示完全k叉树的叉数k
* @param a int整型一维数组 表示这棵完全k叉树的Bfs遍历序列的结点编号
* @return long长整型
*/
function tree2( k , a ) {
// write code here
let arr = a.shift( 1 );
let maxLen = k;
while( a.length ){
if( a.length>maxLen ){
arr.push( a.splice( 0, maxLen ) );
k = k * k;
} else {
arr.push( a.splice() );
}
}
let sum = 0;
arr.map((e,i)=>{
if( i==0 )
return true;
e.map((item,itemIndex)=>{
let p =
})
})
}
module.exports = {
tree2 : tree2
};
Read More
post @ 2020-11-20

牛客编程巅峰赛S2第2场
题目链接

题目描述

牛牛有一根长度为a(3 \leq a \leq 1e18)(3≤a≤1e18)的木棒,现在牛牛想将木棒分成一些段(每段木棒长度必须为整数),使得分隔后的木棍中,任意三段都不能构成三角形,牛牛想知道木棒最多被分成几段呢?

输入

1
5

输出

1
3

说明

1
可以分成1 1 3三段

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
*
* @param a long长整型 木棒的长度
* @return int整型
*/
function stick( a ) {
// write code here
if( a<5 )
return 0;
let s = [1,1]
while( true ){
let next = s[s.length-1] + s[s.length-2];
if( a>next ){
s.push( next )
a -= next;
} else {
break;
}
}
return s.length;
}
module.exports = {
stick : stick
};
Read More
post @ 2020-11-20

牛客编程巅峰赛S2第2场
题目链接

题目描述

牛牛是个非常热心的人,所以他有很多的朋友。这一天牛牛跟他的n个朋友一起出去玩,在出门前牛牛的妈妈给了牛牛k块糖果,牛牛决定把这些糖果的一部分分享给他的朋友们。由于牛牛非常热心,所以他希望他的每一个朋友分到的糖果数量都比牛牛要多(严格意义的多,不能相等)。牛牛想知道他最多能吃到多少糖果?

输入

1
2,10

输出

1
2

说明

牛牛可以分给他的两个朋友各4个糖果,这样他能吃到2个糖果,这样能保证他的每个朋友的糖果数都比他多,不存在牛牛能吃到3个或者以上糖果的情况

输入

1
3,11

输出

1
2

说明

牛牛可以分给他的3个朋友各3个糖果,这样他能吃到2个糖果,这样能保证他的每个朋友的糖果数都比他多,不存在牛牛能吃到3个或者以上糖果的情况

备注

对于百分之30的数据:1\leq n\leq 100,n\leq k\leq 1001≤n≤100,n≤k≤100

对于百分之100的数据:1\leq n\leq 1e18,n\leq k\leq 1e181≤n≤1e18,n≤k≤1e18
函数有两个long long型参数

第一个参数代表题目中的n

第二个参数代表题目中的k

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 返回牛牛能吃到的最多糖果数
* @param n long长整型
* @param k long长整型
* @return long长整型
*/
long long Maximumcandies(long long n, long long k) {
// write code here
return (k-n) / (n+1);
}
};

备注

这题使用JS实现的话,会因为JS的intNumber.MAX_SAFE_INTEGER9007199254740991Math.pow(2,53)-1)。
需要使用BigInt,或大数处理类。
但是在实际评测中,使用BigInt只能AC 90%。 具体原因不详。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 返回牛牛能吃到的最多糖果数
* @param n long长整型
* @param k long长整型
* @return long长整型
*/
function Maximumcandies( n , k ) {
return parseInt((BigInt(k)-BigInt(n)) / (BigInt(n)+1n));
}
module.exports = {
Maximumcandies : Maximumcandies
};

Read More
post @ 2020-11-20

2020-11-20 明略科技集团 2021 校招笔试-前端类 B卷 编程题第二题

牛客网原题:CD136

题目描述

对于字符串str,其中绝对不含有字符.*。再给定字符串exp,其中可以含有.`**字符不能是exp的首字符,并且任意两个*字符不相邻。exp中的.代表任何一个字符,exp中的*表示*的前一个字符可以有0个或者多个。请写一个函数,判断str是否能被exp匹配(注意:输入的数据不保证合法,但只含小写字母和.*)。

输入

1
"abc", "abc"

输出

1
true

备注

1
1≤|str|, |exp|≤300

实现

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
function canMatch( str, exp ){
// 异常筛选
if( str.indexOf("*") != -1 || str.indexOf("*") != -1 || exp.indexOf("*") == 0 || exp.indexOf("**") != -1 )
return false;
while( str.length && exp.length ){
let currExp = exp[0]; // 当前匹配的字符(首个)
let nextIsX = false; // 记录下一个是否为*
if( exp.length>1 && exp[1] == "*" )
nextIsX = true;
// 将.重新定义为字符串首个字符
if( currExp == '.' )
currExp = str[0];
if( nextIsX ){
// 如果接下来带星号,首先删除字符串前面相同的值,然后删除exp前面相同的值/*
while( str[0] == currExp ){
str=str.substr( 1 );
}
while( exp[0] == currExp || exp[0] == "*" ){
exp=exp.substr( 1 );
}
} else if( currExp == str[0] ){
// 如果只是单字符,且不带exp。直接删除首个字符
str=str.substr( 1 );
exp=exp.substr( 1 );
} else {
// 如果第一个字符不相同,且第二个字符不是*
return false;
}
}
return str.length && exp.length ? false : true;
}

console.log( canMatch( "aaaabc", "a*abc" ) )
Read More
post @ 2020-11-20

2020-11-20 明略科技集团 2021 校招笔试-前端类 B卷 编程题第一题

题目描述

输入年、月、日,计算该天是本年的第几天。

输入描述

包括三个整数年(1≤Y≤3000)、月(1≤M≤12)、日(1≤D≤31

输出描述

输入可能有多组测试数据,对于每一组测试数据,
输出一个整数,代表Input中的年、月、日对应本年的第几天。

输入

1
2
1990 9 20
2000 5 1

输出

1
2
263
122

代码实现

1
2
3
4
5
6
7
while(line=readline()){
let [years, month, day] = line.split(" ");
let dateTo = new Date(`${years}-${month}-${day}`);
let dateForm = new Date(`${years}-1-1`);
let dateDiff = (dateTo-dateForm) / 1000 / 60 / 60 / 24 + 1;
print( dateDiff )
}
Read More
post @ 2020-11-18

题目

32进制数相加

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// fromCharCode() 可接受一个指定的 Unicode 值,然后返回一个字符串
// charCodeAt() 方法可返回指定位置的字符的 Unicode 编码。这个返回值是 0 - 65535 之间的整数。

function hexPlus36( string1, string2 ){
let currentIndex = 0;
let start = "0";
let end = "Z";
let isAdd = false; // 进位标志符
let startCharCode = start.charCodeAt();
let endCharCode = end.charCodeAt();
let sum = []; //总和
let Lenstring1 = string1.length;
let Lenstring2 = string2.length;
while( Lenstring1>currentIndex || Lenstring2>currentIndex ){
// 对两位进行预处理,屏蔽[9-a]中间的字符
let addA = startCharCode;
if( Lenstring1>currentIndex ){
let currentCharCode = string1.charCodeAt(Lenstring1-currentIndex-1);
if( currentCharCode >= startCharCode+9 ){
addA = currentCharCode - "a".charCodeAt() + startCharCode + 10;
} else {
addA = currentCharCode;
}
}
let addB = startCharCode;
if( Lenstring2>currentIndex ){
let currentCharCode = string2.charCodeAt(Lenstring2-currentIndex-1);
if( currentCharCode >= startCharCode+9 ){
addB = currentCharCode - "a".charCodeAt() + startCharCode + 10;
} else {
addB = currentCharCode;
}
}

// 进行加法
let sumCharCode = (isAdd&&1) + addA + addB - startCharCode;
if( sumCharCode >= startCharCode + 36 ){
sumCharCode -= 36;
isAdd = true;
}
// 回退屏蔽
if( parseInt(sumCharCode) > startCharCode+9 ){
sumCharCode += "a".charCodeAt() - startCharCode - 10;
}
sum.unshift( String.fromCharCode(sumCharCode) );
currentIndex++;
}
if( isAdd )
sum.unshift( String.fromCharCode(startCharCode+1) );
return sum.join("");
}

let result = hexPlus36("1","1");
console.log( result );
Read More
post @ 2020-11-17

题目描述

拟将任意给定的正整数n转换成对应的二进制数的过程:对于输入的任意正整数n,输出若干行“shang: yu:”的形式,表示其转换过程。

输入描述

输入正整数n。

输出描述

输出其转为二进制的过程(具体见样例)。

示例输入

1
13

示例输出

1
2
3
4
shang:6 yu:1
shang:3 yu:0
shang:1 yu:1
shang:0 yu:1

HINT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>

int main(){
int n;
scanf( "%d", &n );
while( n!=1 ){
int mod = n % 2;
if( mod == 1 ){
n = n-1;
}
n /= 2;
printf( "shang:%d yu:%d\n", n, mod );
}
printf( "shang:0 yu:1\n" );
return 0;
}

题目链接

Read More
post @ 2020-11-17

计算逻辑表达式

计算逻辑表达式的值(优先级顺序:()>!>&&>||

输入描述

请输入逻辑表达式,表达式由以下字符组成:TF&&||!()

T:表示布尔的true
F:表示布尔的false

输出描述

返回逻辑表达式的结果,油校的结果包括TFE
T:表示逻辑表达式的结果为true
F:表示逻辑表达式的结果为false
E:表示逻辑表达式不正确,不能计算出结果

样例输入

1
2
3
T || F && F || F  
! F || T && T
T && F

样例输出

1
2
3
T
T
F

HINT

![upload successful](/images/pasted-0.png

代码

未测试

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;

string dealNull( string &str ){
int finder;
while( true ){
// 处理空格
finder = str.find(" ");
if( finder == -1 ){
break;
}
str.erase( finder, 1 );
}
return str;
}

string deal( string &str ){
int isError = 0;
int finder;

// 处理括号
int lk = str.find("(");
int rk =str.rfind(")");
if( (lk!=-1) xor (rk!=-1) ){
return "E";
} else if( (lk!=-1) ) {
str = str.replace( lk, rk-lk+1, deal(((string)"").assign(str,lk+1,rk-lk-1)) );
}

while( true ){
finder = str.find("!");
if( finder == -1 ){
break;
} else {
// 处理!
switch( str[finder+1] ){
case 'T':
str[finder+1] = 'F';
break;
case 'F':
str[finder+1] = 'T';
break;
case '!':
str.erase( finder+1, 1 );
break;
default:
isError = 1;
}
str.erase( finder, 1 );
if( isError ) return "E";
}
}

while( true ){
finder = str.find("&&");
if( finder == -1 ){
break;
} else if( finder<0 || finder==(int)str.length()-1 ) {
isError = 1;
break;
} else {
if( str[finder-1] == 'T' && str[finder+2] == 'T' ){
str[finder-1] = 'T';
} else if(
(str[finder-1]=='F'||str[finder-1]=='T') &&
(str[finder+2]=='T'||str[finder+2]=='F')
){
str[finder-1] = 'F';
} else {
isError = 1;
}
}
str.erase( finder, 3 );
if( isError ) return "E";
}

while( true ){
finder = str.find("||");
if( finder == -1 ){
break;
} else if( finder<0 || finder==(int)str.length()-1 ) {
isError = 1;
break;
} else {
if( (str[finder-1]=='T'||str[finder-1]=='F') && (str[finder+2]!='T'||str[finder+2]!='F') ){
if(
(str[finder-1]=='T'&&str[finder+2]=='F') ||
(str[finder-1]=='F' && str[finder+2]=='T') ||
(str[finder-1]=='T' && str[finder+2]=='T')
){
str[finder-1] = 'T';
} else {
str[finder-1] = 'F';
}
} else {
isError = 1;
}
}
str.erase( finder, 3 );
if( isError ) return "E";
}
if( isError ){
return "E";
}
return str;
}

string dealString( string &str ){
str = dealNull( str );
str = deal( str );
return str=="E"||str=="F"||str=="T"?str:"E";
}

int main(){
string str;
getline( cin, str );
string sb = dealString(str);
cout<<sb<<endl;
}
Read More

题目

1
数字转字符串千分位

输入

1
1000000.01

输出

1
1,000,000.01

回答

回答1

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
function a( _num ){
_str = _num.toString();
let _arr = _str.split(".");
let _newStr = "";
var t = 0;
for( let i=_arr[0].length-1;i>=0;i-- ){
if( t==2 ){
_newStr = `,${_arr[0][i]}${_newStr}`;
t = 0;
} else {
_newStr = `${_arr[0][i]}${_newStr}`;
t++;
}
}

// 处理前置的“ , ”
_newStr = _newStr.replace( /^,?(.*?),?$/g, "$1" );

// 拼接整数部分
if( _arr[1] ){
return `${_newStr}.${_arr[1]}`;
} else {
return `${_newStr}`;
}
}
console.log( a( 1000000.01 ) )

回答2

1
2
3
4
function b( _num ){
return _num.toString().replace( /\d{1,3}(?=(\d{3})+)(?=.\d*)/g, "$&," )
}
console.log( b( 1000000.01 ) )

回答3

1
2
3
4
function c( _num ){
return _num.toLocaleString()
}
console.log( c( 1000000.01 ) )
Read More
⬆︎TOP