做了一下7.6,就是找经过点最多的直线。
答案给的比较复杂,是用一个 >的hashmap,在斜率匹配的情况
下,再去vector找匹配的line,而且感觉有bug,在匹配斜率的时候没有考虑斜率无穷
大的情况。
我想了一下C++的做法,比较直观的做法是建立 的hashtable,然后重载一下
预算符,当斜率差和截距差都小于eps = 0.0001的时候视作两条线是同一条线。
但是因为重载这一块不太熟,不知道写的对不对,请大牛们指点一下:
//Given a two-dimensional graph with points on it,find a line which passes
the most number of points.
class Line{
private:
double slope;
double intercept;
bool infinity_slope;
static double eps;
challenge me
bool isRepeat(string s) {
bool ret = false;
int sz = s.size();
vector pi(sz, 0);
int k = 0;
for (int i = 1; i < sz; i ++) {
while (k != 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k ++;
}
pi[i] = k;
}
int d = sz - pi[sz - 1];
int idx = d - 1;
int expectedRes = 0;
bool rFlag = false;
if (d < 2) {
ret = false;
goto e;
}
while (t... 阅读全帖
challenge me
bool isRepeat(string s) {
bool ret = false;
int sz = s.size();
vector pi(sz, 0);
int k = 0;
for (int i = 1; i < sz; i ++) {
while (k != 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k ++;
}
pi[i] = k;
}
int d = sz - pi[sz - 1];
int idx = d - 1;
int expectedRes = 0;
bool rFlag = false;
if (d < 2) {
ret = false;
goto e;
}
while (t... 阅读全帖
class Solution {
public:
Write a function to find the longest common prefix string amongst an array
of strings.
The Time complexity is O(logM * N), while M is the size of strs, N is the
shortest length of the str in the strs
而我觉得这个时间复杂度应该是O(MN). 因为isEqual()的复杂度应该是O(M), as T(M
) = 2T(M/2) + O(1). 谢谢。
============================
bool isEqual(vector &strs, int index, int start, int end) {
if(end < start) return true;
if(end == start) {
if(strs[start].size() > index) return ... 阅读全帖
题目 https://oj.leetcode.com/problems/search-a-2d-matrix/
我写的如下,先搜索行,再列。后面那个简短的是看到的别人的答案,简洁很多,但要
不要考虑行数*列数overflow的情况呢?多谢!
bool searchMatrix(vector > &matrix, int target) {
int row = matrix.size();
if (row==0) return false;
int col = matrix[0].size();
if (col==0) return false;
int rmin=0, rmax=row-1, cmin=0, cmax=col-1,rmid,cmid;
while (rmin<=rmax)
{
rmid = rmin+(rmax-rmin)/2;
if (matrix[rmid][0]>target... 阅读全帖
这样是不是 O(N^N)的复杂度?
class Solution {
public:
int maximalRectangle(vector > &matrix) {
int row=matrix.size();
if (row==0) return 0;
int col=matrix[0].size();
if (col==0) return 0;
//find all disjoint rectangles
vector> flag(row, vector(col,false));
int maxArea=INT_MIN;
楼主题目没有描述清楚,看完你的解答才明白完整的题意是什么。我感觉更好的答案是
并查集和树的结合。peer用并查集表示(一个集合里面的都是peer),manager关系用
树的结构表示。构建过程中先用(manager,A,B)先构建树结构;然后再用(peer,A,C)构建
并查集结构(在树中有父结点的是并查集的root)。is_peer(a,b)要么a,b在一个并查
集中,要么两个所属的并查集有相同的manager。is_manager(a,b)就递归地找了。自己
写的测试用例过了,如有不对请指正
class People:
def __init__(self, name):
self.name = name
#parent in tree to represent employee-manager info,
#tree_parent is manager of this person
self.tree_parent = None
#parent in union-find group
... 阅读全帖
写了一下。不用build tree,找ancestor,求p和q到ancestor的距离即可,只是corner
case实在多,发现bug记得告诉我一声
int BST_distance(vector& nums, int p, int q){
if (p>q) return BST_distance(nums,q,p);
int ancestor=-1, grandpa=-1;
bool left;
for (int i=0; i
if (nums[i]>=p && nums[i]<=q){
ancestor=i;
for (int j=i-1, dist=INT_MAX; j>=0; j--){
if (abs(nums[j]-nums[i])
if (nums[j]>nums[i]) left=true;
else... 阅读全帖
抽血: detect antibody. less false negative, more false positive. if you have
not undergone h. pylori treatment in ~ 1 year, false positive is still very
low.
呼吸: urea breath test. more false negative, less false positive.
【 以下文字转载自 Military 讨论区 】
发信人: horsemen (horseman), 信区: Military
标 题: 一名华裔美籍女子被美国联邦法官剥夺美国国籍
发信站: BBS 未名空间站 (Fri Sep 5 22:38:43 2014, 美东)
一名华裔美籍女子因涉入2007年的一件国家安全信息走漏事件而被美国联邦法官剥夺美
国国籍。这名45岁李姓女子在2005年加入美籍,她名义上的假丈夫是中国公民持绿卡,
去年被驱逐出境。李姓女子是亚利桑反恐信息中心的合同工,负责头像识别技术。
Grace Li became a naturalized U.S. citizen in 2005. In 2009, she pleaded
guilty to knowingly making false statements in her pursuit of citizenship.
Credit: Courtesy of Grace Li
A federal judge in Arizona has ordered the U.S. government to rev... 阅读全帖
Earthquake detection systems can sound the alarm in the moments before a
big tremor strikes—time enough to save lives
Japan’s system, which went live in 2007, makes heavy use of personal
technology. Alerts go out not only on television and radio but through
special receivers in homes, offices and schools. Pop-up windows on
computers show a real-time map with the epicenter’s location and the
radiating seismic waves. A timer counts down to the shaking at your
location and highlights predicted inte... 阅读全帖
Earthquake detection systems can sound the alarm in the moments before a
big tremor strikes—time enough to save lives
Japan’s system, which went live in 2007, makes heavy use of personal
technology. Alerts go out not only on television and radio but through
special receivers in homes, offices and schools. Pop-up windows on
computers show a real-time map with the epicenter’s location and the
radiating seismic waves. A timer counts down to the shaking at your
location and highlights predicted inte... 阅读全帖
1. It is your turn at front . you gracefully slide into position , then
A. Accelerate to drag the line with you.
B. Maintain the average pace of the group.
C. Adjust your speed to accommodate all levels of effort within the pack.
2. Midpack riders are not expected to point out hazards or announce traffic.
(True) Only the lead and rearmost riders can see what's going on from ahead
and behind.
(False) It is every rider's responsibility to relay messages through the
pack whether from front to back ... 阅读全帖
看这个网站 http://www.radiationnetwork.com/Message.htm
Update: 6/6/12, 11:55 P.M. - Very high reading in South Bend, IN station
this evening. Reason unknown. Station unresponsive to contact at this
late hour. Since this same station has triggered the Alert system before,
which Alerts may have been false, and because his current readings do not
appear to be corroborated by nearby stations, we have disabled his station
for the time being. Will report back when we know more.
然后更正了,说是false alert:
U... 阅读全帖
http://www.usms.org/rules/part1.pdf
103.8.6 False Starts
A. Any swimmer starting before the starting signal is given shall be
disqualified if the referee independently observes and confirms the starter
’s observation that a violation occurred. Swimmers remaining on the
starting blocks shall be relieved from their starting positions with the “
Stand up” command and may step off the blocks.
B. If the starting signal has been given before the disqualification is
declared, the race shall continue wi... 阅读全帖
http://www.usms.org/rules/part1.pdf
103.8.6 False Starts
A. Any swimmer starting before the starting signal is given shall be
disqualified if the referee independently observes and confirms the starter
’s observation that a violation occurred. Swimmers remaining on the
starting blocks shall be relieved from their starting positions with the “
Stand up” command and may step off the blocks.
B. If the starting signal has been given before the disqualification is
declared, the race shall continue wi... 阅读全帖
先贴后看 http://en.wikipedia.org/wiki/Fair_comment
In the United States, the traditional privilege of "fair comment" is seen as
a protection for robust, even outrageous published or spoken opinions about
public officials and public figures. Fair comment is defined as a "common
law defense [that] guarantees the freedom of the press to express statements
on matters of public interest, as long as the statements are not made with
ill will, spite, or with the intent to harm the plaintiff".[1]
The defense... 阅读全帖
请问老 E,你有能力证明神不不存在吗?
----------------------
发信人: Eloihim (真神), 信区: TrustInJesus
标 题: Re: 我相信沒有神(譯)
发信站: BBS 未名空间站 (Thu Apr 12 17:00:27 2012, 美东)
嘿嘿! 你有證據,我一定相信你。 你敢説有證據證明神不存在就不信神嗎?
-----------------------
请读下面这个文章. http://www.philosophynow.org/issues/78/Wheres_The_Evidence
The New Atheism
Where’s The Evidence?
Michael Antony argues that the New Atheists miss the mark.
“A wise man,” wrote Hume, “proportions his belief to the evidence.” This
is a formulation of evidentialism – the view that a bel... 阅读全帖
这是数学家,逻辑学家Smullyan对free will问题的一次尝试。Smullyan本人认为他自
己是道家哲学者。
Mortal:
And therefore, O God, I pray thee, if thou hast one ounce of mercy for
this thy suffering creature, absolve me of having to have free will!
God:
You reject the greatest gift I have given thee?
Mortal:
How can you call that which was forced on me a gift? I have free will,
but not of my own choice. I have never freely chosen to have free will. I
have to have free will, whether I like it or not!
God:
Why would you wish ... 阅读全帖
Word Story
How shocked and offended will people be if you use this word? Well, that all
depends on how you are using it and what you are referring to. Originally,
bitch simply meant a female dog, and it still does. But around the year
1400, it gained currency as a disparaging term for a woman, originally
specifically “a lewd or sensual woman,” and then more generally “a
malicious or unpleasant woman.” The word is first found used this way in
the Chester Plays of the 1400's, which has the line “... 阅读全帖
Word Story
How shocked and offended will people be if you use this word? Well, that all
depends on how you are using it and what you are referring to. Originally,
bitch simply meant a female dog, and it still does. But around the year
1400, it gained currency as a disparaging term for a woman, originally
specifically “a lewd or sensual woman,” and then more generally “a
malicious or unpleasant woman.” The word is first found used this way in
the Chester Plays of the 1400's, which has the line “... 阅读全帖
DogSet ds = new DogSet();
public static void checkDogs(DogSet allDogs, int foundOtherSickDogAmt)
{
if (allDogs.getSickDogAmt()<1) throw new Exception("CDC Sucks!");
Dog myDog;
if(iAmNWWolf)
myDog = new Dog(true);
else
myDog = new Dog(false);
int dayCounter = 1;
while(true)
{