【Review】编程之法—面试和算法心得 第一章
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【Review】编程之法—面试和算法心得 第一章，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4698字，纯文字阅读大概需要7分钟。
内容图文
第一章 字符串
1.1 字符串的旋转
- 三步反转
| 左 | 右 |
|---|---|
| abc | def |
| cba | fed |
最后defabc，每一部分反转通过两端字母交换，向中心靠拢的方式实现。
- 实现I am a student. -> student. a am I
- 方法1 反转
#include<bits/stdc++.h>
using namespace std;
char a[100];
void Reverse(int i,int j){
while(i<j){
swap(a[i],a[j]);
i++;
j--;
}
}
int main(){
cin.getline(a,100);
int len=strlen(a);
int l=0,r=0;
for(int i=0;i<len;i++){
if(a[i+1]==' '||a[i+1]=='\0'){
r=i;
Reverse(l,r);
l=r+2;
if(l>len-1)
break;
}
}
for(int i=len-1;i>=0;i--){
cout<<a[i];
}
return 0;
}
- 方法2 strtok函数
#include<bits/stdc++.h>
using namespace std;
vector<string> temp;
char a[100];
int main(){
cin.getline(a,100);
char *t0=strtok(a," ");
if(t0!=NULL){
string tString(t0);
temp.push_back(t0);
}
while(t0!=NULL){
t0=strtok(NULL," ");
if(t0==NULL)
break;
string t(t0);
temp.push_back(t);
}
for(vector<string>::iterator it=temp.end()-1;it!=temp.begin();it--){
cout<<*it<<" ";
}
if(temp.size()>0)
cout<<temp[0];
return 0;
}
1.2 字符串的包含
a字符串包含b的全部字符
计算Hash，每一位表示一个字母，用整数代表散列表，大小写可以分成两个int计算。
#include<bits/stdc++.h>
using namespace std;
char a[100],b[100];
void getInt(char* a,int&aMin,int &aMax){
int aLen=strlen(a);
for(int i=0;i<aLen;i++){
if(a[i]>='a'&&a[i]<='z'){
aMin|=1<<(a[i]-'a');
}
else{
aMax|=1<<(a[i]-'A');
}
}
}
int main(){
scanf("%s%s",a,b);
int aMin=0,aMax=0;
int bMin=0,bMax=0;
getInt(a,aMin,aMax);
getInt(b,bMin,bMax);
if((aMin&bMin)==bMin &&(aMax&bMax)==bMax){
cout<<"b in a";
}
else cout<<"b isn't in a";
return 0;
}
1.3 字符串的全排列
字典序全排列
- 递归
#include<bits/stdc++.h>
using namespace std;
char Input[100];
bool chose[100];
vector<char> out;
void Cal(){
if(out.size()==strlen(Input)){
for(int i=0;i<out.size();i++){
cout<<out[i];
}
cout<<endl;
return ;
}
for(int i=0;i<strlen(Input);i++){
if(chose[i]==false){
out.push_back(Input[i]);
chose[i]=true;
Cal();
out.pop_back();
chose[i]=false;
}
}
}
int main(){
cin>>Input;
sort(Input,Input+strlen(Input));
for(int i=0;i<strlen(Input);i++){
chose[i]=false;
}
Cal();
return 0;
}
- 使用next_permutation
头文件 algorithm
#include<bits/stdc++.h>
using namespace std;
char a[100];
int main(){
while(scanf("%s",a)!=EOF) {
for(int i=0;i<strlen(a);i++){
cout<<a[i];
}
cout<<endl;
while(next_permutation(a,a+strlen(a))){
for(int i=0;i<strlen(a);i++){
cout<<a[i];
}
cout<<endl;
}
cout<<endl;
}
return 0;
}
- next_permutation 实现
从右向左，第一个不满足升序的为i，i与其右面从右向左第一个比它大的元素交换，之后把i+1到n-1的元素倒序
#include<bits/stdc++.h>
using namespace std;
char a[100];
bool NextPermutation(char a[]){
int i;
for(i=strlen(a)-1;i>0;i--){
if(a[i-1]<a[i]){
i=i-1;
break;
}
}
if(i==0&&a[0]>a[1])
return false;
int j;
for( j=strlen(a)-1;j>=i;j--){
if(a[j]>a[i]){
break;
}
}
if(i<j){
//cout<<a[i]<<" "<<a[j]<<endl;
swap(a[i],a[j]);
}
else
return false;
int l=i+1,r=strlen(a)-1;
while(l<r){
swap(a[l],a[r]);
l++;r--;
}
return true;
}
int main(){
while(scanf("%s",a)!=EOF) {
for(int i=0;i<strlen(a);i++){
cout<<a[i];
}
cout<<endl;
while( NextPermutation(a)){
for(int i=0;i<strlen(a);i++){
cout<<a[i];
}
cout<<endl;
}
cout<<endl;
}
return 0;
}
- 有重复的全排列
http://codeup.cn/problem.php?id=2903- 数字版
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int main(){
int n;
while(cin>>n){
int cnt=0;
while(1){
if(cnt==(int)pow(n,n))
break;
for(int j=1;j<=n;j++){
cout<<(cnt/(int)pow(n,n-j))%n+1;
}
cout<<endl;
cnt++;
}
}
return 0;
}
- 字母版
#include<bits/stdc++.h>
using namespace std;
int main(){
char a[100];
while(cin>>a){
int cnt=0;
int n=strlen(a);
while(1){
if(cnt==(int)pow(n,n))
break;
for(int j=1;j<=n;j++){
cout<<a[(cnt/(int)pow(n,n-j))%n];
}
cout<<endl;
cnt++;
}
}
return 0;
}
1.4 字符串转换成整数
注意用long long，如果用int考虑n*10的时候可能已经发生溢出错误
1.5 回文判断
两头往中间扫
1.6 最长回文子串
- 动态规划
bool dp[i][j]表示从i->j的串是否为回文
题目
#include<bits/stdc++.h>
using namespace std;
char input[5010];
int pos[5010];
bool dp[5010][5010];
string toBig(char *a){
char temp[5010];
int tempInt=0;
int cnt=0;
for(int i=0;a[i]!='\0';i++){
if(a[i]>='a'&&a[i]<='z'||a[i]>='A'&&a[i]<='Z'){
pos[tempInt]=cnt;
temp[tempInt++]=a[i];
}
else{
pos[i]=i;
cnt++;
}
}
temp[tempInt]='\0';
string re(temp);
transform( re.begin(),re.end(),re.begin(),::toupper );
return re;
}
void get(string a,int &l,int &r){
int MaxL=1;
for(int i=0;i<a.length();i++){
dp[i][i]=1;
}
for(int i=1;i<a.length();i++){
if(a[i-1]==a[i]){
dp[i-1][i]=1;
if(MaxL<2){
MaxL=2;
l=i-1;
r=i;
}
}
}
for(int L=3;L<=a.length();L++){
//左端点为i时，右端点为i+L-1
//cout<<L;
for(int i=0;(i+L-1)<a.length();i++){
if(a[i]==a[i+L-1]){
dp[i][i+L-1]=dp[i+1][i+L-2];
if(dp[i][i+L-1]==1){
if(L>MaxL){
MaxL=L;
l=i;
r=i+L-1;
}
}
}
else{
dp[i][i+L-1]=0;
}
}
}
return ;
}
void rcv(int &l,int &r){
l=l+pos[l];
r=r+pos[r];
}
int main(){
while(gets(input)!=NULL){
string a=toBig(input);
int l=5010,r=5010;
get(a,l,r);
rcv(l,r);
for(int i=l;i<=r;i++)
cout<<input[i];
cout<<endl;
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的【Review】编程之法—面试和算法心得 第一章全部内容，希望文章能够帮你解决【Review】编程之法—面试和算法心得 第一章所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】