算法学习——华为机考题库8（HJ46 - HJ50）
HJ46 截取字符串
描述
输入一个字符串和一个整数 k ，截取字符串的前k个字符并输出
数据范围： 字符串长度满足 1≤n≤1000 ， 1≤k≤n
输入描述：
1.输入待截取的字符串
2.输入一个正整数k，代表截取的长度
输出描述：
截取后的字符串
示例
代码解析
#include <iostream>
#include <string>
using namespace std;
int main() {
string Str;
cin>>Str;
int k;
cin>>k;
Str = Str.substr(0,k);
cout<<Str;
}
// 64 位输出请用 printf("%lld")
HJ48 从单向链表中删除指定值的节点
描述
输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。
链表的值不能重复。
构造过程，例如输入一行数据为:
6 2 1 2 3 2 5 1 4 5 7 2 2
则第一个参数6表示输入总共6个节点，第二个参数2表示头节点值为2，剩下的2个一组表示第2个节点值后面插入第1个节点值，为以下表示:
1 2 表示为
2->1
链表为2->1
3 2表示为
2->3
链表为2->3->1
5 1表示为
1->5
链表为2->3->1->5
4 5表示为
5->4
链表为2->3->1->5->4
7 2表示为
2->7
链表为2->7->3->1->5->4
最后的链表的顺序为 2 7 3 1 5 4
最后一个参数为2，表示要删掉节点为2的值
删除 结点 2
则结果为 7 3 1 5 4
数据范围：链表长度满足 1≤n≤1000 ，节点中的值满足 0≤val≤10000
测试用例保证输入合法
输入描述：
输入一行，有以下4个部分：
1 输入链表结点个数
2 输入头结点的值
3 按照格式插入各个结点
4 输入要删除的结点的值
输出描述：
输出一行
输出删除结点后的序列，每个数后都要加空格
示例
代码解析
#include <bits/types/struct_tm.h>
#include <ctime>
#include <iostream>
using namespace std;
class Node
{
public:
int value;
Node* next;
Node():value(0),next(nullptr){}
Node(int a):value(a),next(nullptr) {}
Node(int a , Node* b):value(a),next(b) {}
};
int main() {
int num,head_value;
cin>>num;
cin>>head_value;
Node* Head = new Node(head_value);
for(int i=0 ; i < num-1 ; i++)
{
int value,insertValue;
cin>>value;
cin>>insertValue;
// cout<<value<<' '<<insertValue<<endl;
Node* tmp = Head;
while(tmp != nullptr)
{
if(tmp->value == insertValue)
{
Node* nextNode = tmp->next;
Node* cur = new Node(value,nextNode);
tmp->next = cur;
break;
}
tmp = tmp->next;
}
}
int delate;
cin>>delate;
Node* tmp = Head;
while(tmp != nullptr)
{
if(tmp->value != delate) cout<<tmp->value<<' ';
tmp= tmp->next;
}
}
// 64 位输出请用 printf("%lld")
HJ50 四则运算
描述
输入一个表达式（用字符串表示），求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
**数据范围：**表达式计算结果和过程中满足 ∣val∣≤1000 ，字符串长度满足 1≤n≤1000
输入描述：
输入一个算术表达式
输出描述：
得到计算结果
示例
代码解析
#include <iostream>
#include <stack>
using namespace std;
int pos;
int compute(string & data)
{
int len = data.length();
int num = 0;
char flag = '+';
stack<int> st;
while (pos < len)
{
if (data[pos] == '{' || data[pos] == '[' || data[pos] == '(')
{
pos++;
num = compute(data);
}
while (pos < len && isdigit(data[pos]))
{
num = num * 10 + data[pos] -'0';
pos++;
}
switch (flag)
{
case '+':
st.push(num);
break;
case '-':
st.push(-num);
break;
case '*':
{
int temp = st.top();
temp *= num;
st.pop();
st.push(temp);
break;
}
case '/':
{
int temp = st.top();
temp /= num;
st.pop();
st.push(temp);
break;
}
}
num = 0;
flag = data[pos];
if (data[pos] == '}' || data[pos] == ']'|| data[pos] == ')')
{
pos++;
break;
}
pos++;
}
int sum = 0;
while (st.size()) {
sum += st.top();
st.pop();
}
return sum;
}
int main()
{
string data;
while (cin >> data) {
pos = 0;
cout << compute(data) << endl;
}
return 0;
}
HJ51 输出单向链表中倒数第k个结点
描述
输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
正常返回倒数第k个结点指针，异常返回空指针.
要求：
(1)正序构建链表;
(2)构建后要忘记链表长度。
**数据范围：**链表长度满足 1≤n≤1000 ， k≤n ，链表中数据满足 0≤val≤10000
本题有多组样例输入。
输入描述：
输入说明
1 输入链表结点个数
2 输入链表的值
3 输入k的值
输出描述：
输出一个整数
示例
代码解析
#include <bits/types/struct_tm.h>
#include <iostream>
using namespace std;
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
int main() {
int num;
while(cin>>num)
{
ListNode *head = new ListNode();
int date;
ListNode *tmp;
for(int i=0 ; i<num ; i++)
{
cin>>date;
if(i==0)
{
head->m_nKey = date;
tmp = head;
}else
{
ListNode *cur = new ListNode();
cur->m_nKey = date;
tmp->m_pNext = cur;
tmp = tmp->m_pNext;
}
}
int k;
cin>>k;
ListNode *fast = head , *low = head;
while(k--) fast = fast->m_pNext;
while(fast != nullptr)
{
fast = fast->m_pNext;
low = low ->m_pNext;
}
cout<<low->m_nKey<<endl;
}
}
// 64 位输出请用 printf("%lld")
HJ52 计算字符串的编辑距离
描述
Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
例如：
字符串A: abcdefg
字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求：
给定任意两个字符串，写出一个算法计算它们的编辑距离。
**数据范围：**给定的字符串长度满足 1≤len(str)≤1000
输入描述：
每组用例一共2行，为输入的两个字符串
输出描述：
每组用例输出一行，代表字符串的距离
示例
代码解析
#include <iostream>
#include <vector>
using namespace std;
int main() {
string str1 , str2;
cin>>str1>>str2;
int m = str1.size();
int n = str2.size();
vector<vector<int>> dp(m+1 , vector<int>(n+1 , 0));
for(int i=0 ; i<= m ; i++)
dp[i][0] = i;
for(int j=0 ; j<= n ; j++)
dp[0][j] = j;
for(int i=1 ; i<= m ; i++)
{
for(int j=1 ; j<= n ; j++)
{
if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = min( dp[i-1][j-1] + 1 , min( dp[i-1][j] + 1 , dp[i][j-1] + 1 ));
}
}
cout<<dp[m][n];
}
// 64 位输出请用 printf("%lld")
HJ53 杨辉三角的变形
描述
以上三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数、左上角数和右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。
求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3，输入2则输出-1。
数据范围： 1≤n≤10 9
输入描述：
输入一个int整数
输出描述：
输出返回的int值
示例
代码解析
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin>>N;
if(N==0 || N==1 || N==2) cout<<"-1";
else if(N%4 == 0) cout<<"3";
else if(N%4 == 1) cout<<"2";
else if(N%4 == 2) cout<<"4";
else cout<<"2";
}
// 64 位输出请用 printf("%lld")
HJ55 挑7
描述
输出 1到n之间 的与 7 有关数字的个数。
一个数与7有关是指这个数是 7 的倍数，或者是包含 7 的数字（如 17 ，27 ，37 … 70 ，71 ，72 ，73…）
数据范围： 1≤n≤30000
输入描述：
一个正整数 n 。( n 不大于 30000 )
输出描述：
一个整数，表示1到n之间的与7有关的数字个数。
示例
代码解析
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin>>n;
int flag = 0;
for(int i=1 ; i <= n ; i++)
{
if( i%7 == 0) flag++;
else
{
string tmp = to_string(i);
if(tmp.find('7') != -1) flag++;
};
}
cout<<flag;
}
// 64 位输出请用 printf("%lld")
![洛谷_P1014 [NOIP1999 普及组] Cantor 表_python写法](https://img-blog.csdnimg.cn/direct/bb9e829731a446c0be4cabaae92419eb.png)
