首页 > 试题广场 >

找位置

[编程题]找位置
  • 热度指数:28764 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
对给定的一个字符串,找出有重复的字符,并给出其位置,如:abcaaAB12ab12 输出:a,1;a,4;a,5;a,10,b,2;b,11,1,8;1,12, 2,9;2,13。

输入描述:
输入包括一个由字母和数字组成的字符串,其长度不超过100。


输出描述:
可能有多组测试数据,对于每组数据,
按照样例输出的格式将字符出现的位置标出。

1、下标从0开始。
2、相同的字母在一行表示出其出现过的位置。
示例1

输入

abcaaAB12ab12

输出

a:0,a:3,a:4,a:9
b:1,b:10
1:7,1:11
2:8,2:12
#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;

int main(){
    string s;
    int len,i, j;
    char cs[100];
    map<char, vector<int> > m; //建立char和出现char的位置间的map
    while(cin>>s){
        len=s.size();
        int idx=0;
        for(i=0; i<len; i++){
            if(m.count(s[i])==0){
                cs[idx++]=s[i];
                m[s[i]] = vector<int>(1, i);
            }else{
                m[s[i]].push_back(i);
            }
        }
        //输出
        for(i=0; i<idx; i++){
            vector<int> vec=m[cs[i]];
            int num=vec.size();
            if(num==1)//个数为0 说明没有重复的
                continue;
            int flag=1;
            for(j=0; j<num; j++){
                if(flag==1){
                    cout<<cs[i]<<":"<<vec[j];
                    flag=0;
                }else{
                    cout<<","<<cs[i]<<":"<<vec[j];
                }
            }
            cout<<endl;
        }
    }
    return 0;
}
发表于 2019-08-25 13:41:27 回复(0)
HashMap保存字符和位置
LinkedHashMap保存字符的顺序
遍历LinkedHashMap,找Map中的value

            HashMap<String, String> map = new HashMap<String, String>();
            LinkedHashMap<String,String> linkedmap = new LinkedHashMap<String,String>();
            for(int i= 0;i<str.length();i++){
                String s = str.charAt(i)+"";
                
                if(map.containsKey(s)){
                    String v = map.get(s);
                    map.remove(s);
                    map.put(s, v+ s+":"+(i)+",");
                }else{
                    map.put(s, s+":"+(i)+",");
                    linkedmap.put(s,"");
                }
            }
            Iterator iter = linkedmap.entrySet().iterator(); 
	    while (iter.hasNext()) { 
		Map.Entry entry = (Map.Entry) iter.next(); 
		Object key = entry.getKey(); 
                String v = map.get(key);
                String[] t = v.split(",");
                if(t.length==1){
                    continue;
                }
                System.out.println(v.substring(0,v.length()-1));
	    } 

发表于 2017-05-21 15:27:44 回复(0)
//java
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        Map<Character, List<Integer>> map = new LinkedHashMap<>();
        for (int i = 0; i < str.length(); i++) {
            List<Integer> list;
            if (!map.containsKey(str.charAt(i))) {
                list = new ArrayList<>();
                list.add(i);
                map.put(str.charAt(i), list);
            } else {
                list = map.get(str.charAt(i));
                list.add(i);
            }
        }
        for (Map.Entry<Character, List<Integer>> entry: map.entrySet()) {
            List<Integer> list = entry.getValue();
            if (list != null && list.size() > 1) {
                for (int i = 0; i < list.size(); i++) {
                    System.out.printf("%c:%d", entry.getKey(), list.get(i));
                    if (i != list.size() - 1) {
                        System.out.print(",");
                    }
                }
                System.out.println();
            }
        }
    }
}


// c++
#include<bits/stdc++.h>
using namespace std;
int main() {
    vector<pair<char, vector<int>>> m;
    string str;
    cin >> str;
    vector<pair<char, vector<int>>>::iterator it;
    for(int i = 0; i < str.length(); i++) {
        for(int j = 0; j < m.size(); j++) {
                // find
            pair<char, vector<int>> p= m[j];
            if(p.first == str[i]) {
                vector<int> v = p.second;
                v.push_back(i);
                p.second = v;
                m[j] = p;
                break;
            }
        }
        // not find
        pair<char, vector<int>> p;
        p.first = str[i];
        vector<int> v;
        v.push_back(i);
        p.second = v;
        m.push_back(p);
    }

    for(int i = 0; i < m.size(); i++) {
        pair<char, vector<int>> p= m[i];
        vector<int> v = p.second;
        if(v.size() > 1) {
            for(int j = 0; j < v.size(); j++) {
                printf("%c:%d", p.first, v[j]);
                if(j != v.size() - 1) {
                    printf(",");
                }
            }
            cout << endl;
        }
    }
    return 0;
}


