Skip to content

Latest commit

 

History

History
208 lines (180 loc) · 11.4 KB

math.md

File metadata and controls

208 lines (180 loc) · 11.4 KB

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