math
089.Gray-Code (M+) (aka. 1238. Circular Permutation in Binary Representation) 233.Number-of-Digit-One (H-) 458.Poor-Pigs (H) 400.n-th-digit (M) 441.Arranging-Coins (M-) 628.Maximum-Product-of-Three-Numbers (M) 672.Bulb-Switcher-II (H) 754.Reach-a-Number (H) 829.Consecutive-Numbers-Sum (M) 878.Nth-Magical-Number (M+) 883.Projection-Area-of-3D-Shapes (E+) 891.Sum-of-Subsequence-Widths (M+) 899.Orderly-Queue (M) 963.Minimum-Area-Rectangle-II (H-) 964.Least-Operators-to-Express-Number (H) 972.Equal-Rational-Numbers (H) 1012.Numbers-With-Repeated-Digits (H-) 1017.Convert-to-Base--2 (M+) 1073.Adding-Two-Negabinary-Numbers (H-) 1025.Divisor-Game (M) 1040.Moving-Stones-Until-Consecutive-II (H) 1015.Smallest-Integer-Divisible-by-K (M+) 1103.Distribute-Candies-to-People (M+) 1330.Reverse-Subarray-To-Maximize-Array-Value (TBD) 1250.Check-If-It-Is-a-Good-Array (M+) 1605.Find-Valid-Matrix-Given-Row-and-Column-Sums (M+) 1680.Concatenation-of-Consecutive-Binary-Numbers (M) 1739.Building-Boxes (H-) 1806.Minimum-Number-of-Operations-to-Reinitialize-a-Permutation (H) 1969.Minimum-Non-Zero-Product-of-the-Array-Elements (M+)
Distances
296.Best-Meeting-Point (M+) 1131.Maximum-of-Absolute-Value-Expression (H) 1515.Best Position for a Service Centre (TBD) 1703.Minimum-Adjacent-Swaps-for-K-Consecutive-Ones (H) 1956.Minimum-Time-For-K-Virus-Variants-to-Spread (H+)
Geometry
223.Rectangle-Area (M+) 335.Self-Crossing (H) 391.Perfect-Rectangle (H) 587.Erect-the-Fence (H) 593.Valid-Square (H) 858.Mirror-Reflection (H) 1401.Circle-and-Rectangle-Overlapping (H) 1453.Maximum-Number-of-Darts-Inside-of-a-Circular-Dartboard (H) 1610.Maximum-Number-of-Visible-Points (H)
Random Pick
382.Linked-List-Random-Node (H) 470.Implement-Rand10()-Using-Rand7() (M+) 478.Generate-Random-Point-in-a-Circle (H-) 497.Random-Point-in-Non-overlapping-Rectangles (M+) 519.Random-Flip-Matrix (H-) 528.Random-Pick-with-Weight (H-) 710.Random-Pick-with-Blacklist (M+) 1227.Airplane-Seat-Assignment-Probability (M+)
Random pattern
Reservoir sampling: sample k from n
Example problems: Shuffle an array, Random pick index, Linked list random node.
public List<Integer> sample( List<Integer> list, int k )
{
final List<Integer> samples = new ArrayList<Integer>( k );
int count = 0;
final Random random = new Random();
for ( Integer item : list )
{
if ( count < k )
{
samples.add( item );
}
else
{
// http://en.wikipedia.org/wiki/Reservoir_sampling
// In effect, for all i, the ith element of S is chosen to be included in the reservoir with probability
// k/i.
int randomPos = random.nextInt( count );
if ( randomPos < k )
{
samples.set( randomPos, item );
}
}
count++;
}
return samples;
}
Combinatorics
046.Permutations (M+) 047.Permutations-II (H) 060.Permutation-Sequence (H) 077.Combinations (H-) 1286.Iterator-for-Combination (M+) 1359.Count-All-Valid-Pickup-and-Delivery-Options (M+) 1467.Probability-of-a-Two-Boxes-Having-The-Same-Number-of-Distinct-Balls (H-) 1641.Count-Sorted-Vowel-Strings (M+) 1643.Kth-Smallest-Instructions (M+) 1735.Count-Ways-to-Make-Array-With-Product (H) 1830.Minimum-Number-of-Operations-to-Make-String-Sorted (H) 1866.Number-of-Ways-to-Rearrange-Sticks-With-K-Sticks-Visible (H) 1916.Count-Ways-to-Build-Rooms-in-an-Ant-Colony (H)
Generate all unique permutations
void generatePerms( List<List<Integer>> allPerms, List<Integer> onePerm, int[] nums, boolean[] isUsed )
{
if ( onePerm.size() == nums.length )
{
allPerms.add( new LinkedList<>( onePerm ) );
return;
}
for ( int i = 0 ; i < nums.length; i++ )
{
if ( !isUsed[i] )
{
if ( i > 0 && nums[i] == nums[i-1] && !isUsed[i-1] )
{
continue;
}
isUsed[i] = true;
onePerm.add( nums[i] );
generatePerms( allPerms, onePerm, nums, isUsed );
onePerm.remove( onePerm.size( ) - 1 );
isUsed[i] = false;
}
}
}
Generate all subsets
void generateSubsets( List<List<Integer>> allSubsets, LinkedList<Integer> oneSubset, int[] nums, int startPos )
{
if ( startPos > nums.length )
{
return;
}
allSubsets.add( new LinkedList<>( oneSubset ) );
for ( int i = startPos; i < nums.length; i++ )
{
if ( i > startPos
&& nums[i] == nums[i-1] )
{
continue;
}
oneSubset.addLast( nums[i] );
generateSubsets( allSubsets, oneSubset, nums, i + 1 );
oneSubset.removeLast( );
}
}
Generate all combinations summing to a target
void generateCombs( List<List<Integer>> allCombs, LinkedList<Integer> oneComb, int[] nums, int startPos, int targetSum )
{
if ( targetSum < 0 || startPos >= nums.length )
{
return;
}
if ( targetSum == 0 )
{
allCombs.add( new LinkedList<>( oneComb ) );
return;
}
for ( int i = startPos; i < nums.length; i++ )
{
oneComb.addLast( nums[i] );
generateCombs( allCombs, oneComb, nums, i, targetSum - nums[i] );
oneComb.removeLast( );
}
}
Numerical Theory
343.Integer-Break (H-) 365.Water-and-Jug-Problem (H) 1808.Maximize-Number-of-Nice-Divisors (H-)
Last updated