TLE opimization
几道题目很悲剧
Longest Parenthese 不是一次遍历+stack, 而是DP，但是DP TLE了。这道题目一开始以为是普通的stack括号匹配，一次扫描，后面逻辑改了半天还没过所有的case，然后看了才知道DP，感觉
最什么的问题都不是朴素算法，一般考虑DP 贪心啥的。这里的DP方程一开始以为是dp[i][j]表示整数啥的，递推写起来很别扭，后来想起曹博PPT提过bool的状态，所以改成bool值了，然后
括号字串类似矩阵链从短到长，遍历结束就是最后赋dp[i][j]=true的就是maxlen了，都不用打擂台。
#include <iostream>
using namespace std;
//#define MAXNUM 10000
//bool dp[MAXNUM][MAXNUM];
int longestValidParentheses(string str)
{
int n=str.size();
if(n==0) return 0;
bool** dp=new bool*[n];
for(int i=0;i<n;i++)
dp[i]=new bool[n],memset(dp[i],0,n*sizeof(bool));
/*
for(int i=0;i<str.size();i++)
{
for(int j=0;j<str.size();j++)
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
*/
//for(int i=0;i<=n-1;i++)
// dp[i][i]=false;
int maxlen=0;
for(int i=0;i<=n-2;i++)
{
if(str[i]=='(' && str[i+1]==')')
dp[i][i+1]=true,maxlen=2;
//else
// dp[i][i+1]=false;
}
for(int length=3;length<=n;length++)
{
for(int i=0;i<=n-3;i++)
{
int j=i+length-1;
if(j>=n)
break;
//dp[i][j]=false;
if(dp[i+1][j-1]==true && str[i]=='(' && str[j]==')')
{ dp[i][j]=true; maxlen=length;continue;}
for(int k=i;k<j;k++)
{
if(dp[i][k] && dp[k+1][j])
{ dp[i][j]=true;maxlen=length;break;}
}
}
}
for(int i=0;i<n;i++)
delete[] dp[i];
delete[] dp;
return maxlen;
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
string str;
while(getline(cin,str))
{
time_t start=clock();
cout<<longestValidParentheses(str)<<endl;
time_t end=clock();
cout<<"time: "<<end-start<<endl;
/*
for(int i=0;i<str.size();i++)
{
for(int j=0;j<str.size();j++)
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}*/
}
return 0;
}
认识已经如此的艰难，为何还要这样对我。后来leetcode版主回我说是有一个one pass的用栈的算法。。。我欲哭无泪了。。。。
这个是看的别人的代码，就像一道题目想不出最后看答案一个道理，和自己想出来对于自己的印象和理解是不可同日而语的。只能暂时解释下代码了。算法是被人的。
This algorithm seems a brainstorm method. stack stores position, which I have not thought before, it is so hard to think. Maxlen records current longest string length, last records last unmatched ),
int longestValidParentheses(string s) {
if (s.empty()) return 0;
stack<int> ms;
int maxlen = 0;
int last = -1; // Position of the last unmatched ')'
for (int i = 0; i < s.size(); i ++)
{
if (s[i] == '(') ms.push(i); //
else if (ms.empty()) last = i; // == ')' and the stack is empty, it means this is a non-matching ')'
else
{
ms.pop(); // pops the matching '('.
if (ms.empty()) // If there is nothing left in the stack, it means this ')' matches a '(' after the last unmatched ')'
maxlen = max(maxlen, i-last);
else // otherwise,
maxlen = max(maxlen, i-ms.top());
}
}
return maxlen;
}
Merged K linklist，优化了一次，去掉while 条件的 一次N重循环，还是不行，已经想到解决方案了，可以用heap，里面用pair，key是结点值，value是链表索引号，便于后面找到链表后移。
用了堆之后，我就在想，以后要有意识，找元素，能二分先考虑二分，找K个最大或者最小，能堆先堆，虽然建堆要O(n),但是当查找最大最小频繁的时候，例如在一个loop里面，那么loop里O(n)
就变为O(logn)了，如果n次loop，那么总复杂度从O(n^2)降到O(n+nlogn)=O(nlogn)了，所以堆的确是很强的DS。
另外需要注意的是，默认的make_heap一般都是 less compare函数，那么这个是产生大顶堆，这个不知道为什么，就理解成反的吧，例如父亲要小于孩子的(less than)，产生小顶堆，但是这里却是
大顶堆。默认less函数都知道的，就像排序默认less函数，然后递增。
Insert intervals 也要第二次搞定。。。。
另外今天看到一个语法问题，拷贝构造函数参数必须是引用传递，而不可以是值传递，因为本身参数传递如果是值，就要对象赋值，再次调用拷贝构造函数本身，造成自身递归调用，无穷递归。所以
一定是const T& a这种类型的 参数。
数组inta, a+1 相当于地址a+14了