首页 > 试题广场 >

编程题：给定一个文件每一行是字符串，找出所有的逆序对，比如a

[问答题]

编程题：给定一个文件每一行是字符串，找出所有的逆序对，比如abc和cba是逆序的对。

查看答案及解析

推荐

牛客630575号

#include"iostream"
#include"string"
#define MAX 100
using namespace std;
bool check(string str1,string str2)
{
    bool flag = true;
    for(int i=0; i<str1.length(); i++)
    {
        if(str1[i]!=str2[str1.length()-1-i])
        {
            flag = false;
            return flag;
        }
    }
    return flag;
}
int main(int argc, char* argv[])
{
    string str[MAX];
    int n,a[MAX];
    bool flag[MAX];
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>str[i];
        a[i] = str[i].length();
        flag[i] = true;
    }
    int num = 0;
    for(int i=0; i<n; i++)
    {
        int len = a[i];
        if(flag[i]==true)
        {
            for(int j=0;j<n;j++)
            {
                if(flag[j]==true&&len==a[j])
                {
                    if(check(str[i],str[j]))
                    {
                        num++;
                        flag[i] = false;
                        flag[j] = false;
                        break;
                    }
                }
            }
        }
    }
    for(int i=0; i<n; i++)
        cout<<str[i]<<'\t';
    cout<<endl;
    cout<<"The Number of Matched String Is: "<<num<<endl;
    getchar();
    getchar();
    return 0;
}

编辑于 2015-01-28 14:37:18 回复(3)

流

bool judge(const char *c1,const char *c2,int len)
{
    for(int i=0;i<len;i++)
        if(c1[len-i-1] != c2[i]) return false;
    return true;
}
int get_substr(const char *s,int len)
{
    int count=0;
    for(int i=0;i<len;i++)
        for(int j=1;j<=len;j++){
            for(int k=i+1;k<len;k++)
                if(judge(s+i,s+k,j)){
                    count++;
                    //printf("%s\n",sybstr(s,i,j));
                }
        }
    return count;
}

发表于 2014-12-19 16:08:13 回复(0)

Goats

