jiahuang
BAN USERUse two pointers, O(n) time complexity, O(1) space:
////assume target is positive
public boolean hasContSum(List<Integer> list, int target)
{
int tail = 0;
int sum = 0;
for(int i=0;i<list.size();i++)
{
sum+=list.get(i);
while(sum>target){
sum=list.get(tail++);
}
if(sum == target) return true;
}
return false;
}

jiahuang
December 12, 2017 My O(nlongn) solution (Worse case O(n^2), best case O(n)):
My approach:
1. Find the max value in the array, we will buy all the stocks before the max and sell it at the max price.
2. Treat all elements after the max as a new array and repeat the steps until there is one or no element left.
public int maxProfit(int[] prices) {
return maxProfit(prices,0,prices.length);
}
public int maxProfit(int[] prices, int left, int right){
if(rightleft <=1)return 0;
int[] cum = new int[prices.length];
int maxPoint = 1;
int maxPointIndex = 1;
for(int i=left;i<right;i++){
cum[i]+=prices[i];
if(i>left)cum[i]+=cum[i1];
if(maxPoint<=prices[i]){
maxPoint = prices[i];
maxIndex = i;
}
}
return (maxIndexleft+1)*maxPointcum[maxIndex]+maxProfit(prices,maxIndex+1,right);
}

jiahuang
December 07, 2017 Here is my approach O(n) time complexity and O(1) space:
1. Set two pointers (A and B) point at the beginning of the string.
2. Pointer A walks through the string and record the frequency of each character in count[26].
3. If the current character that pointer A points to appears more than K, save the substring between B (inclusive) and A (exclusive) if it is the longest substring so far.
4. Move the pointer B and subtract the pointing character from count[26] until we get the frequencies of all characters in count[26] no more than K.
5. Repeat the process from step 2 until it reaches the end of the string.
//Assume given string is all low case between [az]
public String longestSubstring(String str, int K)
{
int A = 0;
int B = 0;
int[] count = new int[26];
int longestLen = 0;
String result;
for(;A<str.length();A++)
{
if(++count[str.charAt(A)'a'] > K)
{
if(longestLen < AB)
{
result = str.substring(B,A);
}
for(;B<A;B++)
{
if(count[str.charAt(B)'a'] == K)
{
B++;
break;
}
}
}
}
//indicates none of the characters in given string appears more than K
if(result == null) return str;
return result;
}

