wangpidong
BAN USERGenerally, we have a left index and a right index indicating the boundaries of the current window. We also have a running sum of the current window. If the running sum goes below zero, then we start a new window from right+1. Update the maxSum accordingly. It works for both negative or positive arrays.
public class Pair
{
public int first;
public int second;
public Pair(int f, int s)
{
first=f;
second=s;
}
public String toString()
{
return String.format("[Pair: first=%d, second=%d]", first, second);
}
}
public class ID5256786030362624
{
public Pair maxSubarray(int[] A)
{
if (A==null || A.length==0)
return null;
Pair result=new Pair(-1, -1);
int maxSum=Integer.MIN_VALUE;
int left=0;
int sum=0;
for (int right=0; right<A.length; right++)
{
sum += A[right];
if (sum>maxSum)
{
maxSum=sum;
result.first=left;
result.second=right;
}
if (sum<0)
{
sum=0;
left=right+1;
}
}
return result;
}
public static void main(String[] args)
{
int[] A={5,6,-4,3};
int[] B={8,9,-6,0,3,9};
int[] C={-1, -2, -5, -10};
ID5256786030362624 wpd=new ID5256786030362624();
System.out.println(wpd.maxSubarray(A));
System.out.println(wpd.maxSubarray(B));
System.out.println(wpd.maxSubarray(C));
}
}
Not exactly.
The steps should be as follows:
1. use a fast and a slow pointer to find the middle node and the last node and the node before the middle node, and also count the number of nodes in the list.
2. from the head, find the node containing the target value, and its previous node.
3. adjust the next pointer of the last node.
4. delete the target node.
public class LinkedListNode
{
public LinkedListNode next=null;
public int val=Integer.MIN_VALUE;
public LinkedListNode(int v)
{
this(v, null);
}
public LinkedListNode(int v, LinkedListNode node)
{
val=v;
next=node;
}
public String toString()
{
return String.format("[LinkedListNode: val=%d]", val);
}
public String toStringAll()
{
return String.format("[LinkedListNode: val=%d, next=%s]", val, (next!=null) ? next.toStringAll() : null);
}
}
public class ID24819662
{
public LinkedListNode delete(LinkedListNode head, int target)
{
if (head==null)
return null;
else if (head.next==head)
{// only one node
if (head.val==target)
return null;
else
return head;
}
else if (head.next.next==head)
{// two nodes
LinkedListNode node=head;
while (node.val!=target)
{
node=node.next;
if (node==head)// no target node
return head;
}
if (node==head)
{
LinkedListNode newHead=head.next;
newHead.next=newHead;
return newHead;
}
else
{
head.next=head;
return head;
}
}
// 1. use a fast and a slow pointer to find the middle node
// and the last node and the node before the middle node,
// and also count the number of nodes in the list.
LinkedListNode beforeMiddle=null;
LinkedListNode middle=null;
LinkedListNode last=null;
LinkedListNode slow=head;
LinkedListNode fast=head;
int countNodes=1;
while (true)
{
beforeMiddle=slow;
slow=slow.next;
fast=fast.next.next;
countNodes += 2;
if (fast.next==slow)
{// odd number of nodes
middle=slow;
last=fast;
break;
}
else if (fast.next.next==slow)
{// even number of nodes
countNodes++;
middle=slow;
last=fast.next;
break;
}
}
// 2. from the head, find the node containing the target value, and its previous node.
LinkedListNode previous=null;
LinkedListNode node=head;
boolean passedMiddle=false;
while (true)
{
if (node==middle)
passedMiddle=true;
if (node.val==target)
break;
previous=node;
node=node.next;
if (passedMiddle && node==middle)// no such node found
return head;
}
LinkedListNode newHead=(node==head) ? head.next : head;
// 3. adjust the next pointer of the last node
if (!passedMiddle)
{
if ((countNodes&1)==0)// even number of nodes
last.next=middle.next;
// if odd number of nodes, do nothing
}
else if (node==middle)
{
if ((countNodes & 1) == 1)// odd number of nodes
last.next = beforeMiddle;
else
last.next=middle.next;
}
else if (passedMiddle)
{
if ((countNodes&1)==1)// odd number of nodes
last.next=beforeMiddle;
// if even number of nodes, do nothing
}
// 4. delete the node
if (previous!=null)
previous.next=node.next;
return newHead;
}
public static void main(String[] args)
{
LinkedListNode head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
System.out.println(head.toString());
ID24819662 wpd=new ID24819662();
wpd.delete(head, 4);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 10);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 2);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 0);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 1);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 5);
}
}
A Java implementation using only one stack. Use recursion to implement dequeue.
public class ID64863
{
// Use only one stack. Use recursion to implement dequeue.
StackWithCount stack=new StackWithCount();
public void enqueue(int element)
{
stack.push(element);
}
public int dequeue()
{
if (stack.count()<=1)
return stack.pop();
int top=stack.pop();
int result=dequeue();
stack.push(top);
return result;
}
public static void main(String[] args)
{
ID64863 queue=new ID64863();
queue.enqueue(0);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
}
public class StackWithCount extends Stack<Integer>
{
public int count()
{
return elementCount;
}
}
}
A Java solution for this question. It is basically a post-order traversal of the input tree with some early cut-offs (proceeding if we already found the first common ancestor). Time O(n), Space O(1).
public class TreeNode
{
public TreeNode left=null;
public TreeNode right=null;
int val;
public TreeNode(int v)
{
val=v;
}
public String toString()
{
return String.format("[TreeNode: val=%d]", val);
}
public String toStringAll()
{
return String.format("[TreeNode: val=%d, left=%s, right=%s]", val,
(left!=null) ? left.toStringAll() : null,
(right!=null) ? right.toStringAll() : null);
}
}
public class ID2319
{
TreeNode ancestor=null;
boolean done=false;
public TreeNode firstCommonAncestor(TreeNode root, TreeNode leaf1, TreeNode leaf2)
{
if (root==null || leaf1==null || leaf2==null)
return null;
// initialize
ancestor=null;
done=false;
TreeNode result=firstCommonAncestorRecursive(root, leaf1, leaf2);
if (result==null || result==leaf1 || result==leaf2)
return null;
else
return result;
}
public TreeNode firstCommonAncestorRecursive(TreeNode root, TreeNode leaf1, TreeNode leaf2)
{// post-order traversal with early cut-offs
if (root==null || root==leaf1 || root==leaf2)
return root;
TreeNode left=firstCommonAncestorRecursive(root.left, leaf1, leaf2);
if (done)
return ancestor;
TreeNode right=firstCommonAncestorRecursive(root.right, leaf1, leaf2);
if (done)
return ancestor;
if (left==null)
return right;
else if (right==null)
return left;
else if (left!=null && right!=null)
{
if (ancestor==null)
{
ancestor=root;
done=true;
}
return ancestor;
}
return ancestor;
}
public static void main(String[] args)
{
TreeNode root=new TreeNode(1);
root.left=new TreeNode(2);
root.right=new TreeNode(3);
root.left.left=new TreeNode(4);
root.left.right=new TreeNode(5);
root.right.left=new TreeNode(6);
root.right.right=new TreeNode(7);
root.left.left.left=new TreeNode(8);
root.left.left.right=new TreeNode(9);
root.right.left.left=new TreeNode(10);
root.right.left.right=new TreeNode(11);
root.right.right.right=new TreeNode(12);
System.out.println(root.toStringAll());
ID2319 wpd=new ID2319();
System.out.println(wpd.firstCommonAncestor(root, root.left.left.right, root.right.right.right));
System.out.println(wpd.firstCommonAncestor(root, root.left.left.right, root.left.right));
System.out.println(wpd.firstCommonAncestor(root, root.left.left.right, new TreeNode(14)));
System.out.println(wpd.firstCommonAncestor(root, root.left.left.right, null));
}
}
The tree in the question is not a binary search tree.
- wangpidong October 15, 2013XOR does work, no need to check duplicated characters:
public class ID62240
{
public void reverse(char[] string)
{// swap two numbers without temp variables
int n=string.length;
int left=0;
int right=n-1;
while (left<right)
{
// swap
string[left]=(char)(string[left]^string[right]);
string[right]=(char)(string[left]^string[right]);
string[left]=(char)(string[left]^string[right]);
// next
left++;
right--;
}
}
public static void main(String[] args)
{
ID62240 wpd=new ID62240();
String input="abcdefg12a";
char[] string=input.toCharArray();
wpd.reverse(string);
for (char c: string)
System.out.print(c);
System.out.println();
}
}
Questions: does any node contain a negative value? If yes, then the cut off can not be done so easily. E.g. if the target sum is 5 and the tree is as follows:
Tree:
5
/
-1
\
1
An iterative solution: level by level with constant space (no stack/queue).
An recursive solution: using a HashMap to record the current first node of each level, each time we deal with the current root node first and then its right child and then its left child.
Another recursive solution: adapted from the iterative solution.
public class ID17808664
{
private HashMap<Integer, TreeNode> m_level2firstNode=new HashMap<Integer, TreeNode>();
public void linkSiblingRecursion(TreeNode root)
{// recursion with recording the current first node for each level in HashMap
linkSiblingRecursion(root, 0);
}
private void linkSiblingRecursion(TreeNode root, int level)
{// root, right, left
if (root==null)
return;
// the current first node on the same level as root
TreeNode currentFirstNode=m_level2firstNode.get(level);
root.next=currentFirstNode;
m_level2firstNode.put(level, root);// update
// next level
linkSiblingRecursion(root.right, level+1);
linkSiblingRecursion(root.left, level+1);
}
public void linkSiblingRecursion2(TreeNode root)
{// essentially it is still iteration
if (root==null)
return;
TreeNode firstOfNextLevel=root;
// one level down
TreeNode parent=firstOfNextLevel;
firstOfNextLevel=null;
TreeNode previous=null;
TreeNode node=null;
while (parent!=null)
{
if (parent.left!=null)
{
node=parent.left;
if (previous!=null)
previous.next=node;
else
firstOfNextLevel=node;
previous=node;
}
if (parent.right!=null)
{
node=parent.right;
if (previous!=null)
previous.next=node;
else
firstOfNextLevel=node;
previous=node;
}
parent=parent.next;
}
linkSiblingRecursion2(firstOfNextLevel);
}
public void linkSiblingIteration(TreeNode root)
{// level by level
TreeNode firstOfNextLevel=root;
while (firstOfNextLevel!=null)
{
// one level down
TreeNode parent=firstOfNextLevel;
firstOfNextLevel=null;
TreeNode previous=null;
TreeNode node=null;
while (parent!=null)
{
if (parent.left!=null)
{
node=parent.left;
if (previous!=null)
previous.next=node;
else
firstOfNextLevel=node;
previous=node;
}
if (parent.right!=null)
{
node=parent.right;
if (previous!=null)
previous.next=node;
else
firstOfNextLevel=node;
previous=node;
}
parent=parent.next;
}
}
}
public static void main(String[] args)
{
ID17808664 wpd=new ID17808664();
TreeNode root=wpd.new TreeNode(1);
root.left=wpd.new TreeNode(2);
root.right=wpd.new TreeNode(3);
root.left.left=wpd.new TreeNode(4);
root.left.right=wpd.new TreeNode(5);
root.right.left=wpd.new TreeNode(6);
root.right.right=wpd.new TreeNode(7);
root.left.left.left=wpd.new TreeNode(8);
root.left.left.right=wpd.new TreeNode(9);
root.right.left.left=wpd.new TreeNode(10);
root.right.left.right=wpd.new TreeNode(11);
root.right.right.right=wpd.new TreeNode(12);
System.out.println(root.toStringAll());
wpd.linkSiblingIteration(root);
System.out.println(root.toStringAll());
root=wpd.new TreeNode(1);
root.left=wpd.new TreeNode(2);
root.right=wpd.new TreeNode(3);
root.left.left=wpd.new TreeNode(4);
root.left.right=wpd.new TreeNode(5);
root.right.left=wpd.new TreeNode(6);
root.right.right=wpd.new TreeNode(7);
root.left.left.left=wpd.new TreeNode(8);
root.left.left.right=wpd.new TreeNode(9);
root.right.left.left=wpd.new TreeNode(10);
root.right.left.right=wpd.new TreeNode(11);
root.right.right.right=wpd.new TreeNode(12);
wpd.linkSiblingRecursion(root);
System.out.println(root.toStringAll());
root=wpd.new TreeNode(1);
root.left=wpd.new TreeNode(2);
root.right=wpd.new TreeNode(3);
root.left.left=wpd.new TreeNode(4);
root.left.right=wpd.new TreeNode(5);
root.right.left=wpd.new TreeNode(6);
root.right.right=wpd.new TreeNode(7);
root.left.left.left=wpd.new TreeNode(8);
root.left.left.right=wpd.new TreeNode(9);
root.right.left.left=wpd.new TreeNode(10);
root.right.left.right=wpd.new TreeNode(11);
root.right.right.right=wpd.new TreeNode(12);
wpd.linkSiblingRecursion2(root);
System.out.println(root.toStringAll());
}
public class TreeNode
{
public TreeNode left=null;
public TreeNode right=null;
public TreeNode next=null;
int val;
public TreeNode(int v)
{
val=v;
}
public String toString()
{
return String.format("[TreeNode: val=%d]", val);
}
public String toStringAll()
{
return String.format("[TreeNode: val=%d, left=%s, right=%s, next=%s]", val,
(left!=null) ? left.toStringAll() : null,
(right!=null) ? right.toStringAll() : null,
next);
}
}
}
What about the following two cases?
{4,1,4,4,4,4,4,4,4,4}
{1,2,3,4} (i.e., no rotation)
This question has a trap: whether the sorted array has duplicates. E.g., if the input is {4,1,4,4,4,4,4,4,4}, then this solution will fail. Correct me if I was wrong. Thanks.
- wangpidong October 13, 2013A solution in Java with test cases. I use two while loops. Each time I reverse the next n nodes. I do not use stack to save space, because we can always reverse a list by inserting the next node after the new head node. Time O(n), Space O(1).
public class LinkedListNode
{
public LinkedListNode next=null;
public int val=Integer.MIN_VALUE;
public LinkedListNode(int v)
{
this(v, null);
}
public LinkedListNode(int v, LinkedListNode node)
{
val=v;
next=node;
}
public String toString()
{
return String.format("[LinkedListNode: val=%d]", val);
}
public String toStringAll()
{
return String.format("[LinkedListNode: val=%d, next=%s]", val, (next!=null) ? next.toStringAll() : null);
}
public static void main(String[] args)
{
LinkedListNode head=new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5,
new LinkedListNode(6))))));
System.out.println(head.toStringAll());
}
}
public class ID15138683
{
public LinkedListNode reverse(LinkedListNode head, int n)
{
LinkedListNode newHead=new LinkedListNode(-1);
LinkedListNode tail=newHead;
LinkedListNode node=head;
LinkedListNode tempHead=newHead;
while (node!=null)
{
int index=0;
while (node!=null && index<n)
{
if (tempHead.next==null)
tail=node;
// insert node after tempHead to finally get a reversed list of the n nodes
LinkedListNode nextNode=node.next;
node.next=tempHead.next;
tempHead.next=node;
node=nextNode;
index++;
}
tempHead=tail;
}
return newHead.next;
}
public static void main(String[] args)
{
LinkedListNode head=new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5,
new LinkedListNode(6,
new LinkedListNode(7)))))));
System.out.println(head.toStringAll());
ID15138683 wpd=new ID15138683();
System.out.println(wpd.reverse(head, 3).toStringAll());
System.out.println(wpd.reverse(null, 1));
}
}
My solution is a recursive traversal with recording the parent node of the current node and whether the current node is the left child of its parent node. A test case and class TreeNode are attached also.
public class TreeNode
{
public TreeNode left=null;
public TreeNode right=null;
int val;
public TreeNode(int v)
{
val=v;
}
public String toString()
{
return String.format("[TreeNode: val=%d]", val);
}
public String toStringAll()
{
return String.format("[TreeNode: val=%d, left=%s, right=%s]", val,
(left!=null) ? left.toStringAll() : null,
(right!=null) ? right.toStringAll() : null);
}
}
public class ID60068
{
public ArrayList<TreeNode> reverseBinaryTree(TreeNode root)
{
ArrayList<TreeNode> resultList=new ArrayList<TreeNode>();
reverseBinaryTree(root, null, true, resultList);
return resultList;
}
private void reverseBinaryTree(TreeNode root, TreeNode parentNode, boolean isLeft, ArrayList<TreeNode> resultList)
{
if (root==null)
return;
reverseBinaryTree(root.left, root, true, resultList);
reverseBinaryTree(root.right, root, false, resultList);
if (root.left==null && root.right==null)
resultList.add(root);
if (isLeft)
{// originally this node is the left child of its parent node
root.left=null;
root.right=parentNode;
}
else
{
root.left=parentNode;
root.right=null;
}
}
public static void main(String[] args)
{
TreeNode root=new TreeNode(1);
root.left=new TreeNode(2);
root.right=new TreeNode(3);
root.left.left=new TreeNode(4);
root.left.right=new TreeNode(5);
root.right.left=new TreeNode(6);
root.right.right=new TreeNode(7);
System.out.println(root.toStringAll());
ID60068 wpd=new ID60068();
System.out.println(wpd.reverseBinaryTree(root));
}
}
This solution is quite incomplete, e.g., for
- wangpidong October 20, 2013(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,2)