[编程题]找位置
- 热度指数：30408 时间限制：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;
}
#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)
#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;
}
#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;
}
#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)
//希望大佬能帮忙优化，感觉有点浪费内存
#include<iostream>
#include<string>
using namespace std;
int main(){
string str;
cin>>str;
int nums[75][101]={0};
for(int i=0;i<str.length();i++){
nums[(str[i]-48)][0]++;
nums[(str[i]-48)][(nums[(str[i]-48)][0])]=i;
}
for(int i=0;i<str.length();i++){
if(nums[(str[i]-48)][0]>1){
int j=1;
for(;j<nums[(str[i]-48)][0];j++){
cout<<str[i]<<':'<<nums[(str[i]-48)][j]<<',';
}
cout<<str[i]<<':'<<nums[(str[i]-48)][j]<<endl;
nums[(str[i]-48)][0]=0;
}
}
return 0;
}
发表于 2018-03-09 20:35:08
回复(0)
问题信息
难度：
272条回答
320收藏
23717浏览
通过挑战的用户
查看代码-
2023-03-13 19:53:40 -
2023-03-13 17:33:25 -
2023-03-12 22:51:21
-
2023-03-12 16:58:36 -
2023-03-11 21:29:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