编辑于 2020-02-20 17:30:35 回复(0)
这个可以用multimap
#include "bits/stdc++.h"
using namespace std;
#pragma warning (disable:4996)
typedef long long int LL;

int main() {
	string str;
	multimap<char, int> mp;
	while (cin >> str) {
		mp.clear();
		int n = str.length();
		for (int i = 0; i < n; i++) {
			mp.insert(pair<char, int>(str[i], i));
		}
		for (int i = 0; i < n; i++) {
			char ch = str[i];
			if (mp.count(ch) > 1) {
				auto mit = mp.equal_range(ch);
				for (auto it = mit.first; it != mit.second; it++) {
					if (it != mit.first) cout << ',';
					cout << ch << ':' << it->second;					
				}
				mp.erase(ch);
				cout << endl;
			}
		}


	}

	return 0;
}
 

发表于 2017-04-29 23:38:35 回复(0)
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
	char str[100] = {};
	char restr[123] = {};
	while (cin >> str)
	{
		int len=strlen(str);
		for (int i=0; i<len; i++)
			restr[int(str[i])] = restr[int(str[i])] + 1;
		for (int i=0; i<len; i++)
		{
			if (int(restr[int(str[i])]) > 1)
			{
				for (int j=i; j<len; j++)
				{
					if (str[i] == str[j])
					{
						cout << str[i] << ":" << j;
						restr[int(str[i])] = restr[int(str[i])] - 1;
						if (int(restr[int(str[i])]) > 0)
							cout << ",";
					}
				}
				cout << endl;
			}
		}
		for (int i=0; i<123; i++)
			restr[i] = 0;
	}
	return 0;
}

发表于 2017-04-27 14:39:06 回复(1)
 import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
    		Scanner scan=new Scanner(System.in);
    		StringBuffer sb = new StringBuffer();
    		int flag;
    		while(scan.hasNext()){
            String str=scan.nextLine(); 
            int[] visited = new int[str.length()]; //已经重复过的就不用输出了
          for(int i=0;i<str.length();i++){
        	  flag = 0;
        	  for(int j=i+1;j<str.length();j++){
        		  if(  visited[j]==0){
        		  if(flag==0 && str.charAt(i) ==str.charAt(j) ){
            			  sb.append(str.charAt(j)+":"+i+","+str.charAt(j)+":"+j);
            			  flag=1;
            			  visited[j]=1;
        		  }else if(str.charAt(i) ==  str.charAt(j) && flag==1){
        			  sb.append(","+str.charAt(j)+":"+j);
        			  visited[j]=1;
        		  }
        	  }
        	  }
        	  if(flag==1){
        		  System.out.println(sb.toString());
        		  sb.setLength(0);//将sb清空
        	  }
          }
        
    }
}
}
发表于 2017-01-18 17:44:16 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    while(cin>>s)
    {
        int visited[101]={0};
        int len=s.length();
        for(int i=0;i<len;++i)
        {
            bool first=true;
            visited[i]=1;
            for(int j=i+1;j<len;++j)
            {
                if(s[j]==s[i]&&visited[j]==0)
                {
                    if(first)
                    {
                        cout<<s[i]<<":"<<i;
                        first=false;
                    }
                    cout<<","<<s[j]<<":"<<j;
                    visited[j]=1;
                }
                
            }
            if(!first)cout<<endl;
        }
    }
    return 0;
}
不用vector
发表于 2021-01-25 10:58:16 回复(0)
有没有大佬帮忙看一下为什么输出"\b "会过不了测试用例吗,在codeblock上跑都没问题的呀
#include <iostream>
using namespace std;

