22 posts tagged with "Leetcode"

/**
 * 704. Binary Search
 * <p>
 * Given a sorted (in ascending order) integer array nums of n elements and a target value, write a
 * function to search target in nums. If target exists, then return its index, otherwise return -1.
 * <p>
 * <p>
 * Example 1:
 * <p>
 * Input: nums = [-1,0,3,5,9,12], target = 9
 * Output: 4
 * Explanation: 9 exists in nums and its index is 4
 * <p>
 * Example 2:
 * <p>
 * Input: nums = [-1,0,3,5,9,12], target = 2
 * Output: -1
 * Explanation: 2 does not exist in nums so return -1
 */
public class BinarySearch {

	/**
	 * Iterative binary search
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public int search(int[] nums, int target) {
		int low = 0;
		int high = nums.length - 1;

		while (low <= high) {
			int mid = (low + high) / 2;

			if (nums[mid] == target)
				return mid;

			if (nums[mid] > target) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return -1;
	}

	/**
	 * Recursive binary search
	 *
	 * @param nums
	 * @param low
	 * @param high
	 * @param target
	 * @return index of search element if found else -1
	 */
	public int binarySearch(int[] nums, int low, int high, int target) {
		while (low <= high) {
			int mid = (low + high) / 2;

			if (nums[mid] == target)
				return mid;

			if (nums[mid] > target) {
				return binarySearch(nums, low, mid - 1, target);
			} else {
				return binarySearch(nums, mid + 1, high, target);
			}
		}
		return -1;
	}

}

/**
 * 2. Add Two Numbers
 *
 * You are given two non-empty linked lists representing two non-negative integers. 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.
 * <p>
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 * <p>
 * Example:
 * <p>
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 */
public class AddTwoNumbers {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode output = null;
		int carry = 0;

		ListNode current = null;
		while (l1 != null && l2 != null) {

			int val = (l1.val + l2.val + carry) % 10;
			carry = (l1.val + l2.val + carry) / 10;

			l1 = l1.next;
			l2 = l2.next;

			if (output == null) {
				output = new ListNode(val);
				current = output;
			} else {
				current.next = new ListNode(val);
				current = current.next;
			}
		}


		while (l1 != null) {
			int val = (l1.val + carry) % 10;
			carry = (l1.val + carry) / 10;

			l1 = l1.next;
			current.next = new ListNode(val);
			current = current.next;
		}

		while (l2 != null) {
			int val = (l2.val + carry) % 10;
			carry = (l2.val + carry) / 10;

			l2 = l2.next;
			current.next = new ListNode(val);
			current = current.next;
		}

		if (carry != 0) {
			current.next = new ListNode(carry);
		}
		return output;
	}
}