首页 > 代码库 > Careercup | Chapter 7
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 }
Careercup | Chapter 7
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。