面试题：在字符串内找到所有不重复的字符，如”BWABSDWD”中找出”S”和”A”.考虑时间和空间复杂度。(请用C# 或 Javascript 实现)我写的算法： String.prototype.repeatOpt = function () {
var str = this + "",objStr = "";
for (var i = 0; i < this.length; i++) {
var s = str[i];
var newStr = str.replace(s, '');
var j = newStr.indexOf(s);
if (j == -1) {
objStr += s;
}
}
return objStr;
}
alert("BWABSDWD".repeatOpt()); 虽然这能实现，但觉得不怎么好，大家有什么好方法。。尤其是说明考虑时间和空间复杂度。
var str = this + "",objStr = "";
for (var i = 0; i < this.length; i++) {
var s = str[i];
var newStr = str.replace(s, '');
var j = newStr.indexOf(s);
if (j == -1) {
objStr += s;
}
}
return objStr;
}
alert("BWABSDWD".repeatOpt()); 虽然这能实现，但觉得不怎么好，大家有什么好方法。。尤其是说明考虑时间和空间复杂度。
function searchNoRepeat(str){
var repeat = '',
norepeat = [];
for(var i = 0; i < str.length; i++){
var s = str[i];
if(repeat.indexOf(s) === -1){
last_index = str.lastIndexOf(s);
if( last_index === i){
norepeat.push(s);
}else{
repeat += s;
}
}
}
return norepeat;
}
alert(searchNoRepeat('BWABSDWD'));
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<TITLE> New Document </TITLE>
<META NAME="Generator" CONTENT="EditPlus">
<META NAME="Author" CONTENT="">
<META NAME="Keywords" CONTENT="">
<META NAME="Description" CONTENT="">
<script type="text/javascript">
function norepeat(str){
var newStr="";
while(str.charAt(0)!=""){
var fc=str.charAt(0);
var reg=new RegExp(""+fc,"g");
var sl=str.match(reg);
if(sl.length==1){
newStr+=fc;
}
str=str.replace(reg,"");
}
return newStr;
}
alert(norepeat("BWABSDWD"));
</script>
</HEAD> <BODY>
</BODY>
</HTML>
String.prototype.repeatOpt = function () {
var i=0,str = this,objStr = "";
while(str){
var s = str.charAt(0);
objStr += s;
var re = new RegExp(s,"ig");
str = str.replace(re,"");
}
return objStr;
}
alert("BWABSDWD".repeatOpt()); 这样呢？不用遍历整个字符串了，不知道会不会好些？
{
static void Main(string[] args)
{
string car = "BWABSDWD";
for (int i = 0; i < car.Length; i++)
{
bool fg = false;
for (int j = 0; j < car.Length; j++)
{
if (i != j)
{
if (car[i] == car[j])
{
fg = true;
break;
}
}
}
if (!fg)
{
Console.WriteLine(car[i] + "\r\n");
}
}
Console.ReadLine();
}
}
可能 这样不会满足 LZ的需求了
否则，真是 N的平方。
var ret = [];
for(var i = 0; i < str.length; i++){
var s = str[i],
reg = new RegExp(s + '.*' + s, 'g');
if(!str.match(reg)){
ret.push(s);
}
}
return ret;
}
var result = searchNoRepeat('BWABSDWD');
alert(result);这个会不会好点
var dict = {}, result = [];
s.replace(/(.)(?=.*\1)/g, function(all, c){
dict[c] = true;
});
s.replace(/(.)(?!.*\1)/g, function(all, c){
if (!dict[c]) {
result.push(c);
}
});
return result.join("");
}var data = ["1234123", "abcabcdec", "BWABSDWD"];
var messages = [];
for (var i = 0; i < data.length; i++) {
messages.push(data[i] + ' => ' + calc(data[i]));
}alert(messages.join("\n"));1234123 => 4
abcabcdec => de
BWABSDWD => AS
function calc(s) {
var dict = {}, result = [];
s.replace(/(.)(?=.*\1)/g, function(all, c){
dict[c] = true;
return "";
}).replace(/(.)(?!.*\1)/g, function(all, c){
!dict[c] && result.push(c);
});
return result.join("");
}
var dict = {}, result = [];
这一句，是什么意思？
和这个一样
var dict = {};
var result = [];
这再不明白就得自己多看看书了。
var result = new Array();
var testStr=["123131341414","aaaaaaaaaaaaaaa","abcdefghijklmnopqrspuvwxyz","adsfffffffffffasdfasdfdsafsafdsafasfsafsadfsdfsadfsafsdf"],
tims=1000;
var testWrap=function(fn){
var begin=new Date();
for(var i=0;i<tims;i++){
for(var j=0,len=testStr.length;j<len;j++){
fn(testStr[j]);
}
}
return new Date()-begin;
}function calc(s) {
var dict = {}, result = [];
s.replace(/(.)(?=.*\1)/g, function(all, c){
dict[c] = true;
return "";
}).replace(/(.)(?!.*\1)/g, function(all, c){
!dict[c] && result.push(c);
});
return result.join("");
}function myc(str){
var o={},c,s="";
for(var i=0,len=str.length;i<len;i++){
c=str.charAt(i);
o[c]=(o[c]==undefined?1:0);
}
for(var k in o){
o[k]&&(s+=k);
}
return s;
}console.log("RegExp:"+testWrap(calc));
console.log("Two Traversal:"+testWrap(myc));</script>
这里给你一个找重复的几种方法：http://www.scriptlover.com/static/867-javascript-重复字符
class Program
{
static void Main(string[] args)
{
TimeSpan ts1 = new TimeSpan(DateTime.Now.Ticks); string car = @"123131341414aaaaaaaaaaaaaaaabcdefghijklmnopqrspuvqwerqweasdafdadadfadfacvcadfdadfadfadfad
wxyzadsfffffffffffasdfasdfdsafsafdsafasfsafsadfsdfsadfsafsdfqwerqwerqwerqewrqwerqwerqwerq
ssdfasdfasdffasdfewrwerwerqweraweasdfasdfadfadqewrqwerqwerddadasdfadfadsfewrqwerqwerqwerq
asdfasdfasdfqwerwesdfasdfasdxcvr234123sdfsddddddddddddddddddddddddddddddddddddddddddddddd
dffffffffffffffffffffffffffffffffffffffffffffffffasdfasdfqw3xcvzxcvasdysdfadfasdfadfadf
wrqwerqwerqwerqwerqwerqwerqwer23423qwerqwerqwerasdfasdfasdfasdfasdfasdfadsfasdfasdfadf
333333333333333333333333333333333333333333333333333qwerqwerqwerffffffffffsdfasdfadfasd
444444444442342341234123412341qwerqewrqersafddddddddddddddddddddddddddddddddddddddddddf
1234123412341234123412341qewrqwerqeqwerqwerqwerqerddddddddddddddddddddddddddddddddddddd
14234123wasdfasdfaaaaaaaaaaaaaaaaaaaaaaaaaaqwerqwerqwerqwerqwerqerqerqerqerqerqewrqerqe";
for (int i = 0; i < car.Length; i++)
{
bool fg = false;
for (int j = 0; j < car.Length; j++)
{
if (i != j)
{
if (car[i] == car[j])
{
fg = true;
break;
}
}
}
if (!fg)
{
Console.Write(car[i] );
}
} TimeSpan ts2 = new TimeSpan(DateTime.Now.Ticks); //get current ticks.
string spanTotalSeconds = ts2.Subtract(ts1).Duration().TotalSeconds.ToString(); //计算整个程序的运行时间
//整个程序的运行时间
Console.WriteLine("运行时间:" + spanTotalSeconds);
Console.ReadKey();
}
}
var str ="123131341414aaaaaaaaaaaaaaaabcdefghijklmnopqrspuvqwerqweasdafdadadfadfacvcadfdadfadfadfadwxyzadsfffffffffffasdfasdfdsafsafdsafasfsafsadfsdfsadfsafsdfqwerqwerqwerqewrqwerqwerqwerqssdfasdfasdffasdfewrwerwerqweraweasdfasdfadfadqewrqwerqwerddadasdfadfadsfewrqwerqwerqwerqasdfasdfasdfqwerwesdfasdfasdxcvr234123sdfsddddddddddddddddddddddddddddddddddddddddddddddddffffffffffffffffffffffffffffffffffffffffffffffffasdfasdfqw3xcvzxcvasdysdfadfasdfadfadfwrqwerqwerqwerqwerqwerqwerqwer23423qwerqwerqwerasdfasdfasdfasdfasdfasdfadsfasdfasdfadf333333333333333333333333333333333333333333333333333qwerqwerqwerffffffffffsdfasdfadfasd444444444442342341234123412341qwerqewrqersafddddddddddddddddddddddddddddddddddddddddddf1234123412341234123412341qewrqwerqeqwerqwerqwerqerddddddddddddddddddddddddddddddddddddd14234123wasdfasdfaaaaaaaaaaaaaaaaaaaaaaaaaaqwerqwerqwerqwerqwerqerqerqerqerqerqewrqerqe"
function getNoRepeat(s) {
return s.length? s.split('').sort().join('').replace(/(.)\1+/g, '') : '';
}
alert(getNoRepeat(str));
var re = new RegExp(s,"ig");
这句ig啥意思？
String.prototype.repeatOpt = function() {
var o = {}, len = this.length, ret = [];
for(var i = 0; i < len; i++){
c = this.charAt(i);
if(!o[c]){
o[c] = 1;
}else{
o[c]++;
}
}
for( c in o){
if(o[c] == 1){
ret.push(c);
}
}
return ret.join('');
};
alert("BWABSDWD".repeatOpt());
String.prototype.repeatOpt = function () {
var str = this + "",objStr = "";
for (var i = 0; i < this.length; i++) {
var s = str[i];
var j = str.indexOf(s);
var k = str.indexOf(s,j);
if (k == -1) {
objStr += s;
}
}
return objStr;
}
alert("BWABSDWD".repeatOpt());
String.prototype.repeatOpt = function () {
var str = this + "",objStr = "";
var j = newStr.indexOf(str[0]);
while(j>=0)
{
var s = str[0];
var k = str.indexOf(s,j);
if(k<0)
{
objStr += s;
str.replace(s, '');
}
else
{
str.replace(s, '');
}
j = newStr.indexOf(s);
}
return objStr;
}
alert("BWABSDWD".repeatOpt());
pattern: 正则表达式字符串。
flag: "i"(ignore)、"g"(global)、"m"(multiline)的组合
i-忽略大小写，g-反复检索，m-多行检索
flag中没有g时，返回字符串，有g时返回字符串数组