p*****3
发帖数: 488 | 1 http://leetcode.com/2011/05/longest-substring-without-repeating
丢个简单的：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map mp;
int ret = 0;
int beg = 0;
for (int i = 0; i < s.length(); i++)
{
if (mp.find(s.at(i)) != mp.end() && mp[s.at(i)] >= beg)
beg = mp[s.at(i)] + 1;
mp[s.at(i)] = i;
ret = max(ret, i - beg + 1);
}
return ret;
}
};
文康，要不给改改？ |
r**h
发帖数: 1288 | 2 这思路不错，赞
我觉得hash直接用数组就可以了
int hash[256];
for(int i=0; i<256; i++) hash[i] = -1;
【在 p*****3 的大作中提到】
: http://leetcode.com/2011/05/longest-substring-without-repeating
: 丢个简单的：
: class Solution {
: public:
: int lengthOfLongestSubstring(string s) {
:
: unordered_map mp;
: int ret = 0;
: int beg = 0;
:
|
p*****3
发帖数: 488 | 3
这么做要是被用java的人面就会说要优化一下，
问半天原来是用hashmap，这算啥优化，学乖了直接用hashmap了
【在 r**h 的大作中提到】
: 这思路不错，赞
: 我觉得hash直接用数组就可以了
: int hash[256];
: for(int i=0; i<256; i++) hash[i] = -1;
|
r**h
发帖数: 1288 | 4 晕。。。
我的理解是频繁的call成员函数不是开销更大了嘛，虽然空间上是省了一点儿不过256
个int也不是啥大事吧还是O(1)
看来和面试官思路不同真的挺悲剧的
【在 p*****3 的大作中提到】
:
: 这么做要是被用java的人面就会说要优化一下，
: 问半天原来是用hashmap，这算啥优化，学乖了直接用hashmap了
|
l********7
发帖数: 3 | 5 public static int find (String s){
Map hm = new HashMap();
char[] chars = s.toCharArray();
int length = 0;
for(int i = 0; i < chars.length; i++){
if (!hm.containsKey(chars[i])){
hm.put(chars[i], i);
length++;
}
else{
int tmp = i - hm.get(chars[i]);
if (tmp > length) length = tmp;
hm.put(chars[i], i);
}
}
return length;
} |
z****e
发帖数: 54598 | 6 数组容易越界，而且不易维护，不易扩展
map可以写得很通俗易懂
比如
map.put(1,"1");
map.put(2,"2");
……
这样一串下来，傻子都能看懂
再比如同一个对象的重用，你要remove所有value
map.clear就搞定了，数组就要自己去实现了，多半要循环一下
而循环在多线程环境中极容易出一些并发修改的异常
256
【在 r**h 的大作中提到】
: 晕。。。
: 我的理解是频繁的call成员函数不是开销更大了嘛，虽然空间上是省了一点儿不过256
: 个int也不是啥大事吧还是O(1)
: 看来和面试官思路不同真的挺悲剧的
|
z****e
发帖数: 54598 | 7 写得很好
static，接口的使用，循环的定义，contiainsKey方法的使用
这些非常漂亮滴细节可以看出作者的水平
跟这样的程序猿一起干活，工作会比较愉快
【在 l********7 的大作中提到】
: public static int find (String s){
: Map hm = new HashMap();
: char[] chars = s.toCharArray();
: int length = 0;
: for(int i = 0; i < chars.length; i++){
: if (!hm.containsKey(chars[i])){
: hm.put(chars[i], i);
: length++;
: }
: else{
|
s*******e
发帖数: 1630 | 8 没明白，遇到有重复元素的时候，hm里边部分元素不用清掉？
【在 l********7 的大作中提到】
: public static int find (String s){
: Map hm = new HashMap();
: char[] chars = s.toCharArray();
: int length = 0;
: for(int i = 0; i < chars.length; i++){
: if (!hm.containsKey(chars[i])){
: hm.put(chars[i], i);
: length++;
: }
: else{
|
l********7
发帖数: 3 | 9 hm.put一个新value的以后旧的就被替换掉了。
【在 s*******e 的大作中提到】
: 没明白，遇到有重复元素的时候，hm里边部分元素不用清掉？
|
l********7
发帖数: 3 | 10 谢谢夸奖，那天刚好看见就写了一下。
我还在找工作啊
【在 z****e 的大作中提到】
: 写得很好
: static，接口的使用，循环的定义，contiainsKey方法的使用
: 这些非常漂亮滴细节可以看出作者的水平
: 跟这样的程序猿一起干活，工作会比较愉快
|
r**h
发帖数: 1288 | 11 谢谢建议
是不是说能用接口的时候用接口比较好呢？
比如说Queue, Map, Deque这些？
【在 z****e 的大作中提到】
: 写得很好
: static，接口的使用，循环的定义，contiainsKey方法的使用
: 这些非常漂亮滴细节可以看出作者的水平
: 跟这样的程序猿一起干活，工作会比较愉快
|
s*******e
发帖数: 1630 | 12 不行吧？例如 abcba 当读到第二个b的时候不应该把第一个a也清掉吗？这时候是从c开
始算最长的吧
【在 l********7 的大作中提到】
: hm.put一个新value的以后旧的就被替换掉了。
|
