笔试题目

机考的经验和练习题网站

常考知识点：

基本操作：输入输出处理（重点），字符串操作与ASCii码（重点）
数据结构：一维数组，栈，队列
编程思想：暴力法（重点），递归
算法：排列组合（重点），快速排序（重点），二分查找，位运算，滑动窗口，深度优先搜索（进阶），广度优先搜索（进阶），搜索回溯（进阶）

登录牛客网华为机试专栏练习并熟悉机试环境：https://www.nowcoder.com/ta/huawei

机考辅导

需要开摄像头，不能访问其他网页或查找资源，可以在本地IDE调试好后拷贝到牛客网上再调试
多刷一下各种类型算法题，难度中等及以上，在牛客有或力扣上刷都可以
熟悉牛客网考试环境，和本地IDE，力扣有差异
ACM模式，需要解决输入输出
一定不要死磕某一题，三题得分加起来达到及格分即可

逐个击破

牛客网环境check

输入输出处理

核心代码模式处理
不需要处理任何输入输出，直接返回值即可。
ACM 模式
你的代码需要处理输入输出，请使用如下样例代码读取输入和打印输出：

#include <iostream>
using namespace std;

int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case 。 这个while以后用起来
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

华为机试题目：https://www.nowcoder.com/ta/huawei

python解法过目：https://pycoder.blog.csdn.net/article/details/124648380

刷题

loading…

总结

数据结构

set和map的key是有序的 unorder_set和unorder_map无序，需要不同的头文件，另外，multimap和multiset的key允许重复， key有序

参考：https://www.cnblogs.com/PiaYie/p/15877059.html

string常用方法

https://blog.csdn.net/qq_37954088/article/details/82286530

在c++中谨慎用int

这个整型变量会参与到地址运算吗？(对于整型变量这非常常见，例如用作数组以及stl的索引)，如果是，那么不要用int了。

在索引访问、指针地址相关的运算上，使用ptrdiff_t和unsigned_int，应当是规范的C++的统一标准。否则混用的话，必然会出现大片的编译器警告，并且降低程序效率。

一些注意的点

int类型转换来做浮点数的四舍五入

int main() {
	float a;

	while (cin >> a) {
		if (a > 0) {
			cout << int(a + 0.5) << endl;
		}
	}

	return 0;
}

输入输出处理

输入原理

程序的输入都有一个缓冲区，即输入缓冲区。一次输入过程是这样的，当一次键盘输入结束时会将输入的数据存入输入缓冲区，而cin对象直接从输入缓冲区中取数据。正因为cin对象是直接从缓冲区取数据的，所以有时候当缓冲区中有残留数据时，cin对象会直接取得这些残留数据而不会请求键盘输入

cin的说明

参考 https://blog.csdn.net/selina8921/article/details/79067941

该操作符是根据后面变量的类型读取数据。
输入结束条件：遇到Enter、Space、Tab键。
当cin>>从缓冲区中读取数据时，若缓冲区中第一个字符是空格、tab或换行这些分隔符时，cin>>会将其忽略并清除，继续读取下一个字符，若缓冲区为空，则继续等待。但是如果读取成功，字符后面的分隔符是残留在缓冲区的，cin>>不做处理。

cout的说明

输入一个字符串不带空格和一个变量

cout.width(8);

控制 下一次 cout输出宽度至少大于等于8

cout.fill(‘0’);

下一次 cout输出不够就填充0

cout << left << “asdasdas”<< endl;

本次左对齐

技巧

若要读取单个字符，直接cin.get(char ch)或ch=cin.get()即可

cin.get()的返回值是int类型，成功：读取字符的ASCII码值，遇到文件结束符时，返回EOF，即-1，Windows下标准输入输入文件结束符为Ctrl+z，Linux为Ctrl+d。

cin.get(str,size);读取一行时，只能将字符串读入C风格的字符串中，即char*，但是C++的getline函数还可以将字符串读入C++风格的字符串中，即string类型。
while(cin>>s);

注意 while 处理多个 case。退出方法：回车后，在新行Ctrl+z并回车。若输入数据后Ctrl+z再回车无效。

这是因为：https://blog.csdn.net/qq_41543888/article/details/102766294

ch = toupper(getchar())

tolower()/toupper() c++内建函数

int tolower(int c)
{
	if ((c >= 'A') && (c <= 'Z'))
		return c + ('a' - 'A');
	return c;
}
 
int toupper(int c)
{
	if ((c >= 'a') && (c <= 'z'))
		return c + ('A' - 'a');
	return c;
}

读取一行用cin.get(a, 5);

cin.get(数组名，长度，[结束符]) 结束符可选,默认回车Enter

对结束符处理：不丢弃缓冲区中的Enter（自定义结束符时同样不丢弃缓冲区中的结束符）