jiahuang
November 30, 2017 It can be done in O(n) time complexity (save the list into a Hashset for fast look up).
Iterate each node in the list and check the following conditions:
1. Its left and right node are null.We move the node from the list to a hashset, called "lookForParent".
2. Its left or right node does not belong to the list nor appear in the "lookForParent",
It violates rule #1 or #2, we can simply return false.
3. Its left and/or right node belongs to the list or appears in 'lookForParent".
(a) Remove this node from the list.
(b) Check if this node's child(ren) are in the list or in the "lookForParent" recursively
(if not, it violates rule #1 or #2 and return false) and remove the node from the list
or from the "lookForParent".
(c) Move this node to "lookForParent".
At the end if the "lookForParent" hashset contains one node (it is the root), return true. Otherwise return false (violates rule #3).
public boolean isValidTree(List<Node> list){
Set<Node> set = new HashSet<Node>(list);
HashSet<Node> lookForParent = new HashSet<Node>();
for(Node each:list){
if(set.contains(each){
if(each.left == null && each.right == null){
set.remove(each);
lookForParent.add(each);
}
else if(each.left != null  each.right != null){
Node tmp = each;
boolean good = checkChildren(each.left,set,lookForParent) &&
checkChildren(each.right,set,lookForParent);
if(good){
lookForParent.add(tmp);
}
else{
return false;
}
}
}
}
if(lookForParent.size() == 1){
return true;
}
return false;
}
public boolean checkChildren(Node node, HashSet<Node> set, HashSet<Node> lookForParent){
if(node == null) return true;
else if(lookForParent.contains(node)){
lookForParent.remove(node);
return true;
}
else if(set.contains(node)){
set.remove(node);
return checkChildren(each.left,set,lookForParent) &&
checkChildren(each.right,set,lookForParent);
}
return false;
}

jiahuang
October 25, 2017 Use two pointers to keep track the 'tail' and 'head' of the subarray. O(n) complexity:
public int countSubArrays(int[] array, int k){
int head = 0;
int tail = 0;
int total = 1;
int count = 0;
for(;head<array.length;head++){
total*=array[head];
if(total < k){
count+=head  tail + 1;
}
else{
while(total>=k && head >= tail){
total/=array[tail];
tail++;
}
if(head>=tail){
count+=head  tail + 1;
}
}
}
return count;
}

jiahuang
October 08, 2017 1. I think 123 should be equals to 6, not 6.
2. Some people mentioned the answer should be equals to ZERO. Let's take a look at the simplest number "12" Here are all the possible combinations:
12 = 12
1+2 = 3
12 = 1
+12 = 12
+1+2 = 3
+12 = 1
12 = 12
1+2 = 1
12 = 3
Sum = 14, so it is not equal to zero. If you look carefully, the final sum equals to the sum of the first three (the first number without the +/ sign). Let's check the number "123":
123 = 123
12+3 = 15
123 = 9
1+23 = 24
1+2+3 = 6
1+23 = 0
123 = 22
12+3 = 2
123 = 4
+123 = 123
+12+3 = 15
+123 = 9
+1+23 = 24
+1+2+3 = 6
+1+23 = 0
+123 = 22
+12+3 = 2
+123 = 4
123 = 123
12+3 = 9
123 = 15
1+23 = 22
1+2+3 = 4
1+23 = 2
123 = 24
12+3 = 0
123 = 6
sum = 153. The final sum is same as the sum of the first nine line. Also I see the pattern that for number "ab", the sum equals to ab+a*2, and for number "abc", the sum equals to abc+ab*2+a*6. I think you get the idea now. The time complexity should be O(n) where n is the length of the string.
1. Find the largest number (I called it A) from the array and remember its index.
2. Find the next largest number (I called it B) from the array. If B comes before A, we're good, otherwise move B to the front, MoveToFront(B).
3. A = B, and repeat (2). it needs to loop n2 times to check all other numbers.
It's not the fastest algorithm, but it should be very easy to understand. The time complexity is O(n^2).
1. find the smallest number in the first column and print it out.
2. remove the smallest number from its row, and shift all number to the left.
3. repeat.
Assume the max value in the matrix is smaller than 10^321
public void printSortedMatrix(int[][] matrix)
{
for(int a=0;a<matrix.length*matrix[0].length;a++){
int min = Integer.MAX_VALUE;
int index = 0;
for(int i=0;i<matrix.length;i++){
if(matrix[i][0] < min){
min = matrix[i][0];
index = i;
}
}
System.out.print(min+",");
for(int j=1;j<matrix[0].length;j++){
matrix[index][j1] = matrix[index][j];
}
matrix[index][matrix[0].length1] = Integer.MAX_VALUE;
}
}

jiahuang
August 04, 2015 recursive dynamic programming
public static void findSteps(int N){calSteps(N,"");};
public static void calSteps(int N, String stepsNow){
if(N >2){
calSteps(N2,stepsNow+"2");
}
else if(N == 2){
System.out.println(stepsNow+"2");
}
if(N>1){
calSteps(N1,stepsNow+"1");
}
else if(N == 1){
System.out.println(stepsNow+"1");
}
}

jiahuang
August 04, 2015 Here is an example to print output without return anything and without worry about the performance.
public static void printPermutate(String[] listStr)
{
recPrint(listStr, "", 0);
}
public static void recPrint(String[] listStr, String current, int index)
{
if(index == listStr.length1)
{
for(char ea : listStr[index].toCharArray())
{
System.out.println(current+ea);
}
}
else
{
for(char ea : listStr[index].toCharArray())
{
recPrint(listStr,current+ea,index+1);
}
}
}

jiahuang
August 04, 2015 1. if the current node has right child node, and if the right child node has left child node, return the leaf of the left most node. If the the right child node has no left child, return its value.
2. if the current node has no right child node, and if the current node is the left child of its parent, return its parent node's value (parent node can be null). If the current node is the right child node of its parent, set the parent node as the current node, and repeat (2).
public Node{
int value;
Node left;
Node right;
Node parent;
}
public Node findInOrderSuccessor(Node currentNode)
{
if(currentNode.right != null)
{
Node leftNode = currentNode.right.left;
if(leftNode == null) return currentNode.right;
while(leftNode.left != null)
{
leftNode = leftNode.left;
}
return leftNode;
}
else if(currentNode.parent != null)
{
while(currentNode.parent != null)
{
if(currentNode.parent.left.value == currentNode.value)return currentNode.parent;
currentNode = currentNode.parent;
}
}
return null;
}

jiahuang
August 04, 2015 1. Insert same level node in a list, from left to right.
2. iterate the list and assign the element[i].next = element[i+1], the last element's next should be null
3. go down to the next level and repeat 1.
public void PopulateNext(Node node)
{
List<Node> listNodes = new ArrayList<Node>();
node.next = null;
listNodes.add(node);
while(listNodes.size() > 0)
{
List<Node> newListNodes = new ArrayList<Node>();
for(int i=0;i<listNodes.size()1;i++)
{
listNodes.get(i).next = listNodes.get(i+1);
if(listNodes.get(i).left != null)
newListNodes.add(listNodes.get(i).left);
if(listNodes.get(i).right != null)
newListNodes.add(listNodes.get(i).right);
}
Node mostRightNode = listNode.get(listNodes.size()1);
mostRightNode.next = null;
if(mostRightNode.left != null)
newListNodes.add(mostRightNode.left);
if(mostRightNode.right != null)
newListNodes.add(mostRightNode.right);
listNodes = newListNodes;
}
}

jiahuang
August 03, 2015 If the time is in integer and is military time, then we can use an array to keep track any overlaps (back to back not consider overlap)
public int findRooms(int[] startTime, int[] endTime)
{
int maxRoom = 1;
int[] sch = new int[24];
for(int a=0;a<startTime.length;a++){
for(int i=startTime[a];i<endTime[a];i++)
{
sch[i]++;
maxRoom = Math.max(maxRoom,sch[i]);
}
}
return maxRoom;
}

jiahuang
August 03, 2015 Assume there are no parenthesis, the easy and neat solution would be use recursive function. Java code:
public static double cal(String expression){
double ret = 0;
if(expression.matches(".*\\+.*")){
for(String ea:expression.split("\\+")){
ret+=cal(ea);
}
}
else if(expression.matches(".*\\.*")){
String[] sp = expression.split("\\");
ret = cal(sp[0]);
for(int i=1;i<sp.length;i++){
ret=cal(sp[i]);
}
}
else if(expression.matches(".*\\*.*")){
ret = 1;
for(String ea:expression.split("\\*")){
ret*=cal(ea);
}
}
else if(expression.matches(".*\\/.*")){
String[] sp = expression.split("\\/");
ret = cal(sp[0]);
for(int i=1;i<sp.length;i++){
ret/=cal(sp[i]);
}
}
else ret = Double.parseDouble(expression);
return ret;
}

jiahuang
August 03, 2015 Open Chat in New Window
This can be done in two ways:
Approach 1: Construct the final line which takes O(2^k) time where k is the max row in all queries. Each query will only take O(1) time. The downside of this approach is it requires O(2^k) space.
Approach 2: Without construct the lines, it takes O(k) time for each query, and only takes O(1) space.
 jiahuang December 24, 2017