w*****h
发帖数: 423 | 1 湾区startup
第一个墨西哥哥们，很简单的valid soduku
第二个三姐，问了一个表达式是不是valid括号的问题，有{，[, (三种括号
用stack秒杀，然后followup说有million种括号咋办，我开始有点慌，连LRU都想到了
。后来发现million括号存到内存也就2M，就说用hashmap存括号，三姐说sounds good
后来就收到拒信，WTF！ |
c*******e
发帖数: 373 | 2 million种括号，还用stack不挺好的吗
为什么要用hash |
w*****h
发帖数: 423 | 3 我可能没表达好，肯定是还用stack
但是你得判断哪两个char是一对，如果就三种，就显示的打出来好了，
但million的话就用hashmap存一下提高速度吧。
BTW: 仔细想想million括号的话肯定很多重复的pair,或者互相冲突的pair
不知道三姐问这个followup的用意是啥,nnd，move on了
【在 c*******e 的大作中提到】
: million种括号，还用stack不挺好的吗
: 为什么要用hash
|
c*******e
发帖数: 373 | 4 明白了，处理“括号对”的关系。
Java char类型，目前标准是16 bit的unicode，所以说她说million种括号，肯定无法
直接用char类型代表字符，需要自定义新型字符，这是题外话了。
就这题而言，我想更好的回答是：你既然定义了million中括号，请问每对左右括号，
by definition，他们之间有没有简单的关系，比如 0x1000是左括号的编码，那么
0x1001一定是右括号？
如果括号定义时就有这种简单的关系，那就不需要hashmap了。如果没有这样简单的规
律，都是乱对应的，那就用hashmap
【在 w*****h 的大作中提到】
: 我可能没表达好，肯定是还用stack
: 但是你得判断哪两个char是一对，如果就三种，就显示的打出来好了，
: 但million的话就用hashmap存一下提高速度吧。
: BTW: 仔细想想million括号的话肯定很多重复的pair,或者互相冲突的pair
: 不知道三姐问这个followup的用意是啥,nnd，move on了
|
l*****0
发帖数: 13 | 5 找到问题的关键点，great
【在 c*******e 的大作中提到】
: 明白了，处理“括号对”的关系。
: Java char类型，目前标准是16 bit的unicode，所以说她说million种括号，肯定无法
: 直接用char类型代表字符，需要自定义新型字符，这是题外话了。
: 就这题而言，我想更好的回答是：你既然定义了million中括号，请问每对左右括号，
: by definition，他们之间有没有简单的关系，比如 0x1000是左括号的编码，那么
: 0x1001一定是右括号？
: 如果括号定义时就有这种简单的关系，那就不需要hashmap了。如果没有这样简单的规
: 律，都是乱对应的，那就用hashmap
|
J*******o
发帖数: 741 | |