会在读取的字符串后面自动加上’/0′

#include<iostream>
using namespace std;
int main(void){
  char ch='a',a[20];
  cin.get(a,5);
  cin.get(ch);
  cout<<a<<"--"<<(int)ch<<endl;  Enter 的ascii为10
return 0;
}

输入：
1 23回车
输出:
1 23--10

读取一行用getline

cin.getline(数组名，长度，[结束符]) 结束符可选,默认回车Enter, i.e., ‘/n’

getline()的原型是 istream& getline ( istream &is , string &str , char delim );

cin就是一个输入流

会在读取的字符串后面自动加上’/0′

鉴于getline较cin.get()的优点，建议使用getline进行行的读取。区别：

cin.get()当输入的字符串超过规定长度时，不会引起cin函数的错误，后面的cin操作会继续执行，只是直接从缓冲区中取数据。

但是cin.getline()当输入超过规定长度时，会引起cin函数的错误，后面的cin操作将不再执行。

当输入的字符数大于count时，则get函数只读取count-1个字符，而其余的字符仍然保存在缓冲区中，还可再对其进行读取；

但是函数getline则不然，getline()会设置失效位(faibit)，并且关闭后面的输入，这个时候再用ch=cin.get()是读取不到留在输入队列中的字符的。
可以用下面的命令来恢复输入：

cin.clear()； //因为clear()会重置失效位，打开输入。这个时候ch=cin.get();就可以读取留在输入队列中的字符。

cin.get读取一行时，遇到换行符(自定义结束符)时结束读取，但是不对换行符(自定义结束符)进行处理，换行符(自定义结束符)仍然残留在输入缓冲区。

getline读取一行字符时，默认遇到’/n’(自定义结束符)时终止，并且将’/n’(自定义结束符)直接从输入缓冲区中删除掉，不会影响下面的输入处理。

两者都会在读取的字符串后面自动加上’/0′

cin.get(str,size);读取一行时，只能将字符串读入C风格的字符串中，即char*，但是C++的getline函数还可以将字符串读入C++风格的字符串中，即string类型。（string test; getline(cin,test);）

清楚缓冲区的4种办法
#include<sstream>

使用sstream::stringstream输入输出流进制转换

	stringstream ss;
	string tmp;
	int a = 10;
	ss << hex << a;
	ss >> tmp;
	cout << tmp<< endl;//输出 a

字符串操作与ascii码

字符串中的某一个字串全替换为另一个串

string& replace_all(string& src, const string& old_value, const string& new_value) {
	// 每次重新定位起始位置，防止上轮替换后的字符串形成新的old_value
	for (string::size_type pos(0); pos != string::npos; pos += new_value.length()) {
		if ((pos = src.find(old_value, pos)) != string::npos) {
			src.replace(pos, old_value.length(), new_value);
		}
		else break;
	}
	return src;

}

即使str字符串长度不足8，str.substr(0, 8)也能正常获取剩余的字符，不会报错。

int main()
{
	string str;
	cin >> str;
	cout << str.substr(0, 8) << endl;
	return 0;
}

字符串转数值，可以用内建函数如 stoll stoi stof stod

int stoi (const string& str, size_t* idx = 0, int base = 10); base 默认值为10即以十进制解析， idx默认为 nullptr即可，表示从后面碰到数值的第一个字符开始解析

int main() {
	string str;
	while (cin >> str) {
		cout << stoi(str,nullptr,0) << endl;
	}

	return 0;
}

自己按照逻辑实现进制转换
十六进制转10进制

十六进制转10进制输入 ‘0xAAA’ /to int32

使用pow函数要加头文件< cmath > 不然过不了编译

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

int main() {
    string str;
    while (cin >> str) {
        int pow_up_num = 0;
        int res = 0;
        for (int i = str.size() - 1; i > 1; i --) {
            if(str[i] >= '0' && str[i] <= '9')
            {
                res += (str[i] - '0') * pow(16, pow_up_num);
                pow_up_num++;
            }
            else if(str[i] >= 'A' && str[i] <= 'F'){
                res += (str[i] - 'A'+10) * pow(16, pow_up_num);
                pow_up_num++;
            }
            else if (str[i] >= 'a' && str[i] <= 'f') {
                res += (str[i] - 'a'+10) * pow(16, pow_up_num);
                pow_up_num++;
            }
            else {
                cout << "error input!" << endl;
                exit(-1);
            }
        }
        cout << res << endl;

    }

    return 0;
}

字符串反转
- 内建函数reverse(s,s.begin(),s.end());记得加头文件#include< algorithm.h >
- 自己实现reverse函数

    void reverse_string(string& s, int start, int end) {
        while (start < end) {
            swap(s[start++], s[end--]);
        }
    }

