meow
BAN USERthe thing is, you calculate the max profit of the opponent. suppose you take it from the front, your opponent can choose from F(a+2, b), F(a+1, b1) , and since the opponent plays optimally, he/she would choose max(F(a+2, b), F(a+1, b1)), which left you min(F(a+2, b), F(a+1, b1));
same logic, if you choose from the end, your opponent can choose from F(a, b2), F(a+1,b1), and he/she would choose max(F(a, b2), F(a+1,b1)), which left you min(F(a, b2), F(a+1,b1))
so you actually need the max leftover so you max whatever your opponent left to you, which is the first formula above.
the idea is use DP to find the height, left, right for each element.
if(matrix[i][j] == '0'){
height[i][j] = 0; left[i][j] = 0; right[i][j] = 0; //because it's an obstacle
}
else{
height[i][j] = 1  if matrix[i1][j] == '0';
height[i][j] = matrix[i1][j] + 1  otherwise
left[i][j] = max(left[i1][j], the index of the first obstacle on the element's left);
right[i][j] = min(right[i1][j], the index of the first obstacle on the element's right)
}
then we just go through the elements and find the max area, which is height*(rightleft).
idea from: hi.baidu.com/mzry1992/item/030f9740e0475ef7dc0f6cba
//oj.leetcode.com/problems/maximalrectangle/
public int maximalRectangle(char[][] matrix) {
if(matrix==null  matrix.length==0  matrix[0].length==0){
return 0;
}
else{
int row = matrix.length;
int col = matrix[0].length;
int[][] lefts = new int[row][col];
int[][] rights = new int[row][col];
int[][] heights = new int[row][col];
int[] leftObs = new int[col];
int[] rightObs = new int[col];
findLeftRightObs(0, matrix, leftObs, rightObs);
for(int i=0; i<col; i++){
if(matrix[0][i] != '0'){
heights[0][i] = 1;
lefts[0][i] = leftObs[i];
rights[0][i] = rightObs[i];
}
}
for(int i=1; i<row; i++){
findLeftRightObs(i, matrix, leftObs, rightObs);
for(int j=0; j<col; j++){
if(matrix[i][j] != '0'){
if(matrix[i1][j] == '0'){
heights[i][j] = 1;
lefts[i][j] = leftObs[j];
rights[i][j] = rightObs[j];
}
else{
heights[i][j] = 1+heights[i1][j];
lefts[i][j] = (int)Math.max(lefts[i1][j], leftObs[j]);
rights[i][j] = (int)Math.min(rights[i1][j], rightObs[j]);
}
}
}
}
int max = 0;
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if((rights[i][j]lefts[i][j])*heights[i][j]>max){
max = (rights[i][j]lefts[i][j])*heights[i][j];
}
}
}
return max;
}
}
public void findLeftRightObs(int row, char[][] matrix, int[] leftObs, int[] rightObs){
int obs = 0;
for(int i=0; i<matrix[0].length; i++){
if(matrix[row][i] == '0'){
leftObs[i] = i;
obs = i+1;
}
else{
leftObs[i] = obs;
}
}
obs = matrix[0].length;
for(int i=matrix[0].length1; i>=0; i){
if(matrix[row][i] == '0'){
rightObs[i] = obs;
obs = i;
}
else{
rightObs[i] = obs;
}
}
}

meow
March 22, 2014 no its not.
ie. you have sticks length 1,2,3
case 1:
you put 1 and 2 together first, cost1 = 1+2 = 3, and you have sticks length 3,3
then you put 3 in, cost2 = 3+3=6;
so the total cost = cost1+cost2 = 3+6 = 9;
case 2"
you put 2 and 3 together first, cost1 = 2+3 =5, and you have sticks length 1,5
then you put 1 in, cost2 = 1+5=6;
so the total cost =cost1+cost2 = 5+6 = 11;
this is just a backtracking solution
public static ArrayList<ArrayList<Integer>> sumSubset(int[] a, int start, int target,
ArrayList<ArrayList<Integer>> result, ArrayList<Integer> cur){
if(target==0){
result.add(new ArrayList<Integer>(cur));
}
else if(target>0){
int i = start;
while(i<a.length && a[i]<=target){
if(i==0  i==start  a[i]!=a[i1]){
cur.add(a[i]);
sumSubset(a, i+1, targeta[i], result, cur);
cur.remove(cur.size()1);
}
i++;
}
}
return result;
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
int[] a = new int[]{1,2,2,3,4,5};
res = sumSubset(a,0,5,res, new ArrayList<Integer>());
}

