phonenum:
使用快速排序 将调整好的标准电话号码与出现次数以字符串形式连接，再直接快速排序。
#include<string>
#include<string.h>
#include <stdlib.h>
using namespace std;
//¿ìËÙÅÅÐòº¯Êý
int partition(string *a,int p,int r){
string temp;
string x=a[r];
int i=p-1;
for(int j=p;j<r;j++){
if(a[j]<x){
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[i+1];
a[i+1]=a[r];
a[r]=temp;
return i+1;
}
void quicksort(string *a,int p,int r){
//Êý×éa£¬Ï±êpµ½Ï±êr
if(p<r){
int q=partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q,r);
}
}
int main(){
int N;
int temp=0;
cout<<"ÇëÊäÈë´ÎÊýN"<<endl;
cin>>N;
string *sta=new string[N];
char arr[100];
for(int i=0;i<N;i++){
temp=0;
cin>>arr;
//¿ªÊ¼ÅжÏ
for(int j=0;j<strlen(arr);j++){
if(temp==3){
sta[i]+='-';
j--;
temp++;
continue;
}
if(arr[j]!='-'){
if(arr[j]=='A'||arr[j]=='B'||arr[j]=='C'){
sta[i]+='2';
temp++;
continue;
}else if(arr[j]=='D'||arr[j]=='E'||arr[j]=='F'){
sta[i]+='3';
temp++;
continue;
}else if(arr[j]=='G'||arr[j]=='H'||arr[j]=='I'){
sta[i]+='4';
temp++;
continue;
}else if(arr[j]=='J'||arr[j]=='K'||arr[j]=='L'){
sta[i]+='5';
temp++;
continue;
}else if(arr[j]=='M'||arr[j]=='N'||arr[j]=='O'){
sta[i]+='6';
temp++;
continue;
}else if(arr[j]=='P'||arr[j]=='R'||arr[j]=='S'){
sta[i]+='7';
temp++;
continue;
}else if(arr[j]=='T'||arr[j]=='U'||arr[j]=='V'){
sta[i]+='8';
temp++;
continue;
}else if(arr[j]=='W'||arr[j]=='X'||arr[j]=='Y'){
sta[i]+='9';
temp++;
continue;
}
else{
//µ±arr[j]ΪÊý×ÖµÄʱºò
sta[i]+=arr[j];
temp++;
continue;
}
}
}
}
int k=0;
int flag=0;
int count[N]={0};
int sum=0;
string *sta1=new string[N];
//±È½Ï
for(int i=0;i<N;i++){
for(k=0;k<sum+1;k++){
flag=0;
for(int j=0;j<8;j++){
if(sta[i][j]!=sta1[k][j]&&k==sum){
flag=1;
break;
}else if(sta[i][j]!=sta1[k][j]){
//²»Í¬È´Ã»Óв鵽×îºó
flag=2;
}
}
if(flag==0){
//Èç¹ûÏàͬ£¬Ôò¼ÆÊý+1
count[k]+=1;
break;
}else if(flag==1){
//Èç¹û²»Í¬£¬Ôò¸´ÖÆ
sta1[k]+=sta[i];
sum++;
break;
}
}
}
//°ÑÊý×éºÍ´ÎÊýºÏ²¢
char num[100];
for(int i=0;i<sum;i++){
itoa(count[i]+1, num, 10);
sta1[i]+=" ";
sta1[i]+=num;
}
quicksort(sta1,0,sum-1);
if(sum==N){
cout<<"No duplicates."<<endl;
}else{
for(int i=0;i<sum;i++){
if(sta1[i][9]!='1')
cout<<sta1[i]<<endl;
}
}
return 0;
}
1.1最短路径
部分编译器不支持动态数组定义，所以需要用
int *node;
node=(int*)malloc(N*sizeof(int));
代码段定义。头文件为#include <stdlib.h>
#include<iostream>
#include <stdlib.h>
using namespace std;
int partition(int *a,int p,int r){
int temp;
int x=a[r];
int i=p-1;
for(int j=p;j<r;j++){
if(a[j]<x){
//ij交换
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[r];
a[r]=a[i+1];
a[i+1]=temp;
return i+1;
}
void quicksort(int *a,int p,int r){
if(p<r){
int q=partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q,r);
}
}
int main(){
int N;
int start;
cin>>N;
cin>>start;
int *node;
node=(int*)malloc(N*sizeof(int));
for(int i=0;i<N;i++){
cin>>node[i];
}
quicksort(node,0,N-1);
if((start-node[0])>(node[N-1]-start)){
if((start-node[1])>(node[N-1]-start)){
cout<<2*node[N-1]-node[1]-start;
}else{
cout<<node[N-1]-2*node[1]+start;
}
}else{
if((start-node[0])>(node[N-2]-start)){
cout<<2*node[N-2]-node[0]-start;
}else{
cout<<node[N-2]-2*node[0]+start;
}
}
return 0;
}
#include <stdlib.h>
using namespace std;
int partition(int *a,int p,int r){
int temp;
int x=a[r];
int i=p-1;
for(int j=p;j<r;j++){
if(a[j]<x){
//ij交换
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[r];
a[r]=a[i+1];
a[i+1]=temp;
return i+1;
}
void quicksort(int *a,int p,int r){
if(p<r){
int q=partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q,r);
}
}
int main(){
int N;
int start;
cin>>N;
cin>>start;
int *node;
node=(int*)malloc(N*sizeof(int));
for(int i=0;i<N;i++){
cin>>node[i];
}
quicksort(node,0,N-1);
if((start-node[0])>(node[N-1]-start)){
if((start-node[1])>(node[N-1]-start)){
cout<<2*node[N-1]-node[1]-start;
}else{
cout<<node[N-1]-2*node[1]+start;
}
}else{
if((start-node[0])>(node[N-2]-start)){
cout<<2*node[N-2]-node[0]-start;
}else{
cout<<node[N-2]-2*node[0]+start;
}
}
return 0;
}