@yubad2000 Thank you for sharing! What if the additional condition is "every element could be used once"?
Heronalps
@Heronalps
Posts made by Heronalps

RE: JAVA: followup using recursion and memorization.

RE: Java solution, sliding window
@2499370956 Yes, your explanation is in hand with what I thought. But, it seems like LeetCode changed the test case and runtime. Now, this solution is rejected for TLE.

RE: Accepted Java Solution using memoization
@kay_deep Great idea!
For those who needs further explanation, I think this solution adopts "divide and conquer" with two pointers technique. An array of TreeSet is to store all possible indices, which could confine the range of a palindrome. Then, memo function will be called recursively to search symmetric characters within such range until start meets end pointer. DP array is to memorize all previous outcome and the value from 0 to S.length()  1 is the final result.

RE: Java solution, sliding window
@2499370956 Pretty decent solution! Thank you for sharing.
I tried to analyze TC. Is it (n  m) * m, given n is length of S and m is length of T ? How does minLen help to improve TC? Let me know your opinion.

Java AC solution with O(1) pop() & popMax()
class MaxStack { TreeMap<Integer, LinkedList<Integer>> map; List<Integer> stack; int addIndex; int popIndex; public MaxStack() { map = new TreeMap<>((a, b) > Integer.compare(b, a)); stack = new ArrayList<>(); addIndex = 0; popIndex = 0; } public void push(int x) { if (map.containsKey(x)) { map.get(x).add(addIndex); } else { LinkedList<Integer> indices = new LinkedList<>(); indices.add(addIndex); map.put(x, indices); } stack.add(x); addIndex++; popIndex = addIndex  1; } public int pop() { int head = backtrackPopIndex(); map.get(head).removeLast(); popIndex; return head; } public int top() { return backtrackPopIndex(); } public int peekMax() { int max = map.firstKey(); while (map.get(max).size() == 0) { max = map.higherKey(max); } return max; } public int popMax() { int max = peekMax(); int index = map.get(max).pollLast(); if (index == popIndex) { popIndex; } return max; } private int backtrackPopIndex (){ int head = stack.get(popIndex); while (!map.get(head).contains(popIndex)) { head = stack.get(popIndex); } return head; } }
The Max Stack is basically an appendonly arraylist. In order to operate pop() & popMax() in constant time, a TreeMap<element, LinkedList<index>> is needed to record the index of new comer, as well as tracking the max value in the Max Stack. The order in the treemap will let us know which is the next max value to popMax(), which is just simply evicting the last index in its corresponding indices list.
The reason why the Max Stack is appendonly is because the popMax() operation with remove operation will scramble the recorded indices in our map. Then, we need two pointers, addIndex & popIndex, to track the append and pop/top operation respectively. Since popMax() would make element after popIndex invalid, popIndex should backtrack every time pop() or top() is called. No list will be removed from treemap to keep backtrackPopIndex operation valid.
One thing is a bit confusing is higherKey(). Since treemap has a reverse comparator, higherKey refers to the greatest key less or equal to the passed key. It has the reverse effect as in min TreeMap.
Hope it can inspire some better ideas!

RE: Short and easy to understand solution
Two corner cases are added. [1.00000, 2147483648], [0.50000, 2147483648]
Tiny update to the answer:
public double myPow(double x, int n) { long l = n; int half = 0; if (n < 0) { half = (int) (l / 2); x = 1 / x; } else { half = n / 2; } if (n == 0) { return 1; } else if (n % 2 == 0) { return myPow(x * x, half); } return myPow(x * x, half) * x; }

4ms simple Java Solution
The idea is in line with the most voted solution, except I didn't use last1 & last2 to keep track of min cost in previous row. The critical part is to cascade the assignment of minCost1 & minCost2. (i.e. a cost that is smaller than both minCost1 & minCost2 should bump up minCost1 to be minCost2)
public int minCostII(int[][] costs) { if (costs.length == 0  costs[0].length == 0) { return 0; } int row = costs.length; int col = costs[0].length; int result = Integer.MAX_VALUE; for (int i = 1; i < row; i++){ int minCost1 = 0; int color1 = 1; int minCost2 = 0; int color2 = 1; for (int j = 0; j < col; j++) { if (j == 0) { minCost1 = costs[i  1][0] > costs[i  1][1] ? costs[i  1][1] : costs[i  1][0]; color1 = costs[i  1][0] > costs[i  1][1] ? 1 : 0; minCost2 = costs[i  1][0] < costs[i  1][1] ? costs[i  1][1] : costs[i  1][0]; color2 = costs[i  1][0] < costs[i  1][1] ? 1 : 0; } else if (costs[i  1][j] < minCost2 && costs[i  1][j] < minCost1){ minCost2 = minCost1; color2 = color1; minCost1 = costs[i  1][j]; color1 = j; } else if (costs[i  1][j] < minCost2 && costs[i  1][j] >= minCost1 && color1 != j){ minCost2 = costs[i  1][j]; color2 = j; } } for (int j = 0; j < col; j++) { if (color1 != j) { costs[i][j] += minCost1; } else { costs[i][j] += minCost2; } } } for (int k = 0; k < col; k++) { result = Math.min(costs[row  1][k], result); } return result; }

RE: My DFS and BFS java solution
@Xiejiayu It should work by addFirst(), which I used in my solution. Post your code if you want comments.

RE: 2ms Java
@jianchao.li.fighter said in 2ms Java:
Why does the divide operation (l & r) + ((l ^ r) >> 1) works?
I think some folks may have the same question as I first encountered this unfamiliar divide operation. Let me try to add an explanation here:
 The result of & indicates every bit that has 1 to carry over to higher bit.
 The result of ^ indicates every bit that has 1 to stay.
 & * 2 + ^ gives out the addition of two numbers.
 & + ^ >> 1 gives out the addition of two numbers / 2.
 &, ^ and >> operations will not overflow even two operands are MAX_VALUE.

RE: My DFS and BFS java solution
@root_010 I believe you're concerned about the arrangement of lists of node's value. add(index, E), in which the index is zero, will insert the incoming List at the top of the wrapper List. SInce the nature of linkedlist, a new node will be created and points to the current head, meaning no shift of rest lists is necessary.
Additionally, in DFS solution, "list.get(list.size()level1).add(root.val);" will retrieve the list of corresponding level and add its value, when it's been visited.