ZhenyiLuo
BAN USERpublic static boolean hasDuplicateParenthesis(String exp){
Stack<Character> st = new Stack<Character>();
for(int i = 0; i < exp.length(); i++){
char c = exp.charAt(i);
if(c != ')' && c != '}'){
st.push(c);
}else{
if(c == ')'){
if(st.peek() == '('){
return true;
}
while(st.peek() != '('){
st.pop();
}
st.pop();
}
if(c == '}'){
if(st.peek() == '{'){
return true;
}
while(st.peek() != '{'){
st.pop();
}
st.pop();
}
}
}
return false;
}
Find the path for each node, and compare the path.
BinaryTreeNode getLatestCommonParent(BinaryTreeNode root, ArrayList<BinaryTreeNode> nodes){
if(root == null){
return null;
}
boolean[] boolResult= new boolean[nodes.size()];
ArrayList<ArrayList<BinaryTreeNode>> pathList = new ArrayList<ArrayList<BinaryTreeNode>>();
for(int i = 0; i < nodes.size(); i++){
if(nodes.get(i) == null){
return null;
}
boolResult[i] = getNodePath(root, nodes.get(i), pathList.get(i));
}
for(int i = 0; i < nodes.size(); i++){
if(!boolResult[i]){
return null;
}
}
boolean mark = false;
int loc = 0;
BinaryTreeNode LCA = root;
while(!mark){
for(int i = 0; i < nodes.size(); i++){
if(pathList.get(i).get(loc) == null || pathList.get(i).get(loc) != pathList.get(0).get(loc)){
mark = true;
}
}
}
return LCA;
}
private boolean getNodePath(BinaryTreeNode root,
BinaryTreeNode node, ArrayList<BinaryTreeNode> path) {
if(root == null){
return false;
}
if(root == node){
path.add(node);
return true;
}
path.add(node);
if(getNodePath(root.left, node, path)){
return true;
}
if(getNodePath(root.right, node, path)){
return false;
}
return false;
}
- ZhenyiLuo January 20, 2014Directed acyclic graph is equivalent to strictly partial order sets.
This problem can be solved by pre-construct a Hasse diagram for divisibility.
Ex.
-----------------90 (Exit)
/|\
/ | \
6 10 9
\ /\ /
\/ \/
/\ /\
/ 3 \
2 | 5
\ | /
\ | /
\|/
1(Entrance)
After precompute this hasse diagram, for any given start point and end point, we just need to find the corresponding value of them, and check whether the end point value is divided by the start point value.
- ZhenyiLuo January 19, 2014public class CalculateLongIntegers {
public static void main(String[] args){
String s1 = "123456278798238093532765432662476427646456353425635454854";
String s2 = "1234562787982380935327654326624764276464563534248758758756";
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int[] c3;
c3 = add(c1, c2);
if(c3[0] != 0){
System.out.print(c3[0]);
}
for(int i =1; i< c3.length; i++){
System.out.print(c3[i]);
}
}
private static int[] add(char[] c1, char[] c2) {
int l1 = c1.length;
int l2 = c2.length;
int len = l1 > l2 ? l1: l2;
int[] result = new int[len+1];
int i = c1.length-1;
int j = c2.length-1;
int carry = 0;
while(i >= 0 &&j >=0){
result[len] = (c1[i] - '0' + c2[j] - '0' +carry) % 10;
carry = (c1[i]-'0' + c2[j]-'0' + carry)/10;
i--;
j--;
len--;
}
while(i>=0){
result[len] = (c1[i] -'0' + carry) %10;
carry = (c1[i] -'0'+ carry) /10;
i--;
len--;
}
while(j>=0){
result[len] = (c1[j]-'0' + carry) %10;
carry = (c1[j]-'0' + carry) /10;
j--;
len--;
}
return result;
}
}
DP problem (partition problem)
Recurrence relation:
Assume P[i,j] be true if a subset of {a[1], a[2]..., a[j]} sums to i and false otherwise.
P[sum/2][N] is what we want to calculate.
P[i,j] is true if ether P[i,j-1] is true or P[i - a[j], j-1] is true.
Here is the code:
private static boolean isGoodPartion(int[] a) {
int N = a.length;
int sum = 0;
for(int i= 0; i < N; i++){
sum += a[i];
}
if(sum %2 != 0){
return false;
}
boolean[][] P = new boolean[sum/2+1][N+1];
for(int i = 0; i < N+1; i++){
P[0][i] = true;
}
for(int i = 1; i < sum/2+1; i++){
P[i][0] = false;
}
for(int i = 1; i <= sum/2; i++){
for(int j = 1; j <= N; j++){
if(i < a[j-1]){
P[i][j] = P[i][j-1];
}else{
P[i][j] = P[i][j-1] || P[i-a[j-1]][j-1];
}
}
}
return P[sum/2][N];
}
public class SwapInPlace {
public static void main(String[] args){
int N = 5;
int[] a = new int[]{11, 12, 13, 14, 15, 21, 22, 23, 24, 25};
for(int i = 0; i < N-1; i++){
int tmp = a[N + i];
for(int j = N+i; j >= 2*i+2; j--){
a[j] = a[j-1];
}
a[2*i+1] = tmp;
}
for(int i = 0; i < 2*N; i++){
System.out.println(a[i]);
}
}
}
public class KMP {
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(KMPSearching("ABABBABABC", "BBAB"));
}
public static int KMPSearching(String target, String pattern){
int[] prefixArray = prefix(pattern);
int length = target.length();
int lengthP = pattern.length();
int num = 0;
for(int i = 0; i<length; i++){
while(num > 0 && target.charAt(i) != pattern.charAt(num) ){
num = prefixArray[num-1];
}
if(target.charAt(i) == pattern.charAt(num)){
num++;
}
if(num == lengthP){
return i- lengthP+1;
}
}
return -1;
}
public static int[] prefix(String pattern){
int length = pattern.length();
int[] prefix = new int[length];
prefix[0] = 0;
for(int i = 1; i < length; i++){
int k = prefix[i-1];
while((pattern.charAt(i) != pattern.charAt(k)) &&(k!=0)){
k = prefix[k-1];
}
if(pattern.charAt(i) == pattern.charAt(k)) prefix[i] = k+1;
else prefix[i] = 0;
}
return prefix;
}
}
max heap does not necessarily keep the top k bids.
- ZhenyiLuo February 15, 2015