[编程题]首个重复字符
• 热度指数：40868 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

"qywyer23tdd",11

classFirstRepeat {
public:
charfindFirstRepeat(string A, intn) {
bool times[256] = {0};
if(A.size()==0|| n==0)
return0;
for(inti=0;i<n;i++) {
if(!times[A[i]])
times[A[i]] = 1;
else
returnA[i];
}
}
};

class FirstRepeat {
public:
char findFirstRepeat(string A, int n) {
// write code here
bool times[256] ={0};
if(A.size() == 0 || n ==0)
return 0;
int i;
for( i = 0 ;i<n;i++)
{
if(!times[A[i]])
times[A[i]] = 1;
else
break;
}
return A[i];
}
};

python解法

def findFirstRepeat(self, A, n):
chars=[]
for i in A:
if i not in chars:
chars.append(i)
else:
return i

① HashMap
② HashSet
③ 数组Hash

package nowcoder.codingPro;

import java.util.HashMap;
import java.util.HashSet;

public class 去哪儿_首个重复字符 {

/**
*
*
* HashMap解
*
* @param A
* @param n
* @return
*/
public char findFirstRepeat_1(String A, int n) {

HashMap<Character, Integer> hm = new HashMap<Character, Integer>();

char[] charArray = A.toCharArray();

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

if (hm.get(charArray[i]) == null) {
hm.put(charArray[i], 1);
} else {
return charArray[i];
}
}

return '\n';
}

/**
*
* HashSet解
*
* @param A
* @param n
* @return
*/
public char findFirstRepeat_2(String A, int n) {

HashSet<Character> hm = new HashSet<Character>();

char[] charArray = A.toCharArray();

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

} else {
return charArray[i];
}
}
return '\n';
}

/**
*
* 数组模拟hash 高效解法
*
* @param A
* @param n
* @return
*/
public char findFirstRepeat_3(String A, int n) {

char[] charArray = A.toCharArray();
int[] hashChar = new int[256]; // ASCII 范围

for (int i=0; i<charArray.length; i++) {
if (hashChar[charArray[i] - '0'] == 0) {
hashChar[charArray[i] - '0'] = 1;
} else {
return charArray[i];
}
}
return '\n';
}
}

publicclassFirstRepeat {
publiccharfindFirstRepeat(String A, intn) {
HashSet hs=newHashSet();
intlength=A.length();
char[] a=A.toCharArray();
for(inti=0;i<length;i++)
{
if(b==false)
{
returna[i];
}
}
return'0';
// write code here
}
}

0000000010000000

1. 判断c重复方法如下：
( (1<<col) & cset[row] ) ! = 0当且仅当A[i ]重复
2. 置位方法如下：
cset[row] |= (1<<col);

class FirstRepeat {
public:
char findFirstRepeat(string A, int n) {
int cset[8] = {0};	//32 * 8
for (int i = 0;i < n; ++i)
{
int row = A[i] / 32, col = A[i] % 32;
if (((1<<col) & cset[row]) != 0) return A[i];
else cset[row] |= (1<<col);	//turn-on bit
}
return '\0';	//not exists
}
};

int arr[256];
memset(arr, 0, sizeof(arr));
for(int i=0;i<n;i++){
arr[(int) A[i]] += 1;
if(arr[(int)A[i]] > 1)
return A[i];
return 'a';
}

import java.util.*;

public class FirstRepeat {
public char findFirstRepeat(String A, int n) {
HashSet<Character> set = new HashSet<>();
char[] ch = A.toCharArray();
for(char c : ch) {
if(!set.contains(c)) {
} else {
return c;
}
}
return '\0';
}
}

public char findFirstRepeat(String A, int n) {
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(A.charAt(i)==A.charAt(j)) return A.charAt(i);
}
}
return '!';
}

#include<unordered_set>
class FirstRepeat {
public:
char findFirstRepeat(string A, int n)
{
unordered_set<char> hs;
for(auto& c:A)
{
if(hs.find(c) != hs.end()) return c;
hs.emplace(c);
}

return ' ';
}
};

