Two Sum III - Data structure design @LeetCode

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

	import java.util.HashMap;
	import java.util.Map;
	// case: add(0) -> find(0) -> should be false
	public class TwoSumIII {
	Map<Integer, Integer> dict = new HashMap<Integer, Integer>();
	public void add(int number) {
	if (dict.containsKey(number)) {
	dict.put(number, dict.get(number) + 1);
	} else {
	dict.put(number, 1);
	}
	}
	public boolean find(int value) {
	for (Integer key : dict.keySet()) {
	if (value - key == key) {
	if (dict.get(key) >= 2) {
	return true;
	}
	} else if (dict.containsKey(value - key)) {
	return true;
	}
	}
	return false;
	}
	public static void main(String[] args) {
	TwoSumIII util = new TwoSumIII();
	util.add(1);
	util.add(3);
	util.add(5);
	System.out.println(util.find(4));
	System.out.println(util.find(7));
	}
	}

view raw TwoSumIII.java hosted with ❤ by GitHub

Two Sum II - Input array is sorted @LeetCode

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

	public class TwoSumII {
	public int[] twoSum(int[] numbers, int target) {
	int[] result = {-1, -1};
	if (numbers == null || numbers.length == 0) {
	return result;
	}
	int start = 0;
	int end = numbers.length - 1;
	while (start < end) {
	int sum = numbers[start] + numbers[end];
	if (sum == target) {
	result[0] = start + 1;
	result[1] = end + 1;
	break;
	} else if (sum < target) {
	start++;
	} else {
	end--;
	}
	}
	return result;
	}
	}

view raw TwoSumII.java hosted with ❤ by GitHub

Factorial Trailing Zeroes @LeetCode

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

	/*
	* Trailing zeros of n!
	*
	* take care Integer OverFlow
	* Reference:
	* http://www.purplemath.com/modules/factzero.htm
	* http://www.cnblogs.com/EdwardLiu/p/4207498.html
	*/
	public class TrailingZeroes {
	public static int trailingZeroes(int n) {
	if (n < 0) {
	n = -1* n;
	}
	int result = 0;
	for (int i = 5; n / i >= 1; n = n / 5) {
	result += n / i;
	}
	return result;
	}
	public static void main(String[] args) {
	System.out.println(trailingZeroes(1808548329));
	}
	}

view raw TrailingZeroes.java hosted with ❤ by GitHub

