题解

Sieve of Eratosthenes, Miller Rabin.

  • 7 Reverse Integer
    • Mind overflow!
  • 9 Palindrome Number
  • 29 Divide Two Integers
    • Do division without using *, / and mod. Generate binary representation of result.
  • 149 Max Points on a Line
    • O(n^2) time. For each point, sort other points into buckets according to their slopes.
    • O(n^3) method also works, uses dot product.
  • 166 Fraction to Recurring Decimal
    • Given x/y representation, calculate recurring decimal representation.
    • Be careful with overflow.
  • 168 Excel Sheet Column Title
    • 28 -> AB
    • Items within length N = 26 + 26^2 + 26^3 + … + 26^N
  • 171 Excel Sheet Column Number
  • 204 Count Primes
    • Given n, count how many primes there are from 1 to n.
    • Sieve of Eratosthenes, erase ik, stop at i = sqrt(n).
    • Miller-Rabin.
  • 223 Rectangle Area
    • Given two rectangles, find overall area.
    • Similar to a problem in USACO training, cut the other rectangle from up, down, left, right.
  • 233 Number of Digit One
    • Given a positive number n, count number of 1’s appearing in numbers from 1 to n.
    • O(n) time, classical digit DP.
  • 247 Strobogrammatic Number II
    • Find all numbers that would look the same after turning 180 degree, like 69, 11, 88, 0, etc.
    • Simple recursion.
  • 231 Power of Two
    • Determine whether an integer is a power of two. Use lowbit.
  • 248 Strobogrammatic Number III
    • Find all numbers between low and high.
    • Add a comparator.
  • 277 Find the Celebrity
    • N-person team, there is a person that doesn’t know others but others all know him. Find it by sending knows(A, B) queries.
    • O(n) time. Each query at least strikes out one person.
  • 292 Nim Game
  • 294 Flip Game II
    • Non-trivial O(n^2) solution by Sprague-Grundy function.
  • 319 Bulb Switcher
    • There is a bulb array. There is n operations, and the i-th operation will switch ki bulbs. Calculate whether k-th bulb is on.
    • Count factor numbers. Only square numbers are on.
  • 356 Line Reflection
    • Given several (x, y) points, find a vertical line made the pattern central symmetric.
    • O(n) time. The reflection line’s x is always (minX + maxX) / 2.
    • Double precision is not safe?
  • 360 Sort Transformed Array
    • Given f(x) = ax^2 + bx + c and a sorted array, given the sorted array mapped by f.
    • Find the root.
  • 365 Water and Jug Problem
    • Given two jugs with volume a and b, find whether water volume c can be measured.
    • Equivalant to solve ax + by = c (expand euclid algorithm), with a + b >= c.
    • x < 0 && y > 0: fill a with b, and pour a once full, vice versa.
  • 372 Super Pow
    • Caculate a^b mod 1337, where b is very large.
    • Use Chinese remainder theorem because 1337 = 7 * 191?
  • 375 Guess Number Higher or Lower II
    • Guess number, each time wrong pay $x where x is the guessing number. Find the cost that guarantees to win.
    • Minimax. Enumerate each split point and take the best cost, each best cost is the worst cost of left/right side.
    • Follow up: expected loss instead of worst loss. Use probability to multiply worst cost in DP?
  • 382 Linked List Random Node
    • Classic reservior sampling.
  • 384 Shuffle an Array
    • Classic Fisher-Yates algorithm.
  • 390 Elimination Game
    • Given an array from 1 to n, remove odd/even position numbers. Find the last number.
    • Each time all a mod b (b is 2^n) is eliminated. Infer “a” each time.
  • 396 Rotate Function
    • Given A, Bk is A’s rotation, find maximum F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1]
  • 398 Random Pick Index
    • Use map + rand or origin vector + reservior sampling.
  • 412 Fizz Buzz
  • 423 Reconstruct Original Digits from English
    • Given a permutation of a string made up by 0-9’s english words’s, recover digits.
    • Use some unique character in the word.
  • 453 Minimum Moves to Equal Array Elements
    • Given number array, each time we can increase n-1 numbers, find minimum moves to make all elements equal.
    • Increase n-1 == decrease 1. Find minimum.
  • 462 Minimum Moves to Equal Array Elements II
    • Given number array, find minimum moves (+1/-1) to make all elements equal.
    • Find median.
  • 469 Convex Polygon
    • Find whether points sequence form a convex polygon.
    • Cross product is sufficient. No dot product validation needed.
  • 470 Implement Rand10() Using Rand7()
    • Rejection sampling. Pitfall: don’t use rand7() * rand7(), use 7 * rand7() + rand7() instead.
    • Can re-use redundant digits in next rejection sampling.
  • 477 Total Hamming Distance
    • Hamming distance of two numbers: bit number of XOR. Given a number array, count sum of all number pair hamming distance.
    • O(n) time, make use of prefix one/zero counts.
  • 483 Smallest Good Base
    • Given n, find minimum k that n’s representation is all-one-sequence in base k.
    • Enumerate one-sequence’s length and binary search for k. Need __u128int_t to avoid overflow.
  • 486 Predict the Winner
    • Two players fetch number from array’s two ends alternatively, judge whether player1 can win.
    • Typicial minimax.
  • 497 Random Point in Non-overlapping Rectangles
    • Area-weighted probability. Why only upper_bound works?
  • 528 Random Pick with Weight
    • Use map and lower_bound.
  • 593 Valid Square
    • Check 6 possible point orders with cross product and distance.
  • 670 Maximum Swap
    • Given a number, swap any two digits once to get maximum.
    • Find first non-largest digit and swap it with least significant largest.
  • 793 Preimage Size of Factorial Zeroes Function
    • Find how many number X are there i.e. X! has k trailing zeros.
    • Trailing zero number increases every 5 numbers.
  • 812 Largest Triangle Area
    • Given points, find maximum area of triangle formed by any of them.
    • Heron’s formula: S = sqrt(p(p-a)(p-b)(p-c)).
  • 829 Consecutive Numbers Sum
    • Find how many ways a number can be represented as an arithmetic sequence.
    • N=k(k+1)/2+k*M, enumerate k.
  • 878 Nth Magical Number
    • Given A and B, find k-th smallest number divisible by A or B.
    • Binary search on n*A array.
  • 891 Sum of Subsequence Widths
    • Given a number array, find sum of all (max-min) of subsequences.
    • Sort and count neighbor coverage times. It’s all about power of twos.
  • 899 Orderly Queue
    • Given a string, one can move any character in prefix of length N to the end of the string. Find the lexicographically minimum string reachable.
    • When N>=2, this is a insertion sort.
  • 949 Largest Time for Given Digits
    • Given four digits, make up largest HH:MM time.
  • 957 Prison Cells After N Days
    • Find loop.
  • 963 Minimum Area Rectangle II
    • Given (x, y) points, find minimum area rectangle formed by those points. Sides are not necessarily parallel to x or y.
  • 970 Powerful Integers
    • Given x and y, find all numbers x^i + y^i <= bound.
  • 972 Equal Rational Numbers
    • Given two rational numbers (like 7.3(9) == 7.4), judge whether they’are equal.
    • Shorten cycling part, then shorten fractional part, then process (9) case.
  • 977 Squares of a Sorted Array
  • 991 Broken Calculator
    • Given X and Y, one can do -1 and *2 to X, find minimum steps to Y.
    • Consider convert Y to X by doing +1 and /2. Greedily do /2 when even, +1 when odd.
  • 997 Find the Town Judge
    • Similar to 277.
  • 1006 Clumsy Factorial
    • clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1, implement clumsy(N).
  • 1015 Smallest Integer Divisible by K
    • Find minimum length of 1-seq divisible by K if possible.
    • next_module = (10 * prev_module + 1) % K. There will be a loop.
  • 1025 Divisor Game
    • Given N, one can replace it with N - x where 0<x<N and N % x == 0. Given N, find whether first player will win.
    • Just return N % 2 == 0. All odd numbers are replaced to even numbers, while even numbers can be replaced to N - 1.