HJ1 字符串最后一个单词的长度
HJ1 字符串最后一个单词的长度
描述
计算字符串最后一个单词的长度,单词以空格隔开,字符串长度小于5000。(注:字符串末尾不以空格为结尾)
输入描述:
输入一行,代表要计算的字符串,非空,长度小于5000。
输出描述:
输出一个整数,表示输入字符串最后一个单词的长度。
方法一
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s;
getline(cin, s);
int ans=0, i=s.length()-1;
while(i>=0 && s[i]!=' ')
{
i--;
ans++;
}
cout<<ans;
return 0;
}
方法二
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s;
while (cin>>s);
cout<<s.size();
}
HJ2 计算某字符出现次数(字符串,哈希)
描述
写出一个程序,接受一个由字母、数字和空格组成的字符串,和一个字符,然后输出输入字符串中该字符的出现次数。(不区分大小写字母)
数据范围: 1≤n≤1000
输入描述:
第一行输入一个由字母和数字以及空格组成的字符串,第二行输入一个字符。
输出描述:
输出输入字符串中含有该字符的个数。(不区分大小写字母)
方法一:哈希表
#include<iostream>
#include<unordered_map>
using namespace std;
int main(){
char target;
unordered_map<char, int> mp;
char c;
while((c = getchar()) != '\n'){ //按字符输入字符串
if(c >= 'A' && c <= 'Z') //大写转小写
c = c - 'A' + 'a';
mp[c]++; //统计频率
}
cin >> target; //输入目标字符
if(target >= 'A' && target <= 'Z') //大写转小写
target = target - 'A' + 'a';
cout << mp[target] << endl;
return 0;
}
方法二:遍历统计法
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
vector<string> s;
string input;
while(cin >> input) //将字符串以空格分割作为单词保存在数组
s.push_back(input);
char target = s[s.size() - 1][0]; //第二行输入的目标字符也会被上方代码读取,数组最后一个字符串就是目标字符
if(target >= 'A' && target <= 'Z') //大写转小写
target = target - 'A' + 'a';
int res = 0;
for(int i = 0; i < s.size() - 1; i++){ //遍历数组的每个字符
for(int j = 0; j < s[i].length(); j++){
char c = s[i][j];
if(c >= 'A' && c <= 'Z') //大写转小写
c = c - 'A' + 'a';
if(c == target) //记录出现次数
res++;
}
}
cout << res << endl;
return 0;
}
HJ3 明明的随机数(数组)
描述
明明生成了NN个1到500之间的随机整数。请你删去其中重复的数字,即相同的数字只保留一个,把其余相同的数去掉,然后再把这些数从小到大排序,按照排好的顺序输出。
数据范围:1≤n≤1000 ,输入的数字大小满足 1≤val≤500
输入描述:
第一行先输入随机整数的个数 N 。 接下来的 N 行每行输入一个整数,代表明明生成的随机数。 具体格式可以参考下面的"示例"。
输出描述:
输出多行,表示输入数据处理后的结果
方法一:暴力排序去重
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
while(cin >> n){ //首先输入每次调查的人数n
vector<int> v(n);
for(int i = 0 ; i < n; i++) //连续输入n个整数
cin >> v[i];
sort(v.begin(), v.end()); //排序
for(int i = 0; i < n; i++){ //去重输出
if(i != 0 && v[i] == v[i - 1])
continue;
else
cout << v[i] << endl;
}
}
return 0;
}
方法二:有序集合
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int main(){
int n;
set<int> s;
while(cin >> n){ //首先输入每次调查的人数n
s.clear(); //每次调查清空集合
for(int i = 0 ; i < n; i++){
int temp;
cin >> temp; //连续输入n个整数
s.insert(temp); //插入集合中,自动排序去重
}
for(auto iter = s.begin(); iter != s.end(); iter++) //遍历集合直接输出即可
cout << *iter << endl;
}
return 0;
}
HJ4 字符串分隔
描述
•输入一个字符串,请按长度为8拆分每个输入字符串并进行输出;
•长度不是8整数倍的字符串请在后面补数字0,空字符串不处理。
输入描述:
连续输入字符串(每个字符串长度小于等于100)
输出描述:
依次输出所有分割后的长度为8的新字符串
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int main() {
string s;
getline(cin, s);
while (true) {
int len = s.size();
if (len <= 8) {
s.insert(s.end(), 8-len, '0');
cout << s << endl;
if (!getline(cin, s)) break;
}
else {
cout << s.substr(0, 8) << endl;
s = s.substr(8, len-8);
}
}
return 0;
}
HJ5 进制转换
描述
写出一个程序,接受一个十六进制的数,输出该数值的十进制表示。
数据范围:保证结果在1≤n≤2^31−1
输入描述:
输入一个十六进制的数值字符串。
输出描述:
输出该数值的十进制字符串。不同组的测试用例用\n隔开。
方法一:遍历转换
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int main(){
string s;
while(cin >> s){ //连续读取字符串
int bit = 0; //记录当前位数
int res = 0;
for(int i = s.length() - 1; i > 1; i--){
if(s[i] >= '0' && s[i] <= '9'){
res += (s[i] - '0') * pow(16, bit); //当前数字乘16的位数次方
bit++;
}
else if(s[i] >= 'A' && s[i] <= 'F'){
res += (s[i] - 'A' + 10) * pow(16, bit); //字母要转化成数字
bit++;
}
}
cout << res << endl;
}
return 0;
}
方法二:流输入输出的格式化
#include<iostream>
using namespace std;
int main(){
int res = 0;
while(cin >> hex >> res) //hex表示读入十六进制数
cout << dec << res << endl; //dec表示输出十进制数
return 0;
}
HJ6 质数因子
描述
功能:输入一个正整数,按照从小到大的顺序输出它的所有质因子(重复的也要列举)(如180的质因子为2 2 3 3 5 )
数据范围: 1≤n≤2×10^9+14
输入描述:
输入一个整数
输出描述:
按照从小到大的顺序输出它的所有质数的因子,以空格隔开。
方法一:迭代
#include<iostream>
#include<cmath>
using namespace std;
int main(){
long n;
cin >> n;
for(long i = 2; i <= sqrt(n) && i <= n; i++){ //从小到大的质因子,质因子不会超过它的开方
while(n % i == 0){ //所有的质数前面全部除掉,后续就不会有合因子
cout << i << " ";
n /= i; //除掉质因子
}
}
if(n - 1) //自己本身就是质数
cout << n << " ";
return 0;
}
方法二:递归
#include<iostream>
#include<cmath>
using namespace std;
void recursion(long n){//递归函数
for(long i = 2; i <= sqrt(n); i++){ //每次遍历到n的开方就行了
if(n % i == 0){
cout << i << " ";
recursion(n / i); //递归解决后续更小的
return;
}
}
if(n - 1 > 0) //自己就是质数
cout << n << " ";
}
int main(){
long n;
cin >> n;
recursion(n);
return 0;
}
HJ7 取近似值
描述
写出一个程序,接受一个正浮点数值,输出该数值的近似整数值。如果小数点后数值大于等于 0.5 ,向上取整;小于 0.5 ,则向下取整。
数据范围:保证输入的数字在 32 位浮点数范围内
输入描述:
输入一个正浮点数值
输出描述:
输出该数值的近似整数值
方法一:比较判断法
#include<iostream>
#include<cmath>
using namespace std;
int main(){
float x;
cin >> x;
int y = x / 1; //得到整数部分
if(x - (float)y < 0.5) //判断小数部分与0.5的大小
cout << y << endl; //四舍
else
cout << y + 1 << endl; //五入
return 0;
}
方法二:强制类型转换
#include<iostream>
using namespace std;
int main(){
float x;
cin >> x;
cout << (int)(x+0.5) << endl; //强制类型转换
return 0;
}
HJ8 合并表记录
描述
数据表记录包含表索引index和数值value(int范围的正整数),请对表索引相同的记录进行合并,即将相同索引的数值进行求和运算,输出按照index值升序进行输出。
提示:
0 <= index <= 11111111
1 <= value <= 100000
输入描述:
先输入键值对的个数n(1 <= n <= 500)
接下来n行每行输入成对的index和value值,以空格隔开
输出描述:
输出合并后的键值对(多行)
方法一:桶排序(空间溢出)
#include <iostream>
#define size 11111112 // 申请的空间大小
using namespace std;
int main() {
int n;
cin >> n;
int kv[size] = {0}; // 初始化空间
while(n) {
int k, v;
cin >> k;
cin >> v;
kv[k] += v; // 对每一个对应的桶进行value值的装填
n--;
}
for(int i = 0; i < size; i++) {
if(kv[i]) cout << i << " " << kv[i] << endl; // 根据桶排序的索引顺序输出键值对
}
return 0;
}
方法二:红黑树
#include <iostream>
#include <map>
using namespace std;
int main() {
int n;
cin >> n;
map<int, int> kv; // 声明map数据结构
while(n) {
int k, v;
cin >> k;
cin >> v; // 装填key-value信息
kv[k] += v; // 根据key值在value上累加
n--;
}
for(auto [k, v] : kv) {
cout << k << " " << v << endl; // 按照map中元素的顺序进行访问
}
}
方法三
#include <iostream>
#include <algorithm>
using namespace std;
//合并表记录的函数接口
int ConsolidateTableRecords (int num) {
int index; //索引,key(键)
int value; //数值,值
int a[1000] = {0}; //初始化一个数组,用于记录输入的合并表
int b[1000] = {0}; //*初始化一个数组,用于记录出现的索引
int max = 0; //记录输入的最大索引值
while (num--) {
//将数组的下标视为索引,下标对应的元素值视为数值
cin >> index >> value;
//相同索引对应的数值自动合并
a[index] += value;
b[index] = 1; //*补充当索引值对应的数值累加和为零的情况
if (index >= max) {
max = index;
}
}
//按key值升序输出,直到输出最大索引值 index 对应的数值 value 为止
for(int i = 0; i <= max; i++) {
//*增加了 if 语句的第二个判定条件
if ((a[i] > 0) || ((a[i] == 0) && (b[i] == 1))) {
cout << i << ' ' << a[i] << endl;
}
}
return 0;
}
//主函数
int main () {
int num;
while (cin >> num) {
ConsolidateTableRecords (num);
}
return 0;
}
HJ9 提取不重复的整数
描述
输入一个 int 型整数,按照从右向左的阅读顺序,返回一个不含重复数字的新的整数。
保证输入的整数最后一位不是 0 。
数据范围: 1≤n≤10^28
输入描述:
输入一个int型整数
输出描述:
按照从右向左的阅读顺序,返回一个不含重复数字的新的整数
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
int num;
cin>>num; //输入一个int型整数
vector<int> vec; //使用vector容器
while(num) {
if(find(vec.begin(), vec.end(), num%10) == vec.end()) //插入数据前判断是否已有该数字
vec.push_back(num%10); //从右向左添加数字
num /= 10; //除以10
}
int n=0; //初始化一个新的整数
for(int i=0;i<vec.size();i++) {
n *= 10;
n += vec[i];
}
cout<<n<<endl;
}
HJ10 字符个数统计
描述
编写一个函数,计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ,包括 0 和 127 ),换行表示结束符,不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
例如,对于字符串 abaca 而言,有 a、b、c 三种不同的字符,因此输出 3 。
数据范围: 1≤n≤500
输入描述:
输入一行没有空格的字符串。
输出描述:
输出 输入字符串 中范围在(0~127,包括0和127)字符的种数。
方法一:使用数组记录每种字符是否已经出现 (哈希表思想)
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int ans=0;
int vis[128]={0};
string str;
int main() {
cin>>str;
int len=str.length();
for(int i=0;i<len;i++){
int asc=(int)str[i];
if(vis[asc]==0) { //如果当前字符没出现过
vis[asc]=1; //标记该字符的出现
ans++; //增加字符种类统计数
}
}
cout<<ans<<endl;
return 0;
}
方法二:使用集合来统计(同样是哈希表的思想)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;
string str;
set<char> ascs;
int main() {
cin>>str;
int len=str.length();
for(int i=0;i<len;i++){
ascs.insert(str[i]); //向集合中添加字符
}
cout<<ascs.size()<<endl; //输出集合的尺寸
return 0;
}
HJ11 数字颠倒
描述
输入一个整数,将这个整数以字符串的形式逆序输出
程序不考虑负数的情况,若数字含有0,则逆序形式也含有0,如输入为100,则输出为001
数据范围: 0≤n≤2^30−1
输入描述:
输入一个int整数
输出描述:
将这个整数以字符串的形式逆序输出
方法一:转换为字符串
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string s;
cin >> s; // 以字符串格式输入
reverse(s.begin(), s.end()); // reverse来倒序原有的字符串
cout << s;
return 0;
}
方法二:数学方法转换
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
if(n == 0) cout<<0;
while(n) {
cout << n % 10; // 取个位数字并输出
n /= 10; // 整除10
}
return 0;
}
HJ12 字符串反转
描述
接受一个只包含小写字母的字符串,然后输出该字符串反转后的字符串。(字符串长度不超过1000)
输入描述:
输入一行,为一个只包含小写字母的字符串。
输出描述:
输出该字符串反转后的字符串。
方法一:逆序拼接
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
string s;
cin >> s;
string output = ""; //从一个空串开始
for(int i = s.length() - 1; i >= 0; i--) //逆序遍历字符串
output += s[i]; //将字符加到新串后面
cout << output << endl;
return 0;
}
方法二:双指针交换
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
string s;
cin >> s;
//左右双指针
int left = 0;
int right = s.length() - 1;
while(left < right){ //两指针往中间靠
swap(s[left], s[right]); //交换两边字符
left++;
right--;
}
cout << s << endl;
return 0;
}
方法三:反转函数
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
string s;
cin >> s;
reverse(s.begin(), s.end()); //逆转函数
cout << s;
return 0;
}
HJ13 句子逆序
描述
将一个英文语句以单词为单位逆序排放。例如“I am a boy”,逆序排放后为“boy a am I”
所有单词之间用一个空格隔开,语句中除了英文字母外,不再包含其他字符
数据范围:输入的字符串长度满足1≤n≤1000
注意本题有多组输入
输入描述:
输入一个英文语句,每个单词用空格隔开。保证输入只包含空格和字母。
输出描述:
得到逆序的句子
方法一
#include<iostream>
using namespace std;
int main() {
string s,str="";
while(cin>>s) {//循环输入流 ctrl+z表示最后输入结束
s+= " " +str;
str=s;
}
cout <<str<< endl;
return 0;
}
方法二:两次反转
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
string s, temp;
while(cin >> temp) //输入字符串
s += " " + temp;
int n = s.length();
reverse(s.begin(), s.end()); //第一次整体反转
for(int i = 0; i < n; i++){
int j = i;
while(j < n && s[j] != ' ') //以空格为界找到一个单词
j++;
reverse(s.begin() + i, s.begin() + j); //将这个单词反转
i = j;
}
cout << s << endl;
return 0;
}
方法二:分割字符串+栈
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
int main(){
string s, temp;
while(cin >> temp) //输入字符串
s += " " + temp;
int n = s.length();
stack<string> st;
for(int i = 0; i < n; i++){ //遍历字符串,找到单词并入栈
int j = i;
while(j < n && s[j] != ' ') //以空格为界,分割单词
j++;
st.push(s.substr(i, j - i)); //单词进栈
i = j;
}
s = "";
while(!st.empty()){ //栈遵循先进后厨,单词顺序是反的
s += st.top();
st.pop();
if(!st.empty())
s += " ";
}
cout << s << endl;
return 0;
}
方法三:输入时反向拼接
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
int main(){
string s, temp;
while(cin >> temp){ //输入字符串
temp += " " + s; //每个单词加在字符串前面
s = temp;
}
cout << s << endl;
return 0;
}
HJ14 字符串排序
描述
给定 n 个字符串,请对 n 个字符串按照字典序排列。
数据范围: 1≤n≤1000 ,字符串长度满足 1≤len≤100
输入描述:
输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。
输出描述:
数据输出n行,输出结果为按照字典序排列的字符串。
方法一:冒泡排序
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
int n;
cin >> n;
vector<string> strs; //字符串数组
string s;
for(int i = 0; i < n; i++){ //输入n个字符串
cin >> s;
strs.push_back(s); //堆排序
}
for(int i = 0; i < n; i++)
for(int j = 1; j < n; j++)
if(strs[j] < strs[j - 1]){//比较并冒泡
string temp = strs[j]; //交换
strs[j] = strs[j - 1];
strs[j - 1] = temp;
}
for(int i = 0; i < n; i++) //输出
cout << strs[i] << endl;
return 0;
}
方法二:堆排序
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
int n;
cin >> n;
priority_queue<string, vector<string>, greater<string> > strs; //小根堆
string s;
for(int i = 0; i < n; i++){ //输入n个字符串
cin >> s;
strs.push(s); //堆排序
}
while(!strs.empty()){ //从小到大输出
cout << strs.top() << endl;
strs.pop();
}
return 0;
}
方法三:库函数快排
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<string> strs;
string s;
for(int i = 0; i < n; i++){ //输入n个字符串
cin >> s;
strs.push_back(s);
}
sort(strs.begin(), strs.end()); //排序函数
for(int i = 0 ;i < n; i++) //输出
cout << strs[i] << endl;
return 0;
}
方法四:有序集合
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
int main(){
int n;
cin >> n;
multiset<string> strs; //可重复的有序集合
string s;
for(int i = 0; i < n; i++){ //输入n个字符串
cin >> s;
strs.insert(s); //加入集合中
}
for(auto iter = strs.begin(); iter != strs.end(); iter++) //遍历集合输出
cout << *iter << endl;
return 0;
}
方法五:归并排序
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<string> temp;
void mergeSort(vector<string>& strs, int l, int r) {
if (l >= r)
return;
int mid = (l + r) / 2; //中间划分
mergeSort(strs, l, mid); //排序两边
mergeSort(strs, mid + 1, r);
int i = l, j = mid + 1;
int cnt = 0;
//合并
while (i <= mid && j <= r) { //依次比较,先取较小值
if (strs[i] <= strs[j])
temp[cnt++] = strs[i++];
else
temp[cnt++] = strs[j++];
}
while (i <= mid) //剩余的元素
temp[cnt++] = strs[i++];
while (j <= r)
temp[cnt++] = strs[j++];
for (int i = 0; i < r - l + 1; ++i)
strs[i + l] = temp[i];
}
int main(){
int n;
cin >> n;
vector<string> strs; //可重复的有序集合
string s;
for(int i = 0; i < n; i++){ //输入n个字符串
cin >> s;
strs.push_back(s); //加入集合中
}
temp.resize(n);
mergeSort(strs, 0, n - 1); //归并排序
for(auto iter = strs.begin(); iter != strs.end(); iter++) //遍历排序后的结果输出
cout << *iter << endl;
return 0;
}
HJ15 求int型正整数在内存中存储时1的个数
描述
输入一个 int 型的正整数,计算出该 int 型数据在内存中存储时 1 的个数。
数据范围:保证在 32 位整型数字范围内
输入描述:
输入一个整数(int类型)
输出描述:
这个数转换成2进制后,输出1的个数
方法一:转化二进制
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
cin >> n;
int count = 0;
string s = "";
while(n){ //十进制转化成二进制
s += ((n % 2) + '0'); //用字符串记录二进制每一位
n /= 2;
}
for(int i = 0; i < s.length(); i++) //遍历字符串统计1的个数
if(s[i] == '1')
count++;
cout<< count << endl;
return 0;
}
方法二:移位运算
#include<iostream>
using namespace std;
int main(){
int n;
cin >> n;
int count = 0;
while(n){
if(n & 1) //和最后一位按位与运算
count++; //与的结果是1说明这位是1
n >>= 1; //移位
}
cout<< count << endl;
return 0;
}
方法三:用位与去掉二进制末尾1
#include<iostream>
using namespace std;
int main(){
int n;
cin >> n;
int count = 0;
while(n){
count++; //统计+1
n &= (n - 1); //去掉末尾的1
}
cout<< count << endl;
return 0;
}