gaoxiao
BAN USER
Comments (8)
Reputation 30
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 2 vote
I think this can be done in O(n):
1.we can use a stack, traverse the arr from 0 > n1, for every val, if val <= top of stack, pop out the top, and the top to the child list of curr. Do this until top of stack < val or stack is empty.
2.At end, all the value in stack's target is 0, and the target of 'children of this value ' is +1.
3. Every node get visited at most twice, so is O(n).
see my python code:
def main():
ar = [1,3,2,4,5,4,2]
n = len(ar)
q = []
# val, idx, ans, children
q.append((ar[0], 0, 0, []))
for i in xrange(1, n):
curr = (ar[i], i, 0, [])
while len(q) > 0 and ar[i] <= q[len(q)  1][0]:
tp = q.pop()
curr[3].append(tp)
q.append(curr)
ans = [0] * n
for x in q:
idx = x[1]
tar = x[2]
chi = x[3]
ans[idx] = tar
for c in chi:
q.append((c[0], c[1], c[2] + tar + 1, c[3]))
print ans

gaoxiao
October 09, 2013 Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 4 vote
I think Manacher algo can solve this in O(n):
(I treat single character as palindrome)
int longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stringstream ss;
int n = s.size();
ss << "#";
for(int i = 0; i < n; i++){
ss << s[i] << "#";
}
string ns = ss.str();
int ret = 0;
vector<int> arr(ns.size(), 0);
int cm = 0;
int ci = 0;
for(int i = 0; i < ns.size(); i++){
int pi = 2 * ci  i;
int pl = 0;
if(pi >= 0){
pl = arr[pi];
}
if(i + pl < cm){
arr[i] = pl;
}else{
while(i + pl < ns.size() && i  pl >= 0){
if(ns[i + pl] != ns[i  pl]) break;
else pl++;
}
pl = 1;
arr[i] = pl;
if(pl > cm) cm = pl;
}
ret += (arr[i] + 1) / 2;
}
return ret;
}

gaoxiao
September 22, 2013 Comment hidden because of low score. Click to expand.
2
of 2 vote
I think Manacher algo can solve this in O(n), I implement two algos:
1. longestPalindrome is O(n) using Manacher
2. partition is O(n^2) using 2order DP
#include <stdio.h>
#include <iostream>
#include "climits"
#include "vector"
#include "cstring"
#include <sstream>
#include "cstdlib"
#include "map"
#include "algorithm"
#include "cmath"
#include "queue"
#include "stack"
using namespace std;
class Solution {
public:
int longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stringstream ss;
int n = s.size();
ss << "#";
for(int i = 0; i < n; i++){
ss << s[i] << "#";
}
string ns = ss.str();
int ret = 0;
vector<int> arr(ns.size(), 0);
int cm = 0;
int ci = 0;
for(int i = 0; i < ns.size(); i++){
int pi = 2 * ci  i;
int pl = 0;
if(pi >= 0){
pl = arr[pi];
}
if(i + pl < cm){
arr[i] = pl;
}else{
while(i + pl < ns.size() && i  pl >= 0){
if(ns[i + pl] != ns[i  pl]) break;
else pl++;
}
pl = 1;
arr[i] = pl;
if(pl > cm) cm = pl;
}
ret += (arr[i] + 1) / 2;
}
return ret;
}
int partition(string s) {
int n = s.size();
vector< vector< bool > > palindromeMatrix(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
palindromeMatrix[i][i] = true;
}
int ret = n;
for (int margin = 1; margin < n; margin++) {
for (int i = 0; i < n  margin; i++) {
int j = i + margin;
if ((i + 1 > j  1  palindromeMatrix[i + 1][j  1])
&& s[i] == s[j]) {
palindromeMatrix[i][j] = true;
palindromeMatrix[j][i] = true;
ret += 1;
}
}
}
return ret;
}
};
int main(int argc, char** argv) {
Solution ss;
string s = "abaaba";
cout << ss.longestPalindrome(s) << endl;
cout << ss.partition(s) << endl;
}

gaoxiao
September 22, 2013 Comment hidden because of low score. Click to expand.
0
of 0 vote
I think we can use 2order DP, here is my python code:
def mat(s, p):
ps = []
for c in p:
if c != '*' and c != '+':
ps.append(c)
else:
prev = ps[len(ps)  1]
ps.pop()
ps.append(c + prev)
m = len(ps)
n = len(s)
arr = [[False] * (n + 1) for i in xrange(m + 1)]
# init
arr[0][0] = True
for i in xrange(m):
if ps[i][0] == '*':
arr[i + 1][0] = arr[i][0]
# DP
for i in xrange(m):
for j in xrange(n):
currs = s[j]
tmp = False
if ps[i][0] == '*':
currp = ps[i][1]
if currp == currs:
# use 0, 1, n times
tmp = arr[i][j]  arr[i][j + 1]  arr[i + 1][j]
else:
# can only use 0 time
tmp = arr[i][j + 1]
elif ps[i][0] == '+':
currp = ps[i][1]
if currp == currs:
# use 1, n times
tmp = arr[i][j]  arr[i + 1][j]
else:
currp = ps[i]
if currp == currs:
# must match
tmp = arr[i][j]
arr[i + 1][j + 1] = tmp
return arr[m][n]

gaoxiao
September 22, 2013 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
nice!
 gaoxiao October 23, 2013