Greedy

Simulation:

860 Lemonade Change (N)

Simply simulate each customer buy and change process by looping over each bill in the bills array and handle 3 cases: bill == 5, 10 and 20.
Must greedily use $10 first before using $5  when do change for  $20.

874 Walking Robot Simulation (Y)

We simulate the path of the robot step by step ( d is direction):
For each cmd in the commands array do the following:
           (cmd == -1) :  d = (d + 1) % 4;    
           (cmd == -2) : d = (d + 3) % 4;
           Otherwise: (move steps)
                while (cmd-- > 0 && !hashSet.count(make_pair(x + dirs[d][0], y + dirs[d][1])))
                    x += dirs[d][0];
                    y += dirs[d][1];

             // res is the maximum of x^2 + y^2 for all the steps passed.

              res = max(res, x * x + y * y); 

 Where:  vector<vector<int> > dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

455 Assign Cookies (N)

Just sort the two arrays in ascending order and assign the cookies starting from the child with less greediness to maximize the number of happy children .

122. Best Time to Buy and Sell Stock II (N)

Greedily Add all the prices[i] - prices[i - 1] delta to the total profit if it is greater than zero (since we can complete as much transactions as we want and there is no transaction fees)

A slightly improvement is that, in a inner while loop, first record j = i as the starting price, while (i < N - 1 && prices[i] < prices[i +1]) we keep increase i, until it no longer holds. Then add the delta prices[i] - prices[j] to the total res. This is still O(N) time and O(1) space, but slightly less arithmetic operations.


