目录
Day46-学习内容：
1.剑指Offer
面试题22：链表中倒数第k个节点
面试题23：链表中环的入口节点
2.Leetcode
例1:链表的中间节点
3.华为机试题
例1:单词倒排
例2:字符串加解密
例3:字符串合并处理
1.剑指Offer
面试题22：链表中倒数第k个节点
题目描述：输入一个链表，输出该链表中倒数第k个结点。
思路：两个指针
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if(pListHead==nullptr||k==0){ return nullptr; } ListNode* pFront=pListHead; int i=0; for(;i<k-1;i++){ if(pFront->next==nullptr){ return nullptr; } pFront=pFront->next; } ListNode* pbehind=pListHead; while(pFront->next!=nullptr){ pFront=pFront->next; pbehind=pbehind->next; } return pbehind; } };
面试题23：链表中环的入口节点
题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路：
1、设置快慢指针，假如有环，他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { if(pHead==nullptr||(pHead!=nullptr&&pHead->next==nullptr)){ return nullptr; } ListNode* pFast=pHead; ListNode* pSlow=pHead; while(pFast!=nullptr&&pFast->next!=nullptr){ pFast=pFast->next->next; pSlow=pSlow->next; if(pFast==pSlow){ break; } } if(pFast==nullptr||pFast->next==nullptr){ return nullptr; } pFast=pHead; while(pFast!=pSlow){ pFast=pFast->next; pSlow=pSlow->next; } return pFast; } };
2.Leetcode
例1:链表的中间节点
题目描述：
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
提示：
- 给定链表的结点数介于
1和100之间。
思路：快慢指针
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution { public: ListNode* middleNode(ListNode* head) { if(head==nullptr){ return nullptr; } ListNode* pFast=head; ListNode* pSlow=head; while(pFast!=nullptr&&pFast->next!=nullptr){ pFast=pFast->next->next; pSlow=pSlow->next; } return pSlow; } };
3.华为机试题
例1:单词倒排
题目描述：
对字符串中的所有单词进行倒排。
说明：
1、每个单词是以26个大写或小写英文字母构成；
2、非构成单词的字符均视为单词间隔符；
3、要求倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；
4、每个单词最长20个字母；
输入描述:
输入一行以空格来分隔的句子
输出描述:
1输出句子的逆序
示例1
输入
1I am a student
输出
1student a am I
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32不通过！！ #include <iostream> #include <string> using namespace std; int main(){ string str; while(getline(cin,str)){ int len=str.length(); string res; int i=len-1; while(str[i]==' '){ i--; } string tmp=""; for(;i>=0;i--){ if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')){ tmp=str[i]+tmp; } else{ res+=tmp; res+=' '; tmp.clear(); } } res+=tmp; cout << res << endl; } return 0; }
您的代码已保存
格式错误:您的程序输出的格式不符合要求（比如空格和换行与要求不一致）
case通过率为90.00%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#include <iostream> #include <string> #include <vector> using namespace std; int main(){ string str; while(getline(cin,str)){ int len=str.length(); vector<string> res; res.clear(); string tmp=""; for(int i=0;i<len;i++){ if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')){ tmp+=str[i]; } else{ if(tmp.size()>0){ res.push_back(tmp); tmp.clear(); } } } if(tmp.size()>0){ res.push_back(tmp); } for(int i=res.size()-1;i>0;i--){ cout<< res[i] << ' '; } cout << res[0] << endl; } return 0; }
注意输入输出的格式和首个字符串为空的情况！！
解析：
质数（prime number）又称素数，有无限个。
质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
例2:字符串加解密
题目描述：
1、对输入的字符串进行加解密，并输出。
2加密方法为：
当内容是英文字母时则用该英文字母的后一个字母替换，同时字母变换大小写,如字母a时则替换为B；字母Z时则替换为a；
当内容是数字时则把该数字加1，如0替换1，1替换2，9替换0；
其他字符不做变化。
3、解密方法为加密的逆过程。
接口描述：
实现接口，每个接口实现1个基本操作：
void Encrypt (char aucPassword[], char aucResult[])：在该函数中实现字符串加密并输出
说明：
1、字符串以结尾。
2、字符串最长100个字符。
int unEncrypt (char result[], char password[])：在该函数中实现字符串解密并输出
说明：
1、字符串以结尾。
2、字符串最长100个字符。
输入描述:
输入说明
输入一串要加密的密码
输入一串加过密的密码
输出描述:
1
2
3输出说明 输出加密后的字符 输出解密后的字符
示例1
输入
abcdefg BCDEFGH
输出
1
2BCDEFGH abcdefg
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63//直接在原字符串上变换 #include <iostream> #include <string> using namespace std; void Encrypt(string str){ for(int i=0;i<str.size();i++){ if(str[i]>='a'&&str[i]<'z'){ str[i]=str[i]-'a'+'A'+1; } else if(str[i]=='z'){ str[i]='A'; } else if(str[i]>='A'&&str[i]<'Z'){ str[i]=str[i]-'A'+'a'+1; } else if(str[i]=='Z'){ str[i]='a'; } else if(str[i]>='0'&&str[i]<'9'){ str[i]=str[i]+1; } else if(str[i]=='9'){ str[i]='0'; } } cout << str << endl; } void unEncrypt(string str){ for(int i=0;i<str.size();i++){ if(str[i]>'a'&&str[i]<='z'){ str[i]=str[i]-'a'+'A'-1; } else if(str[i]=='a'){ str[i]='Z'; } else if(str[i]>'A'&&str[i]<='Z'){ str[i]=str[i]-'A'+'a'-1; } else if(str[i]=='A'){ str[i]='z'; } else if(str[i]>'0'&&str[i]<='9'){ str[i]=str[i]-1; } else if(str[i]=='0'){ str[i]='9'; } } cout << str << endl; } int main(){ string str1,str2; while(cin>>str1>>str2){ Encrypt(str1); unEncrypt(str2); } return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#include<iostream> #include<string> using namespace std; void Enpt(string s){ for(int i=0;i<s.size();i++){ if(s[i] >='a' && s[i]<='z'){ s[i] = (s[i]-'a'+1)%26+'A'; } else if(s[i]>='A' && s[i]<='Z'){ s[i] =(s[i]-'A'+1)%26+'a'; } else if(s[i]>='0' && s[i]<='9'){ s[i]= (s[i]-'0'+1)%10+'0'; } } cout<<s<<endl; } void unEnpt(string s){ for(int i=0;i<s.size();i++){ if(s[i] >='a' && s[i]<='z'){ s[i] = (s[i]-'a'+25)%26+'A'; } else if(s[i]>='A' && s[i]<='Z'){ s[i] =(s[i]-'A'+25)%26+'a'; } else if(s[i]>='0' && s[i]<='9'){ s[i]= (s[i]-'0'+9)%10+'0'; } } cout<<s<<endl; } int main(){ string s1,s2; while(cin>>s1){ cin>>s2; Enpt(s1); unEnpt(s2); } return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#include<iostream> #include<string> #include<algorithm> using namespace std; const string helper1 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; const string helper2 = "BCDEFGHIJKLMNOPQRSTUVWXYZAbcdefghijklmnopqrstuvwxyza1234567890"; void Encrypt(string str){ string res; for (int i = 0; i < str.size(); i++) { res += helper2[helper1.find(str[i])]; } cout << res << endl; } void unEncrypt(string str){ string res; for (int i = 0; i < str.size(); i++) { res += helper1[helper2.find(str[i])]; } cout << res << endl; } int main(){ string str1, str2; while(getline(cin, str1)){ getline(cin, str2); Encrypt(str1); unEncrypt(str2); } return 0; }
收获：
1.可以直接对原有字符串变换，或是通过string res(str.size(),'')初始化一个新的字符串保存结果
2.if ...else if 可以没有else
3.学习
加密：
if(s[i] >='a' && s[i]<='z'){
s[i] = (s[i]-'a'+1)%26+'A';
}
else if(s[i]>='A' && s[i]<='Z'){
s[i] =(s[i]-'A'+1)%26+'a';
}
else if(s[i]>='0' && s[i]<='9'){
s[i]= (s[i]-'0'+1)%10+'0';
}解密：
if(s[i] >='a' && s[i]<='z'){
s[i] = (s[i]-'a'+25)%26+'A';
}
else if(s[i]>='A' && s[i]<='Z'){
s[i] =(s[i]-'A'+25)%26+'a';
}
else if(s[i]>='0' && s[i]<='9'){
s[i]= (s[i]-'0'+9)%10+'0';
}
例3:字符串合并处理
题目描述：
按照指定规则对输入的字符串进行处理。
详细描述：
将输入的两个字符串合并。
对合并后的字符串进行排序，要求为：下标为奇数的字符和下标为偶数的字符分别从小到大排序。这里的下标意思是字符在字符串中的位置。
对排序后的字符串进行操作，如果字符为‘0’——‘9’或者‘A’——‘F’或者‘a’——‘f’，则对他们所代表的16进制的数进行BIT倒序的操作，并转换为相应的大写字符。如字符为‘4’，为0100b，则翻转后为0010b，也就是2。转换后的字符为‘2’； 如字符为‘7’，为0111b，则翻转后为1110b，也就是e。转换后的字符为大写‘E’。
举例：输入str1为"dec"，str2为"fab"，合并为“decfab”，分别对“dca”和“efb”进行排序，排序后为“abcedf”，转换后为“5D37BF”
接口设计及说明：
/*
功能:字符串处理
输入:两个字符串,需要异常处理
输出:合并处理后的字符串，具体要求参考文档
返回:无
*/
void ProcessString(char* str1,char *str2,char * strOutput)
{
}
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#include <iostream> #include <string> #include <algorithm> using namespace std; const string helper1="0123456789abcdefABCDEF"; const string helper2="084C2A6E195D3B7F5D3B7F"; int main(){ string str1,str2; while(cin>>str1>>str2){ string s,s1,s2; s=str1+str2; int len=s.size(); for(int i=0;i<len;i++){ if(i%2==0){ s1+=s[i]; } else{ s2+=s[i]; } } sort(s1.begin(),s1.end()); sort(s2.begin(),s2.end()); s.clear(); //记住一定要清空 for(int i=0,j=0,k=0;i<len;i++){ if(i%2==0){ s+=s1[j++]; } else{ s+=s2[k++]; } } for(int i=0;i<len;i++){ int n=helper1.find(s[i]); if(n!=-1){ s[i]=helper2[n]; } } cout << s << endl; } return 0; }
最后
以上就是结实蜜粉最近收集整理的关于编程之旅-Day46目录的全部内容，更多相关编程之旅-Day46目录内容请搜索靠谱客的其他文章。
发表评论 取消回复