public int ReverseString(String filename) throws Exception
	{	
		//文件名
		File file=new File(filename);
		//存放读取到的所有word
		String [] str=new String[100];
		//存放单个的长度，便于筛选
		int [] wlen=new int[100];
		//判断有无访问，便于筛选
		boolean [] visited=new boolean[100];
		//存放临时word
		String temp="";
		int i=0;
		int n=0;//计数
		BufferedReader reader=null;
		try {
			reader=new BufferedReader(new FileReader(file));//读取文件
			while((temp=reader.readLine())!=null)
			{
				
				str[i]=temp;
				wlen[i]=temp.length();
				visited[i]=false;
				i++;
				if(i>=100)
				{
					reader.close();
					throw new Exception("Error: Limited Str[] Size!");
				}	
			}
			//数组中数量为i
			for(int j=0;j<i;j++)
			{
				for(int k=j+1;k<i;k++)
				{
					//当且仅当后面未访问且长度相等时比较
					if(visited[k]==false && (str[k].length()==str[j].length()))
					{
						//进行比较
						if(check(str[j].toCharArray(),str[k].toCharArray()))
						{
							visited[j]=true;
							visited[k]=true;
							n++;
						}
					}
				}
			}
			System.out.println("the number is "+n);
			//reader.close();
			//return n;
			
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (Exception e){
			//
			System.out.println(""+e.getMessage());
			e.printStackTrace();
		} finally
		{
			reader.close();
			//return n;
		}
		return n;
		
	}
	
	//判断单个是否为逆序
	boolean check(char [] str1,char [] str2)
	{
		//boolean flag=false;
		int len=str1.length;
		for(int i=0;i<str1.length;i++)
		{
			if(str1[i]!=str2[len-1-i])
			{
				return false;
			}
		}
		return true;
	}

发表于 2016-04-24 16:44:55 回复(0)

OnePiece12138

O(n)的时间复杂度吗，使用存储空间map，类似于寻找两个数的和算法，

public void reverse(){

int n ;//字符的数量

Scanner in = new Scanner(System.in);

n = in.nextInt();

String strs[] = new String[n];

for(int i = 0;i<n;i++){

strs[i] = in.next();

}

int count = 0;

Map<String,Integer>map = new HashMap<String,Integer>();

for(int i = 0;i<n;i++){

if(map.containsKey(strs[i])){

count++;

int index = map.get(strs[i]);

System.out.println(strs[index]+" "+strs[i]);

}else{

String reverse = reverseStr(strs[i]);

map.put(reverse, i);

}

System.out.println(count++);

}

private String reverseStr(String str) {

char[] s= str.toCharArray();

char rever[] = new char[s.length];

for(int i = 0;i<s.length;i++)

rever[i] = s[s.length-1-i];

return new String(rever);

}

发表于 2015-09-13 23:35:27 回复(0)

Trenson

#include <iostream>
#include <string>
using namespace std ;
#define len 3//文件中字符串数量
int main(){
char str[len][100] ;//输入字符串
char str2[len][100] ;
int count=0;
for (int i=0;i<len;i++)
{
cin>>str[i];
}
for(int i=0;i<len;i++)
{
for(int j=i+1;j<len;j++){
if(strlen(str[j])==strlen(str[i])){
int start=0,end=strlen(str[i])-1;
while(str[j][start]==str[i][end]&&end>start){
start++;end--;
}
if(start==end&&str[j][start]==str[i][end]){
strcpy(str2[count],str[i]);
str2[count][strlen(str[i])]='\0';
count++;
strcpy(str2[count],str[j]);
str2[count][strlen(str[j])]='\0';
count++;
}
}
}
}
for(int i=0;i<count;i++)
cout<<str2[i]<<endl;
}

发表于 2014-11-09 11:29:48 回复(1)

码偶渣哈

#include<iostream>

#include<fstream>

#include<string>

#include<cassert>

#include<vector>

#include<map>

using namespace std;

/** read file, return a pointer **/

ifstream readfile(string str){

ifstream infile;

(infile).open(str.data());

assert((infile).is_open());

return infile;

}

///** invert string itself **/

string invert_string(string &str){

int strsize = str.length();

string inverted;

char* str_c = new char[strsize];

for (int i = 0; i < strsize; i++){

inverted.push_back(str[strsize - 1 - i]);

}

return inverted;

}

/* find the inverted string */

vector<pair<int,int>> findinvert(vector<string> &vs){

vector<pair<int, int>> index; //存储逆序的下标

for (int i = 0; i < vs.size(); i++){

string former = vs[i];

for (int j = i + 1; j < vs.size(); j++){

string later_invert;

later_invert = invert_string(vs[j]);//对string进行反转

if (former.size() == later_invert.size()){

if (former.compare(later_invert)==0){

pair<int, int> pair;//将i, j左边保存在pair中

pair.first = i;

pair.second = j;

index.push_back(pair);

}

return index;

}

int main(){

string filename = "a.txt";

string s;

vector<string> bagstring;

ifstream rfile = readfile(filename);

while (getline(rfile, s)){

bagstring.push_back(s);

}

vector<pair<int, int>> inverted = findinvert(bagstring);

rfile.close();

return 0;

}

发表于 2017-08-30 21:31:21 回复(0)

MatthewMatt

大家不觉得推荐答案时间复杂度有点高吗？

发表于 2017-03-15 14:26:27 回复(0)

幸福密码

//给定一个文件每一行都是字符串，找出所有的逆序对，比如abc和cba就是逆序对

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

bool cmp (const string & _pre, const string & _post) {

if (_pre.size () != _post.size()) {

return _pre < _post;

}

else {

return _pre.size() < _post.size();

}

int main () {

string a[] = {"abc", "cba", "333323", "1"};

sort(a, a + 4, cmp);//直接调用库函数

for (int i = 0; i < 4; ++ i) {

string j = "";

for (int k = a[i].size() - 1; k >= 0 ;-- k) {

j.push_back(a[i][k]);//直接调用库函数

}

if (binary_search (a + i + 1, a + 4, j, cmp)) { //直接调用库函数

cout << a[i] << " " << j << std::endl;

}

发表于 2016-09-16 12:08:09 回复(0)

PengSC

我发现你们各有各的理解

发表于 2015-10-10 17:50:06 回复(0)

小菜101

发表于 2015-09-11 17:37:28 回复(0)

树枝

一句话，把字符串反转后和原字符串匹配。

这不就是求最大公共子串么，只不过在寻找最大公共子串的过程中记录下所有的公共子串并打印而已。

发表于 2015-09-11 10:46:54 回复(0)

CodeSheep

void findReverPair( string s ){

	int len = s.length();
	if( len < 2)
		cout << "No ReversePair"<< endl;
	string res;
		
	for( int index=0; index<len-1; ++index ){
	
		int i = index;
		int j = len-1;
		for( ; i<j; --j ){
			
			int tmpj = j;
			while( s[i] != s[tmpj] ){
				--tmpj;
			}
			
			if( tmpj>i ){
				
				int tmpi = i;
				while( s[tmpi]==s[tmpj] ){
					res.push_back( s[tmpi] );
					++tmpi;
					--tmpj;
				}
				cout << res << endl;
				res.clear();
			}
		}
	}
}

发表于 2015-09-01 21:07:17 回复(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
				

				
					46
				

				
					47
				

				
					48
				

				
					49
				

				
					50
				

				
					51
				

			

			
				
				
					
					
						    #include <iostream>
					

					
						    #include <vector>
					

					
						    using namespace std;
					

					
						 
					

					
						    vector<vector<string> > Inversion(vector<string> strs){
					

					
						        vector<vector<string> > result;
					

					
						        vector<string> path;
					

					
						 
					

					
						        intsize = strs.size();
					

					
						        if(size <= 1){
					

					
						            returnresult;
					

					
						        }//if
					

					
						        string str1,str2;
					

					
						        intsize1,size2;
					

					
						        // 第i个字符串和第j个字符串比较
					

					
						        for(inti = 0;i < size;++i){
					

					
						            for(intj = i+1;j < size;++j){
					

					
						                str1 = strs[i];
					

					
						                str2 = strs[j];
					

					
						                size1 = str1.size();
					

					
						                size2 = str2.size();
					

					
						                // 只有两个字符串个数相等才有可能是逆序对
					

					
						                if(size1 == size2){
					

					
						                    intk;
					

					
						                    // 判断str1和str2是否为逆序
					

					
						                    for(k = 0;k <size1;++k){
					

					
						                        // 字符不相同则不是逆序对
					

					
						                        if(str1[k] != str2[size2-k-1]){
					

					
						                            break;
					

					
						                        }//if
					

					
						                    }//for
					

					
						                    // 为逆序
					

					
						                    if(k == size1){
					

					
						                        path.push_back(str1);
					

					
						                        path.push_back(str2);
					

					
						                        result.push_back(path);
					

					
						                        path.clear();
					

					
						                    }//if
					

					
						                }//if
					

					
						            }//for
					

					
						        }//for
					

					
						    }
					

					
						 
					

					
						    intmain(){
					

					
						        vector<string> strs = {"abc","acb","abcd","cba","cab","dcba"};
					

					
						        vector<vector<string> > inver = Inversion(strs);
					

					
						        for(inti = 0;i < inver.size();++i){
					

					
						            cout<<inver[i][0]<<" "<<inver[i][1]<<endl;
					

					
						        }//for
					

					
						        return0;
					

					
						    }

发表于 2015-04-01 20:11:32 回复(0)

墨半成霜

Public void main(String[] args)

File f=new File("c:/input.txt");

String [MAX] strs=new String[MAX];

int count=0;

while (1){

String s= f.readline();

if (s.length==0||s.isEqualToString("")||s.isEqualToString("\eof"))

break;

strs[count]=s;

count++;

}

for (String a in strs){

for (String b in strs){

if (revers(a).isEqualToString(b)){

System.out.println("b是a的逆序对");

}

public String revers(String in){

StringBuffer out=new StringBuffer();

for (int i=in.lengh-1;i>=0;i--){

out.append(in[i]);

}

return out.toString();

}

发表于 2014-12-03 19:12:45 回复(0)

壕

XcXcXcXcXcXc

发表于 2014-12-01 21:55:43 回复(0)

linko解万

从第一行开始，判定此字符串的翻转是否与另一个字符串相等，设定一个int变量用以计算逆序的对数，相等则自加1并结束循环进入下一次循环，不相等则继续比较，直至第一行与所有行判定完。第二次循环从第二行开始，如此类推，最后输出用以储存逆序的对的变量。

发表于 2014-11-12 02:07:28 回复(0)

sroom

1，找出该文件中所有相同的字符，

2，找出上述字符中满足前字符等于后字符的字符，

3，输出字符串，即逆序对，

发表于 2014-11-10 16:12:17 回复(0)

fairyex

String[] input="abc".split(""); boolean is=true; for(i=0;i

发表于 2014-11-05 21:26:03 回复(0)

天狼

hash

发表于 2014-11-05 16:32:28 回复(1)

牛客446259号

// 使用异或操作对字符串s进行逆序
char* Reverse(char* s)
{
char* r = s ;

//令p指向字符串最后一个字符
char* p = s;
while (*(p + 1) != '\0')
++p ;

// 使用异或操作进行交换
while (p > s)
{
*p = *p ^ *s ;
*s = *p ^ *s ;
*p = *p-- ^ *s++ ;
}

return r ;
}

发表于 2014-11-04 13:43:33 回复(1)

黑风

好难,这个不会

发表于 2014-11-04 10:06:58 回复(0)

提交观点

问题信息

字符串百度

来自：百度研发工程师2015...

上传者：Pt3567

难度：

21条回答 86收藏 22867浏览

编程题：给定一个文件每一行是字符串，找出所有的逆序对，比如a

问题信息

热门推荐

相关试题