[ LeetCode #179] Largest Number

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.

public class Solution {
	public String largestNumber(int[] num) {

		String[] NUM = new String[num.length];

		for (int i = 0; i < num.length; i++) {
			NUM[i] = String.valueOf(num[i]);
		}

		java.util.Arrays.sort(NUM, new java.util.Comparator<String>() {
			public int compare(String left, String right) {
				String leftRight = left.concat(right);
				String rightLeft = right.concat(left);
				return rightLeft.compareTo(leftRight);
			}
		});

		java.lang.StringBuffer buffer = new java.lang.StringBuffer();
		for (int i = 0; i < NUM.length; i++) {
			buffer.append(NUM[i]);
		}
		// String result = buffer.toString();
		java.math.BigInteger result = new java.math.BigInteger(
				buffer.toString());
		return result.toString();
	}

	public static void main(String args[]) {
		Solution s = new Solution();
		{
			int A[] = new int[] { 0, 0 };
			String solution = s.largestNumber(A);
			System.out.println("Solution : " + solution);
		}
		{
			int A[] = new int[] { 128, 12, 320, 32 };
			String solution = s.largestNumber(A);
			System.out.println("Solution : " + solution);
		}

		{
			int A[] = new int[] { 3, 30, 34, 5, 9 };
			String solution = s.largestNumber(A);
			System.out.println("Solution : " + solution);
		}

	}
}
Advertisements

[LeetCode #65] Valid Number

Valid Number
Validate if a given string is numeric.

Some examples:
“0” => true
” 0.1 ” => true
“abc” => false
“1 a” => false
“2e10” => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

public class Solution {
	public boolean isNumber(String s) {
		s = s.trim();
		if ( s.isEmpty()) {
			return false;
		}
		
		String regex = "[-+]?(\\d+\\.?|\\.\\d+)\\d*(e[-+]?\\d+)?";
		if ( s.matches(regex)) {
			return true;
		} else {
			return false;
		}
			
	}

	public static void main(String args[]) {
		Solution s = new Solution();
		if (false != s.isNumber("...")) {
			System.out.println("Something is wrong !!!");
		}
		if (true != s.isNumber("0")) {
			System.out.println("Something is wrong !!!");
		}

		if (true != s.isNumber(" 0.1 ")) {
			System.out.println("Something is wrong !!!");
		}
		if (false != s.isNumber("abc")) {
			System.out.println("Something is wrong !!!");
		}
		if (false != s.isNumber("1 a")) {
			System.out.println("Something is wrong !!!");
		}
		if (true != s.isNumber("2e10")) {
			System.out.println("Something is wrong !!!");
		}
	}
}

[LeetCode #75 ] Sort Colors

Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

public class Solution {
	public void sortColors(int[] A) {
		int red = 0;
		int white = 0;
		int blue = 0;

		for (int i = 0; i < A.length; i++) {
			if (A[i] == 0) {
				red++;
			} else if (A[i] == 1) {
				white++;
			} else {
				blue++;
			}
		}
		int index = 0;
		while ( red > 0 ) {
			A[index++] = 0;
			red--;
		}
		while ( white > 0 ) {
			A[index++] = 1;
			white--;
		}
		while ( blue > 0 ) {
			A[index++] = 2;
			blue--;
		}
	}

	public static void main(String args[]) {
		Solution s = new Solution();
		int A[] = new int[] { 0, 1, 2, 0, 0, 1, 0, 1, 0, 2 };
		s.sortColors(A);
	}
}

[LeetCode #2 ] Add Two Numbers

Problem Description : Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

package adongre.solutions.leetcode;

public class ProblemOneTwoSum {
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	public class Solution {
		public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

			java.util.ArrayList<Integer> l1Array = new java.util.ArrayList<Integer>();
			java.util.ArrayList<Integer> l2Array = new java.util.ArrayList<Integer>();

			while (l1 != null) {
				l1Array.add(l1.val);
				l1 = l1.next;
			}

			while (l2 != null) {
				l2Array.add(l2.val);
				l2 = l2.next;
			}
			java.util.Collections.reverse(l1Array);
			java.util.Collections.reverse(l2Array);

			int pow = l1Array.size() - 1;
			long number1 = 0;
			long number2 = 0;
			for (Integer num : l1Array) {
				number1 += num.intValue() * Math.pow(10, pow--);
			}
			pow = l2Array.size() - 1;
			for (Integer num : l2Array) {
				number2 += num.intValue() * Math.pow(10, pow--);
			}
			long result = (number1 + number2);
			if (result == 0) {
				ListNode result1 = new ListNode(0);
				return result1;
			}
			java.util.ArrayList<Integer> r = new java.util.ArrayList<Integer>();
			while (result > 0) {
				r.add((int)(result % 10));
				result /= 10;
			}

			ListNode result1 = new ListNode(r.get(0));
			ListNode tempHead = result1;
			for (int i = 1; i < r.size(); i++) {
				ListNode tempNode = new ListNode(r.get(i));
				tempHead.next = tempNode;
				tempHead = tempNode;
			}

			return result1;
		}
	}

	public static void main(String[] args) {
		ProblemOneTwoSum p = new ProblemOneTwoSum();
		ProblemOneTwoSum.Solution s = p.new Solution();
		{
			ListNode A = p.new ListNode(0);
			ListNode B = p.new ListNode(1);
			ListNode r = s.addTwoNumbers(A, B);
		}

		{
			// {9}, {1,9,9,9,9,9,9,9,9,9}
			ListNode A = p.new ListNode(9);

			ListNode B = p.new ListNode(1);

			ListNode B91 = p.new ListNode(9);
			ListNode B92 = p.new ListNode(9);
			ListNode B93 = p.new ListNode(9);
			ListNode B94 = p.new ListNode(9);
			ListNode B95 = p.new ListNode(9);
			ListNode B96 = p.new ListNode(9);
			ListNode B97 = p.new ListNode(9);
			ListNode B98 = p.new ListNode(9);
			ListNode B99 = p.new ListNode(9);

			B.next = B91;
			B91.next = B92;
			B92.next = B93;
			B93.next = B94;
			B94.next = B95;
			B95.next = B96;
			B96.next = B97;
			B97.next = B98;
			B98.next = B99;
			ListNode r = s.addTwoNumbers(A, B);

		}

		{
			ListNode A = p.new ListNode(2);
			ListNode A4 = p.new ListNode(4);
			ListNode A3 = p.new ListNode(3);

			A.next = A4;
			A4.next = A3;

			ListNode B = p.new ListNode(5);
			ListNode B6 = p.new ListNode(6);
			ListNode B4 = p.new ListNode(4);

			B.next = B6;
			B6.next = B4;

			ListNode r = s.addTwoNumbers(A, B);

		}
		{
			ListNode A = p.new ListNode(0);
			ListNode B = p.new ListNode(0);

			ListNode r = s.addTwoNumbers(A, B);
		}
	}
}

Sum Of Embedded Numbers in a String

A Friend ask a question.
You have given a string which has embedded numbers, characters, special characters for example “ab-2cd34ef89x9a”. You need to find all the numbers from the string and return the sum of those numbers.

In this case number would be -2, 34, 89, 9 , and Sum would be 130

Here is my Java Solution for the same. If you find this is failing for any particular input let me know.

	public static void main(String[] args) {
		//String s1 = "ab-2cd34ef89x9a";
		//String s1 = "111111";
		//String s1 = "111a111";
		//String s1 = "ab-2cd34ef89x9a-";
		//String s1 = "ab-2cd34ef89x9a+";
		//String s1 = "ab-2c-d34ef89x9a+";
		int isNegative = 1;
		int sum = 0;
		java.util.Stack<Integer> numStack = new java.util.Stack<Integer>();
		for(char ch: s1.toCharArray()){
			if ( ch == '-') {
				isNegative = -1;
				continue; //fetch next character
			}
			if ( Character.isDigit(ch)) {
				numStack.push(Character.getNumericValue(ch));				
			} else {
				Iterator<Integer> iterator = numStack.iterator();
				int pow = numStack.size() - 1;
				int embeddedNumber = 0;
				
				while (iterator.hasNext()) {
					int i = (int) iterator.next();
					embeddedNumber += i * Math.pow(10, pow--);
				}
				sum += isNegative * embeddedNumber;
				numStack.clear();
				isNegative = 1;
			}
		}
		Iterator<Integer> iterator = numStack.iterator();
		int pow = numStack.size() - 1;
		int embeddedNumber = 0;
		
		while (iterator.hasNext()) {
			int i = (int) iterator.next();
			embeddedNumber += i * Math.pow(10, pow--);
		}
		sum += isNegative * embeddedNumber;
		
		System.out.println("SUM ==> " + sum);
		
	}