math

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-)

PreviouseverythingNextTree

Last updated