meow
March 11, 2014 my implementation based on this algorithm
static boolean anaStrStr (String needle, String haystack){
Map<Character, Integer> needleMap = new HashMap<Character, Integer>();
for(int i=0; i<needle.length(); i++){
char c = needle.charAt(i);
if(needleMap.get(c)!=null){
needleMap.put(c, needleMap.get(c)+1);
}
else{
needleMap.put(c, 1);
}
}
int diff = needle.length();
Map<Character, Integer> haystackMap = new HashMap<Character, Integer>();
for(int i=0; i<needle.length(); i++){
char c = haystack.charAt(i);
if(haystackMap.get(c)!=null){
haystackMap.put(c, haystackMap.get(c)+1);
}
else{
haystackMap.put(c, 1);
}
if(needleMap.get(c)!=null && needleMap.get(c)>=haystackMap.get(c)){
diff;
}
}
for(int i=needle.length(); i<haystack.length(); i++){
if(diff==0){
return true;
}
char c = haystack.charAt(ineedle.length());
haystackMap.put(c, haystackMap.get(c)1);
if(needleMap.get(c)!=null && needleMap.get(c)>haystackMap.get(c)){
diff++;
}
c = haystack.charAt(i);
if(haystackMap.get(c)!=null){
haystackMap.put(c, haystackMap.get(c)+1);
}
else{
haystackMap.put(c, 1);
}
if(needleMap.get(c)!=null && needleMap.get(c)>=haystackMap.get(c)){
diff;
}
}
return false;
}

meow
February 21, 2014 keep a map M of lists such that map.get(i) = lists of nodes that points to (i) minus the ith node;
also keep a set S of good nodes, initialize with the tail node;
then starting from the list of nodes that point to the tail node, proceed the lists and mark every node a good node (put it in the set S); repeat this step with nodes in the list;
finish when every node in the list is already a good node or the list is empty;
just keep a count of the first char and compare to the others on the way through, reset the letters index when finish one check
public static boolean isValidWord(String word, char[] letters){
if(word==null  word.isEmpty()  letters==null  letters.length==0){
return false;
}
else{
int index = 0;
int count = 0;
int tmpCount = 0;
for(int i=0; i<word.length(); i++){
if(word.charAt(i)==letters[index]){
if(index==0){
count++;
}
tmpCount++;
}
else if(word.charAt(i)!=letters[index] && tmpCount!=count){
//not matching letters[index]
return false;
}
else if(word.charAt(i)!=letters[index] && index==letters.length1){
//end of 1 valid word
index = 0;
i;
tmpCount=0;
count = 0;
}
else if(word.charAt(i)!=letters[index]){
index++;
i;
tmpCount=0;
}
}
if(index==letters.length1 && tmpCount==count){
return true;
}
else{
return false;
}
}
}
public static void main(String[] args) {
System.out.println(isValidWord("HIREHHIIRREE", new char[]{'H','I','R','E'})); //true
System.out.println(isValidWord("HIREHHIIRRREE", new char[]{'H','I','R','E'})); //false
System.out.println(isValidWord("HIREHHIIRREEHIE", new char[]{'H','I','R','E'})); //false
}

meow
January 12, 2014 My idea is use map. it's O(n) time and O(n) space where n is the number is nodes
Given a list of nodes
1. put nodes in a hashmap
2. find the direct child nodes of each node and put it in a hash map
1) make a new HashMap<Integer, ArrayList<Node>> (ie name it map)
2) for each node, map.put(node.id, new ArrayList<Node>())
3) for each node, map.get(node.parent.id).add(node.id)
3. make a new HashMap<Integer, Integer> (ie name it weight) which the id is key and weight is value
4. for each key>value in map,
for each subelement in value, process them
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Solution{
public static void main(String[] args){
//10,30,1
//30,0,10
//20,30,2
//50,40,3
//40,30,4
ArrayList<Node> nodes = new ArrayList<Node>();
nodes.add(new Node(10,30,1));
nodes.add(new Node(30,0,10));
nodes.add(new Node(20,30,2));
nodes.add(new Node(50,40,3));
nodes.add(new Node(40,30,4));
Map<Node, Integer> weight =getSubTreeWeight(nodes);
int i=1;
}
public static Map<Node, Integer> getSubTreeWeight(List<Node> nodes){
Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
for(int i=0; i<nodes.size();i++){
nodeMap.put(nodes.get(i).id, nodes.get(i));
}
Map<Integer, ArrayList<Node>> childMap = new HashMap<Integer, ArrayList<Node>>();
for(int i=0; i<nodes.size();i++){
childMap.put(nodes.get(i).id, new ArrayList<Node>());
}
for(int i=0; i<nodes.size(); i++){
if(childMap.get(nodes.get(i).parentId)!=null){
childMap.get(nodes.get(i).parentId).add(nodes.get(i));
}
}
Map<Node, Integer> weightMap = new HashMap<Node, Integer>();
for(Node n : nodeMap.values()){
if(weightMap.get(n)==null){
calculateWeight(n, childMap, weightMap);
}
}
return weightMap;
}
public static void calculateWeight(Node n, Map<Integer, ArrayList<Node>> childMap, Map<Node,Integer> weightMap){
if(childMap.get(n.id).isEmpty()){//no child
weightMap.put(n, n.weight);
}
else{
int weight = n.weight;
for(Node child : childMap.get(n.id)){
if(weightMap.get(child)==null){
calculateWeight(child, childMap, weightMap);
}
weight+= weightMap.get(child);
}
weightMap.put(n, weight);
}
}
}
class Node {
int id;
int parentId;
int weight;
Node(int id, int parentId, int weight){
this.id = id;
this.parentId = parentId;
this.weight = weight;
}
}

