Careercup | Chapter 7

7.4 Write methods to implement the multiply, subtract, and divide operations for integers. Use only the add operator.

比较简单。但是要封装得好。

7.5 Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis.

怎样写得简洁。要解决：

1. 怎么把多种情况综全考虑？

这类题就是先把special case想法，再写算法。

7.6 Given a two-dimensional graph with points on it, find a line which passes the most number of points.

见此。当时没考虑精度的问题。

 1 int findMaxLine(vector<int> &points) {
 2     int max = 0;
 3     int dup = 0;
 4     map<int, int> counts;
 5     double epison = 0.0001;
 6 
 7     for (int i = 0; i < points.size(); ++i) {
 8         counts.clear();
 9         dup = 1;
10         int m = 0;
11         for (int j = i + 1; j < points.size(); ++j) {
12             if (points[i].x == points[j].x && points[i].y == points[j].y) {
13                 dup++;
14             } else if (points[i].x == points[j].x) {
15                 counts[0]++;
16                 if (counts[0] > m) m = counts[0];
17             } else {
18                 double k = (points[i].y - points[j].y) * 1.0 / (points[i].x - points[j].x);
19                 counts[(int)(k/epison)]++;
20                 if (counts[int)(k/epison)] > m) m = counts[int)(k/epison)];
21             }
22         }
23         if (m + dup > max) max = m + dup;
24     }
25     return max;
26 }

7.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

 1 int findKthMagicNumber(int k) {
 2     vector<queue<int> > queues(3);
 3     queues[2].push(1);
 4     
 5     for (int i = 0; i < k; ++i) {
 6         int minIndex = 0, minNumber;
 7         for (int j = 1; j < 3; ++j) {
 8             if (!queues[j].empty() && queues[j].front() < queues[minIndex].front()) minIndex = j;
 9         }
10         minNumber = queues[minIndex].front();
11         for (int j = minIndex; j < 3; ++j) {
12             queues[j].push(minNumber * nums[j]);
13         }
14         queues[minIndex].pop();
15     }
16     return minNumber;
17 }