LintCode - Michael's Blog

First Position of Target

LintCode-14.First Position of Target For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. If the target number does not exist in the array, return -1. Example If the array is [1, 2, 3, 3,

LintCode

Find Minimum in Rotated Sorted Array II

LintCode-160.Find Minimum in Rotated Sorted Array II 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. Notice The array may contain duplicates. Example

LintCode

Remove Duplicates from Unsorted List

LintCode-217.Remove Duplicates from Unsorted List Write code to remove duplicates from an unsorted linked list. Example Given 1->3->2->1->4. Return 1->3->2->4 Challenge (hard) How would you solve this problem if a temporary buffer is not allowed?

LintCode

Longest Words

LintCode-133.Longest Words Given a dictionary, find all of the longest words in the dictionary. Example Given { "dog", "google", "facebook", "internationalization", "blabla" } the longest words are(is) ["internationalization"]. Given { "like", "love", "hate"

LintCode

Rotate List

LintCode-170.Rotate List Given a list, rotate the list to the right by k places, where k is non-negative. Example Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3. /** * Definition for singly-linked list. * public class ListNode

LintCode

Triangle

LintCode-109. Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. Notice Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows

LintCode

Climbing Stairs

LintCode-111.Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Example Given an example n=3 , 1+1+1=2+1=

LintCode

House Robber

LintCode-392.House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if

LintCode

Swap Two Nodes in Linked List

LintCode-511.Swap Two Nodes in Linked List Given a linked list and two values v1 and v2. Swap the two nodes in the linked list with values v1 and v2. It's guaranteed there is no duplicate values in the linked list. If v1 or v2 does not exist in the

LintCode

Max Points on a Line

LintCode-186.Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Example Given 4 points: (1,2), (3,6), (0,0), (1,3). The maximum number is 3. /** * Definition for a point. * class Point { * int

LintCode

Majority Number

LintCode-46. Majority Number Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it. Example Given [1, 1, 1, 1, 2, 2, 2], return 1 Challenge O(n) time and O(1) extra space This problem could

LintCode

Subarray Sum

LintCode-138.Subarray Sum Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number. Notice: There is at least one subarray that it's sum equals to zero. Have you met

LintCode

The Smallest Difference

LintCode-387.The Smallest Difference Given two array of integers(the first array is array A, the second array is array B), now we are going to find a element in array A which is A[i], and another element in array B which is B[j], so that the difference

LintCode

Interleaving Positive and Negative Numbers

LintCode-144.Interleaving Positive and Negative Numbers Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers. Notice: You are not necessary to keep the original order of positive integers or negative integers. Example: Given [-1, -2, -3, 4, 5, 6], after re-range, it

LintCode

Anagrams

LintCode-171.Anagrams Given an array of strings, return all groups of strings that are anagrams. Notice: All inputs will be in lower-case. Example Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"]. Given ["ab"

LintCode

Compare Strings

LintCode-55.Compare Strings Compare two strings A and B, determine whether A contains all of the characters in B. The characters in string A and B are all Upper Case letters. Notice: The characters of B in A are not necessary continuous or ordered. Example: For A = "ABCD"

LintCode

Two Strings Are Anagrams

LintCode-158.Two Strings Are Anagrams Write a method anagram(s,t) to decide if two strings are anagrams or not. Clarification: What is Anagram? Two strings are anagram if they can be the same after change the order of characters. Example: Given s = "abcd", t = "dcab"

LintCode

Binary Tree Path Sum

LintCode-376. Binary Tree Path Sum Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target. A valid path is from root node to any of the leaf nodes. Example: Given a binary tree, and target = 5: 1 / \ 2 4

LintCode

Palindrome Partitioning

LintCode-136.Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Given s = "aab", return: [ ["aa","b"], ["a","a","b"] ] public class

LintCode

Maximum Subarray Difference

LintCode-45.Maximum Subarray Difference Given an array with integers. Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest. Return the largest difference. Notice: The subarray should contain at least one number Example: For [1, 2, -3, 1], return 6. Challenge: O(n) time

LintCode

Maximum Subarray II

LintCode-42.Maximum Subarray II Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum. Notice: The subarray should contain at least one number Example: For given [1, 3, -1, 2, -1, 2], the two

LintCode

Best Time to Buy and Sell Stock III

LintCode-151.Best Time to Buy and Sell Stock III Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Notice: You may not engage in

LintCode

Partition Array by Odd and Even

LintCode-373.Partition Array by Odd and Even Partition an integers array into odd number first and even number second. Example: Given [1, 2, 3, 4], return [1, 3, 2, 4] Challenge: Do it in-place. public class Solution { /** * @param nums: an array of integers * @return: nothing */ public void partitionArray(int[] nums)

LintCode

Trapping Rain Water

LintCode-363.Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. Example: Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. Challenge: O(n)

LintCode

Two Sum Closest

LintCode-533.Two Sum Closest Given an array nums of n integers, find two integers in nums such that the sum is closest to a given number, target. Return the difference between the sum of the two integers and the target. Example: Given array nums = [-1, 2, 1, -4], and target