714 Best Time to Buy and Sell Stock with Transaction Fee (Y)
On the ith day，If we sell the stock，then the profit we get is the profit from holding it in the (i -1)th day (otherwise we have nothing to sell), plus the current price and minus the fee. And compare it with sell it on the (i - 1) th day,  choose the bigger one of the two ( if the sell it on the (i -1)th day makes a larger profix, we won't hold it until the ith day).

Let us look at the profit of not selling it on the ith day. Which is the profit from selling it yesterday and buy today (need to minus today's price), and hold it from the (i-1)th day to ith day. Choose the larger one of the two. If hold it yesterday makes a larger profit, we will hold it to today.
sold[0] = 0, hold[0] = -prices[0];

sold[i] = max(sold[i - 1], hold[i - 1] + prices[i] - fee);
hold[i] = max(hold[i - 1], sold[i - 1] - prices[i]);
where i is from [1 to n -1]
Note:
Pay the transaction when sold the stock (the transaction is completed), only this way hold[1] is max of (-prices[0], -prices[1]), otherwise inconsistent.

861 Score After Flipping Matrix (Y)

(1) Flip all the rows that start with zero to make the first col all ones

(2) Flip these cols that have more 0s than 1s

(3) Calculate the final result by summing up each row binary number. 

 

406 Queue Reconstruction by Height (Y)

(1) sort the people array in height(h) descending order and k ascending order.
(2) insert the people into the result array according to the k value.

 

392  Is Subsequence (N)
Try to greedily match the short string S from beginning with T, if matched increase both i and j, otherwise just increase pointer j of T. In the end return weather i == S.size().


881
Sort people by descending order of weight.
For the current heaviest person, we try to let him go with the lightest person.
As all people need to get on the boat.
If the sum of weight is over the limit, we have to let the heaviest go alone.
No one can take the same boat with him.
621 Task Scheduler   (Y)
The idea is to create a priority queue. First use hash map  to count each chars frequency and put the frequency inside the priority queue so that the most frequent number is in front of the queue. Since each
cycle we could schedule at most n + 1 task. We always try round robin between the most popular tasks at any time.  Get a task from each category task and put it in a temp array. Then iterate the array, decrease the frequency by 1, if still >= 0, then push it back to the priority queue. If after iteration, the queue is not empty, that means the full cycle is filled or we have to insert some idle slot. if the queue is empty, then we add count to the total time.

In one sentence, greedily try to round robin from longest task to shortest task.

452 Minimum Number of Arrows to Burst Balloons (Y)
First, we sort balloons by increasing points.end (if ends are the same, then by increasing of points.start). Every time arrow shot points.end, say, points[i].second. If next balloon.start <= points[i].second, it is also shot, thus we don't need to count again. Keep skipping these points has a smaller start value than points[i].second until there are no more, then increase count and start a new points[i].

 The key is sort the points by second value first and then the first value, this ensures that when shoot the first element range end all the ones that haves a smaller first value intersect with the current range (since we know points[j].first <= points[i].second && points[j].second >= points[i].second (ensured by sorting)

435 Non-overlapping Intervals (N)

Similar to 452, same way to sort the intervals. And count the number of intersected interval groups U, and  if total intervals is N, return N - U.
Only difference with 452 is that here 'touch' is not considered as intersect (i.e: [1,2] doesn't intersect with [2, 3] should be put into different interval groups)

738 Monotone Increasing Digits (Y)

要找到从后往前遍历的最后一个值升高的位置，让前一位减1，并把当前位以及后面的所有位都变成9，以得到最大的单调递增数

870 Advantage Shuffle (Y)

Idea: For each B[i], we select the smallest number in A that is greater than B[i]. If there are no such number, we select the smallest number in A.
Algorithm: I am usign multiset to sort and keep track of numbers in A. After a number is selected, we need to remove it from the multiset (erase by iterator takes a constant time).


767
Reorganize String     (Y)
O(N) time, O(N) space solution, using priority_queue with a helper queue to filter the already 0-counted pairs.
For priority queue, the highest priority element (maximum count element here, therefore we want the pair in the priority queue be pair<int, char> rather than pair<char, int>, the later will sort the queue by descending alphabetical order, the first will sort the array according to the int number in descending order) is always at the front.

hash map + priority_queue  
Idea:  greedily try to append to the shortest length list first so that the list are distributed as evenly as possible maximize the possibility of get all of the size() >= 3
Maintain a set of consecutive sequences, call this set S. S begins as an empty set of consecutive sequences.
Now, iterate through each num in nums. For each iteration, if there exists a consecutive sequence in S that ends with element num - 1, then append num to the end of the shortest such sequence; otherwise, create a new sequence that begins with num.
The problem has a solution (i.e. the array can be split into consecutive sub-sequences such that each sub-sequence consists of at least 3 consecutive integers) if and only if each sequence in S has size greater than or equal to 3.

(a) DP:

      if (nums[i] > nums[i - 1]
        up[i] = down[i  - 1] + 1;
        down[i] = down[i - 1];
      else if (nums[i] < nums[i - 1])
         down[i] = up[i - 1] + 1;
         up[i] = up[i - 1];
      else
       down[i] = down[i - 1];
        up[i] = up[i - 1];

(b) Greedy
We don't need sovle this problem use dp. Since the prolem is equivalent to find the number of alternating max and min: i.e: number of peaks. Since if you choose any non-peak values the result sequence is guarantee to be same or smaller. Because 
any sequence made from non-peaks, peaks could also achieve that same or even bigger sequence.

842 Split Array into Fibonacci Sequence (Y)

backtracking search
套用模板 
 1. 退出条件： if (start >= n && res.size() >= 3), i.e: If we reached end of
            string and we have at least 3 elements in our sequence then return true
 2. 已经拿过的数处理：  do not allow use the same char multiple times，
                     start = start + i, where i is the length of the first 
                     split part. guarded with isFibonacci()or they are numbers
                     from the first two split parts.
                     pos = start to pos = s.size() - 1.
  3. 回溯： res.push_back(num) before recursion, and res.pop_back() after recursion.
  if (backtracking(S, start + i, res))
      return true;
  Note here the problem only ask return any split, we don't have to save all the results, therefore out and res are combined together.

Greedy?

55 Jump Game

Calculate the left most reachable index from right to left. Initially, the left most reachable index is n - 1, if find another index that plus its value is greater or equal than the current left most reachable index, update it.  In the end, check whether the left most reachable index is 0.
   
 int leftMostReachableIdx = n - 1;
        for (int i = n - 2; i >= 0; i--)
            if (i + nums[i] >= leftMostReachableIdx)
                leftMostReachableIdx = i;


        return leftMostReachableIdx == 0;

Can be done by dp as well.

HERE

stack

402  Remove K Digits (Y)

        Keep track of how many characters we can remove
        if the previous character in stk is larger than the current one
        then removing it will always get a smaller number
        but we can only do so when k is larger than 0


134 Gas Station (Y)

  • If car starts at A and can not reach B. Any station between A and B
    can not reach B.(B is the first station that A can not reach.)
  • If the total number of gas is bigger than the total number of cost. There must be a solution.

Comments

Post a Comment

Popular posts from this blog

zhitongguigu

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN
Read more

Array Part2

Two pointers 977 Squares of a Sorted Array      We can use two pointers to read the positive and negative parts of the array - one pointer  j  in the positive direction, and another  i  in the negative direction. Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique. 11 Container With Most Water      O(N) time and O(1) space, since better candidadates must use the taller line of l and r therefore we can use two pointer keep moving towards each other until they meet. Always abandon the shorter line while moving. 80 Remove Duplicates from Sorted Array II      tail = 0; for (int i = 0;  i < nums.size(); i++)           if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet                 nums[tail++] = nums...
Read more

Two pointers (Part 1)

344 Reverse String      Use two pointers i, j. keep switching elements at position i, j while i < j.     string reverseString(string s) {        for (int i = 0, j = s.size() - 1; i < j; i++, j--)            swap(s[i], s[j]);                  return s;     } 345 Reverse Vowels of a String      Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not. 283 Move Zeroes      Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero. 349 Intersection of Two Arrays      ...
Read more