Skip to main content

22 posts tagged with "Leetcode"

Hola tag description

View All Tags

Binary Search

· 2 min read
Sandeep Bhardwaj

Binary Search Iterative and Recursive

/**
* 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;
}

}

Add two numbers represented as LinkedList

· 2 min read
Sandeep Bhardwaj

Add two numbers represented as LinkedList

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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

/**
* 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;
}
}