c*******a 发帖数: 1879 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: centralla (central LA), 信区: JobHunting
标 题: LC 387 怎么优化
发信站: BBS 未名空间站 (Fri Mar 30 17:31:17 2018, 美东)
要求一次LOOP就解决? |
S******g 发帖数: 93 | |
c*********n 发帖数: 1282 | |
c*******a 发帖数: 1879 | 4 那也要循环2次
【在 c*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用HashMap.
|
c*********n 发帖数: 1282 | |
g******g 发帖数: 5920 | 6 非得一次的话用linkedhashmap
【在 c*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那也要循环2次
|
n********g 发帖数: 6504 | 7 不需要循环2次。题目问第一个,不是所有unique的。
会算法有鸟用。可怜俺家里蹲啊。
【在 c*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那也要循环2次
|
v***a 发帖数: 903 | 8 题目贴出来看看
【在 c*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那也要循环2次
|
m**********e 发帖数: 12525 | 9 主要是你想得Millennium award
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不需要循环2次。题目问第一个,不是所有unique的。 : 会算法有鸟用。可怜俺家里蹲啊。
|
n********g 发帖数: 6504 | 10 俺开始往脑袋里塞维纳-斯托克斯存在性与光滑性知识了。后台跑了几个星期,还没报
告有进展。
【在 m**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要是你想得Millennium award
|
|
|
n********g 发帖数: 6504 | 11 不过讲真,俺们码工真没几个有兴趣解P/NP。好端端地不用干活6位数到手。累死累活
搞NP挣1m还得纳50%的税,也就小黑屋几年增长。然后出了名镁光灯下丢了悠哉悠哉的
工作只能到处讨饭。不知道还住不住得起小黑屋。尼玛智商正常一点的都不会去干。
【在 m**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要是你想得Millennium award
|
c*******a 发帖数: 1879 | 12 你写出来看看
【在 g******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非得一次的话用linkedhashmap
|
g******g 发帖数: 5920 | 13 评论里的,自己去看,可以跑过的
【在 c*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你写出来看看
|
c*********n 发帖数: 1282 | 14 希望大家都能拿到大包裹,我帖一个答案吧。其实就一层床糊纸。
import java.io.IOException;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Map.Entry;
import java.util.Set;
public class FirstUniqueCharacter {
public int firstUniqChar(String s)
{
Set set = new HashSet();
LinkedHashMap result = new LinkedHashMap
Integer>();
for (int i=0; i
char c = s.charAt(i);
if (set.contains(c)) {
result.remove(c);
} else {
set.add(c); // first occurrence
result.put(c, i);
}
}
Object[] arr = result.entrySet().toArray();
if (arr.length == 0) {
return -1;
}
@SuppressWarnings("unchecked")
Entry firstEntry = (Entry)arr[0];
return firstEntry.getValue();
}
public static void main(String[] args) throws IOException {
FirstUniqueCharacter fuc = new FirstUniqueCharacter();
System.out.println("leetcode result is: "+fuc.firstUniqChar("
leetcode"));
System.out.println("loveleetcode result is: "+fuc.firstUniqChar("
loveleetcode"));
System.out.println("aabbcc result is: "+fuc.firstUniqChar("aabbcc"));
System.out.println("abcabc result is: "+fuc.firstUniqChar("abcabc"));
}
} |
n********g 发帖数: 6504 | 15 不需要map。人家只限定loop一次字串。
用一个链表一个数组就行了。链表存工作状态,数组存某字符是否已重复了。
扫描到一个字符的时候:
1、如果数组里已经有了,忽略
2、扫描链表,如果已经有了,移除到数组里;否则加在链表末并下标
扫描完字串则链表中第一个元素的下标就是答案。
严格地说只用一链表也可以。如果这么抠门只用26个存储空间没有52个。
【在 c*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你写出来看看
|
c*******a 发帖数: 1879 | 16 你写这个面试官当场就把你混出去!
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不需要map。人家只限定loop一次字串。 : 用一个链表一个数组就行了。链表存工作状态,数组存某字符是否已重复了。 : 扫描到一个字符的时候: : 1、如果数组里已经有了,忽略 : 2、扫描链表,如果已经有了,移除到数组里;否则加在链表末并下标 : 扫描完字串则链表中第一个元素的下标就是答案。 : 严格地说只用一链表也可以。如果这么抠门只用26个存储空间没有52个。
|
n********g 发帖数: 6504 | 17 也许吧。取决于面试你的是几十三。你要用map人家就会问你map是什么工作原理。到最
后还是数组、链表。
【在 c*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你写这个面试官当场就把你混出去!
|
n********g 发帖数: 6504 | 18 这个问题的终极就是需要26(的倍数)个存储空间。如果要快,就加辅助指针(如所谓
的hash)。用map的应该拿不到level 3的offer。在俺那个年代。
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 也许吧。取决于面试你的是几十三。你要用map人家就会问你map是什么工作原理。到最 : 后还是数组、链表。
|
n********g 发帖数: 6504 | 19 嗯,再给一终极程序。
1、一不超过26格双向链表
2、一26格数组。对象为:数字下标及指向链表中对象
扫描字串:
1、检查数组对应对象下标如果为负数,跳过忽略;否则
2、如果为正数,改为-1,将对应链表中对象删除;否则
3、下标改为当前字符串下标+1,并把对应对象加在双向链表末段
全部扫描完后,双向链表中第一个对象的下标-1就是答案。
单循环也不需要遍历数组和链表。不算整数、指针等辅助内存只用了26(52)个对象。
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个问题的终极就是需要26(的倍数)个存储空间。如果要快,就加辅助指针(如所谓 : 的hash)。用map的应该拿不到level 3的offer。在俺那个年代。
|
K******r 发帖数: 4052 | 20 不知道要不要区分大小写
建数组26或者52
用ascii-‘a’做角标
出现一次+1
一次循环搞定
[在 calcityloan (没有昵称) 的大作中提到:]
:希望大家都能拿到大包裹,我帖一个答案吧。其实就一层床糊纸。
:import java.io.IOException;
:import java.util.HashSet;
:import java.util.LinkedHashMap;
:import java.util.Map.Entry;
:import java.util.Set;
:public class FirstUniqueCharacter {
:
: public int firstUniqChar(String s)
: {
:.......... |
|
|
g******g 发帖数: 5920 | 21 你这个counting sort一次搞不定,还要再loop一次找第一个出现
【在 K******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不知道要不要区分大小写 : 建数组26或者52 : 用ascii-‘a’做角标 : 出现一次+1 : 一次循环搞定 : [在 calcityloan (没有昵称) 的大作中提到:] : :希望大家都能拿到大包裹,我帖一个答案吧。其实就一层床糊纸。 : :import java.io.IOException; : :import java.util.HashSet; : :import java.util.LinkedHashMap;
|
m**********e 发帖数: 12525 | 22 题目如下
Given a string, find the first non-repeating character in it and return it's
index. If it doesn't exist, return -1.
Examples:
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
这么简单的玩意,竟然这么多人不知道怎么办 |
K******r 发帖数: 4052 | 23 你不能+1之前判断一次?
[在 goodgang (一见不日,如隔三秋) 的大作中提到:]
:你这个counting sort一次搞不定,还要再loop一次找第一个出现
:☆ 发自 iPhone 买买提 1.24.06 |
g******g 发帖数: 5920 | 24 第一次标记次数,第二次找到第一个,两次
【在 K******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你不能+1之前判断一次? : [在 goodgang (一见不日,如隔三秋) 的大作中提到:] : :你这个counting sort一次搞不定,还要再loop一次找第一个出现 : :☆ 发自 iPhone 买买提 1.24.06
|
s*****r 发帖数: 43070 | |
t**8 发帖数: 4527 | 26 ID 鉴定
用 map 的是程序员, 用数组的是工程师 |
v***a 发帖数: 903 | 27 哥们,你不能从后往前数?
即使按你说的,那也不叫数两次。
【在 g******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一次标记次数,第二次找到第一个,两次
|
B*Q 发帖数: 25729 | |
n********g 发帖数: 6504 | 29 通常涉及string的题都不要从后往前数。只能扫描一次提示这是个stream。要想象非常
大不能缓存不可再生。这也是显示你以前经验的一个标志。
【在 v***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哥们,你不能从后往前数? : 即使按你说的,那也不叫数两次。
|
g******g 发帖数: 5920 | 30 楼主的意思很简单,一次循环内搞定
你只用数组记出现次数,最后要不要再扫描一遍?
【在 v***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哥们,你不能从后往前数? : 即使按你说的,那也不叫数两次。
|
|
|
b********6 发帖数: 35437 | 31 那就多记录一些信息,在loop结束的时候就可以知道结果
这叫脱裤子放屁,整个运行的计算步骤一点没减少
【在 c*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那也要循环2次
|
v***a 发帖数: 903 | 32 我不懂你们马工这些奇技淫巧。
如果一个循环的话,需要维护两个东西:
1. 每个字母出现的次数,用数组或者hashmap
2. 一个栈或者队列记住所有出现一次的字母,当然上面的数组或者hashmap 还要指向
栈或者队列里的元素
所以一次应该是可以的吧
【在 g******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主的意思很简单,一次循环内搞定 : 你只用数组记出现次数,最后要不要再扫描一遍?
|
a****g 发帖数: 3027 | 33 大思路是要记住合适的东西?
a. 扫一遍,转成26个字母的信息
b. 然后在26个字母的数组内部,比较一下
只懂C,什妈数据结构也不懂,差不多这样?
int i;
int cnt[26];
int charFirstIndex[26];
for (i=0; i<26; i++) {
cnt[i] = 0;
charFirstIndex[i] = -1;
}
// scan through the string
for (i=0; *(str+i) != 0x00; i++) {
// this char is converted to a number
int j = str[i] - 'a';
// for any letter '', remember the number of occurences
cnt[j]++;
// for this letter, always remember its first occurrence index in string,
and forget about all later occurrences, if applicable
if ( charFirstIndex[j] == -1)
charFirstIndex[j] == i;
}
// now scan through the fixed 26 statistics, post processing
// regardless how long the string is, post processing is constant in time
and space
int firstIndex = 0;
int smallestIndexSofar = -1;
int CharSofar = -1;
for (i=0; i<26; i++) {
// a letter only occurred once
if ( cnt[i] == 1 ) {
if (smallestIndexSofar == -1) {
smallestIndexSofar = charFirstIndex[i];
charSofar = i;
}
else { // could this be even smaller indexed?
if ( charFirstIndex[i] < smallestIndexSofar ) {
smallestIndexSofar = charFirstIndex[i];
CharSofar = i;
}
}
}
}
// up to now, CharSofar+'a' is the real char, and its firstIndex is at
charFirstIndex[CharSofar]
print("char %c found at index %dn", CharSofar+'a', smallestIndexSofar);
【在 v***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不懂你们马工这些奇技淫巧。 : 如果一个循环的话,需要维护两个东西: : 1. 每个字母出现的次数,用数组或者hashmap : 2. 一个栈或者队列记住所有出现一次的字母,当然上面的数组或者hashmap 还要指向 : 栈或者队列里的元素 : 所以一次应该是可以的吧
|