/*C/C++不支持数组整体赋值，可以在声明数组时整体初始化。

class FirstRepeat {
public:
char findFirstRepeat(string A, int n) {
int a[256] = {0};
int i;
if( n==0 || A.size() == 0 ){
return 0;
}
else{
for(i=0;i<n;i++){
if( !a[ A[i] ] )
a[ A[i] ] = 1;
else
break;
}
}
return A[i];
}
};
//遍历原数组，新建数组存储不重复元素
class FirstRepeat {
public:
char findFirstRepeat(string A, int n) {
char a[500];
int i,j,x=0,z=0;
for(i=0;i<n;i++){
for(j=0;j<x;j++){
if(a[j] == A[i]){
z = 1;
break;
}
}
if(z == 1)
break;
if(j == x)
a[x++] = A[i];
}
return A[i];
}
};

//使用set，依次压入元素，来判断第一个在set中出现的字符，符合题意
char findFirstRepeat(string A, int n) {
// write code here
set<char> chset;
int i;
for(i=0; i<n; ++i){
if(chset.find(A[i]) == chset.end())
chset.insert(A[i]);
else
break;
}
return A[i];
}
//第一次没看清题意，返回的是字符串中最前面的重复字符，如abba，返回了a，不合题意
char findFirstRepeat(string A, int n) {
// write code here
int i;
string::size_type idx = 0;
for(i=0; i<n-1; ++i){
string tmp = A.substr(i, 1);
if((idx = A.find_first_of(tmp, i+1)) != string::npos)
break;
}
return A[idx];
}

count则是判断list的大小，字符不重复，那么count就等于list长度；否则即为第一个重复的字符。
importjava.util.*;

publicclassFirstRepeat {
publiccharfindFirstRepeat(String A, intn) {
// write code here
charc=0;
List<Character> list = newArrayList<Character>();
for(inti = 1; i < n;i++)

{
intcount =0;
for(intj = 0; j < list.size() ; j++)

{
if(A.charAt(i) != list.get(j)) count++;
}
if(count == list.size())
{
}
else
{
c = A.charAt(i);break;
}
}
returnc;
}
}

#include <iostream>
using namespace std ;

class FirstRepeat{
public:
char find_first_repeat(char *s,int n){
int hash[500] = {0} ;
if(s == NULL || n == 0){
return 0;
}
int i ;
for(i=0;i<n;i++){
if(hash[s[i]] != 0){
return s[i];
}else{
hash[s[i]] = 1 ;
}
}
return s[i] ;
}

};

int main(){
FirstRepeat *firstrepeat = new FirstRepeat() ;
char *s = "qywyer23tdd" ;
char c = firstrepeat->find_first_repeat(s,11) ;
cout<<c<<endl ;
return 0 ;
}

/*解题思路：利用hash的方式，遍历字符串，若该字符出现

char findFirstRepeat(string A, int n)
{
int flag[128] = {0};
for(int i = 0; i < n; i++)
{
flag[A[i]]++;
if(flag[A[i]] > 1)
returnA[i];
}
}

char Findfirstrepeat(string A,int n)
{
map <char,int>has;
pair<map<char,int>::iterator,bool> Insert;
char c;
for(int i=0;i<n;i++)
{
c=A[i];
Insert=has.insert(pair<char,int>(c,1));
if(Insert.second==0)return c;
}
}

class FirstRepeat {
public:
char findFirstRepeat(string A, int n) {
string q="";
for(int i=1;i<n;++i){
q=A.substr(0,i);
for(int j=0;j<q.length();++j){
if(A[i]==q[j])
return A[i];
}
}
// write code here
}
};

//数组记录出现的次数；
import java.util.*;
public class FirstRepeat {
public char findFirstRepeat(String A, int n) {
int [] str = new int[128];
for(int i=0;i<n;i++){
if(str[A.charAt(i)]==1){
return A.charAt(i);
}
str[A.charAt(i)]++;
}
return '0';
}
}

class FirstRepeat {
public:
char findFirstRepeat(string A, int n) {
// write code here
set<char> note;
char result;
for(int i=0;i<n;i++)
{
if(note.find(A[i])!=note.end())
{
result=A[i];
break;
}
else
note.insert(A[i]);
}
return result;
}
};

class FirstRepeat {
public:
char findFirstRepeat(string A, int n) {
bool count[256];
memset(count,false,sizeof(count));
if(A.size()==0 || n==0)
return 0;
int k;
for(k=0;k<n;k++)
{
if(!count[A[k]])
count[A[k]] = 1;
else
break;         }         return A[k];
}
};

public char findFirstRepeat(String A, int n) {
int[] str = new int[256];
if (n == 0 || A == null){
return 0;
}
for (int i = 0; i < n; i++){
if (str[A.charAt(i)] == 1){
return A.charAt(i);
}else {
str[A.charAt(i)]++;
}
}
return 0;
}

348条回答 41231浏览

# 通过挑战的用户

• 2020-06-02 17:00:48
• 2020-06-02 15:11:26
• 2020-06-01 17:42:14
• 2020-05-31 20:08:13
• 2020-05-30 11:03:27

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题