Read N Characters Given Read4 II - Call multiple times @LeetCode

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function may be called multiple times.

	/*
	* The read function may be called multiple times.
	* The previous one we can't use it for multiple times since read4 actually read more and break continuity.
	* This one will sovle that problem. read the buffer used last time.(through offset)
	*/
	public class Read4KII {
	// reused variable.
	private char[] buffer = new char[4];
	private int bufsize = 0;
	private int offset = 0;
	public int read(char[] buf, int n) {
	int total = 0;
	boolean eof = true;
	while (eof && total < n) {
	if (bufsize == 0) {
	bufsize = read4(buffer);
	if (bufsize < 4) {
	eof = false;
	}
	}
	int bytes = Math.min(n - total, bufsize);
	System.arraycopy(buffer, offset, buf, total, bytes);
	offset = (offset + bytes) % 4;
	bufsize -= bytes;
	total += bytes;
	}
	return total;
	}
	// API funciton
	public int read4(char[] buf) {
	return 0;
	}

view raw Read4KII.java hosted with ❤ by GitHub

Read N Characters Given Read4 @LeetCode

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

	/* The read4 API is defined in the parent class Reader4.
	int read4(char[] buf); */
	// Implement readline using read 4k
	public class Read4KI {
	//public class Read4KI extends Reader4 {
	/**
	* @param buf Destination buffer
	* @param n Maximum number of characters to read
	* @return The number of characters read
	*/
	public int read(char[] buf, int n) {
	char[] buffer = new char[4];
	boolean eof = true;
	int total = 0;
	while (eof && total < n) {
	int temp = read4(buffer);
	if (temp < 4) {
	eof = false;
	}
	int bytes = Math.min(n - total, temp);
	System.arraycopy(buffer, 0, buf, total, bytes);
	total += bytes;
	}
	return total;
	}
	// API funciton
	public int read4(char[] buf) {
	return 0;
	}
	}

view raw Read4KI.java hosted with ❤ by GitHub

Min Stack @LeetCode

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

	import java.util.HashMap;
	import java.util.Map;
	import java.util.Stack;
	public class MinStack {
	// retrieving the minimum element in constant time.
	Stack<Integer> stack = new Stack<Integer>();
	Stack<Integer> minStack = new Stack<Integer>();
	Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
	public void push(int x) {
	if (x == getMin()) {
	cache.put(x, cache.get(x) + 1);
	}
	if (x < getMin()) {
	minStack.push(x);
	cache.put(x, 1);
	}
	stack.push(x);
	}
	public void pop() {
	int value = stack.pop();
	if (value == getMin()) {
	if (cache.get(value) == 1) {
	minStack.pop();
	}
	cache.put(value, cache.get(value) - 1);
	}
	}
	public int top() {
	return stack.peek();
	}
	public int getMin() {
	if (minStack.isEmpty()) {
	return Integer.MAX_VALUE;
	} else {
	return minStack.peek();
	}
	}

view raw MinStack.java hosted with ❤ by GitHub

Majority Element @LeetCode

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

	/*
	* O(1) space, O(n) one pass -- one candidate, one candidate occurance.
	*
	* when we meet two numbers different, throw them together, same, count in.
	* if count = 0, change candidate to next value.
	*/
	public class MajorityNumber {
	public int majorityElement(int[] num) {
	int candidate = num[0];
	int count = 1;
	for (int i = 0; i < num.length; i++) {
	if (count == 0) {
	candidate = num[i];
	count++;
	} else {
	if (candidate == num[i]) {
	count++;
	} else {
	count--;
	}
	}
	}
	return candidate;
	}
	}

view raw MajorityNumber.java hosted with ❤ by GitHub

Largest Number @LeetCode

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

	import java.util.Arrays;
	import java.util.Comparator;
	/*
	* Integer Camparation is complicated, Transfer to string, connect s1+s2 and s2+s1.
	*/
	public class LargestNumber {
	// For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
	public static String largestNumber(int[] num) {
	if (num == null || num.length == 0) {
	return "";
	}
	String[] array = new String[num.length];
	for (int i = 0; i < num.length; i++) {
	array[i] = String.valueOf(num[i]);
	}
	Arrays.sort(array, comparator);
	String result = "";
	for (String str: array) {
	result = str + result;
	}
	int i = 0;
	while (i < result.length() - 1) {
	if (result.charAt(i) != '0') {
	break;
	}
	i++;
	}
	return result.substring(i);
	}
	public static Comparator<String> comparator = new Comparator<String>() {
	@Override
	public int compare(String o1, String o2) {
	String comb1 = o1 + o2;
	String comb2 = o2 + o1;
	return comb1.compareTo(comb2);
	}
	};
	public static void main(String[] args) {
	int[] num = {0, 0};
	System.out.println(largestNumber(num));
	}
	}

view raw LargestNumber.java hosted with ❤ by GitHub

Intersection of Two Linked Lists @LeetCode

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

	public class IntersectionOfTwoList {
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	if (headA == null || headB == null) {
	return null;
	}
	int lengthA = getLength(headA);
	int lengthB = getLength(headB);
	if (lengthA > lengthB) {
	for (int i = 0; i < lengthA - lengthB; i++) {
	headA = headA.next;
	}
	} else {
	for (int i = 0; i < lengthB - lengthA; i++) {
	headB = headB.next;
	}
	}
	while (headA != null && headB != null) {
	if (headA == headB) {
	return headA;
	}
	headA = headA.next;
	headB = headB.next;
	}
	return null;
	}
	private int getLength(ListNode head) {
	int length = 0;
	while (head != null) {
	head = head.next;
	length++;
	}
	return length;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
	val = x;
	next = null;
	}
	}
	}

view raw IntersectionOfTwoList.java hosted with ❤ by GitHub

Find Peak Element @LeetCode

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

	public class FindPeakElement {
	// test case: [3,2,1] [2,1]
	public static int findPeakElement(int[] num) {
	if (num == null || num.length == 0) {
	return -1;
	}
	int start = 0;
	int end = num.length - 1;
	while (start + 1 < end) {
	int mid = start + (end - start) / 2;
	if (num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) {
	return mid;
	}
	if (num[mid] < num[start]) {
	end = mid;
	} else {
	start = mid;
	}
	}
	return num[start] > num[end] ? start :end;
	}
	public static void main(String[] args) {
	int[] num = {1,2};
	System.out.println(findPeakElement(num));
	}
	}

view raw findPeakElement.java hosted with ❤ by GitHub