int main(){
    string str;
    cin >> str;
    int length=str.size();
    bool visited[length];
    for(int i=0; i<length; ++i){
        visited[i]=false;
    }
    bool flag=false;
    for(int i=0; i<length; ++i){
        if(!visited[i]){
            flag=false;
            for(int j=i+1; j<length; ++j){
                if(str[i]==str[j]){
                    flag=true;
                    break;
                }
            }
            if(flag){
                cout << str[i] << ":" << i << ",";
                for(int j=i+1; j<length; ++j){
                    if(str[i]==str[j]){
                        cout << str[j] << ":" << j << ",";
                        visited[j]=true;
                    }
                }
                cout << "\b"<<" ";
                cout << endl;
            }
        }
    }
    return 0;
}


发表于 2021-01-15 20:52:03 回复(0)

题目不难,但如何按照要求格式输出确实还是要绕一点弯子的

#include 
#include 
#include      // 因为要是用字符有关函数strlen()
using namespace std;
const int maxN = 100;
char str[maxN];
int flag[maxN];    //使用标记(打印标记)
int main(){
    bool isBlank;    //用于判断是否输出空格
    while(scanf("%s", str) != EOF){
        for(int i = 0; i < strlen(str); i++){
            isBlank = false;    //每个新字母比较的开始, 都置为false
            if(flag[i]) continue;//1、用于判断若该字母在字符串中会重复出现,那么若之前是否已经被查出过之前是否已被   
                                 //2、注意区分break 与 continue, break直接跳出循环,而continue是结束本次循环,开次下次循环
            else{
                for(int j = i+1; j < strlen(str); j++){
                    if(str[i] == str[j]){
                        isBlank = true;     //当有重复出现的字母时,需要输出空格
                        if(!flag[i]) printf("%c:%d", str[i], i);   //是否已经打印过首元,同时控制了何时打印逗号
                        flag[i] = 1;
                        printf(",%c:%d", str[j], j);     
                        flag[j] = 1;      //打印标记(使用标记)
                    }
                }
                if(isBlank) printf("\n");    //打印换行
            }
        }
    }
    return 0;
}
发表于 2021-01-14 17:46:06 回复(0)
//祝我成功!!!
#include<cstring>
(803)#include<vector>
#include<iostream>
(720)#include<unordered_map>
using namespace std;


int main() {
    char c;
    int count=0;
    string keys;
    unordered_map<char, vector<int>> um;
    while(cin>>c) {
        if(um.find(c)==um.end()) keys+=c;
        um[c].emplace_back(count++);
        
    }
    for(char c:keys){
        int size=um[c].size();
        if(size>1) {
            for(int i=0; i<size; ++i) {
                cout<<c<<":"<<um[c][i];
                if(i!=size-1) cout<<',';
                else cout<<'\n';
            }
        }
    }
}

发表于 2020-05-16 21:33:33 回复(0)
用一个长度为128的整型数组a记录字符串出现次数,数组下标对应字符串中字符的ASCII值。
记录完成后,遍历字符串,若字符出现次数大于1,则输出字符串中所有该字符的位置(每输出一次应该将a数组中对应值减1),注意进行输出的格式控制。
#include<string.h>
(845)#include<stdio.h>
#include<stdlib.h>
int main(){
    char s[100];
    int a[128];//对ASCII打表
    memset(a,0,sizeof(a));
    scanf("%s",s);
    //打表
    for(int i=0;s[i]!='\0';i++){
        a[s[i]]++;
    }
    //对字符串每一个字符检测,重复了就进行输出该字符在字符串中的所有位置
    for(int i=0;s[i]!='\0';i++){
        //判断是否重复
        if(a[s[i]]>1){
            char c=s[i];
            //将重复的字符依次输出其位置,注意格式控制
            for(int j=0;s[j]!='\0';j++){
                if(s[j]==c){
                    if(a[s[j]]>1){
                        printf("%c:%d,",s[j],j);
                        a[s[j]]--;
                        continue;
                    }
                    if(a[s[j]]==1){
                        printf("%c:%d\n",s[j],j);
                        a[s[j]]--;
                    }
                }
            }
        }
    }
}

发表于 2020-04-20 22:21:46 回复(0)

