算法专栏基本能力测试

本测试满分100分。

在本测试中，你可以使用任意的编程语言或计算器。

 

一、进制的转换（13分）

1. 请写出十进制数2021的8进制表示（5分）

 

2. 请计算：4 & (5 ^ (6 | 7))，结果用二进制表示（为降低难度已添加部分括号，8分）

 

二、正则表达式（20分）

3. 阅读下列材料：

Usernames are used everywhere on the internet. They are what give users a unique identity on their favorite sites.

You need to check all the usernames in a database. Here are some simple rules that users have to follow when creating their username.

1. Usernames can only use alpha-numeric characters.

2. The only numbers in the username have to be at the end. There can be zero or more of them at the end. Username cannot start with the number.

3. Username letters can be lowercase and uppercase.

4. Usernames have to be at least two characters long. A two-character username can only use alphabet letters as characters.

(1) 请写出符合题意的正则表达式（15分） (2) 使用任一编程语言实现该正则表达式的匹配（5分）

要求能够匹配以下字符串：

JACK、Jo、LoremIpsum、AB1、Z97

要求不得匹配以下字符串：

A1、404、BadUs3rnam3、c57bT3

 

三、神奇的递归（27分）

在不使用你所使用的编程语言中的任何循环、及遍历函数（包括但不仅限于javascript、python中的reduce、map）的情况下，使用递归完成以下练习：

4. 有一段特别的楼梯，每次只能走2阶，3阶，或5阶，请编写函数计算当有n阶（n >= 2）楼梯时，有几种走法。（12分）

5. 请使用你的编程语言实现函数sum(arr []int, n unsigned)

其接收一个数组array和1个正整数n，返回array中的前n个数的和（n不超过数组长度）（15分）

 

四、实践算法 （40分）

6. 阅读材料，编写代码：（20分）

在使用ROT13的凯撒加密算法中，所有的字母均被偏移了13位，比如A加密后的值是N，N加密后的值是A，同理，B加密后为O，O加密后为B。现在请你实现解密器，已知所有输入均为大写字母或标点符号或空格。

例子：

输入：SERR PBQR PNZC 输出：FREE CODE CAMP

输入：CVMMN!输出：PIZZA!

输入：GUR DHVPX OEBJA SBK WHZCF BIRE GUR YNML QBT.输出：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG.

 

7. 请实现回文英文句/词判定器或函数。（20分）

所有空格及标点符号均忽略，忽略大小写

输入：eye输出：true

输入：_eye输出：true

输入：A man, a plan, a canal. Panama输出：true

输入：nope 输出：false

输入：0-0_0输出：true

输入：race car输出：true

 

在完成后请务必反复检查，确保答案的正确性，将于9/25公布答案。