算法题解

Two kinds of greedy policy: proovable by swapping or proovable by math induction.

  • 45 Jump Game II

    • Given an array with max jumping distance at each place. Caculate minimum step to the end.
    • O(n) time by greedy. Note that the minimum step to each index is mono increasing. Update jump number at each interval’s end. Intervals can be updated greedily.

  • 55 Jump Game

    • Given an array with max jumping distance at each place. Judge whether the end is reachable.
    • O(n) time by greedy.

  • 56 Merge Intervals

    • O(nlog(n)) time, sort by start position and merge.

  • 134 Gas Station

    • Given gas stations distributed on a circle, calculate whether one can travel around the circle once clockwise. Each gas station has limited gas volume.
    • O(n) time by greedy. Note that if SUM(cost) <= SUM(gas), there is always a solution, otherwise the circle can be divided into multiple parts where SUM(cost_part) > SUM(gas_part), contradiction. Then go around the circle and find the maximum point as start.

  • 135 Candy

    • Children in a line, each with a rating value. Higher rate has more candy than neighbors. Calculate minimum candy.
    • O(n) time and O(1) space by greedy. Find all mountains, mountain feets are all ones and mountain tops depends to the longer side.

  • 152 Maximum Product Subarray

    • O(n) time. Seperate the array by 0, and try positive greedily.

  • 253 Meeting Rooms II

    • Given some meeting times, find out minimum number of meeting rooms required.
    • O(nlog(n)) time by sorting and line sweeping.

  • 330 Patching Array

    • Given a sorted positive array, return minimum number of numbers needed to make any number in [1, n] is representable by sum of array numbers.
    • If [0, n) is filled, then [0, n + m) can be filled for any m <= n. Greedily choose m == n when there is no number from array.

  • 334 Increasing Triplet Subsequence

    • Given a number sequence, find if there is any i<j<k that nums[i]<nums[j]<nums[k].
    • O(n) time and O(1) space. Like LIS, maintain minimum end of different length (3 here).

  • 358 Rearrange String k Distance Apart

    • Given strings like “aabbcc”, re-arrange it i.e. the same characters are at least distance k from each other.
    • O(n) time, greedily choose most remaining character.

  • 376 Wiggle Subsequence

    • Give a sequence, caculate the maximum length of subsequence that S1 < S2 > S3… or S1 > S2 < S3…
    • O(n) by greedily update current value when the same inequality holds.

  • 392 Is Subsequence

    • Given S and T, judge whether T is a subsequence of S.
    • Follow up: lots of queries. Store T’s chracters’ indices and use binary search.

  • 406 Queue Reconstruction by Height

    • Given (h, k) pairs, k is the number of higher people before self, reconstruct the queue.
    • When h is same, smaller k is better. When k is same, smaller h is better. Greedily choose lowest valid element. Use BIT to save how many pairs before are higher.
    • This is a swap-invariant problem.

  • 435 Non-overlapping Intervals

    • Given intervals, determine minimum intervals needed removing to make intervals non-overlapping.

    • O(nlog(n)) time and O(n) space by DP in the order of interval ends. For each interval find the minimum of removing or not.

    • O(nlog(n)) time and O(1) space by greedy in the order of starts/ends. Two cases:

          ---- : remove the latter    ---   : remove the outer
  ----                        -------

  • 452 Minimum Number of Arrows to Burst Balloons

    • Given some segments, each time one can declare a point to erase all segments covering it. Find minimum declarations to erase all segments.
    • O(nlog(n)) time, greedily accumulate more segments before erasing. Any solution erasing the group by more than one declaration can be optimized to our method.

  • 456 132 Pattern

    • Given a number array, find whether there is i<j<k and nums[i]<nums[k]<nums[j].
    • O(n) time, greedily find maximum (nums[k], nums[j]) pairs from right. Much like Increasing Triplet Subsequence.
    • O(nlog(n)) time, use set to maintain right numbers and find smallest number > nums[i].

  • 484 Find Permutation

    • Given “DI” like sequence, where D is decrese and I is increase, find the lexicographically minimum number sequence. For “DI”, answer is 312.
    • Greedily build I+D+ sequence: put all but last I at the bottom, then ID+ top down.

  • 495 Teemo Attacking

    • Teemo attack at several time points and have poison buff. Calculate total buff time.
    • O(n) time and O(1) space, check at each timepoint whether the poison can last to the next.

  • 621 Task Scheduler

    • Given tasks, the machine must take a rest of L time units between two same tasks, find the minimum working time.
    • O(time) time, greedily choose task with most remaining. Can be optimized to O(n) if skip spare window.

  • 763 Partition Labels

    • Given a string, partition it into as many parts as possible such that each letter appears in at most one part.
    • Greedily find maximum index of encountered characters.

  • 767 Reorganize String

    • Same as 358.

  • 871 Minimum Number of Refueling Stops

    • There are some gas station with limited gas G[i]. Find minimum number of refueling stops to reach the end.
    • O(n^2) time by DP on maximum gas remaining with first M stations and N refuelings.
    • O(nlog(n)) time by greedily choose maximum G[i] in reachable range.

  • 945 Minimum Increment to Make Array Unique

    • Given an array, calculate minimum steps to make elements in A unique by incrementing elements.
    • O(n) time by greedily assigning lowest holes.

  • 948 Bag of Tokens

    • Given power bags, initial power P. If each bag earns 1 point, try to earn maximum points.
    • O(nlog(n)) time, greedily use lowest bags for points, and points for highest bags.

  • 976 Largest Perimeter Triangle

    • Given edge lengths, find maximum perimeter of valid triangles.
    • O(nlog(n)) time, sort then check maximum triples. Note that for optimal solution, given any longest edge, the other two edges must be maximum ones not longer than it.

  • 984 String Without AAA or BBB

    • Generate strings containint m A’s and n B’s without “aaa” or “bbb”.

  • 1005 Maximize Sum Of Array After K Negations

    • Given a number array, find maximum array sum with K negations.
    • Greedily find minimum negative and positive.

  • 1007 Minimum Domino Rotations For Equal Row

    • Given two rows of numbers, find minimum exchanges for numbers in either row become unique.
    • Just try two numbers at the head.