C with STL 天下无敌!
#include <bits/stdc++.h>
using namespace std;
int main(){
	string str;
	map<char,int>visited;
	while(cin>>str){
		for(int i=0;i<str.size();i++){
			if(!visited[str[i]]&&count(str.begin(),str.end(),str[i])>1){
				visited[str[i]]=1;
				cout<<str[i]<<":"<<i;
				int j=i;
				while(str.find(str[i],j+1)!=string::npos){
					j=str.find(str[i],j+1);
					cout<<","<<str[i]<<":"<<j;
					
				}
				cout<<endl;
			}
		}
	}
	return 0;
}

发表于 2020-04-13 12:47:05 回复(0)
STLmap的应用,核心就是建立map<char,vector<int> > mmap;
#include<iostream>
(720)#include<map>
#include<vector>
(721)#include<string>
using namespace std;
int main(){
	string s;
	while(getline(cin,s)){
		map<char,int> mp;
		map<char,vector<int> > mmap;
		map<char,int> is_cout;
		int len=s.size();
		for(int i=0;i<len;i++){   //先记录所有字符的次数 
			mp[s[i]]++;
		}
		for(int i=0;i<len;i++){    //遍历字符串,对于所有次数大于1次的字符,令它对应的vector容器加入出现位置,即下标i 
			if(mp[s[i]]>1){
				mmap[s[i]].push_back(i);
			}
		}
		for(int i=0;i<len;i++){
			if(mp[s[i]]>1 && is_cout[s[i]]==0){    //如果次数大于1次并且没有被输出过,那么就输出这个字符对应的vector的所有值,并且令这个字符已输出 
				is_cout[s[i]]=1;
				for(int j=0;j<mmap[s[i]].size();j++){
					cout << s[i] << ":" << mmap[s[i]][j];
					if(j<mmap[s[i]].size()-1) cout << ",";
					else cout << endl;
				}
			}
		}
	}
	return 0;
}

发表于 2020-03-31 20:30:50 回复(0)
Java 解法
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            char[] array = scanner.nextLine().toCharArray();
            LinkedHashMap<Character, ArrayList<Integer>> map = new LinkedHashMap<>();
            for (int i = 0; i < array.length; i++) {
                if (map.get(array[i])==null){
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(i);
                    map.put(array[i],list);
                }else {
                    ArrayList<Integer> list = map.get(array[i]);
                    list.add(i);
                }
            }
            for (Map.Entry<Character, ArrayList<Integer>> entry : map.entrySet()) {
                ArrayList<Integer> value = entry.getValue();
                if (value.size()>1){
                    Character key = entry.getKey();
                    for (int i = 0; i < value.size() - 1; i++) System.out.print(key+":"+value.get(i)+",");
                    System.out.println(key+":"+value.get(value.size()-1));
                }
            }
        }
    }
}


发表于 2020-03-18 10:43:25 回复(0)
#include <stdio.h>
#include <stdlib.h>

int k = 0;
void pri(int flag[], char s[],int i, int  j) {
	if(flag[i] != 1) {
	    if(k != 0)
                printf("\n");
		printf("%c:%d", s[i], i);
		k = 1;
	}
	printf(",%c:%d", s[i], j);
}

int main() {
	char s[100];
	int flag[100] = {0};
	scanf("%s", s);
	int len = strlen(s);
	for(int i = 0; i < len; i++) {
	    if(flag[i]) continue;
	    for(int j = i+1; j < len; j++) {
		if(s[i] == s[j]) {
		    pri(flag, s, i, j);
		    flag[i] = 1;
		    flag[j] = 1;      
			}
		}
	}
	return 0;
}
编辑于 2020-03-13 17:22:37 回复(0)
//注意最后一个重复的字符输出后面没有',';没有重复的字符不要输出
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
    string str;
    while(cin>>str){
        for(string::size_type i=0;i<str.size();++i){
            char c=str[i];
            if(i==str.find(c)){   //如果没有输出过,就查找并输出
                string::size_type pos=str.find(c);
                if(str.find(c,pos+1)!=string::npos){
                    while((pos=str.find(c,pos))!=string::npos){
                        if(str.find(c,pos+1)==string::npos)     //要到最后一个时改变输出格式
                            cout<<c<<':'<<pos<<endl;
                        else
                            cout<<c<<':'<<pos<<',';
                        ++pos;
                    }
                }
            }
        }
    }
    return 0;
}