使用排序算法sort(s.begin(), s.end());时候记得加头文件#include< algorithm.h >
单词字典序

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;
int main() {
	int N;
	while (cin >> N) {
		//vector<string> res;
		vector<string> s;
		for (int i = 0; i < N; i++) {
			string str;
			cin >> str;
			s.push_back(str);
		}
		sort(s.begin(), s.end()); // str1 > str2 可以这样对比字符串单词字典序
		for (auto a : s) {
			cout << a << endl;
		}
	}


	return 0;
}

正则表达式+stringstream+getline(ss,t,”;”)分割字符串

题目：坐标移动

getline()的第三个参数默认为空格Enter 可以自行更改
使用regex_match要包含头文件 #include<regex>

https://blog.csdn.net/qq_34802416/article/details/79307102
使用stringstream分割字符串需要头文件#include<sstream>

https://www.cnblogs.com/gamesky/archive/2013/01/09/2852356.html

#include<iostream>
#include<string>
#include<regex>
#include <vector>
#include<sstream>
using namespace std;

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0), cout.tie(0);
    string s, t;
    while (getline(cin, s)) {
        stringstream ss(s);
        pair<int, int> p(0, 0);
        while (getline(ss, t, ';')) {
            if (t.empty())
                continue;
            string _ = t.substr(1);
            if (regex_match(_, regex("[0-9]*"))) {
                switch (t[0]) {
                case 'A': p.first -= stoi(_); break; //左移
                case 'D': p.first += stoi(_); break; //右移
                case 'W': p.second += stoi(_); break; //上移
                case 'S': p.second -= stoi(_); break; //下移
                default: break; //无效
                }
            }
        }
        cout << p.first << "," << p.second << endl;
    }
    return 0;
}

ip地址和掩码的判断，地址的分类
主要是几个点要做好判断
1. 如何输入，ip用什么保存
  - 因为ip是以键盘输入如：127.26.135.1~255.255.255.0读入，所以使用 getline(cin,s,'~')分别读取前后ip和掩码，
2. 如何确定是忽略的ip地址，不统计
  - ip地址的第一个字段转int后为 127 或者 0
3. 如何识别是错误的ip
  - 不是合法的ip
    - ip段为空
    - ip段大转int后大于255
    - 不为四个IP段，或少或多
4. 如何识别是错误的掩码
  - 掩码由若干个1接上若干个0组成，问题是怎么把一个字符串做识别，可以每次读一个段，然后左移8位，最后存到一个无符号的int类型中，然后用以下代码判断是不是 111..10..01; if条件是指掩码不为全0，掩码不为全1，掩码由若干个1接若干个0
```
bool isLegalMask(string ip) {
	istringstream iss(ip);
	string sub;
	unsigned int b = 0;
	//vector<int> v;
	
	while (getline(iss, sub, '.'))  b = (b << 8) + stoi(sub);
	if (b == 0 || b == 0xFFFFFFFF || (((b ^ 0xFFFFFFFF) + 1) | b) != b) {
		return false;
	}
	return true;
}
```
5. 如何获取ip地址的某一个段然后进行ip地址的分类判断
  - ip是以string读ru
  - 使用#include<sstream>的istringstream类型作为输入流，然后用while的case功能依次读入每一个段，存到一个vector中即可
```
istringstream iss(ip); //用stringstream也可以
	string sub;
	vector<int> sub_vec;
	while (getline(iss, sub, '.')) sub_vec.push_back(stoi(sub));
```
返回字符串中长度大于2的包含公共元素的最长重复子串

题目：密码验证合格程序

遍历所有的子串，统计出现次数，暴力搜

#include<iostream>
#include<string>
#include<map>
using namespace std;

//暴力破解找最长相同子串
string findMaxSubStr(string s) {
	string ret = "";
	
	int size = s.size();
	map<string, int> m;
	for (int len = 3; len < size; len++) { //每次check的字符串长度
		for (int pos = 0; pos < size; pos++) {//从最后一个字符串开始算起
			if (pos < size && pos + len < size) {
				string sub = s.substr(pos,len);
				m[sub]++;
			}
			

		}
	}

	for (auto i : m) {
		if (i.second >= 2) ret = i.first;
	}
	return ret;
}

//统计字符类型
int statisticStrType(string s) {
	int A = 0, B = 0, C = 0, D = 0;
	for (auto ch : s) {
		if (ch >= 'a' && ch <= 'z') A=1;
		else if (ch >= 'A' && ch <= 'Z') B=1;
		else if (ch >= '0' && ch <= '9') C=1;
		else D=1;
	}
	return (A+B+C+D);

}

int main() {
	string psd;
	while (cin >> psd) {
		if (psd.size() < 9) {
			cout << "NG" << endl;
		}
		else if (findMaxSubStr(psd).size() > 2) {
			cout << "NG" << endl;
		}
		else if (statisticStrType(psd) < 3) {
			cout << "NG" << endl;
		}
		else {
			cout << "OK" << endl;
		}

		
	}
	return 0;
}

