s******e
发帖数: 146 | 1 我今天也正好做到这个。
想法是存上每个‘（’之前已经匹配的括号数量。
比如
（）（（）（）（（）
第1次遇到前括号，入栈数字是0，然后遇到后括号，现在的长度是2+0
第2次遇到前括号，入栈数字是2，当前长度重设为0
第3次遇到前括号，入栈数字是当前长度0.然后后括号，出栈，长度是2+0，
第4次遇到前括号，入栈数字是当前长度2.然后后括号，出栈，长度是2+2，
第5次遇到前括号，入栈数字是当前长度4，当前长度重设为0
第6次遇到前括号，入栈数字是当前长度0，遇到后括号，出栈，长度是2.
如果栈内仍有数字，目前是2，4，则全部出栈，和当前长度2比。取最长为4.
public class Solution {
public int longestValidParentheses(String s) {
// Start typing your Java solution below
// DO NOT write main() function
Stack stack = new Stack();
... 阅读全帖 |
|
w***o
发帖数: 109 | 2 拿这个练练DP：
public int longestValidParentheses(String s) {
int n = s.length();
int[] dp = new int[n+1];
int max = 0;
for(int i = n-2; i >= 0; i--) {
if(s.charAt(i) == '(') {
int j = i+1+dp[i+1];
if(j < n && s.charAt(j) == ')') {
dp[i] = 2+dp[i+1]+dp[j+1];
max = Math.max(max, dp[i]);
}
}
}
return max;
} |
|
j******s
发帖数: 48 | 3 扫描两遍的好处是constant space... |
|
|
s**1
发帖数: 71 | 5 Thank you so much. Would you please walk me through the algorithm a little,
because the hardest part k/2 <= i <= n-k/2 I haven't figured out.
Thanks again.
In addition, if I want to print out all the trees in dotted parenthesized
form, recursion is a good way? Or iterator? I have no clue on that? Can you
please give me some hint?
Thanks again. |
|
l*****a
发帖数: 559 | 6 You are talking about another question "validate the parentheses". |
|
b*2
发帖数: 94 | 7 去年对着电话念代码的飘过……当时跟印度MM在brace, parenthese和 brackets上各种
纠结…… |
|
d******e
发帖数: 164 | 8 ")(()())())(((()))(()()()(()(()(())))(())()((()()(((()())()))(()()())())(())
(()(()()()()))(((()())))(((()))))()()())))(()))))())(((()"
小数据可以过，大数据停在上面这个case。
Run Status: Runtime Error
但是拷出来，自己运行是对的，没有错误。请大家帮忙看看。
class Solution {
public:
int longestValidParentheses(string s) {
int m = 0;
stack stk;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || stk.empty() || s[stk.top()] == ')') {
stk.push(i);
} else {
... 阅读全帖 |
|
|
|
p*****2
发帖数: 21240 | 11
你去考考古。看看这题是怎么来的。拿它当作一个很好的练习题就可以了。 |
|
P*******b
发帖数: 1001 | 12 你定义的是stack,push进去的是int，肯定是超过ascii范围了
)) |
|
|
|
|
|
l*****a
发帖数: 14598 | 17 我以前不做难题的。
现在发现不做就没饭吃了 :( |
|
|
w****a
发帖数: 710 | 19 fresh master，刚刚结束的G家电面，问了两题都答上了除了一处笔误没有被指出bug，
希望不要悲剧，求bless。
两题都简单，第一题是大数加法，还不需要考虑负数情况。第二题是leetcode上的
generate parentheses。
上来没有让我介绍project之类的，直接开始答题，大数加法那个稍微多花了点时间，
主要是开始有点紧张我，写的代码用了两个循环（现在想想真2啊，不这么干估计能做3
题），他直接指出来不要写两个循环，我立马就改了。倒是没有被指出bug，但是他跟
着问了很多，比如我有些if判断，while里面的条件判断，他都一一问我是干嘛的，然
后他自己还在想test case跟着我的代码跑。其实时间不是写代码上的，都是他问问题
上的，可以说交互很频繁。
第二题我进入状态了直接写代码，代码大概也就一两分钟就写好了，有一处检查left<
right，笔误写成left>right了，他当时指出我就改过来了。不知道这个算不算bug。。
然后他依然是问了一堆（重点还是判断我if或while里的条件判断是干嘛的，非法情况
会怎样等等），最后又用他的大脑跑了一遍他的测试用... 阅读全帖 |
|
i*********7
发帖数: 348 | 20 =。=
它的意思是说只要这个message has balanced parentheses就算是yes，否则就是no？=
。=
不懂题意啊不懂。。。 |
|
w********p
发帖数: 948 | 21 evaluator （String expression)
1。将expression parse 成三块 expr1 operator expr2
2 。如果expr1, expr2 都是数字，return 计算结果。 比如6＊6
3。 不然，如果operator 是乘除的话，parse 来string2里的第一个数字，得到结果
4. 再不然，recursively call for rest expression.
有两个links很好和大家分析。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
把网上的code帖出来，给爱偷懒的同伙。我还没仔细看。
无意中运行了下面的code，并不能handle所有的cases 。个人还是喜欢stack的版本。
不会没关系，学学就会了吗。呵呵， 会了不用还是会忘嘛。
本科compiler课是要用java写一个compiler出来的。还有微积分,还给老师的知识还少
嘛？。。。
/*
* The "ExpressionEv... 阅读全帖 |
|
s**x
发帖数: 405 | 22 std::string needs resize, char* does not |
|
|
|
W********e
发帖数: 45 | 25
哦，我是想不明白，不是resize本身，二是为什么要做这个动作，说白了是不理解这里
的DFS啊！ |
|
s**x
发帖数: 405 | 26 resize cancels the push_back.
You can also use pop_back() instead of resize(size()-1), it is the same. |
|
o****d
发帖数: 2835 | 27 他的目的是把sample的最后一个entry去掉
其实他想做的就是 sample.pop_back()，把之前sample.push_back('(')的清掉
(说实话，感觉他这么写有点难看)
另外 如果CombinationPar的第二个参数 不是引用(string& sample)的话
就不用额外做这个处理了
sample.push_back('(');
CombinationPar(result, sample, deep+1, n, leftNum+1, rightNum);
sample.resize(sample.size()-1); |
|
s**x
发帖数: 405 | 28 难看是难看了点，但是避免字符串复制
如果不传引用就可以直接传 sample+"(" |
|
|
o****d
发帖数: 2835 | 30 恩 用引用 避免复制是对的
我想说的意思是 用resize比起pop_back难看懂 理解上不是那么直接 |
|
g***j
发帖数: 1275 | 31 大小集合都过了，大部分一次过，请问这算快还是慢的？才开始做题，不可能每天都2
个小时，如果要做完，这要多久啊!
都是老题
1) 3 sum
2) valid parentheses;
3) merge two sorted lists;
4) implement strstr();
5) pow(x,n);
6) merge intervals; |
|
c**w
发帖数: 1024 | 32 请问大家：
()(() 答案是2
(()() 答案是4
为什么呢？不应该都是4么？
)()())()()( 这个答案应该是几？
谢谢 |
|
|
c**w
发帖数: 1024 | 34 噢。。。我发现我题目没看懂。。
谢谢，明白了 ：P |
|
b******i
发帖数: 914 | 35 你好，很感谢你的面经，想就此问几个问题：
1. generate all possible parentheses, 这题为什么时间是O(n^2)呢？你是用的类似
于DP的方法做的吗？我看九章和careercup只是一个dfs的方法，复杂度感觉是指数的。
2. onsite 3里面10G文件那题的follow up，不是很懂你的答案：follow up是如果只有
400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
hash每次取尾数bits不一样的数以后，是再如何找出其中所有不同的数呢？再哈希一遍？
这题careercup150上面有，好像是分block来做的。
谢谢 |
|
b******i
发帖数: 914 | 36 你好，很感谢你的面经，想就此问几个问题：
1. generate all possible parentheses, 这题为什么时间是O(n^2)呢？你是用的类似
于DP的方法做的吗？我看九章和careercup只是一个dfs的方法，复杂度感觉是指数的。
2. onsite 3里面10G文件那题的follow up，不是很懂你的答案：follow up是如果只有
400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
hash每次取尾数bits不一样的数以后，是再如何找出其中所有不同的数呢？再哈希一遍？
这题careercup150上面有，好像是分block来做的。
谢谢 |
|
a*********0
发帖数: 2727 | 37 是不是连续valid才行？ 比如())() 最大是4还是2？？
网上看到的算法有用stack，首尾2遍扫描，甚至dp，简直不知所云。一个count搞不定
？？ |
|
T******e
发帖数: 157 | 38 挺巧，我今天又做了一遍那道题
要求是连续的，你给的情况的条件应该是2 |
|
a*********0
发帖数: 2727 | 39 连续的用count搞不定么？？非要用stack？ |
|
A*********c
发帖数: 430 | 40 用stack是很自然的做法，看到匹配类的，我就像巴甫洛夫的狗一样想到stack。
你说的单counter应该不work。具体为什么得看你怎么写啊。
你写一个大伙分析一下。 |
|
a*********0
发帖数: 2727 | 41 class Solution {
public:
int longestValidParentheses(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = s.length();
int maxl = 0;
int count = 0;
int len = 0;
for(int i = 0;i < n;i++){
if(s[i] == '('){
count++;
len++;
}
if(s[i] == ')') {
count--;
len++;
}
if(count == 0 ... 阅读全帖 |
|
n*****a
发帖数: 107 | 42 （（（））这个你返回几，应该是4；
还有这个 （）（），应该也返回4 |
|
|
|
s****e
发帖数: 1180 | 45 借宝地问个面试中的sql的问题。
We have two tables, students (student ID, student name, student age, student
zip) and courses (course name, course time) .
The information in the parentheses are the schema.
We want to get how many students enroll all the classes starting at 11:00 AM?
the interviewer mentioned something like many to many join.
the interviewer mentioned something like "dimensionalize" in SQL. I am
wondering who knows any SQL book on this, and can introduce it me?
Thank you so much for your consi... 阅读全帖 |
|
a**********0
发帖数: 422 | 46 The Unix Commands
其实就是攒了一下网上的资料
# Create a new tar archive.
# the folder dirname/ is compressed into archive_name.tar
tar cvf archive_name.tar dirname/
# Extract from an existing tar archive
tar xvf archive_name.tar
# View an existing tar archive
tar tvf archive_name.tar
# Search for a given string in a file (case in-sensitive search).
grep -i "the" demo_file
# Print the matched line, along with the 3 lines after it.
grep -A 3 -i "example" demo_text
# Search for a given string in all files recur... 阅读全帖 |
|
a***e
发帖数: 413 | 47 第一次看到的时候没想到要push数组的位置，而不是push‘（’，结果怎么都做不出来。
后来看了讨论的idea是把Indices存起来，按照那个想法写了，却发现last的初值要设
成-1，而不是0。最后通过的答案，看着觉得好郁闷，想了好久。。。。。。。
int longestValidParentheses(string s) {
vector left;
int n=s.size();
int last=-1,lmax=0;
for (int i=0; i
{
if (s[i]=='(')
{
left.push_back(i);
}
else if (s[i]==')')
{
if (left.empty())
{
... 阅读全帖 |
|
h*******e
发帖数: 1377 | 48 这道题最开始的想法是（也压栈，）也压栈，然后记录相应的index.不过后来发现似乎
）压栈没有必要只有最右边的）有用，就优化成最简那个形式了。 |
|
a***e
发帖数: 413 | 49 我在看讨论之前一直没想过记录相应的index，所以一直搞不定。估计还是题做太少 |
|
s******t
发帖数: 229 | 50 不用什么-1啊，压入index的想法在别的题里也有啊，比如histogram |
|