编辑于 2020-03-12 15:50:56 回复(0)
//使用哈希表和集合实现
#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;

int main()
{
    string s;
    while (cin >> s)
    {
        map <char, set<int>> m;   //采用{字符:{集合},}形式保存
        set <char> has_printed;       //保存已经输出的字符
        for(int i = 0; i < s.size(); i++)
        {
            m[s[i]].insert(i);
        }
        for (int i = 0; i < s.size(); i++)
        {
            if(has_printed.find(s[i]) == has_printed.end() && m[s[i]].size() != 1)  //若在已经输出的元素集合中没找到字符,则输出字符,并将字符写入到集合中
            {
                for(set <int> :: iterator iter = m[s[i]].begin(); iter != m[s[i]].end(); iter++)
                {
                    if(iter != m[s[i]].begin())
                        cout << ",";
                    cout << s[i] << ":" << *iter;
                }
                has_printed.insert(s[i]);
                cout << endl;
            }
        }
    }
}    

发表于 2020-02-08 13:54:45 回复(0)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 101
int num_letter(char *,char);
int main(){
    char a[N],letter[N];
    int num[N];
    int i=0,j=0;
    while(scanf("%s",a)!=EOF){
    while(a[i]!='\0'){
        if(num_letter(letter,a[i])==0){
            letter[j]=a[i];
            num[j]=num_letter(a,a[i]);
            j++;
        }
        i++;
    }
    letter[j]='\0';
    j=0;
    while(letter[j]!='\0'){
        if(num[j]>1){
            i=0;
            while(num[j]>0){
                if(a[i]==letter[j]){
                    num[j]--;
                    if(num[j]!=0){
                        printf("%c:%d,",a[i],i);
                    }
                    else {
                        printf("%c:%d",a[i],i);
                    }
                }
                i++;
            }
            printf("\n");
        }
        j++;
    }
    }
    return 0;
}
int num_letter(char *a,char b){
    int i=0,j=0;
    while(a[i]!='\0'){
        if(a[i]==b){
            j++;
        }
        i++;
    }
    return j;
}

发表于 2020-01-08 16:34:06 回复(0)
#include<stdio.h>
#include<string.h>

int main(){
    char a[101];
    int b[101];
    int i,j,k;
    int len;
    int flag[101];
    int c;
    memset(flag,0,101);
    scanf("%s",&a);
    len=strlen(a);
    for(i=0;i<len;i++){
        c=0;
        k=0;
        if(flag[i]==1)
                continue;
        for(j=i+1;j<len;j++){
            if(a[i]==a[j]){
                if(c==0)
                    b[0]=i;
                c++;
                k++;
                b[k]=j;
                flag[j]=1;
            }
        }
        if(c!=0){
            for(c=0;c<k;c++)
                printf("%c:%d,",a[i],b[c]);
            printf("%c:%d",a[i],b[k]);
            printf("\n");
        }
    }
    return 0;
}
发表于 2018-06-03 17:55:13 回复(0)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<cstring>
#include<iostream>
using namespace std;


int main()
{
    char a[101];
    int n = 0;
    while (cin >> a) {
        n = strlen(a);
        //b数组按顺序存放字符串中重复出现过的元素
        char b[101];
        int b_size = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] == a[j]) {
                    if (b_size == 0) {
                        b[0] = a[i];
                        b_size++;
                    }
                    else {
                        for (int k = 0; k < b_size; k++) {
                            if (a[i] == b[k]) {
                                break;
                            }
                            if (k == b_size - 1) {
                                b_size++;
                                b[b_size - 1] = a[i];
                            }
                        }
                    }
                }
            }
        }

        for (int k = 0; k <= b_size; k++) {
            int first = 0;
            int second = 0;
            for (int i = 0; i < n; i++) {

                //注意此处顺讯,十分关键
                if (b[k] == a[i] && first != 0) {
                    cout << ',' << b[k] << ':' << i;

                }
                if (b[k] == a[i] && first == 0) {
                    cout << b[k] << ':' << i;
                    first++;
                }
            }
            cout << endl;
        }

        getchar();
        getchar();
        getchar();
        return 0;
    }
}
        

发表于 2018-04-11 11:23:58 回复(1)