Geometry

892 Surface Area of 3D Shapes

Intuition:
For each tower, its surface area is 4 * v + 2
However, 2 adjacent tower will hide the area of connected part.
The hidden part is min(v1, v2) and we need just minus this area * 2
Time Complexity:
O(N^2)



963 Minimum Area Rectangle II

Iterate all possible triangles and check the opposite points that creating a quadrilateral.
Time complexity: O(n^3)
Space complexity: O(n)

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