Jason.WengPengfei
BAN USERI don't know if anyone will read this very late solution, but I think I have a very interesting one. : )
The basic idea is to mark the number we have found. If we find m, we will modify a[m-1].
BUT BUT, I don't modify the value of a[m-1], I change the signal (positive or negative).
If we find m, then point to a[m-1], but we find a[m-1] < 0 (I don't care the value in a[m-1], just the signal), then m is the duplicate!
Only assumption is that all numbers are positive, which is guaranteed by the description. Here is the code:
public static int findDuplicates(int[] a)
{
for (int i=0; i<a.length; i++)
{
int index = Math.abs(a[i]);
if (a[index-1] < 0)
return index;
else
a[index-1] = -a[index-1];
}
return -1; //which won't happen, but in case.
}
I write this in Java. Plz feel free to comment.
public static String reverseWord(String s)
{
String result = "";
String word = "";
for (int i=s.length()-1; i>=0; i--)
{
if ((s.charAt(i)>='a' && s.charAt(i)<='z') || (s.charAt(i)>='A' && s.charAt(i)<='T'))
word = s.charAt(i) + word;
else
{
result += word + " ";
word = "";
}
}
result += word; // easy to forget this one!
return result;
}
I think my solution works for no duplicates. It takes O(depth) time and O(1) space. The basic idea is to store the most possible succ till now, which means the node with a value bigger than target but smaller than all the nodes we have checked.
Here is the code, if you find any bugs plz comment. : )
public static TreeNode findSuccessor(TreeNode root, TreeNode target)
{
boolean found = false;
TreeNode succ = null;
while (root != null)
{
if (root == target)
{
found = true;
root = root.right;
}
else if (root.data > target.data)
{
succ = root;
root = root.left;
}
else
root = root.right;
}
return found? succ: null;
}
I also use stack, and write in java. The code is short and pass the example above. I wonder if there are bugs. Plz comment if you find some.
public static ListNode reverseList(ListNode node, int n)
{
ListNode head = new ListNode(0);
ListNode current = head;
Stack<ListNode> stack = new Stack<ListNode>();
while (node != null)
{
if (stack.size() < n)
{
stack.push(node);
node = node.next;
continue;
}
while (!stack.isEmpty())
{
current.next = stack.pop();
current = current.next;
}
}
while (!stack.isEmpty())
{
current.next = stack.pop();
current = current.next;
}
current.next = null;
return head.next;
}
An O(lgn) solution. the result is like { 0 0 1 0 1 0 2 2 1 0 0}, means the elements with the same group number are in the same group.
{
public static int[] consecutiveGroup(int[] a)
{
int[] result = new int[a.length];
HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();
for (int i=0; i<a.length; i++)
{
hmap.put(a[i], i);
}
Arrays.sort(a);
int groupNum = 0;
for (int i=0; i<a.length; i++)
{
result[hmap.get(a[i])] = groupNum;
if (i+1<a.length && a[i+1]>a[i]+1)
{
groupNum++;
}
}
return result;
}
}
I write this in Java. I think this is more easy to understand, but maybe not short enough.
{
public double calculateWaterVol(double c, double l, int kth)
{
// the first cup is numbered as 1, not 0.
int height = 1;
int currentTotal = height;
double water[] = new double[kth];
water[0] = l;
for (int i=1; i<kth; i++)
{
if (i > currentTotal)
{
height++;
currentTotal += height;
}
if (water[i-1] > c)
{
double overLoad = (water[i-1] - c)/2;
int leftChild = i + height;
int rightChild = i + height + 1;
if (leftChild > kth)
break;
else
water[leftChild-1] = overLoad;
if (rightChild > kth)
break;
else
water[rightChild-1] = overLoad;
water[i-1] = c;
}
}
return water[kth-1]>c? c: water[kth-1];
}
}
I have questions about the duplicates. for example, sum = 8; a[] = {3 3 4 4 4 5 5}, then i think you should return seven group of indice. (0 6) (0 5) (1 6) (1 5) (2 3) (3 4) (2 4). But I'm afraid your code cannot do this.
- Jason.WengPengfei March 28, 2013