yitonghe00’s gists

yitonghe00 / 29. Divide Two Integers (#1 Binary search + recursion).java

Last active October 21, 2019 03:56

29. Divide Two Integers (https://leetcode.com/problems/divide-two-integers/): Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero.

	// Binary search solution
	// Time: O(logn) where n is the quotient, 1ms
	// Space: O(1), 33,7mb
	class Solution {
	public int divide(int dividend, int divisor) {
	int sign = 1;
	if((dividend < 0 && divisor > 0) \|\| (dividend > 0 && divisor < 0)) {
	sign = -1;
	}
	long ldividend = Math.abs((long) dividend);

yitonghe00 / 69. Sqrt(x) (#1 Binary search + long type).java

Last active October 21, 2019 06:49

69. Sqrt(x) (https://leetcode.com/problems/sqrtx/submissions/): Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

	class Solution {
	public int mySqrt(int x) {
	//Solution #1: Cast to long type to avoid overflow
	//Corner case: x == 0
	if(x == 0) {
	return 0;
	}
	long begin = 1, end = (long)x - 1, mid;

	while(begin < end - 1) {

yitonghe00 / 29. Divide Two Integers.java

Last active June 12, 2018 12:53 — forked from Siyu-Lei/29. Divide Two Integers.java

By Siyu Lei

	class Solution {
	public int divide(int dividend, int divisor) {
	if (dividend == Integer.MIN_VALUE && divisor == -1) {
	return Integer.MAX_VALUE;
	}
	boolean sign = (dividend > 0) ^ (divisor > 0);
	long dvd = Math.abs((long) dividend);
	long dvs = Math.abs((long) divisor);
	int res = 0;
	while (dvd >= dvs) {

yitonghe00 / 153. Find Minimum in Rotated Sorted Array (#1 Binary search).java

Last active October 22, 2019 17:13

153. Find Minimum in Rotated Sorted Array (https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/): Suppose an array sorted in ascending order 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.

	// Binary search solution: min always lies in the rotated half
	// Time: O(logn), 0ms
	// Space: O(1), 38.2mb
	class Solution {
	public int findMin(int[] nums) {
	// Corner case: 1 element
	if(nums.length == 1) {
	return nums[0];
	}

yitonghe00 / 154. Find Minimum in Rotated Sorted Array II (#1 Binary search + linear search).java

Last active December 24, 2021 17:33

154. Find Minimum in Rotated Sorted Array II (Contains duplicates) (https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/): Suppose an array sorted in ascending order 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.

	// Binary search solution: min always lies in the rotated half
	// Modified from 153: To deal with duplicates, scan through when begin == mid == end
	// Note: take care of equal when comparing
	// Time: O(n), 0ms
	// Space: O(1), 38.2mb
	class Solution {
	public int findMin(int[] nums) {
	// Corner case: 1 element
	if(nums.length == 1) {
	return nums[0];

yitonghe00 / 275. H-Index II (#1 Search in value).java

Last active May 28, 2018 11:04

275. H-Index II

	//Find the h in the range of [0, citations.length], not in the array
	//Runtime: O(logn) 14ms
	class Solution {//[0,3,3] [3,3,3] [] [0] [0,0] [2] [0,0,4,4] [0,1,1,2]
	public int hIndex(int[] citations) {
	int begin = 0, end = citations.length, mid, h = 0;
	if(citations.length > 0) {
	h = Math.min(citations.length, citations[0]);
	}

	while(begin <= end) {

yitonghe00 / 278. First Bad Version (#1 ).java

Created May 28, 2018 14:50

278. First Bad Version

	/* The isBadVersion API is defined in the parent class VersionControl.
	boolean isBadVersion(int version); */

	public class Solution extends VersionControl {
	public int firstBadVersion(int n) {
	int begin = 0, end = n, mid;

	while(begin < end) {
	mid = begin + (end - begin) / 2;

yitonghe00 / 436. Find Right Interval (#1 Binary Search + HashTable).java

Last active November 10, 2019 22:01

436. Find Right Interval

	// Binary Sort + HashTable solution: do binary search for each interval with the help of helper map and array (sort)
	// Time: O(nlogn), 15ms
	// Space: O(n), 46.5mb
	class Solution {
	public int[] findRightInterval(int[][] intervals) {
	int len = intervals.length;
	int[] array = new int[len];
	Map<Integer, Integer> map = new HashMap<> ();
	int[] ans = new int[len];

yitonghe00 / 3. Longest Substring Without Repeating Characters (#1 Two pointer substring).java

Last active October 29, 2019 20:19

3. Longest Substring Without Repeating Characters

	// Two pointer solution: min/max substring templete
	// Time: O(n), 2ms
	// Space: O(1), 37.4mb
	class Solution {
	public int lengthOfLongestSubstring(String s) {
	// char table that keeps track of characters we have met
	int[] table = new int[128];
	int count = 0; // Count of unique char

	int begin = 0, end = 0, maxLen = 0; // Window is [begin, end)

yitonghe00 / 11. Container With Most Water (#1 Two Pointers).java

Last active October 25, 2019 05:01

11. Container With Most Water (https://leetcode.com/problems/container-with-most-water/): Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, suc…

	// Two pointer: begin/end pointers and move inward
	// Time: O(n), 2ms
	// Space: O(1), 39.9mb
	class Solution {
	public int maxArea(int[] height) {
	int left = 0, right = height.length - 1;
	int max = 0;

	while(left < right) {
	max = Math.max(max, Math.min(height[left], height[right]) * (right - left));

YitongHe yitonghe00