Divide and Conquer

169 Majority Element
Here low = 0, high = nums.size(); initially (super end)
solve(vector<int>& nums, int low, int high)
Base case:
1 == high - low return nums[low]
Otherwise, get mid = low + (high - mid) / 2;
int leftMod = solve(nums, low, mid);
int rightMod = solve(nums, mid, high);
if (leftMod == rightMod)
    return leftMod;

Otherwise count the leftMod and rightMod frequency in the whole array. return the bigger one.



53
Get the maximum of (1) maximum sub-array in the left half (2) maximum in the right half (3) and the maximum sub-array that accross the right half and right half.

globalMax = max(solve(nums, left, mid), solve(nums, mid, right));
return  max(globalMax, leftMax + rightMax);


241 Different Ways to Add Parentheses
 Get the different ways to add parentheses  (1) in the left half (2) in the right half (3) and the different combinations in the left half and right half using different operations.


215 Kth Largest Element in an Array
(1) Get the order of the target element: order = nums.size() - k;
(2) while start < end do the following:
(3) Let pivot = start, open = start + 1, close = start, loop every element at idx from open to end and do the following
(4) if nums[idx] < nums[pivot] swap nums[idx] with nums[open], close = open, open++
(5) after the inner loop, swap nums[pivot] with nums[close]
(6) if close == order, return nums[close], else if order < close, let end = close try the left half. Otherwise, let start = order + 1, try the right half.
(7) If after the loop, no early exit, return -1, meaning not exist in the array.


240 Search a 2D Matrix II   

(1) For loop each row of the matrix and try to test whether the target is in that row (check target >= row.front() && target <= row.back() )
(2) When the row contains target is found, do binary search in that row :  serachVector(row, target),
if any row return true, then return found (true) for the problem
(3) If all the rows doesn't contain target, return false (i.e no early exit above)

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