Algorithm - Michael's Blog

Algorithm

A collection of 10 posts

Sort Colors II

LintCode-143.Sort Colors II [http://www.lintcode.com/en/problem/sort-colors-ii/] Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k. Notice: You are not

Maximum Subarray Difference

LintCode-45.Maximum Subarray Difference [http://www.lintcode.com/en/problem/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,

Best Time to Buy and Sell Stock III

LintCode-151.Best Time to Buy and Sell Stock III [http://www.lintcode.com/en/problem/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

Partition Array by Odd and Even

LintCode-373.Partition Array by Odd and Even [http://www.lintcode.com/en/problem/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

Trapping Rain Water

LintCode-363.Trapping Rain Water [http://www.lintcode.com/en/problem/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,

Two Sum Closest

LintCode-533.Two Sum Closest [http://www.lintcode.com/en/problem/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

Stack Sorting

LintCode-229.Stack Sorting [http://www.lintcode.com/en/problem/stack-sorting] > Sort a stack in ascending order (with biggest terms on top). > You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (e.g. array). > Given stack = | | |3|

Construct Binary Tree from Inorder and Postorder Traversal

LintCode-72.Construct Binary Tree from Inorder and Postorder Traversal [http://www.lintcode.com/en/problem/construct-binary-tree-from-inorder-and-postorder-traversal/] > Given inorder and postorder traversal of a tree, construct the binary tree. > Notice: You may assume that duplicates do not exist in the tree. > Given inorder [1,2,3] and postorder [1,3,2]

Maximum Subarray

LintCode-41.Maximum Subarray [http://www.lintcode.com/en/problem/maximum-subarray/] > Given an array of integers, find a contiguous subarray which has the largest sum. > Notice: The subarray should contain at least one number. > Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,

Find the Connected Component in the Undirected Graph

LintCode-431.Find the Connected Component in the Undirected Graph [http://www.lintcode.com/en/problem/find-the-connected-component-in-the-undirected-graph/] > Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is