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 的大作中提到】
: 用HashMap.
|
c*********n
发帖数: 1282 | |
g******g
发帖数: 5920 | 6 非得一次的话用linkedhashmap
【在 c*******a 的大作中提到】
: 那也要循环2次
|
n********g
发帖数: 6504 | 7 不需要循环2次。题目问第一个，不是所有unique的。
会算法有鸟用。可怜俺家里蹲啊。
【在 c*******a 的大作中提到】
: 那也要循环2次
|
v***a
发帖数: 903 | 8 题目贴出来看看
【在 c*******a 的大作中提到】
: 那也要循环2次
|
m**********e
发帖数: 12525 | 9 主要是你想得Millennium award
【在 n********g 的大作中提到】
: 不需要循环2次。题目问第一个，不是所有unique的。
: 会算法有鸟用。可怜俺家里蹲啊。
|
n********g
发帖数: 6504 | 10 俺开始往脑袋里塞维纳-斯托克斯存在性与光滑性知识了。后台跑了几个星期，还没报
告有进展。
【在 m**********e 的大作中提到】
: 主要是你想得Millennium award
|
|
|
n********g
发帖数: 6504 | 11 不过讲真，俺们码工真没几个有兴趣解P/NP。好端端地不用干活6位数到手。累死累活
搞NP挣1m还得纳50%的税，也就小黑屋几年增长。然后出了名镁光灯下丢了悠哉悠哉的
工作只能到处讨饭。不知道还住不住得起小黑屋。尼玛智商正常一点的都不会去干。
【在 m**********e 的大作中提到】
: 主要是你想得Millennium award
|
c*******a
发帖数: 1879 | 12 你写出来看看
【在 g******g 的大作中提到】
: 非得一次的话用linkedhashmap
|
g******g
发帖数: 5920 | 13 评论里的，自己去看，可以跑过的
【在 c*******a 的大作中提到】
: 你写出来看看
|
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 的大作中提到】
: 你写出来看看
|
c*******a
发帖数: 1879 | 16 你写这个面试官当场就把你混出去！
【在 n********g 的大作中提到】
: 不需要map。人家只限定loop一次字串。
: 用一个链表一个数组就行了。链表存工作状态，数组存某字符是否已重复了。
: 扫描到一个字符的时候：
: 1、如果数组里已经有了，忽略
: 2、扫描链表，如果已经有了，移除到数组里；否则加在链表末并下标
: 扫描完字串则链表中第一个元素的下标就是答案。
: 严格地说只用一链表也可以。如果这么抠门只用26个存储空间没有52个。
|
n********g
发帖数: 6504 | 17 也许吧。取决于面试你的是几十三。你要用map人家就会问你map是什么工作原理。到最
后还是数组、链表。
【在 c*******a 的大作中提到】
: 你写这个面试官当场就把你混出去！
|
n********g
发帖数: 6504 | 18 这个问题的终极就是需要26（的倍数）个存储空间。如果要快，就加辅助指针（如所谓
的hash）。用map的应该拿不到level 3的offer。在俺那个年代。
【在 n********g 的大作中提到】
: 也许吧。取决于面试你的是几十三。你要用map人家就会问你map是什么工作原理。到最
: 后还是数组、链表。
|
n********g
发帖数: 6504 | 19 嗯，再给一终极程序。
1、一不超过26格双向链表
2、一26格数组。对象为：数字下标及指向链表中对象
扫描字串：
1、检查数组对应对象下标如果为负数，跳过忽略；否则
2、如果为正数，改为-1，将对应链表中对象删除；否则
3、下标改为当前字符串下标+1，并把对应对象加在双向链表末段
全部扫描完后，双向链表中第一个对象的下标-1就是答案。
单循环也不需要遍历数组和链表。不算整数、指针等辅助内存只用了26（52）个对象。
【在 n********g 的大作中提到】
: 这个问题的终极就是需要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 的大作中提到】
: 不知道要不要区分大小写
: 建数组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 的大作中提到】
: 你不能+1之前判断一次？
: [在 goodgang (一见不日，如隔三秋) 的大作中提到：]
: :你这个counting sort一次搞不定，还要再loop一次找第一个出现
: :☆ 发自 iPhone 买买提 1.24.06
|
s*****r
发帖数: 43070 | |
t**8
发帖数: 4527 | 26 ID 鉴定
用 map 的是程序员， 用数组的是工程师 |
v***a
发帖数: 903 | 27 哥们，你不能从后往前数？
即使按你说的，那也不叫数两次。
【在 g******g 的大作中提到】
: 第一次标记次数，第二次找到第一个，两次
|
B*Q
发帖数: 25729 | |
n********g
发帖数: 6504 | 29 通常涉及string的题都不要从后往前数。只能扫描一次提示这是个stream。要想象非常
大不能缓存不可再生。这也是显示你以前经验的一个标志。
【在 v***a 的大作中提到】
: 哥们，你不能从后往前数？
: 即使按你说的，那也不叫数两次。
|
g******g
发帖数: 5920 | 30 楼主的意思很简单，一次循环内搞定
你只用数组记出现次数，最后要不要再扫描一遍？
【在 v***a 的大作中提到】
: 哥们，你不能从后往前数？
: 即使按你说的，那也不叫数两次。
|
|
|
b********6
发帖数: 35437 | 31 那就多记录一些信息，在loop结束的时候就可以知道结果
这叫脱裤子放屁，整个运行的计算步骤一点没减少
【在 c*******a 的大作中提到】
: 那也要循环2次
|
v***a
发帖数: 903 | 32 我不懂你们马工这些奇技淫巧。
如果一个循环的话，需要维护两个东西：
1. 每个字母出现的次数，用数组或者hashmap
2. 一个栈或者队列记住所有出现一次的字母，当然上面的数组或者hashmap 还要指向
栈或者队列里的元素
所以一次应该是可以的吧
【在 g******g 的大作中提到】
: 楼主的意思很简单，一次循环内搞定
: 你只用数组记出现次数，最后要不要再扫描一遍？
|
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 的大作中提到】
: 我不懂你们马工这些奇技淫巧。
: 如果一个循环的话，需要维护两个东西：
: 1. 每个字母出现的次数，用数组或者hashmap
: 2. 一个栈或者队列记住所有出现一次的字母，当然上面的数组或者hashmap 还要指向
: 栈或者队列里的元素
: 所以一次应该是可以的吧
|
