ysen
- 浏览: 122204 次
- 性别:
- 来自: 北京
-
文章分类
最新评论
-
roychenyi：
<br>1<br>2<br> ...
pager-taglib 使用说明 -
roychenyi：
<br>换行<br>换行<br& ...
pager-taglib 使用说明 -
wangwenfei1985：
[flash=200,200][url][img][list] ...
pager-taglib 使用说明 -
时光后19：
,看到你这样真好，
FileNet调用webService配置 -
ysen：
大sql导入mysql
如果是SQL格式的。有的可能上100 ...
mysqldump备份详解
寻求最佳的算法
1. 编写一个高效率函数来找出一个字符串中第一个无重复字符.例如:”total”中的o,”teeter”中的r.要求算法效率优于O(n2).函数调用模型如下:
Public static Character FirestNoRepeated(String str);
public class firstNoRepit {
public static void main(String[] args) {
String str="dsfdghgshgfjej";
System.out.println(firstNo( str));
}
public static Character firstNo(String str){
Map <Character,Integer> map = new HashMap<Character,Integer>();
for(int i=0; i<str.length();i++){
if(map.containsKey(str.charAt(i))){
map.put(str.charAt(i), 2);
}else{
map.put(str.charAt(i), 1);
}
}
for(int i=0; i<str.length();i++){
if(map.get(str.charAt(i))==1 ){
return str.charAt(i);
}
}
return null;
}
}
分享到：
评论
32 楼
shake822
2010-04-20
dasimm 写道
public static Character getFristChar2(String arg){
for( int i = 0 ; i < arg.length() ; i++){
if(arg.indexOf(String.valueOf(arg.charAt(i))) == arg.lastIndexOf(String.valueOf(arg.charAt(i)))){
return arg.charAt(i);
}
}
return null;
}
以前看的一个帖子的
和我的想法一樣,但是我沒有用String.valueOf(); 而是直接用arg.indexOf(arg.charAt(i)),測試了下這個速度要快點
31 楼
J-catTeam
2010-04-18
sw1982 写道
拿空间换效率咯。。构造Hashset
HashSet和HashMap这里操作过程差不多的
30 楼
sunson468
2010-04-18
好久没有思考这些问题了，呵呵
只是有个想法，不管什么字符总有自己的编码对应的数，用数来指定内存，总比那些campare对象强多了吧，我这个只是抛砖引玉，欢迎大家提意见。
下面给出我想的一个代码，复杂问题简单化，只考虑26个小写字母，自己组装数据，特别开一个独立的单个字符。
只是有个想法，不管什么字符总有自己的编码对应的数，用数来指定内存，总比那些campare对象强多了吧，我这个只是抛砖引玉，欢迎大家提意见。
下面给出我想的一个代码，复杂问题简单化，只考虑26个小写字母，自己组装数据，特别开一个独立的单个字符。
package sample.test.string;
/**
* @author SuNSoN
*
*/
public class FindFirstNoRepeatChar {
/**
* @param inString
* @return
*/
public char findFirst(String inString) {
// 统计
int[] letterIndexs = new int[26];
int index;
for (int i = 0; i < inString.length(); i++) {
index = inString.charAt(i) - 97;
//
if (letterIndexs[index] == 0) {
// 首次遇到过
letterIndexs[index] = i + 1;
} else if (letterIndexs[index] > 0) {
// 再次遇到
letterIndexs[index] = -1;
}
}
// 分析
int retCharInt = -1, minIndex = -1;
for (int j = 0; j < 26; j++) {
// no repeat
if (letterIndexs[j] > 0) {
if (minIndex == -1) {
minIndex = letterIndexs[j];
retCharInt = j;
} else if (minIndex > letterIndexs[j]) {
minIndex = letterIndexs[j];
retCharInt = j;
}
}
}
// 没有找到符合条件的
if (retCharInt == -1) {
System.out.println("the no repeat char is not found.");
return ' ';
}
// 返回
return (char) (retCharInt + 97);
}
/**
* @param n
* @return
*/
static int randomInt(int n) {
return (int) (n * Math.random());
}
/**
* @param longString
*/
static void printStringByStep(String longString, int printStep) {
for (int k = 0; k < longString.length() / printStep; k++) {
System.out.println("[" + longString.substring(k * printStep, (k + 1) * printStep) + "]");
}
//
if (longString.length() % printStep != 0) {
System.out.println("[" + longString.substring((longString.length() / printStep) * printStep, longString.length())
+ "]");
}
}
/**
* @param args
*/
public static void main(String[] args) {
// 设定测试数据量
int testCount = 1000050;
// 组装测试数据
int sigleChar = randomInt(26);
System.out.println("the sigle char is [" + (char) (97 + sigleChar) + "]");
StringBuilder sb = new StringBuilder();
int random = 0;
for (int i = 0; i < testCount; i++) {
do {
random = randomInt(26);
} while (sigleChar == random);
//
sb.append((char) (97 + random));
}
sb.setCharAt(randomInt(testCount), (char) (97 + sigleChar));
// 设定测试字符串
String testString = sb.toString();
// 打印测试字符串
System.out.println("analyze String is:");
printStringByStep(testString, 100);
// 执行分析过程
long oldTime = System.nanoTime();
// 输出分析结果
System.out.println("the first no repeat char is [" + new FindFirstNoRepeatChar().findFirst(testString) + "]");
System.out.print("cost " + (System.nanoTime() - oldTime) + "ns");
}
}
29 楼
laoshifu
2010-04-17
jqs7807151 写道
把我的上面一贴的数组长度稍微修改一下：
public static Character firstNoRepeated(String str){
int[] aa=new int[Character.MAX_VALUE - Character.MIN_VALUE + 100];
for (int i=0; i<str.length();i++) {
int c =str.charAt(i);
aa[c]++;
}
for (int i : aa) {
if(aa[i] ==1){
return (char)i;
}
}
return null;
}
一开始我默认全部是ascii码的字符了
public static Character firstNoRepeated(String str){
int[] aa=new int[Character.MAX_VALUE - Character.MIN_VALUE + 100];
for (int i=0; i<str.length();i++) {
int c =str.charAt(i);
aa[c]++;
}
for (int i : aa) {
if(aa[i] ==1){
return (char)i;
}
}
return null;
}
一开始我默认全部是ascii码的字符了
错了，这样的结果找出来的不一定是字符串中的第一个无重复的，而是所有无重复的字母集中ascll码最前的字符。
28 楼
yhailj
2010-04-17
茶壶和饺子的故事 写道
长度等于2
我说错了. 如果是第一个字符, 则长度是 2 , 但如果是最后一个字符. 则长度是 1
27 楼
szmq2
2010-04-17
用友面试过这道题，应该是用空间换时间的问题，我是这样写的:
public static char checkFirstChar(String str) {
char temp = 0;
int len = str.length();
Set<Character> set1 = new HashSet<Character>();
Set<Character> set2 = new HashSet<Character>();
for (int i = len - 1; i >= 0; i--) {
temp = str.charAt(i);
if (!set1.add(temp)){
// set2用来记录有重复的字符
set2.add(temp);
}
}
for (int i = 0 ; i < len ; i++) {
temp = str.charAt(i);
if (set2.add(temp)){
return temp;
}
}
return ' ';
}
26 楼
angel243fly
2010-04-17
dasimm 写道
public static Character getFristChar2(String arg){
for( int i = 0 ; i < arg.length() ; i++){
if(arg.indexOf(String.valueOf(arg.charAt(i))) == arg.lastIndexOf(String.valueOf(arg.charAt(i)))){
return arg.charAt(i);
}
}
return null;
}
以前看的一个帖子的东西
for( int i = 0 ; i < arg.length() ; i++){
if(arg.indexOf(String.valueOf(arg.charAt(i))) == arg.lastIndexOf(String.valueOf(arg.charAt(i)))){
return arg.charAt(i);
}
}
return null;
}
以前看的一个帖子的东西
这个算法最简单，呵呵。
至于高不高效，只能测试一下了。
25 楼
茶壶和饺子的故事
2010-04-17
abcda
24 楼
茶壶和饺子的故事
2010-04-17
yhailj 写道
chenyulong1 写道
public static Character FirstNoRepeated(String str){
for(int i = 0; i < str.length(); i++){
if(str.split(String.valueOf(str.charAt(i))).length == 2)
return new Character(str.charAt(i));
}
return null;
};长度应该是 < 3 吧, 只是 等于2 貌似不对. 如果刚好是第一个字符或最后一个字符. 则长度只是 1
长度等于2
23 楼
yhailj
2010-04-17
chenyulong1 写道
public static Character FirstNoRepeated(String str){
for(int i = 0; i < str.length(); i++){
if(str.split(String.valueOf(str.charAt(i))).length == 2)
return new Character(str.charAt(i));
}
return null;
};长度应该是 < 3 吧, 只是 等于2 貌似不对. 如果刚好是第一个字符或最后一个字符. 则长度只是 1
22 楼
nornand
2010-04-17
ansjsun 写道
这种东西用数组是最快的了。。而且是超级快。。内存占用也许不必map多，。我这美jdk
public static void main(String args[]){
int c = new int[65535];
String str = "sdfgfhjiow4ueijkldfsa" ;
char[] tempc = str.toCharArray() ;
for(int i=0; i<tempc.length ;i++){
c[tempc[i]]++ ;
}
for(int j=0;j<c.length;c++){
if(c[j]==1){
System.out.println(new Character([j])) ;
}
}
}
public static void main(String args[]){
int c = new int[65535];
String str = "sdfgfhjiow4ueijkldfsa" ;
char[] tempc = str.toCharArray() ;
for(int i=0; i<tempc.length ;i++){
c[tempc[i]]++ ;
}
for(int j=0;j<c.length;c++){
if(c[j]==1){
System.out.println(new Character([j])) ;
}
}
}
确实很快,只是太不java了...
21 楼
ansjsun
2010-04-17
有个想法，如果程序讲效率就不要用java的集合。。
他把基本数据类型都装箱了。对象的创建销毁是很耗费时间的。
他把基本数据类型都装箱了。对象的创建销毁是很耗费时间的。
20 楼
ansjsun
2010-04-17
这种东西用数组是最快的了。。而且是超级快。。内存占用也许不必map多，。我这美jdk
public static void main(String args[]){
int c = new int[65535];
String str = "sdfgfhjiow4ueijkldfsa" ;
char[] tempc = str.toCharArray() ;
for(int i=0; i<tempc.length ;i++){
c[tempc[i]]++ ;
}
for(int j=0;j<c.length;c++){
if(c[j]==1){
System.out.println(new Character([j])) ;
}
}
}
public static void main(String args[]){
int c = new int[65535];
String str = "sdfgfhjiow4ueijkldfsa" ;
char[] tempc = str.toCharArray() ;
for(int i=0; i<tempc.length ;i++){
c[tempc[i]]++ ;
}
for(int j=0;j<c.length;c++){
if(c[j]==1){
System.out.println(new Character([j])) ;
}
}
}
19 楼
lyw985
2010-04-16
jqs7807151 写道
把我的上面一贴的数组长度稍微修改一下：
public static Character firstNoRepeated(String str){
int[] aa=new int[Character.MAX_VALUE - Character.MIN_VALUE + 100];
for (int i=0; i<str.length();i++) {
int c =str.charAt(i);
aa[c]++;
}
for (int i : aa) {
if(aa[i] ==1){
return (char)i;
}
}
return null;
}
一开始我默认全部是ascii码的字符了
public static Character firstNoRepeated(String str){
int[] aa=new int[Character.MAX_VALUE - Character.MIN_VALUE + 100];
for (int i=0; i<str.length();i++) {
int c =str.charAt(i);
aa[c]++;
}
for (int i : aa) {
if(aa[i] ==1){
return (char)i;
}
}
return null;
}
一开始我默认全部是ascii码的字符了
想法不错，但是每次都要初始化一个大约为60000+长度的数组。。。
根据我的估算，大概为250K内存....
18 楼
jqs7807151
2010-04-16
把我的上面一贴的数组长度稍微修改一下：
public static Character firstNoRepeated(String str){
int[] aa=new int[Character.MAX_VALUE - Character.MIN_VALUE + 100];
for (int i=0; i<str.length();i++) {
int c =str.charAt(i);
aa[c]++;
}
for (int i : aa) {
if(aa[i] ==1){
return (char)i;
}
}
return null;
}
一开始我默认全部是ascii码的字符了
public static Character firstNoRepeated(String str){
int[] aa=new int[Character.MAX_VALUE - Character.MIN_VALUE + 100];
for (int i=0; i<str.length();i++) {
int c =str.charAt(i);
aa[c]++;
}
for (int i : aa) {
if(aa[i] ==1){
return (char)i;
}
}
return null;
}
一开始我默认全部是ascii码的字符了
17 楼
jqs7807151
2010-04-16
public static Character firstNoRepeated(String str){
int[] aa=new int[255];
for (int i=0; i<str.length();i++) {
int c =str.charAt(i);
aa[c]++;
}
for (int i : aa) {
if(aa[i] ==1){
return (char)i;
}
}
return null;
}
经过我的测试，我觉得还有比之前出现的效率都要高
int[] aa=new int[255];
for (int i=0; i<str.length();i++) {
int c =str.charAt(i);
aa[c]++;
}
for (int i : aa) {
if(aa[i] ==1){
return (char)i;
}
}
return null;
}
经过我的测试，我觉得还有比之前出现的效率都要高
16 楼
JE帐号
2010-04-16
LZ的就很快了,只不过因为Character到char的装箱卸箱会比较影响性能.
如果不考虑空间问题,倒是有个很耗空间的方法.不过可惜还是有if语句,怎么全用位运算搞定?
另外,现在所有的方法都是不准确的,因为根据String的定义,一个chatAt返回的char不一定是个完整字符,如果是增补字符还需要考虑代理项对 的问题.详细可以去看String类的javaDoc
运算结果:
131069
快
楼主的time use:172
快
time use:0
如果不考虑空间问题,倒是有个很耗空间的方法.不过可惜还是有if语句,怎么全用位运算搞定?
另外,现在所有的方法都是不准确的,因为根据String的定义,一个chatAt返回的char不一定是个完整字符,如果是增补字符还需要考虑代理项对 的问题.详细可以去看String类的javaDoc
import java.util.HashMap;
import java.util.Map;
public class FirstNoRepeated {
public static Character FirestNoRepeated(String str) {
Map <Character,Integer> map = new HashMap<Character,Integer>();
for(int i=0; i<str.length();i++){
if(map.containsKey(str.charAt(i))){
map.put(str.charAt(i), 2);
}else{
map.put(str.charAt(i), 1);
}
}
for(int i=0; i<str.length();i++){
if(map.get(str.charAt(i))==1 ){
return str.charAt(i);
}
}
return null;
}
public static Character FirestNoRepeated2(String str) {
byte[] all = new byte[Character.MAX_VALUE- Character.MIN_VALUE+1];
int len = str.length();
for (int i = 0; i < len; i++) {
if(all[str.charAt(i)]==0){
all[str.charAt(i)]=1;
}else{
all[str.charAt(i)]=(byte) (all[str.charAt(i)]<<1);
}
}
for (int i = 0; i < len; i++) {
if(all[str.charAt(i)]==1) {
return str.charAt(i);
}
}
return null;
}
public static void main(String[] args) {
StringBuilder sb = new StringBuilder(Character.MAX_VALUE - Character.MIN_VALUE + 100);
//构造一个'快'最先出现的是'快'字的数据源
for (int i = Character.MIN_VALUE; i < Character.MAX_VALUE; i++) {
sb.append((char)i);
}
for (int i = Character.MIN_VALUE; i < '快'; i++) {
sb.append((char)i);
}
for (int i = '快'+1; i < Character.MAX_VALUE; i++) {
sb.append((char)i);
}
String source = sb.toString();
System.out.println(source.length());
long st = System.currentTimeMillis();
System.out.println(FirestNoRepeated(source));
long ed = System.currentTimeMillis();
System.out.println("楼主的time use:"+ (ed -st));
st = System.currentTimeMillis();
System.out.println(FirestNoRepeated2(source));
ed = System.currentTimeMillis();
System.out.println("time use:"+ (ed -st));
}
运算结果:
131069
快
楼主的time use:172
快
time use:0
15 楼
emparadise329
2010-04-16
chenyulong1 写道
楼主，方法名是FirstNoRepeated吧！
写了个看看行不行：
写了个看看行不行：
public static Character FirstNoRepeated(String str){
for(int i=0;i<str.length();i++){
if(str.split(String.valueOf(str.charAt(i))).length==2)
return new Character(str.charAt(i));
}
return null;
};这个方法也有问题啊，要是想这样的“123213”字符串，结果应该是null，但是以上方法得到结果是3
14 楼
taoyu3781212
2010-04-16
import java.util.HashMap;
import java.util.Map;
public class TestChar {
public static void main(String[] args) {
String str = "adsfewvcxrewfdsfrewfdjyi" ;
System.out.println(test1(str)) ;
System.out.println(test2(str)) ;
long startTime = System.nanoTime() ;
for(int i=0;i<1000000;i++){
test1(str) ;
}
long endTime1 = System.nanoTime() ;
for(int i=0;i<1000000;i++){
test2(str) ;
}
long endTime2 = System.nanoTime() ;
System.out.println("Test1 use time:"+(endTime1-startTime));
System.out.println("Test2 use time:"+(endTime2-endTime1));
}
public static Character test1(String str){
Character c = null ;
for(int i=0;i<str.length() ;i++){
if(str.split(String.valueOf(str.charAt(i))).length==2){
return str.charAt(i) ;
}
}
return null ;
}
public static Character test2(String str){
Map <Character,Integer> map = new HashMap<Character,Integer>();
for(int i=0; i<str.length();i++){
if(map.containsKey(str.charAt(i))){
map.put(str.charAt(i), 2);
}else{
map.put(str.charAt(i), 1);
}
}
for(int i=0; i<str.length();i++){
if(map.get(str.charAt(i))==1 ){
return str.charAt(i);
}
}
return null;
}
}
运行结果：
a
a
Test1 use time:2565346154
Test2 use time:3878041483
当循环数为10000时，运行结果：
a
a
Test1 use time:83528214
Test2 use time:52959524
13 楼
keanu-re
2010-04-16
dasimm 写道
public static Character getFristChar2(String arg){
for( int i = 0 ; i < arg.length() ; i++){
if(arg.indexOf(String.valueOf(arg.charAt(i))) == arg.lastIndexOf(String.valueOf(arg.charAt(i)))){
return arg.charAt(i);
}
}
return null;
}
以前看的一个帖子的
这个效率明显低。。
发表评论
-
企业部门志愿筛选
2011-08-17 13:39 1017公司招聘录取问题 某集团公司业务发展迅速，各事业部普 ... -
连续整数之和为1000的共有几组
2010-10-11 00:33 1463public class test { public st ... -
将嵌套文件转成树
2010-05-14 13:37 935package com.test.zhongruan; ... -
获取随机数（每一位数不能重复）
2010-05-11 13:05 1282输入一个个位数，这个数代表产生的随机数的位数，并且随机数的每一 ... -
取两个数组交集然后排序打印
2010-05-11 12:42 1741获取A{12，3，45，6，7，8，9，0，6}，B{12，4 ... -
对象池的
2010-04-26 17:49 860对象池是存放一组特定的对象的容器。对象池是解决性能的一种途径， ... -
java 反射总结
2010-04-01 20:38 10741，java 的反射 让我们可以通过字符串类名生成类的实例，调 ... -
instanceof 与isAssignableFrom
2010-01-12 21:36 1217instanceof 针对实例 isAssignableFro ... -
Comparator和Comparable比较
2010-01-12 04:33 1375当需要排序的集合或数组不是单纯的数字型时，通常可以使用Comp ... -
公司出的题，该如何下手
2010-01-10 00:33 1020测试1 附件Access数据库(test.mdb)中的“来访 ...
相关推荐
去掉重复的字符串及在第一个字符串中删除在第二个字符串中出现的字符两个程序，vs2013已经验证
它接受两个参数：主字符串和要查找的子串，返回子串在主字符串中第一次出现的位置。如果找不到，则返回0。例如，`POS("World", "Hello, World!")`将返回7，因为"World"首次出现在"Hello, World!"中的位置是第7个字符...
求字符串中第一个出现的最长重复字符串。输入任意一个字符串，此程序可求得第一个出现的最长重复字符串。
根据给定的信息，我们需要实现一个C语言函数`void fun(char *s,char *t,char *p)`，该函数的功能是：将未在字符串`s`中出现、而在字符串`t`中出现的字符形成一个新的字符串并存储在指针`p`指向的空间内。新字符串中...
如果需要保留第一次出现的重复字符，可以稍微修改代码，将满足条件的字符直接添加到结果字符串，而不是最后一次性构建： ```csharp public static string KeepFirstOccurrence(string input) { Dictionary, bool> ...
假设我们有一个较长的字符串，但只关心其中的一部分，比如从第3个字符开始的4个字符： ```scl STRING LongString := "ABCDEFGHIJ"; STRING SubString; SubString := SUBSTRING(LongString, 2, 4); // 从索引2开始，...
int strarray cat char arr [str max len] int i char str 把二维arr字符串数组拼接成一个串 i是第一维的长度 存入str int replacate char res int n char const str 产生n个重复的str 串或者字符 存入res ">几个...
Java 实现输出字符串中第一个出现不重复的字符详解 Java 实现输出字符串中第一个出现不重复的字符详解是 Java 编程语言中的一种常见问题，该问题的解决方法有多种，本文将详细介绍两种实现方法。 方法一：使用 ...
select f_find('Ap@2233ll@@l@@','@') from dual 返回结果为5，代表‘@’在该字符串中出现5次。 同理 select f_find('Ap@223SWEQQQ3ll@@l@@','Q') from dual---返回3，代表Q在字符串中出现了3次， select f_find('我...
根据给定的文件信息，我们可以总结出以下关于“求一个字符串中的连续出现次数最多的字串”的相关知识点： ### 一、问题定义与分析 #### 1.1 问题背景 在计算机科学中，字符串处理是常见且重要的任务之一。本问题是...
1. 第一步，遍历字符串中的每个字符，并记录每个字符出现的位置，将这些信息存储在一个对象中。 2. 第二步，再次遍历记录字符位置的对象，找出第一次出现且之后没有重复出现的字符。 在了解了算法的总体结构后，接...
在JavaScript中，split()函数是一个非常实用的字符串处理方法，用于将字符串分割成子字符串数组。标准的split()方法允许用户通过一个特定的分隔符来分割字符串，但在很多实际编程场景中，我们需要按照多个分隔符对...
### Python统计一个字符串中每个字符出现次数的方法 在Python编程中，经常需要处理字符串相关的任务，其中一项常见的需求就是统计一个字符串中每个字符出现的次数。这种方法不仅在文本分析中有广泛应用，也是学习...
* REPLICATE() 函数：返回一个重复 character_expression 指定次数的字符串。REPLICATE() 函数的语法为 REPLICATE (character_expression, integer_expression),如果 integer_expression 值为负值，则返回 NULL。 * ...
4. **字符串查找**：`查找字符串`函数用于在一个字符串中查找指定子串的位置，如果找到，返回子串的第一个字符在原字符串中的位置；如果未找到，返回0。 5. **字符串替换**：`替换字符串`函数可以将字符串中的某个...
它的功能是在目标字符串中找到第一个边界字符串出现的位置，然后截取从那里到第二个边界字符串之前的所有内容。 2. `multiGetBetween()`：此方法可能用于在字符串中查找多个匹配的子串。它可能接受一个边界数组，...
性能提示12.1建议，如果一个字符串在代码中重复出现，可以尽可能地复用它，以节省内存。这是因为string字面量是隐式常量，其副本在内存中只会存在一次。 字符串的操作包括拼接、查找、替换和分割等。C#提供了丰富的...
10. InStr 函数：用于搜索一个字符串在另一个字符串中的第一个匹配的起始位置。 11. Mid 函数：用于从一个字符串中提取指定数量的字符，返回一个新的字符串。 12. Replace 函数：用于将一个字符串中的指定子字符串...