Find Minimum in Rotated Sorted Array II @LeetCode

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

	public class FindMinRotatedSortedArrayII {
	public static int findMin(int[] num) {
	if (num == null || num.length == 0) {
	return Integer.MAX_VALUE;
	}
	int min = Integer.MAX_VALUE;
	int start = 0;
	int end = num.length - 1;
	while (start + 1 < end) {
	int mid = start + (end - start) / 2;
	if (num[mid] > num[start]) {
	min = Math.min(min, num[start]);
	start = mid;
	} else if (num[mid] < num[start]){
	min = Math.min(min, num[end]);
	end = mid;
	} else {
	min = Math.min(min, num[start]);
	start++;
	}
	}
	min = Math.min(min, num[start]);
	min = Math.min(min, num[end]);
	return min;
	}
	public static void main(String[] args) {
	int[] num = {5,5,6,7,7,1,2,3,4};
	System.out.println(findMin(num));
	}
	}

view raw FindMinRotatedSortedArrayII.java hosted with ❤ by GitHub

Find Minimum in Rotated Sorted Array @LeetCode

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

	/*
	* if num[mid] > num[start], the minValue is num[start], then we go right
	* same steps when num[mid] < num[start]
	*
	* (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element.
	*
	* Reference: http://blog.csdn.net/linhuanmars/article/details/40449295
	*/
	public class FindMinRotatedSortedArrayI {
	public int findMin(int[] num) {
	if (num == null || num.length == 0) {
	return Integer.MAX_VALUE;
	}
	int min = Integer.MAX_VALUE;
	int start = 0;
	int end = num.length - 1;
	while (start + 1 < end) {
	int mid = start + (end - start) / 2;
	if (num[mid] > num[start]) {
	min = Math.min(min, num[start]);
	start = mid;
	} else {
	min = Math.min(min, num[mid]);
	end = mid;
	}
	}
	min = Math.min(min, num[start]);
	min = Math.min(min, num[end]);
	return min;
	}
	}

view raw FindMinRotatedSortedArrayI.java hosted with ❤ by GitHub

Excel Sheet Column Number @LeetCode

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

	public class ExcelTitleToNumber {
	public static int titleToNumber(String s) {
	if (s == null || s.length() == 0) {
	return 0;
	}
	int result = 0;
	for (int i = s.length() - 1; i >= 0; i--) {
	result += (s.charAt(i) - 'A' + 1 ) * Math.pow(26, s.length() - i - 1);
	}
	return result;
	}
	public static void main(String[] args) {
	System.out.println(titleToNumber("AA"));
	}
	}

view raw ExcelTitleToNumber.java hosted with ❤ by GitHub

Excel Sheet Column Title @LeetCode

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases.

	public class ExcelColumnName {
	public String convertToTitle(int n) {
	if (n <= 0) {
	return null;
	}
	String result = "";
	while (n > 0) {
	int reminder = n % 26;
	n = n / 26;
	if (n == 0) {
	result += 'Z';
	n--;
	} else {
	result += (char)('A' - 1 + reminder);
	}
	}
	return result;
	}
	}

view raw ExcelColumnName.java hosted with ❤ by GitHub

Word Break II @LeetCode

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

	// Reference: http://blog.sina.com.cn/s/blog_eb52001d0102v2hr.html
	// 优化重点是用HashMap 记录已经切割过的String，避免重复计算
	public List<String> wordBreak(String s, Set<String> dict) {
	if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
	return null;
	}
	Map<String, List<String>> map = new HashMap<String, List<String>>();
	return dfs(s, dict, map);
	}
	private List<String> dfs(String s, Set<String> dict, Map<String, List<String>> map) {
	if (map.containsKey(s)) {
	return map.get(s);
	}
	List<String> list = new ArrayList<String>();
	int length = s.length();
	if (s.length() == 0) {
	list.add("");
	} else {
	for (int i = 1; i <= length; i++) {
	String prefix = s.substring(0, i);
	if (!dict.contains(prefix)) {
	continue;
	}
	List<String> rightList = dfs(s.substring(i, length), dict, map);
	for (String str: rightList) {
	StringBuilder sb = new StringBuilder();
	sb.append(prefix);
	if (i != 0 && i != length) {
	sb.append(" ");
	}
	sb.append(str);
	list.add(sb.toString());
	}
	}
	}
	map.put(s, list);
	return list;
	}

view raw WordBreakII.java hosted with ❤ by GitHub