meow
January 09, 2014 a recursive solution in java.
*assume denom is sorted or we can just sort it
public static void getForms(int n, ArrayList<Integer> denom, int start, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result){
if(n==0){
result.add(new ArrayList<Integer>(current));
}
else{
for(int i=start; i<denom.size(); i++){
if(n>=denom.get(i)){
current.add(denom.get(i));
getForms(ndenom.get(i), denom, i, current, result);
current.remove(current.size()1);
}
}
}
}
public static void main(String[] args){
ArrayList<Integer> denom = new ArrayList<Integer>();
denom.add(1); denom.add(2); denom.add(3);
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
getForms(5, denom, 0, new ArrayList<Integer>(), result);
int i=1;
}
 meow January 08, 2014public static int findNumOfPalindromes(String s) {
// Find number of palindromes in a string
if (s == null  s.isEmpty()) {
return 0;
} else if (s.length() == 1) {
return 1;
} else {
int res = s.length();
for (int i = 0; i < s.length()  1; i++) {
boolean broke = false;
int dif = 1;
while (!broke && i  dif >= 0 && i + dif < s.length()) {
if (s.charAt(i  dif) == s.charAt(i + dif)) {
res++;
} else {
broke = true;
}
dif++;
}
if (s.charAt(i) == s.charAt(i + 1)) {
dif = 1;
broke = false;
res++;
while (!broke && i  dif >= 0 && i + 1 + dif < s.length()) {
if (s.charAt(i  dif) == s.charAt(i + 1 + dif)) {
res++;
} else {
broke = true;
}
dif++;
}
}
}
return res;
}
}

meow
November 13, 2013 public static String maxSubStringWithoutDuplicate(String s){
// Given s string, Find max size of a substring, in which no duplicate chars present.
if(s==null  s.isEmpty()){
return s;
}
Map<Character, Integer> map = new HashMap<Character, Integer>();
String max = "";
int curLen = 0;
int start = 0;
for(int i=0; i<s.length(); i++){
if(map.get(s.charAt(i))==null  map.get(s.charAt(i))==1  map.get(s.charAt(i)) <start){
map.put(s.charAt(i), i);
curLen++;
}
else{
if(curLen > max.length()){
max = s.substring(start, start+curLen);
}
if(curLen > map.get(s.charAt(i))i){
curLen= map.get(s.charAt(i))start;
start = map.get(s.charAt(i))+1;
}
else{
start = i;
curLen = 0;
}
map.put(s.charAt(i), i);
}
}
return max;
}

meow
November 12, 2013
RepLoriKetron, Accountant at Aspire Systems
I am a content marketing professional at HubatSpot, an inbound marketing and sales platform that helps companies attract visitors, convert ...
Repsharonpkarr, None at BT
Hi! My name is Mary. I am a writer for a variety of web and multiplatform applications.I am a ...
Replisaramsey773, Blockchain Developer at Adjetter Media Network Pvt Ltd.
I'm a 27 yearold blogger, makeup junkie and follower of Christ.I love all things that bring happiness. My ...
Repleighpjoyce, job tessio at CapitalIQ
Welcome to my world.I am a safetyconscious HVAC Engineer with experience with mechanical engineering Brampton HVAC design for commercial ...
you basically sort the intervals then merge them will be easy. O(nlogn)
 meow April 14, 2014