记录一下自己的笔试的代码题
第一题
整数n, 0 <= n < 2^31, 输入到isPalindromeBit中，判断其二进制数是否是回文字符串。
string toBinary(int num) {
string ans = "";
int i = 0;
while (num > 0) {
ans += to_string(num & 1);
num = num >> 1;
}
return ans;
}
bool isPalindromeBit(int n) {
// write code here
if (n == 0) return true;
string s = toBinary(n);
string ss = s;
reverse(ss.begin(), ss.end());
return s == ss;
}
转换为二进制字符串，再翻转对比一下就OK了。全通过。
第二题
输入一段字符串，判断有几个子字符串满足下列条件：
- ’@’之前，非首字符任意字符可以为大小写字母、数字、下划线、点、减号，首字母可以为大小写字母、数字、下划线，字符数量大于等于2；
- ’@’之后可以为字母、数字，且至少有一个点，点后面的字符必须大于等于2；
判断是否有1个以上的合法邮箱。如果没有，返回"false"，如果有，则返回true + 最长合法邮箱子串。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @return string字符串
*/
string printEmail(string str) {
const int begin = 0;
const int before = 1;
const int after = 2;
const int after2 = 3;
int cnt = 0;
int state = begin;
// write code here
string s = "", s2 = "";
string ans = "";
int mailcnt = 0;
int index = 0;
string maxMail = "";
for(int i = 0; i < str.size(); ++i){
char c = str[i];
if(c == '@') {
if(state == before){
state = after;
s2 = "";
} else if(state == after2){
state = begin;
if(cnt >= 2) {
++mailcnt;
string mail = s + '@' + s2;
if(mail.size() >maxMail.size()) maxMail = mail;
i = index;
}
cnt = 0;
s = "";
s2 = "";
}
index = i;
continue;
}
if(state == begin){
state = before;
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_'){
s += c;
++cnt;
} else {
s = "";
cnt = 0;
state = begin;
}
}
else if(state == before){
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_' || c == '.' || c == '-'){
s += c;
++cnt;
} else {
s = "";
cnt = 0;
state = begin;
}
} else {
if(cnt < 2 && state == after){
s = "";
cnt = 0;
state = begin;
--i;
continue;
} else {
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')){
if (state == after2){
++cnt;
}
s2 += c;
} else if(c == '.'){
state = after2;
s2 += c;
cnt = 0;
} else {
s = "";
s2 = "";
cnt = 0;
state = begin;
}
}
}
}
if(mailcnt > 0){
return "true " + maxMail;
}
return "false";
}
};
int main(){
string s = "132.66sd@12.dfd@135.23@dfe.d";
Solution s2;
cout<<s2.printEmail(s)<<endl;
return 0;
}
使用状态转移的方法。没来得及提交，但应该是通过的。
第三题
共有n种类型的题，不同的m种题可以组成一张试卷，共可以组成多少试卷。
int calPaper(int &n, int &m, vector<int> &a){
if(n < m) return 0;
sort(a.begin(), a.end());
if(n == m) return a[0];
int cnt = 0;
int total = n;
int tmp = a[n - m];
a[n-m] = 0;
int ans = tmp;
while(total >= m){
for(int i = n - m + 1; i < n; ++i){
a[i] -= tmp;
if(a[i] == 0){
cnt++;
}
}
total = n - cnt;
if(total < m) break;
else {
sort(a.begin(), a.end());
tmp = a[n-m];
a[n-m] = 0;
ans += tmp;
}
}
return ans;
}
int main(){
int n, m;
cin>>n>>m;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin>>a[i];
}
cout<<calPaper(n, m, a);
return 0;
}
排序过后，取后m种类型，组成试卷数量就是a[n-m]个，重复操作，直到剩余试卷种类少于m个。全通过。
第四题
士兵为'S'，敌人为'E'，障碍物为'X'，可通行街区为'B'。士兵转向消耗1，移动消耗1，只能水平竖直移动，找到士兵走到敌人时，花费最少的路径的开销。
（1）我第一次写的dfs算法，未全通过：
#include<iostream>
#include<vector>
#include<math.h>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int U = 0, D = 1, L = 2, R = 3;
int minCost = INT32_MAX;
int getCost(int oldDirect, int newDirect, int cost){
return oldDirect == newDirect ? cost+1 : cost+2;
}
void dfs(vector<vector<char>> &graph, vector<vector<bool>> flag, int direct, int i, int j, int cost){
if(cost > minCost) return;
if(!flag[i][j]){
flag[i][j] = true;
if(graph[i][j] == 'E'){
if(cost < minCost) minCost = cost;
} else if(graph[i][j] == 'B') {
if(i > 0 && graph[i-1][j] != 'X') {
dfs(graph, flag, U, i-1, j, getCost(direct, U, cost));
}
if(j > 0 && graph[i][j-1] != 'X') {
dfs(graph, flag, L, i, j-1, getCost(direct, L, cost));
}
if(i < graph.size()-1 && graph[i+1][j] != 'X') {
dfs(graph, flag, D, i+1, j, getCost(direct, D, cost));
}
if(j < graph[0].size()-1 && graph[i][j+1] != 'X') {
dfs(graph, flag, R, i, j+1, getCost(direct, R, cost));
}
}
}
}
int leastCost(vector<vector<char>> graph, int M, int N, int x, int y){
vector<vector<bool>> flag(M, vector<bool>(N, false));
if(x > 0 && graph[x-1][y] != 'X') {
dfs(graph, flag, U, x-1, y, 1);
}
if(y > 0 && graph[x][y-1] != 'X') {
dfs(graph, flag, L, x, y-1, 1);
}
if(x < M-1 && graph[x+1][y] != 'X') {
dfs(graph, flag, D, x+1, y, 1);
}
if(y < N-1 && graph[x][y+1] != 'X') {
dfs(graph, flag, R, x, y+1, 1);
}
return minCost;
}
int main(){
int M,N;
cin>>M>>N;
vector<vector<char>> graph(M, vector<char>(N));
int x, y;
for(int i = 0 ; i < M; ++i){
for(int j = 0; j < N ; ++j){
cin>>graph[i][j];
if(graph[i][j] == 'S'){
x = i, y = j;
flag[i][j] = true;
}
}
}
cout<<leastCost(graph, M, N, x, y);
return 0;
}