m*********a
发帖数: 3299 | 1 不喜欢这种不直观的很难看懂的写法
你在遇到)，准备pop的时候，看一下stack上对应位置是不是(
如果是，就pop，不是就push
最大值，就是当前i-pop后stack的index+1或i+1 when stack is empty.
来。 |
|
a***e
发帖数: 413 | 2 我不太明白你说的意思，你觉得易懂的写法是怎么样的？能贴出来参考一下么？
如果输入是（（（（））））（（（（（） |
|
h*******e
发帖数: 1377 | 3 楼主如果想做的话，做个四则运算的计算把。。做出来再做一个带括号的。我觉得这个
经常考，也不是特别经常但是作为难题倒是经常出现，而且twitter考过 解方程的，前
一阵一个版友的twitter面经就是这个。 |
|
m*********a
发帖数: 3299 | 4 int longestValidParentheses(string s) {
int max_length=0,length;
stack container;
for (int i=0;i
if (s[i]=='('||container.empty()||s[container.top()]==')')
container.push(i);
else {
container.pop();
length=container.empty()?i+1:i-container.top();
if (length>max_length) max_length=length;
}
}
return max_length;
} |
|
a***e
发帖数: 413 | 5 可能每个人想得不同，我咋觉得这种方法更复杂呢。每个符号都要push进去。 |
|
a***e
发帖数: 413 | 6 请问你说的是
Evaluate Reverse Polish Notation么？或者是类似的
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another
expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
其实一点都不想做题。特别是碰到要花很长时间才能做出来的题，气大得很啊。。。。
。。。。。
估计要等明年才敢出去面试啦。。。。。。。。 |
|
m*********a
发帖数: 3299 | 7 其实反过来写就跟清楚了
如果stack不空的化，
if (s[i]=='(' and s[stack.top()]==')')
container.pop();
length=container.empty()?i+1:i-container.top();
if (length>max_length) max_length=length;
其他的所有情况push stack |
|
|
h*******e
发帖数: 1377 | 9 这个也算，还有正常的四则式子的运算，我经常感觉脑子不够用了， 想到复杂的问题
多想一会儿就特累得休息然后再想~~~~ |
|
a***e
发帖数: 413 | 10 ‘正常的四则式子的运算’是不是用arithmetic expression tree更好做？或者先把它
转换为RPN，再做。Data structure and algorithm 那本书上有解释怎么转换。。。。
。。。。
关于Evaluate Reverse Polish Notation,知道RPN的特点或者说evaluate RPN的算法后
，更像一道细节实现题。
我在OJ上错了就是因为记不清怎么把string变成char，还有没注意isdigit只判断1个符
号，遇到（-4）就没把它当负数了。
int evalRPN(vector &tokens) {
int n = tokens.size();
stack numbers;
for (int i=0; i
{
int len = tokens[i].length();
char * tmp = new char [le... 阅读全帖 |
|
h*******e
发帖数: 1377 | 11 你写得挺好啊，我之前自己实现 atoi 了~~~ 还有自己写 intToStr了~~~ 看过你的发
现这些都不用啊， 代码由50多行缩到了25行 。正常四则运算的如果不带括号的就直接
一个stack就行, 如果带括号的需要2个stack 一个放 符号，一个放 数字。。带括号的
情况还挺复杂~~ 带括号的我还不会 提笔就写~~ 没怎么练过， 不带括号的倒是简单
一点。
我把我照你的改的也给贴上
class Solution {
public:
int evalRPN(vector &tokens) {
stack numStack;
for(int tokI = 0; tokI < tokens.size(); ++ tokI)
if(tokens[tokI] == "*" || tokens[tokI] == "+" || tokens[tokI] ==
"/" || tokens[tokI] == "-")
{
int val1 = numStac... 阅读全帖 |
|
|
d******1
发帖数: 18 | 13 我建了个q群。
欢迎正在刷cc150四版五版到童鞋们加入。
群号是205077190 |
|
|
l*****a
发帖数: 14598 | 15 没细想，直接BFS就可以吧
你只能start from "("这个算root,
他的子节点可以是(( or ()
下一level可以是 ((( or (() or ()(
以此类推。只要number of "(" <= n, number of ")" <=number of "("
就可以插入Queue
最后...
combinations |
|
l******e
发帖数: 54 | 16 一样思路改成递推就行了 空间是还可以优化的
class Solution {
public:
vector generateParenthesis(int n) {
vector f[n + 1][n + 1];
f[0][0] = vector {""};
for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
for (const string& s : f[left][right]) {
if (left < n) {
f[left + 1][right].push_back(s + "(");
}
if (right < left) {
f[left][right + 1].push_back(s + ")");
}
... 阅读全帖 |
|
l******e
发帖数: 54 | 17 再上一个空间优化的吧
class Solution {
public:
vector generateParenthesis(int n) {
vector f[2][n + 1];
f[0][0] = vector {""};
for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
f[(left + 1) & 1][right].clear();
for (const string& s : f[left & 1][right]) {
if (left < n) {
f[(left + 1) & 1][right].push_back(s + "(");
}
if (right < left) {
f[left & 1][rig... 阅读全帖 |
|
l******e
发帖数: 54 | 18 再来更多的空间优化好了
class Solution {
public:
vector generateParenthesis(int n) {
vector f[n + 1];
f[0] = vector {""};
for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
for (int i = 0; i < f[right].size(); ++i) {
if (right < left) {
f[right + 1].push_back(f[right][i] + ")");
}
if (left < n) {
f[right][i] += "(";
}
}
}
}
retur... 阅读全帖 |
|
z**a
发帖数: 69 | 19 好角度，写了个，过了LC，差不多是非递归中序遍历二叉树的思路。
class Solution {
public:
class stack
{
public:
char c;
int flag;
stack(char c, int flag)
{
this->c = c;
this->flag = flag;
}
};
vector generateParenthesis(int n) {
int left = 0;
int right = 0;
vectorrecord;
vectorresult;
stack temp(0,0);
record.push_back(stack('(', 0));
le... 阅读全帖 |
|
m*********a
发帖数: 3299 | 20 大家很牛啊，想得清楚>2可能的非递归的
左右二种选择就比较难了非递归就比较难了 |
|
m**********e
发帖数: 22 | 21 我来贡献一个用queue的方法。C#写的：
// Iterative approach
public List generateParenthesisIter(int n)
{
Queue queue = new Queue(
);
queue.Enqueue(new ParenthesisWrapper("",0,0));
List result = new List();
while (queue.Count > 0)
{
ParenthesisWrapper curr = queue.Dequeue();
if (curr.left == n)
{
if ... 阅读全帖 |
|
|
l***s
发帖数: 15 | 23 贡献一个 python
class Solution:
# @param an integer
# @return a list of string
def generateParenthesis(self, n):
bs='()'
res=['()']
if n==0:
return ''
elif n==1:
return res
for i in range(2,n+1):
leres=len(res)
for j in range(leres):
base=res[0]
del res[0]
lebase=len(base)
for k in range(lebase+1):
new = base[0:k]+bs+b... 阅读全帖 |
|
N**********i
发帖数: 34 | 24 从7月份到现在，磕磕盼盼终于拿到了FB的offer，准备从了。就此做个总结，希望能对
还在找工作的朋友们有所帮助...
准备： lc（没刷完，但是有些高频题做了好几遍，还有水中的鱼的博客），cc150（先
刷了一遍，然后又看了好几遍，反复看了书中的一些不错的解法），g4g（稍稍做了一
些题），各大面经、版上大牛总结帖。我不是new grad(2年工作经验)，所以简历上的
工作时的projects好好准备了一下。
整体感觉就是：
1. 被拒多半还是实力问题+少许运气问题。onsite interview最好保证每一轮都不差（
哪怕都没有很突出），否则就很容易悲剧。所以还是得要多做题甚至多面试找感觉
2. 最有用的是lc+面经+大牛总结，面试时至少有30%-50%会遇到类似甚至一样的
3. bug free很难做到，也没啥必要. 之前有人说FB要求bug free被吓到了，但是感觉
思路+clean code更重要
4. 在三三面试官面前不要害怕，反正你做的多好他们都可以想办法阴你，还不如放松
心态跟他们好好一战
L(电面跪了)
HR分组的时候有点奇怪，分到了类似Site Reliabil... 阅读全帖 |
|
w****a
发帖数: 710 | 25 是DP求结果的数量么？
如果只是求数量，那就跟unqiue BST那题一样，都是卡塔兰数。 |
|
r****7
发帖数: 2282 | 26 这个根本不用dp，就用greedy就行了
combinations |
|
|
C********e
发帖数: 492 | 28 你贴的这个解法不是DP
而且我不认为此题可以用DP做。。。
combinations |
|
r*****3
发帖数: 27 | 29 可以dp的, 不过LZ代码没给全吧
就是i对括号的可以这样考虑, 最左边的做括号对应的右括号有i种情况, 对于每一种情
况, 这对括号里面的j对括号已经在之前被计算过, 因为j
i-j-1对括号也已经在之前被计算过, 因为i-j-1
递推式
buff[i]中的元素 = '(' + buff[j]中的任意一个 + ')' + buff[i-j-1]中的任意一个
, 枚举j就行了, 0 <= j <= i-1 |
|
t*****t
发帖数: 86 | 30
不难，一个valid parenthese，一个是用车运拷在一起的囚犯的问题，本质是遍历
graph，只不过graph不是联通的罢了。 |
|
n******7
发帖数: 99 | 31 Cong!
Return true or false whether a expression has extra parentheses
这题怎么做的？
job |
|
G******d
发帖数: 194 | 32 ****先申明是替朋友发的，我想去G人也不要****
先自我介绍，女生，CS master，纽约附近，今年5月毕业，没有intern经历
备战：
主要刷lc，去年夏天大概刷了四五十道，秋天上课忙又断了。正式开始刷题找工作是去
年12月中旬的寒假。寒假把lc刷完第一遍，今年春季开学开始刷第二遍。刷第二遍时，
为了节约时间，凡是觉得比较有思路的题都只在脑子里过的，每天大概写个两三题让自
己手熟，一题多解的题目都尽量研究了不同的解法。这一遍刷完也快二月底了，感觉略
有小成。之后又分类归纳了lc的题目类型和解法，这一步没花多少时间，但很有意义，
拿到新题目之后开始对题目解法有了比较正确直觉。
我没做过intern是硬伤，所以简历里的course project格外认真准备，确保自己每一个
都能讲清楚。
找工作过程：
从12月寒假开始投简历，以学校joblink，career fair为主，也找人内推了几个和网投
。加起来大概投了150-200个职位，从2月底开始有电面，前后将近20个不同公司，其中
一半要做30分到4小时不等的coding homework，最后onsite拿到6个，只去了4个... 阅读全帖 |
|
b**********5
发帖数: 7881 | 33 我觉得不用对parentheses处理吧， 因为已经prefix了。。。
如果没有let的话， 就是recursive， termination condition就是遇到 number就
return |
|
|
j**********3
发帖数: 3211 | 35 求代码，求思路,
果然年龄大了，智商捉急啊，还好最近不面 |
|
c******n
发帖数: 4965 | 36 你想想手做怎么弄， 基本上左括号多于右括号就可再加右括号 |
|
l******s
发帖数: 3045 | 37 想象一下用手去挨个提溜中间的操作符，每次提溜出一个二叉树。 |
|
|
j**********3
发帖数: 3211 | 39 我说的是那个新题，不是generate parenth的，我们说的是一个题吗？
如果是，就太好了。。。 |
|
|
|
|
|
|
|
j**********3
发帖数: 3211 | 46 这个题有点像那个 unique binary search tree, 是不？ |
|
|
l*****a
发帖数: 14598 | 48 再给你几道follow up questions
输入很长时怎么提高性能呢？
如何去重呢？
如何不用递归呢？ |
|
p*****2
发帖数: 21240 | 49
boolean isOp(char c){
return c == '+' || c == '-' || c == '*';
}
int cal(char c, int x, int y){
switch(c) {
case '+':
return x+y;
case '-':
return x-y;
case '*':
return x*y;
default:
return -1;
}
}
List dfs(String input, int s, int e){
List al = new ArrayList<>();
for(int i=s; i
char c = input.charAt(i);
... 阅读全帖 |
|
l*****a
发帖数: 14598 | 50 怎么解决输入太长，call stack overflow的问题呢？
请校长指点 |
|