只需要遍历所有长度为3的字符串，如果在字符串的其它地方找到了这个串就表示不通过

但是简单的拼接string ss = s.substr(0, pos) + s.substr(pos + 3)会出问题,形如021Aaabcbc$as这样的密码会被认为NG

所以还是遍历一遍所有的三个子字符串做统计，以此来实现优化

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
	string s;
	while (cin >> s) {
		//密码长度需要大于8
		if (s.size() <= 8) {
			cout << "NG" << endl;
			continue;
		}
		//密码至少有四种类型字符的三种
		int A = 0, B = 0, C = 0, D = 0;
		bool flag = false;
		for (auto ch : s) {
			if (ch >= 'a' && ch <= 'z') A = 1;
			else if (ch >= 'A' && ch <= 'Z') B = 1;
			else if (ch >= '0' && ch <= '9') C = 1;
			else D = 1;
		}
		if (A + B + C + D >= 3) {
			flag = true;
		}
		else {
			cout << "NG" << endl;
			continue;
		}
		int size = s.size();
		map<string, int> m;
		//密码不能有大于2包含公共元素的子字符串
		//只需要遍历所有长度为3的子字符串就好
		for (int pos = 0; pos < size; pos++) {//从第一个字符串开始算起
			if (pos < size && pos + 3 < size) {
				string sub = s.substr(pos, 3);
				m[sub]++;
			}
		}
		for (auto i : m) {
			if (i.second >= 2) {
				flag = false;
				break;
			}
		}

			//021Aaabcbc$
		

		if (flag) {
			cout << "OK" << endl;
		}
		else {
			cout << "NG" << endl;
		}
		
	}
	return 0;
}

string::npos用法，参考：https://blog.csdn.net/jiejinquanil/article/details/51789682

npos可以表示string的结束位子，是string::type_size 类型的，也就是find（）返回的类型。find函数在找不到指定值得情况下会返回string::npos
string or char 的一些方法
- islower(ch) ‘a’~’z’
- isupper(ch) ‘A’~’Z’
- isalpha(ch) ‘a’_{‘z’+’A’}‘Z’
- isalnum(ch) ‘a’_{‘z’+’A’}‘Z’+ ‘0’~’9′
- C++中string类下的begin，end，rbegin，rend的用法，返回迭代器，分别指向字符串的第一个位置，最后一个位置的下一个位置，最后一个位置，第一个位置的前一个位置
回文字符串
- 验证一个字符串是不是有效的回文，只考虑字母和数字字符，忽略字母的大小写，这里将空字符串也定义为有效的回文
  - 忽略字符串大小写可以用tolower(ch)或者是toupper(ch)
  - 仅仅考虑数字+字母，可以用 isalnum(ch)
  - 解法1：去除杂糅后，用字符串翻转api，然后看看翻转前后是否相等
  - 解法2：双指针，去除杂糅后，从两端开始分别判断是否相等，相等移动指针，否则不是回文，当两个指针相遇后，那么就是回文
  - 解法2优化，在原字符串上判断：就是要用while(left < right && !isalnum(ch))来忽略无关的字符，从而匹配到两个需要比较的位置
- 字符串中有效的回文子串数量，假设输入为已经处理过的字符串
  - 中心扩散，可以遍历每一个可能是回文中心的位置，然后向外扩散，直到两边字符不相等就停止扩散
  - 但是要注意子串长度，可能是奇数也可能是偶数，需要分别考虑
- 最长回文子序列，给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度；这里子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
  - dp[i][j]表示字符串下标为[i,j]内的最长子字符串
  - 初始化：0<=i<=j<n 时，dp[i][j]才有值，否则为0；任何单个字符都是回文，所以 0<=i<n 时，dp[i][i]=1
  - 当i<j时，考虑s[i]是否和s[j]相等的两种情况
    - s[i]==s[j]:在得到[i+1,j-1]之间的条件下，又在两边各加了一个字符，所以长度+2
    dp[i][j]=dp[i+1][j−1]+2
    - s[i]!=s[j]
      
      原创文章，作者：sunnyman218，如若转载，请注明出处：https://blog.ytso.com/277283.html

hw笔试知识学习记录

笔试题目

机考辅导

逐个击破

牛客网环境check

刷题

总结

数据结构

一些注意的点

输入输出处理

输入原理

cin的说明

cout的说明

技巧

字符串操作与ascii码

发表回复

hw笔试知识学习记录

笔试题目

机考辅导

逐个击破

牛客网环境check

刷题

总结

数据结构

一些注意的点

输入输出处理

输入原理

cin的说明

cout的说明

技巧

字符串操作与ascii码

相关推荐

发表回复